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

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

April 2012, 8(2): 469-484. doi: 10.3934/jimo.2012.8.469

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, China
2.	Department of Mathematics and Computing Science, Hengyang Normal University, Hengyang 421002, China

Received October 2011 Revised January 2012 Published April 2012

Abstract
Related Papers

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: improved Tabu search, time window constraints., Improved ant colony optimization, vehicle routing problem, simultaneous pickups and deliveries.

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

Citation: Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial and Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469

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.

show all references

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.

[1]	Miao Yu. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 979-987. doi: 10.3934/dcdss.2019066
[2]	Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200
[3]	Bin Feng, Lixin Wei, Ziyu Hu. An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021197
[4]	Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial and Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142
[5]	A. Zeblah, Y. Massim, S. Hadjeri, A. Benaissa, H. Hamdaoui. Optimization for series-parallel continuous power systems with buffers under reliability constraints using ant colony. Journal of Industrial and Management Optimization, 2006, 2 (4) : 467-479. doi: 10.3934/jimo.2006.2.467
[6]	Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215
[7]	Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control and Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[8]	Bariş Keçeci, Fulya Altıparmak, İmdat Kara. A mathematical formulation and heuristic approach for the heterogeneous fixed fleet vehicle routing problem with simultaneous pickup and delivery. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1069-1100. doi: 10.3934/jimo.2020012
[9]	Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240
[10]	Shengyang Jia, Lei Deng, Quanwu Zhao, Yunkai Chen. An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2021225
[11]	Ahmed Tarajo Buba, Lai Soon Lee. Differential evolution with improved sub-route reversal repair mechanism for multiobjective urban transit routing problem. Numerical Algebra, Control and Optimization, 2018, 8 (3) : 351-376. doi: 10.3934/naco.2018023
[12]	Erfan Babaee Tirkolaee, Alireza Goli, Mani Bakhsi, Iraj Mahdavi. A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control and Optimization, 2017, 7 (4) : 417-433. doi: 10.3934/naco.2017026
[13]	Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial and Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435
[14]	Min Zhang, Guowen Xiong, Shanshan Bao, Chao Meng. A time-division distribution strategy for the two-echelon vehicle routing problem with demand blowout. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021094
[15]	Mingyong Lai, Hongming Yang, Songping Yang, Junhua Zhao, Yan Xu. Cyber-physical logistics system-based vehicle routing optimization. Journal of Industrial and Management Optimization, 2014, 10 (3) : 701-715. doi: 10.3934/jimo.2014.10.701
[16]	Yao Lu, Rui Zhang, Dongdai Lin. Improved bounds for the implicit factorization problem. Advances in Mathematics of Communications, 2013, 7 (3) : 243-251. doi: 10.3934/amc.2013.7.243
[17]	Pikkala Vijaya Laxmi, Singuluri Indira, Kanithi Jyothsna. Ant colony optimization for optimum service times in a Bernoulli schedule vacation interruption queue with balking and reneging. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1199-1214. doi: 10.3934/jimo.2016.12.1199
[18]	Dieudonné Nijimbere, Songzheng Zhao, Xunhao Gu, Moses Olabhele Esangbedo, Nyiribakwe Dominique. Tabu search guided by reinforcement learning for the max-mean dispersion problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3223-3246. doi: 10.3934/jimo.2020115
[19]	Xuefeng Wang. The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1147-1166. doi: 10.3934/dcdss.2019079
[20]	Shuai Ren, Tao Zhang, Fangxia Shi, Zongzong Lou. The application of improved-DAA for the vehicle network node security in single- and multi-trusted domain. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1301-1309. doi: 10.3934/dcdss.2015.8.1301

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Mingyong Lai Xiaojiao Tong
on Google Scholar
Mingyong Lai Xiaojiao Tong

[Back to Top]