研究包含时间窗、多车场因素的二维装箱车辆路径问题，建立相应的数学模型，并提出求解该问题的一种新的混合算法，混合算法由量子粒子群算法和引导式局部搜索算法组成。其中，量子粒子群算法用于求解车辆路径问题，引导式局部搜索算法用于求解可行装箱方案。在引导式局部搜索算法中，提出一种基于最小浪费原则的启发式装箱规则，以灵活确定待装货物和装货空间之间的匹配关系，减少重复确定装箱方案所消耗的时间。设计了两组数值试验：第一组基于标准算例库，并将混合算法计算结果与已有文献中的结果进行对比；第二组基于随机生成的新算例，新算例给出多车场和时间窗数据，用于演示混合算法对新模型的计算过程和计算结果。两组数值试验的结果表明，混合算法在效率和性能方面均有较好的表现，计算结果和计算时间均优于已有文献，且混合算法能够较好的求解包含时间窗、多车场因素的二维装箱车辆路径问题模型。
Both vehicle routing problem (VRP) and bin packing problem (BPP) are important, typical combinatorial optimization problems, and are frequently and independently studied in the past few decades. In recent years, some attention has been devoted to their combined optimization, called 2L-CVRP (two-dimensional capacitated vehicle routing problem), which is a combination of two important NP-hard optimization problems in distribution logistics. In the 2L-CVRP, clients demand are defined as sets of rectangular weighted items, while vehicles have a weight capacity and a rectangular two-dimensional loading surface. The objective of the 2L-CVPR is to serve all the customers and load the corresponding items into the vehicles, through a road network, with minimum total cost.
Problem description:In this paper, a multi-depots capacitated vehicle routing problem with time window where client demand is composed of two-dimensional weighted items is addressed (2L-CVRP-MDTM).The model and an improved hybrid algorithm to solve the problem are proposed. The hybrid algorithm GLS-QPSO is composed by the Quantum-behaved Particle Swarm Optimization algorithm which is applied to solve the vehicle routing problem and Guided Local Search algorithm which is used to identify the feasible packing solutions.
Method: New loading heuristic rules are proposed in Guided Local Search algorithm based on the principle of minimize the waste to get better results of the matching relationship between the items and the corresponding packing positions in shorter time. Through the algorithm we can get the tours, and identify the clients covered by the vehicles, as well as vehicles in the routes. All the items demanded by the clients need to be loaded in the vehicles with the related constrains. In fact, there are two aspects that packing algorithm needs to consider. One is to determine the next loading item, and another is to determine the feasible loading position.
Computational experiments: Twenty of these 2L-CVRP standard instances are selected randomly, and loading surface (L,W) is fixed as (40,20) for all instances. The 20 selected instances are changed to two depots instances to testify the proposed algorithm in this paper by adding a new depot. We calculate the center of the clients, and then select a point between the first depot and the center randomly as the second depot.
Results: We compare the improved hybrid algorithm with the known best solutions, and the other is based on the new instances which include multi-depots with time window constrain. We calculate the center of the clients, and then select a point between the first depot and the center randomly as the second depot. The results of the numerical experiments show that the proposed hybrid algorithm has better performances in terms of both the calculation results and computing time comparing with the selected recent literature. The computational results show that the proposed algorithm is effective in finding high quality solutions and the practical recharging option may significantly improve the 2L-CVRP-MDTM which a new variant of the 2L-CVRP considering vehicles start from several different depots with time window constrains.
[1] Wei Lijun, Zhang Zhenzhen, Zhang Defu, et al. A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints [J]. European Journal of Operational Research, 2015, 243(3):798-814.
[2] Iori M. Meta-heuristic algorithm for combinatorial optimization problems [J]. 4OR, 2005, 3(2): 163-166.
[3] Zachariadis E E, Tarantilis C D, Kiranoudis C T. A guided Tabu search for the vehicle routing problem with two-dimensional loading constraints [J]. European Journal of Operational Research, 2009, 195(3): 729-743.
[4] Gendreau M, Iori M, Laporte G, et al. A Tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints [J]. Networks,2008,51(2):469-477.
[5] Leung SCH, Zheng Jiemin, Zhang Defu, et al. Simulated annealing for the vehicle routing problem with two-dimensional loading constraints [J]. Flexible Services & Manufacturing Journal, 2010, 22(1): 61-82.
[6] Fuellerer G, Doerner K F, Hartl R F, et al. Ant colony optimization for the two-dimensional loading vehicle routing problem [J]. Computers & Operations Research, 2007, 36(3): 655-673.
[7] Duhamel C, Lacomme P, Quilliot A, et al. A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem [J]. Computers & Operations Research, 2011, 38(3): 617-640.
[8] Iori M, Martello S. Routing problems with loading constraints [J]. Top, 2010, 18(1): 4-27.
[9] Iori M, Juan-José, Salazar-Gonzá, et al. An exact approach for the vehicle routing problem with two-dimensional loading constraints [J]. Transportation Science, 2007, 41(2): 253-264.
[10] Bruno LP, Pedro H, Flavio K, et al. A branch-and-cut approach for the vehicle routing problem with two-dimensional loading constraints [J]. Transportation Science, 2007, 41(2):253-264.
[11] Zachariadis EE, Tarantilis C D, Kiranoudis CT. Integrated distribution and loading planning via a compact metaheuristic algorithm [J]. European Journal of Operational Research, 2013, 228(1): 56-71.
[12] Hokama P, Miyazawa KF, Xavier C E. A branch-and-cut approach for the vehicle routing problem with loading constraints [J]. Expert Systems With Applications, 2016,47: 1-13.
[13] Zachariadis E E, Tarantilis D C, Kiranoudis T C. The vehicle routing problem with simultaneous pick-ups and deliveries and two-dimensional loading constraints [J]. European Journal of Operational Research, 2016,251(2): 369-386.
[14] 马珊静,陈峰,宋德朝,等. 越库配送物流系统车辆调度算法的研究[J]. 现代制造工程, 2009,(1):12-15.
[15] 宁爱兵,熊小华,马良. 城市物流配送中的三维装箱算法[J]. 计算机工程与应用, 2009, 45(9):207-208.
[16] 王征,胡祥培,王旭坪. 带二维装箱约束的物流配送车辆路径问题[J]. 系统工程理论与实践,2011,31(12):2328-2341.
[17] 颜瑞,张群,胡睿. 考虑三维装箱约束的车辆路径问题研究[J]. 中国管理科学, 2015, 23(1):128-132.
[18] Errico F, Desaulniers G, Gendreau M, et al. A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times [J]. European Journal of Operational Research, 2016,249(1): 55-66.
[19] Keskin M, Catay B. Partical recharge strategies for the electric vehicle routing problem with time windows [J]. Transportation Research Part C:Emerqing Technologies, 2016,65:111-127.
[20] 王征,张俊,王旭坪. 多车场带时间窗车辆路径问题的变领域搜索算法[J]. 中国管理科学, 2011,19(2): 99-103.
[21] Kennedy J, Eberhart R C. Swarm intelligence [M]. San Francisco:Morgan Kaufman Publishers,2001.
[22] Ai T, Kachitvichyanukul V. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery [J]. Computers & Operations Research, 2009, 36(5): 1693-1702.
[23] Wu Z. Optimization of distribution route selection based on particle swarm algorithm [J]. International Journal of Simulation Modelling, 2014, 13 (2): 230-242.
[24] Sun Jun, Xu Wenbo, Feng Bin. A global search strategy of quantum-behaved particle swarm optimization [C]//Proceedings of the 2004 IEEE Conference on Cybernetics and Intelligent Systems, Singapore,December 1-3,2004.
[25] Toth P, Vigo D. The vehicle routing problem, chapter branch-and-bound algorithms for the capacitated VRP [J]. Siam Monographs on Discrete Mathematics & Applications, 2002, 94(2-3): 127-153.
