带二维装箱约束的物流配送车辆路径问题  

Vehicle routing problem in distribution with two-dimensional loading constraint

作　　者：王征[1] 胡祥培[2] 王旭坪[2] 

机构地区：[1]大连理工大学软件学院,大连116620 [2]大连理工大学系统工程研究所,大连116024

出　　处：《系统工程理论与实践》2011年第12期2328-2341,共14页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70801008;90924006);国家杰出青年基金(70725004);辽宁省博士科研启动基金(20071091)

摘　　要：现实物流活动中大量存在的易损、易碎物品的运输问题属于带二维装箱约束的物流配送问题,该问题是二维装箱问题与车辆路径问题这两个经典难题融合之后的一个新问题.针对这一问题,在对其进行明确定义的基础上,建立了数学模型,提出了解决该问题一个Memetic算法,对算法中的几个关键算子:深度优先的启发式装箱方法、染色体的编码方式及其路径分割程序、初始解的生成方法、交叉算子、局部搜索算子,进行了详细的阐述.通过初步的实验,确定了Memetic算法的最佳参数配置;然后在Iori提出的30个顾客数在20-199个标准算例上对算法的鲁棒性、求解的质量、以及求解性能等几项指标进行了测试,并与文献中的求解结果进行了比较.试验结果表明,该Memetic算法大大提高了现有算法的性能及求解结果的质量.In real distributions, there is a great amount of transportation problems called vehicle routing problem with two-dimensional loading constraint, in which items demanded by customers are usually fragile and needed to be packed into vehicles. This is a new problem that combines the two classical problems of vehicle routing problem and bin packing problem. To solve the problem, a mathematical model and a Memetic algorithm were presented after an explicit problem definition. The key modules of the algorithm, such as a depth-first based heuristic loading method, an encoding and splitting method of chromosomes. an initial solution generation method, crossover and local search methods, were explained in details. Based on some preliminary experiments, the best combination of parameters＇ values in Memetic algorithm was given. Finally, the robustness and the effectiveness of the Memetic algorithm were tested on Iori＇s 30 instances whose numbers of customers are from 20 to 199 and a comparison with other algorithm in the literature was made, which shows that the memetic algorithm greatly surpasses the algorithiu on aspects of solving capacity and solution quality.

关 键 词：二维装箱约束 物流配送 车辆路径问题 MEMETIC算法 

分 类 号：TP39[自动化与计算机技术—计算机应用技术] C93[自动化与计算机技术—计算机科学与技术]