A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search

Mingyong Lai; Xiaojiao Tong

doi:10.3934/jimo.2012.8.469

Article Contents

2012, Volume 8, Issue 2: 469-484. Doi: 10.3934/jimo.2012.8.469

This issue Previous Article A new heuristic algorithm for laser antimissile strategy optimization Next Article On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem

A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search

Mingyong Lai^1, and
Xiaojiao Tong^2,

1.
Key Laboratory of Logistics Information and Simulation Technology, Hunan University, Changsha 410082
2.
Department of Mathematics and Computing Science, Hengyang Normal University, Hengyang 421002

Received: September 30, 2011

Revised: December 31, 2011

Published: March 2012

Abstract Related Papers Cited by

Abstract

A mixed integer programming mathematical formulation of vehicle routing problem with simultaneous pickups and deliveries, and time window constraints (VRP-SPDTW) is presented in this paper. The proposed model aims at minimizing the vehicle number and the overall travel cost. A novel two-stage hybrid metaheuristic method for VRP-SDPTW is also proposed. The first stage adopts improved ant colony optimization (IACO) to determine the minimum number of used vehicles. The second stage employs improved Tabu search to optimize the total travel cost, in which the initial solutions are obtained by IACO in the first stage. Experimental results demonstrate the effectiveness of the proposed metaheuristic method.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

References

[1]	A. Alshamrani, K. Mathur and R. H. Ballou, Reverse logistics: Simultaneous design of delivery routes and returns strategies, Computers & Operations Research, 34 (2007), 595-619.doi: 10.1016/j.cor.2005.03.015.
[2]	E. Angelelli and R. Mansini, The vehicle routing problem with time windows and simultaneous pick-up and delivery, in "Quantitative Approaches to Distribution Logistics and Supply Chain Management" (eds. M. G. Speranza, A. Klose and L. N. Van Wassenhove), Springer, Berlin, (2002), 249-267.doi: 10.1007/978-3-642-56183-2_15.
[3]	R. Battiti, Reactive search: Toward self-tuning heuristics, Keynote talk at Applied Decision Technologies, Brunel, UK, (1995), 3-4.
[4]	R. Bent and P. Van Hentenryck, A two-stage hybrid local search for the vehicle routing problem with time windows, Transportation Science, 38 (2004), 515-530.doi: 10.1287/trsc.1030.0049.
[5]	R. Bent and P. Van Hentenryck, A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows, Computers & Operations Research, 33 (2006), 875-893.doi: 10.1016/j.cor.2004.08.001.
[6]	G. Berbeglia, J.-F. Cordeau, I. Gribkovskaia and G. Laporte, Static pickup and delivery problems: A classification scheme and survey, TOP, 15 (2007), 1-31.doi: 10.1007/s11750-007-0009-0.
[7]	P. Bieganski, J. Riedl, J. Carlis and E. F. Retzel, Generalized suffix trees for biological sequence data: Applications and implementation, in "The Twenty-Seventh Hawaii International Conference on System Sciences," (1994), 35-44.
[8]	A. Colorni, M. Dorigo and V. Maniezzo, Distributed optimization by ant colonies, in "European Conference of Artificial Life," (1991), 134-142.
[9]	G. Dan, "Algorithms on Strings, Trees, and Sequences," Computer Science and Computational Biology, Cambridge University Press, Cambridge, 1997.
[10]	M. Dell'Amico, G. Righini and M. Salani, A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection, Transportation Science, 40 (2006), 235-247.doi: 10.1287/trsc.1050.0118.
[11]	J. Dethloff, Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up. Operations research in environmental management, OR Spektrum, 23 (2001), 79-96.doi: 10.1007/PL00013346.
[12]	J. Homberger and H. Gehring, Two evolutionary metaheuristics for the vehicle routing problem with time windows, INFOR, 37 (1999), 297-318.
[13]	M. Lai and E. Cao, An improved differential evolution algorithm for vehicle routing problem with simultaneous picks and deliveries and time windows, Engineering Applications of Artificial Intelligence, 23 (2010), 188-195.
[14]	M. Lai, C. Liu and X. Tong, A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows, Journal of Industrial and Management Optimization, 6 (2010), 435-451.doi: 10.3934/jimo.2010.6.435.
[15]	H. C. Lau and Z. Liang, Pickup and delivery with time windows: Algorithms and test case generation, International Journal on Artificial Intelligence Tools (Architectures, Languages, Algorithms), 11 (2002), 455-472.
[16]	H. Min, The multiple vehicle routing problem with simultaneous delivery and pickup points, Transportation Research A, 23 (1989), 377-386.doi: 10.1016/0191-2607(89)90085-X.
[17]	F. Alfredo Tang Montané and R. D. Galvão, A tabu search algorithm for the vehicle routing problems with simultaneous pick-up and delivery service, Computer & Operation Research, 33 (2006), 595-619.doi: 10.1016/j.cor.2004.07.009.
[18]	W. P. Nanry and W. J. Barnes, Solving the pickup and delivery problem with time windows using reactive tabu search, Transportation Research Part B, 34 (2000), 107-121.doi: 10.1016/S0191-2615(99)00016-8.
[19]	B. Nicola and R. Giovanni, Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery, Computers & Operations Research, 34 (2007), 578-594.doi: 10.1016/j.cor.2005.03.014.
[20]	H. N. Psarafis, A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem, Transportation Science, 14 (1980), 130-154.doi: 10.1287/trsc.14.2.130.
[21]	S. Ropke, J.-F. Cordeau and G. Laporte, Models and a branch-and-cut algorithm for pickup and delivery problems with time windows, Networks, 49 (2007), 258-272.doi: 10.1002/net.20177.
[22]	S. Ropke and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40 (2006), 455-472.doi: 10.1287/trsc.1050.0135.