American Institute of Mathematical Sciences

Advanced
  • 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

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 & 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.  Google Scholar

[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.  Google Scholar

[3]

R. Battiti, Reactive search: Toward self-tuning heuristics, Keynote talk at Applied Decision Technologies, Brunel, UK, (1995), 3-4. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[8]

A. Colorni, M. Dorigo and V. Maniezzo, Distributed optimization by ant colonies, in "European Conference of Artificial Life," (1991), 134-142. Google Scholar

[9]

G. Dan, "Algorithms on Strings, Trees, and Sequences," Computer Science and Computational Biology, Cambridge University Press, Cambridge, 1997.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

J. Homberger and H. Gehring, Two evolutionary metaheuristics for the vehicle routing problem with time windows, INFOR, 37 (1999), 297-318. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[3]

R. Battiti, Reactive search: Toward self-tuning heuristics, Keynote talk at Applied Decision Technologies, Brunel, UK, (1995), 3-4. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[8]

A. Colorni, M. Dorigo and V. Maniezzo, Distributed optimization by ant colonies, in "European Conference of Artificial Life," (1991), 134-142. Google Scholar

[9]

G. Dan, "Algorithms on Strings, Trees, and Sequences," Computer Science and Computational Biology, Cambridge University Press, Cambridge, 1997.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

J. Homberger and H. Gehring, Two evolutionary metaheuristics for the vehicle routing problem with time windows, INFOR, 37 (1999), 297-318. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Miao Yu. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization. Discrete & 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 & Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200
[3]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142
[4]

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 & Management Optimization, 2006, 2 (4) : 467-479. doi: 10.3934/jimo.2006.2.467
[5]

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 & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215
[6]

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 & Management Optimization, 2021, 17 (3) : 1069-1100. doi: 10.3934/jimo.2020012
[7]

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
[8]

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 & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[9]

Ahmed Tarajo Buba, Lai Soon Lee. Differential evolution with improved sub-route reversal repair mechanism for multiobjective urban transit routing problem. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 351-376. doi: 10.3934/naco.2018023
[10]

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 & Optimization, 2017, 7 (4) : 417-433. doi: 10.3934/naco.2017026
[11]

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 & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435
[12]

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 & Management Optimization, 2021  doi: 10.3934/jimo.2021094
[13]

Mingyong Lai, Hongming Yang, Songping Yang, Junhua Zhao, Yan Xu. Cyber-physical logistics system-based vehicle routing optimization. Journal of Industrial & Management Optimization, 2014, 10 (3) : 701-715. doi: 10.3934/jimo.2014.10.701
[14]

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 & Management Optimization, 2016, 12 (4) : 1199-1214. doi: 10.3934/jimo.2016.12.1199
[15]

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
[16]

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 & Management Optimization, 2021, 17 (6) : 3223-3246. doi: 10.3934/jimo.2020115
[17]

Xuefeng Wang. The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1147-1166. doi: 10.3934/dcdss.2019079
[18]

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 & Continuous Dynamical Systems - S, 2015, 8 (6) : 1301-1309. doi: 10.3934/dcdss.2015.8.1301
[19]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703
[20]

Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (124)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences