基于模糊时间窗的车辆调度问题研究

基于现实生活中配送企业车辆资源有限和顾客对服务时间要求并非完全刚性的特征,通过时间窗模糊化处理将顾客服务的满意度量化为配送服务开始时间的模糊隶属度函数。在一定满意度下,构建了基于模糊时间窗的车辆调度模型,根据模型的特点,改进了基于客户的染色体编码方式,设定了一种新的约束处理方法,避免了惩罚策略中选取惩罚因子的困难。在算法中用模糊优化程序处理问题的模糊特征,通过对顾客服务时间的局部调整来确定最佳服务时间。最终通过实例验证与原结果比较发现,引用模糊时间窗函数不仅可以降低配送成本,而且有利于节省运力资源。     

集成物流管理系统中定位—运输路线安排问题的研究

综述集成物流管理系统中设施定位—运输车辆行程路线安排问题的主要研究进展 ,分析提出有关求解问题的算法的特点 ,最后提出该研究领域应该关注的几个重要发展方向 .     

随机动态装卸混合问题的分区求解策略

针对需求服从一般分布的随机动态装卸混合问题,提出一种求解该问题的分区求解策略,分析了需求稀少和需求密集情况下该策略的渐近性.仿真比较了需求服从一般分布情形下分区求解策略、随机队列中位策略、多车场随机队列中位策略和堆栈策略的求解效果,以及需求服从一般分布和需求服从均匀分布情形下分区求解策略的求解效果.结果表明,对于需求服从一般分布的随机动态装卸混合问题,分区求解策略是一种有效的求解策略.     

协作车辆路径成本分摊问题的 B-T Shapley 方法

多个企业协作配送能显著地降低物流配送成本和减少尾气排放, 研究协作配送模型与成本分摊方法是亟需解决的关键问题.传统经典成本分摊方法需要计算所有子联盟的协作成本, 在本问题中等价于需要求解2N-1个 (N为企业数量) 复杂的车辆路径问题.本文建立了多方协作车辆路径问题模型, 分析了协作配送成本分摊问题的属性.基于经典的Shapley成本分摊方法, 提出了B-T (Binary Tree) Shapley近似方法, 不仅将成本分摊本身计算复杂度由O (N22N) 降为O (N2log2N) , 而且将需要求解的车辆路径问题数量由2N-1个锐减至2N-1个, 从而能够在合理时间内完成协作配送问题的成本分摊.通过求解算例和实际案例, 计算结果表明, B-T Shapley的耗时与Shapley方法相比几乎可以忽略不计, 更重要的是B-T Shapley与Shapley的成本分摊结果之间仅有细微的偏差, 其平均准确度可以达到95%左右.     

Packing trees in communication networks

Given an undirected edge-capacitated graph and given (possibly) different subsets of vertices, we consider the problem of selecting a maximum (weighted) set of Steiner trees, each tree spanning a subset of vertices, without violating the capacity constraints. This problem is motivated by applications in multicast communication networks. We give an integer linear programming (ILP) formulation for the problem, and observe that its linear programming (LP) relaxation is a fractional packing problem with exponentially many variables and a block (sub-)problem that cannot be solved in polynomial time. To this end, we take an r-approximate block solver (a weak block solver) to develop a (1−ε)/r-approximation algorithm for the LP relaxation. The algorithm has a polynomial coordination complexity for any ε∈(0,1). To the best of our knowledge, this is the first approximation result for fractional packing problems with only weak block solvers (with arbitrarily large approximation ratio) and a coordination complexity that is polynomial in the input size. This leads also to an approximation algorithm for the underlying tree packing problem. Finally, we extend our results to an important multicast routing and wavelength assignment problem in optical networks, where each Steiner tree is to be assigned one of a limited set of given wavelengths, so that trees crossing the same fiber are assigned different wavelengths. A preliminary version of this paper appeared in the Proceedings of the 1st Workshop on Internet and Network Economics (WINE 2005), LNCS, vol. 3828, pp. 688–697. Research supported by a MITACS grant for all the authors, an NSERC post doctoral fellowship for the first author, the NSERC Discovery Grant #5-48923 for the second and fourth author, NSERC Discovery Grant #15296 for the third author, the Canada Research Chair Program for the second author, and an NSERC industrial and development fellowship for the fourth author.     

具有模糊预约时间的VRP混合遗传算法

在对具有模糊预约时间的多对多货物收发情况下的车辆路径问题进行简单描述的基础上,构建了该问题的多目标数学规划模型,提出了解决该问题的一种基于插入启发式算法、并用修正的推—碰—掷过程进行改进的混合遗传算法,最后,给出了该问题的一个计算实例,并与改进的Solomon插入启发式算法进行了比较.     

Possibilistic scheduling routing for short-notice bushfire emergency evacuation under uncertainties: An Australian case study

This paper aims to develop a capacitated vehicle routing solution to evacuate short-notice evacuees with time windows and disruption risks under uncertainties during a bushfire. A heuristic solution technique is applied to solve the triangular possibilistic model to optimise emergency delivery service. The effectiveness of the proposed algorithm is evaluated by comparing it with a designed genetic algorithm on sets of 20 numerical examples. The model is then applied to the real case study of 2009 Black Saturday bushfires in Victoria, Australia. The results show that it is possible to transfer the last-minute evacuees during the Black Saturday bushfires under the hard time window constraint. Network disruptions however have impact on resource utilisation. The modelling outputs will be useful in the development of emergency plans and evacuation strategies to enhance rapid response to last-minute evacuation in a bushfire emergency.     

基于混合蚁群算法的冷链物流配送路径优化研究

基于绿色物流发展理念，为企业寻求经济与环境达到双赢的局面，本研究将节能减排转化为绿色成本，融入路径优化问题中，建立以总成本最小为研究目标的冷链物流路径优化数学模型。针对蚁群算法初始阶段由于信息素不足导致收敛速度慢的问题，将A*算法与蚁群算法相结合，利用A*算法的全局收敛性和蚁群算法的正反馈性构造了一种混合蚁群算法。通过对实例进行仿真优化与对比分析，验证了模型和算法的有效性。     

WDM网上运行IP的研究

对ＷＤＭ网上直接运行ＩＰ的有关研究作了论述;阐述了 ＩＰ ｏｖｅｒ ＷＤＭ的网络结构,其网络 采用光分插复用器（ＯＡＤＭ）和光交叉连接器（ＯＸＣ）,实例说明了采用ＯＸＣ时的网络物理结构和逻辑结构。讨 论了帧结构、路由选择和波长分配以及网络抗毁等问题。     

一种串扰和时延驱动的总体布线算法

提出了一种能够同时考虑串扰和时延,作为综合性能驱动的总体布线算法。该算法由基于边串扰度、变关键路径边容量的初始布线和基于Agent技术的拆线重布两部分组成,仿真实验表明,该算法是有效的。