【摘要】 针对实际物流配送问题的特点,研究三维装箱约束车辆路径问题,首次建立考虑多车场的三维装箱约束车辆路径问题模型,并提出求解该问题的混合算法。混合算法采用遗传算法求解车辆路径问题,采用引导式局部搜索算法求解三维装箱问题。通过计算标准算例检验算法性能,试验结果表明混合算法能够在较短时间内得到质量较高的近似最优解。通过数值仿真检验模型的可解性。更多还原

【Abstract】 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, there was a 57.06% reduction compared with TS in calculationtime and 40.89% compared with GTS. After the efficiency of GLSGA had been proved, it was applied in an experiment of 3L-MDCVRP instance, which was generated randomly. The algorithm derived the solution pretty and all five results were available in the real delivery process after checking.This new GLSGA was capable of improving the efficiency of solving 3L-MDCVRP, which was quite meaningful in the distribution process since it was able to control logistics cost and increase the utilization of vehicles.更多还原