Last ned (Gratis)

Abstrakt

This paper presents a guided cooperative parallel tabu search algorithm
for solving the capacitated vehicle routing problem. In the proposed
algorithm, knowledge is extracted from the previously found solutions
and applied to guide the diversification and intensification of individual
search threads. The computational experiments on two sets of large scale
benchmark instances show that the proposed guidance mechanism is able
to improve the effectiveness of the algorithm. The proposed algorithm
has generated solutions to the benchmark instances that are competitive
or better than the best solutions previously reported in the literature.

Referanser

E. Alba, editor. Parallel Metaheuristics: A New Class of Algorithms. John Willey & Sons, Hoboken, NJ, 2005.

T.G. Crainic. Parallel solution methods for vehicle routing problems. In B. Golden, S. Raghavan, and E. Wasil, editors, The Vehicle Routing Problem: Latest

Advances and New Challenges, pages 171–198, New York, 2008. Springer.

T.G. Crainic and H. Nourredine. Parallel metaheuristics applications. In E. Alba, editor, Parallel Metaheuristics, pages 447–494, Hoboken, NJ, 2005. John Willey & Sons.

M. M. Flood. The traveling-salesman problem. Operations Research, 4:61–75, 1956. F. Glover and M. Laguna. Tabu Search. Kluwer, 1997.

B.L. Golden, E.A.Wasil, J.P. Kelly, and I.-M. Chao. The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results. In T. Crainic and G. Laporte, editors, Fleet management and logistics, pages 33–56, Boston, 1998. Kluwer.

B.L. Golden, S. Raghavan, and E.A. Wasil. The Vehicle Routing Problem: Latest Advances and New Challenges. New York, 2008. Springer.

C. Gro¨er, B.L. Golden, and E.A. Wasil. A parallel algorithm for the vehicle routing problems. INFORMS Journal on Computing, 23:315–330, 2011.

J. Jin, T.G. Crainic, and A. Løkketangen. A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problem. Publication CIRRELT-2010- 54, Centre interuniversitaire de recherche sur les r´eseaux d’entreprise, la logistique et le transport, Universit´e de Montr´eal., 2010.

G. Laporte. Fifty years of vehicle routing. Transportation Science, 43(4):408–416, 2009.

A. Le Bouthillier, T.G. Crainic, and P. Kropf. A guided cooperative search for the vehicle routing problem with time windows. IEEE Intelligent Systems, 20(4): 36–42, 2005.

F. Li, B.L. Golden, and E.A. Wasil. Very large-scale vehicle routing: New test problems, algorithms, and results. Computers & Operations Research, 32:1165– 1179, 2005.

D. Mester and O. Br¨aysy. Active-guided evolution strategies for large-scale capacitated vehicle routing problems. Computers & Operations Research, 34: 2964–2975, 2007.

I. H. Osman. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problems. Annals of Operations Research, 54:421–452, 1993. J-Y. Potvin and J-M. Rousseau. An exchange heuristic for routing problems with time windows. Journal of the Operational Research Society, 46:1433–1446, 1995. M. W. P. Savelsbergh. The vehicle routing problem with time windows: minimizing route duration. INFORMS Journal on Computing, 4:146–154, 1992.

E. Taillard, P. Badeau, M. Gendreau, F. Geurtin, and J-Y. Potvin. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 31:170–186, 1997.

P. Toth and D. Vigo. The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002. PA.

P. Toth and D. Vigo. The granular tabu search and its application to the vehicle routing problem. INFORMS Journal on Computing, 15:333–346, 2003.






Forrige artikkel      Neste artikkel