考虑三维装箱约束的多车场车辆路径问题  

Multi-Depots Vehicle Routing Problem with Three-Dimensional Loading Constraints

作　　者：颜瑞[1] 张群[2] 胡睿[2] 

机构地区：[1]北京信息科技大学经济管理学院,北京100192 [2]北京科技大学东凌经济管理学院,北京100083

出　　处：《管理工程学报》2016年第1期108-116,共9页Journal of Industrial Engineering and Engineering Management

基　　金：国家重点基础研究发展规划资助项目(973;子课题)(2010CB955903-1);国家自然科学基金资助项目(71172168)

摘　　要：针对实际物流配送问题的特点,研究三维装箱约束车辆路径问题,首次建立考虑多车场的三维装箱约束车辆路径问题模型,并提出求解该问题的混合算法。混合算法采用遗传算法求解车辆路径问题,采用引导式局部搜索算法求解三维装箱问题。通过计算标准算例检验算法性能,试验结果表明混合算法能够在较短时间内得到质量较高的近似最优解。通过数值仿真检验模型的可解性。The 3L-MDCVRP （Three-Dimensional Loading Multi-Depots Capacitated Vehicle Routing Problem, 3L-MDCVRP） is a new proposed optimization problem, which is a combination of loading problem and VRP problem based on multi-depots. There are several constraints for 3L-MDCVRP： 1） the demand of a certain set of customers; 2） a feasible placement of items within the loading space;and 3） a fleet of identical vehicles of limited capacity based onseveral depots.Loading items into vehicles and successive routing of vehicles along the road network are the most important problems in distribution management. This paper addressed an important problem combining three-dimensional loading and multi-depots vehicle routing problems. A brand new solution has been proposed, The new algorithm was a combination of two intelligent algorithms and it passed the test with good performance. Both the capacity vehicle routing problem and three-dimensional problem are NP-hard problems.Thus,the combinatorial problem 3L-MDCVRP is clearly also the case. Exact algorithmic methodologies are not expected to solve the real-world problems of large customers and item sets in a reasonable time. Therefore, we solve the problem by using a heuristics algorithm named Guided Local Search Genetic Algorithm （GLSGA）, which makes use of fast packing heuristics for the loading. The hybrid algorithm combines two different heuristic information measures： a genetic algorithm for routing because of its specialty in finding local optima, and a guided local search algorithm for loading. The algorithm was tested on the set of benchmark instances proposed by Gendreau and Iori. These instances were the only 3L-CVRP instances available in all publications. It had been shown that the new algorithm had a better performance than the benchmark approach when all loading restrictions were satisfied.Both the distance and calculationtime were significantly reduced.There was a 6.38% decrease compared with TS in distance and a 2.16% compared with GTS. In addition, the

关 键 词：车辆路径问题 多车场 三维装箱 遗传算法 

分 类 号：O224[理学—运筹学与控制论]