• 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

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

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

[3]

R. Battiti, Reactive search: Toward self-tuning heuristics,, Keynote talk at Applied Decision Technologies, (1995), 3.   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.  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.  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.  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, (1994), 35.   Google Scholar

[8]

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

[9]

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

[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.  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.  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.  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.  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.  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.  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.  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.  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, (2002), 249.  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, (1995), 3.   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.  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.  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.  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, (1994), 35.   Google Scholar

[8]

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

[9]

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

[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.  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.  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.  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.  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.  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.  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.  doi: 10.1287/trsc.1050.0135.  Google Scholar

[1]

Jean Dolbeault, Maria J. Esteban, Michał Kowalczyk, Michael Loss. Improved interpolation inequalities on the sphere. Discrete & Continuous Dynamical Systems - S, 2014, 7 (4) : 695-724. doi: 10.3934/dcdss.2014.7.695

[2]

Xianchao Xiu, Ying Yang, Wanquan Liu, Lingchen Kong, Meijuan Shang. An improved total variation regularized RPCA for moving object detection with dynamic background. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1685-1698. doi: 10.3934/jimo.2019024

[3]

Luigi C. Berselli, Jishan Fan. Logarithmic and improved regularity criteria for the 3D nematic liquid crystals models, Boussinesq system, and MHD equations in a bounded domain. Communications on Pure & Applied Analysis, 2015, 14 (2) : 637-655. doi: 10.3934/cpaa.2015.14.637

[4]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002

[5]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329

[6]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[7]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[8]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[9]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[10]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[11]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463

[12]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[13]

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075

[14]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183

[15]

Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493

[16]

Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189

[17]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258

[18]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401

[19]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151

[20]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]