PDF(723 KB)
A heuristic algorithm for vehicle routing problem with heterogeneous fleet, simultaneous pickup and delivery
TIAN Yu, WU Wei-qin
Systems Engineering - Theory & Practice ›› 2015, Vol. 35 ›› Issue (1) : 183-190.
PDF(723 KB)
PDF(723 KB)
A heuristic algorithm for vehicle routing problem with heterogeneous fleet, simultaneous pickup and delivery
In this paper, we propose a new algorithm multi-label based ant colony system (MLACS) algorithm to address the vehicle routing problem with heterogeneous fleet, simultaneous pickup and delivery (VRPHSPD) problem which meet often in the real word. Leveraging the object-oriented principle, we build multi-attribute labels for various customers (demands), vehicles and routes. And then, we initialize the solution through nearest neighbor heuristic approach and minimize the number of vehicles required and total travel length by MLACS. To evaluate the efficiency and effectiveness of MLACS, we compare it with other optimization algorithms using benchmark problems and practical problem. Our results show that the MLACS algorithm has significant advantages in achieving the objectives as well as computing time. In addition, a numerical simulation using the actual data shows that MLACS is also good at solving the real world problem.
label based ant colony system / vehicle routing problem with heterogeneous fleet, simultaneous pickup and delivery / vehicle routing problem {{custom_keyword}} /
[1] Qu Y, Bard J F. The heterogeneous pickup and delivery problem with configurable vehicle capacity[J]. Transportation Research Part C: Emerging Technologies, 2013, 32(1): 1-20.
[2] Taillard E D. A heuristic column generation method for the heterogeneous fleet VRP[J]. RAIRO-Operations Research, 1999, 33(1): 1-14.
[3] Brandao J. A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem[J]. Computers & Operations Research, 2011, 38(1): 140-151.
[4] Salhi S, Nagy G. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling[J]. Journal of the Operational Research Society, 1999, 50(10): 1034-1042.
[5] Toth P, Vigo D. An exact algorithm for the vehicle routing problem with backhauls[J]. Transportation Science, 1997, 31(4): 372-385.
[6] Cheung R K, Hang D D. Multi-attribute label matching algorithms for vehicle routing problems with time windows and backhauls[J]. IIE Transactions, 2003, 35(3): 191-205.
[7] Min H. The multiple vehicle routing problem with simultaneous delivery and pick-up points[J]. Transportation Research Part A: General, 1989, 23(5): 377-386.
[8] Dethloff J. Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up[J]. OR Spektrum, 2001, 23: 79-96.
[9] 张涛, 田文馨, 张玥杰,等. 带车辆行程约束的VRPSPD 问题的改进蚁群算法[J]. 系统工程理论与实践, 2008, 28(1): 132-140. Zhang Tao, Tian Wenxin, Zhang Yuejie, et al. The improved ant colony algorithm for the VRPSPD with maximum distance constraint[J]. Systems Engineering——Theory & Practice, 2008, 28(1): 132-140.
[10] Gajpal Y, Abad P. An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup[J]. Computers & Operations Research, 2009, 36(12): 3215-3223.
[11] Vidal T, Crainic T G, Gendreau M, et al. Heuristics for multi-attribute vehicle routing problems: A survey and synthesis[J]. European Journal of Operational Research, 2013, 231(1): 1-21.
[12] Gambardella L M, Taillard É, Dorigo M. Ant colonies for the quadratic assignment problem[J]. The Journal of the Operational Research Society, 1999, 50(2): 167-176.
[13] 李泰琳, 张靖. 调适型导引蚂蚁算法求解时窗收卸货问题之研究[J]. 运输计划季刊, 2010, 39(1): 99-132. Li Tailin, Zhang Jing. Solve pick up and delivery problem with time windows via a guided adaptive ant colony system[J]. Transportation Planning Journal, 2010, 39(1): 99-132.
[14] Dorigo M, Gambardella L M. Ant colonies for the traveling salesman problem[J]. Biosystems, 1997, 43: 73-81.
[15] Gambardella L M, Taillard E, Agazzi G. MACS-VRPTW——A multiple ant colony system for vehicle routing problems with time windows[C]//Corne D, Dorigo M, Glover F. New Ideas in Optimization. McGraw-Hill: London, UK, 1999: 63-76.
[16] Duhamel C, Potvin J, Rousseau J. A tabu search heuristic for the vehicle routing problem with backhauls and time windows[J]. Transportation Science, 1997, 31(1): 49-59.
[17] Taillard E D, Badeau P, Gendreau M, et al. A tabu search heuristic for the vehicle routing problem with soft time windows[J]. Transportation Science, 1997, 31: 170-186.
[18] Dongarra J J. Performance of various computers using standard linear equations software[R]. Technical Report, University of Tennessee, 2011.
[19] Chen J, Wu T. Vehicle routing problem with simultaneous deliveries and pickups[J]. Journal of the Operational Research Society, 2006, 57(5): 579-587.
[20] Zachariadis E E, Tarantilis C D, Kiranoudis C T. An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries[J]. European Journal of Operational Research, 2010, 202(2): 401-411.
[21] Li F, Golden B, Wasil E. A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem[J]. Computers & Operations Research, 2007, 34(9): 2734-2742.
PDF(723 KB)
/
| 〈 |
|
〉 |
