主管:中国科学院
主办:中国优选法统筹法与经济数学研究会
   中国科学院科技战略咨询研究院
Articles

Research ofthe Model and Algorithm for Two-dimensional Multi-depots Capacitated Vehicle Routing Problem with Time Window Constrain

Expand
  • 1. Beijing Information Science and Technology University, Beining 100192, China;
    2. University of Science and Technology Beijing, Beijing 100083, China

Received date: 2015-11-22

  Revised date: 2016-03-01

  Online published: 2017-09-25

Abstract

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.

Cite this article

YAN Rui, ZHU Xiao-ning, ZHANG Qun, QI Yao-yuan, LIN Yu-zheng . Research ofthe Model and Algorithm for Two-dimensional Multi-depots Capacitated Vehicle Routing Problem with Time Window Constrain[J]. Chinese Journal of Management Science, 2017 , 25(7) : 67 -77 . DOI: 10.16381/j.cnki.issn1003-207x.2017.07.008

References

[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.
Outlines

/