American Institute of Mathematical Sciences

Advanced
  • Previous Article
    A new heuristic algorithm for laser antimissile strategy optimization
  • JIMO Home
  • This Issue
  • Next Article
    On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem
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. 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, (2002), 249. doi: 10.1007/978-3-642-56183-2_15.

[3]

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

[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. 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. 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. 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, (1994), 35.

[8]

A. Colorni, M. Dorigo and V. Maniezzo, Distributed optimization by ant colonies,, in, (1991), 134.

[9]

G. Dan, "Algorithms on Strings, Trees, and Sequences,", Computer Science and Computational Biology, (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. 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. 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.

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

[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. 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, 11 (2002), 455.

[16]

H. Min, The multiple vehicle routing problem with simultaneous delivery and pickup points,, Transportation Research A, 23 (1989), 377. 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. 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. 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. 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. 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. 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. 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. 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, (2002), 249. doi: 10.1007/978-3-642-56183-2_15.

[3]

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

[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. 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. 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. 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, (1994), 35.

[8]

A. Colorni, M. Dorigo and V. Maniezzo, Distributed optimization by ant colonies,, in, (1991), 134.

[9]

G. Dan, "Algorithms on Strings, Trees, and Sequences,", Computer Science and Computational Biology, (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. 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. 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.

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

[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. 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, 11 (2002), 455.

[16]

H. Min, The multiple vehicle routing problem with simultaneous delivery and pickup points,, Transportation Research A, 23 (1989), 377. 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. 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. 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. 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. 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. 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. doi: 10.1287/trsc.1050.0135.

[1]

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, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2018200
[2]

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

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. 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]

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

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

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

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

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

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

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

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

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

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

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

Tao Zhang, W. Art Chaovalitwongse, Yue-Jie Zhang, P. M. Pardalos. The hot-rolling batch scheduling method based on the prize collecting vehicle routing problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749
[18]

Guangmei Shao, Wei Xue, Gaohang Yu, Xiao Zheng. Improved SVRG for finite sum structure optimization with application to binary classification. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2019052
[19]

Nurhadi Siswanto, Stefanus Eko Wiratno, Ahmad Rusdiansyah, Ruhul Sarker. Maritime inventory routing problem with multiple time windows. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1185-1211. doi: 10.3934/jimo.2018091
[20]

Yangzi Hu, Fuke Wu. The improved results on the stochastic Kolmogorov system with time-varying delay. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : 1481-1497. doi: 10.3934/dcdsb.2015.20.1481

2017 Impact Factor: 0.994

Tools

Metrics

  • PDF downloads (22)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences