Abstract
In this paper we propose two cooperation schemes to compose new parallel variants of the Variable Neighborhood Search (VNS). On the one hand, a coarse-grained cooperation scheme is introduced which is well suited for being enhanced with a solution warehouse to store and manage the so far best found solutions and a self-adapting mechanism for the most important search parameters. This makes an a priori parameter tuning obsolete. On the other hand, a fine-grained scheme was designed to reproduce the successful properties of the sequential VNS. In combination with the use of parallel exploration threads all of the best solutions and 11 out of 20 new best solutions for the Multi Depot Vehicle Routing Problem with Time Windows were found.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alba, Enrique (2005): Parallel Metaheuristics: A New Class of Algorithms, Wiley: Hoboken, New Jersey.
Alba, Enrique and Gabriel Luque (2005): Measuring the Performance of Parallel Metaheuristics, Wiley: Hoboken, New Jersey.
Alba, Enrique and the MALLBA Group (2002): MALLBA: A library of skeletons for combinatorial optimization (Proceedings of the Euro-Par, LNCS 2400), Springer, London, 927–932.
Barr, Richard S. and Betty L. Hickman (1993): Reporting computational experiments with parallel algorithms: issues, measures, and experts’ opinions, ORSA Journal of Computing, 5 (1): 2–18.
Braysy, Olli (2003): A reactive variable neighborhood search for the vehicle-routing problem with time windows, INFORMS Journal on Computing, 15 (4): 347–368.
Cahon, Sebastien, Nordine Melab and El-Ghazali Talbi (2004): ParadisEO:A framework for the reusable design of parallel and distributed metaheuristics, Journal of Heuristics, 10 (3): 357–380.
Cordeau, Jean-Francois, Gilbert Laporte and Anne Mercier (2001): A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society, 52 (8): 928–936.
Cordeau, Jean-Francois, Gilbert Laporte and Anne Mercier (2004): An improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows, Journal of the Operational Research Society, 55 (5): 542–546.
Crainic, Teodor G., Michel Gendreau, Pierre Hansen and Nenad Mladenovic (2004): Cooperative parallel variable neighborhood search for the p-median, Journal of Heuristics, 10 (3): 293–314.
Crainic, Teodor G. and Michel Toulouse (2002): Parallel strategies for meta-heuristics, in: Fred W. Glovers (ed.): Handbook of Metaheuristics, Kluwer, Dordrecht, 251–285.
Dueck, Gunter and Tobias Scheuer (1990): Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, 90 (1): 161–175.
Fischetti, Matteo and Andrea Lodi (2003): Local branching, Mathematical Programming Series B, 98 (1–3): 23–47.
Florian, Michael and Michel Gendreau (2001): Applications of parallel computing in transportation, Parallel Computing, 27 (12): 1521-1522.
Garcia Lopez, Felix, Belen Melian-Batista, Jose A. Moreno-perez and J. Marcos Moreno-Vega (2002): The parallel variable neighbourhood search for the p-median problem, Journal of Heuristics, 8 (3): 375–388.
Hansen, Pierre and Nenad Mladenovic (1999): An introduction to variable neighborhood search, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Boston: 433–458.
Hansen, Pierre and Nenad Mladenovic (2001): Variable neighborhood search: Principles and applications, European Journal of Operational Research, 130 (3): 449–467.
Hansen, Pierre, Nenad Mladenovic and Dragan Urosevic (2006): Variable neighborhood search and local branching, Computers & Operations Research, 33 (10): 3034–3045.
Jozefowiez, Nicolas, Frederic Semetand El-Ghazali Talbi (2002): Parallel and hybrid models for multiobjective optimization: applicationtothe vehicle routing problem, in: Juan Guervós, Panagiotis Adamidis, Hans-Georg José-Luis Fernández-Villacanas and Hans-Paul Schwefel (eds.): Parallel Problem Solving from Nature — PPSN VII, Lecture Notes in Computer Science, Vol. 2439, Springer, Berlin et al., 271–280.
Jozefowiez, Nicolas, Frederic Semetand El-Ghazali Talbi (2006): Enhancements of NSGA II and its applications to the vehicle routing problem with route balancing, in: El-Ghazali Talbi, Pierre Liardet, Pierre Collet, Evelyne Lutton, and Marc Schoenauer (eds.): Artificial Evolution: 7th International Conference — EA 2005, Lecture Notes in Computer Science, Vol. 3871, Springer, Berlin et al., 131–142.
Karp, Alan and Horace P. Flatt (1990): Measuring parallel processor performance, Communications of the ACM, 33 (5): 539–543.
Le Bouthillier, Alexandre and Teodor G. Crainic (2005): A cooperative parallel meta-heuristic for the vehicle routing problem with time windows, Computers & Operations Research, 32 (7): 1685–1708.
Moreno Perez, Jose A., Pierre Hansen and Nadan Mladenovic (2005): Parallel variable neighborhood search, in: Enrique Alba (ed.): Parallel Metaheuristics: A New Class of Algorithms, Wiley, Hoboken, New Jersey, 131–142.
MPI (1995) A message-passing interface standard version 1.1, Message Passing Interface Forum. http://www.mpi-forum.org/docs/docs.html.
Polacek, Michael, Richard F. Hartl, Karl Doerner and Marc Reimann (2004): A variable neighborhood search for the multi depot vehicle routing problem with time windows, Journal of Heuristics, 10 (6): 613–627.
Polacek, Michael, Karl Doerner, Richard F. Hartl and Guenter Kiechle (2007): Scheduling periodic customer visits for a traveling salesperson, European Journal of Operational Research, 179 (3): 823–837.
Ralphs, Ted K. (2004): Parallel Branch and Cut for Capacitated Vehicle Routing, Parallel Computing, 29 (5): 607–629.
Taillard, Eric, Philippe Badeau, Michel Gendreau, Francois Guertin and Jean-Yves Potvin (1997): A tabu search heuristic for the vehicle routing problem with soft time windows, Transportation Science, 31 (2): 170–186.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0), which permits use, duplication, adaptation, distribution, and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Polacek, M., Benkner, S., Doerner, K.F. et al. A Cooperative and Adaptive Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows. Bus Res 1, 207–218 (2008). https://doi.org/10.1007/BF03343534
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF03343534