A memetic algorithm for the vehicle routing problem with time windows
- 1 July 2008
- journal article
- research article
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 42 (3), 415-431
- https://doi.org/10.1051/ro:2008021
Abstract
This article deals with the vehicle routing problem with time windows (VRPTW). This problem consists in determining a least-cost set of trips to serve customers during specific time windows. The proposed solution method is a memetic algorithm (MA), a genetic algorithm hybridised with a local search. Contrary to most papers on the VRPTW, which minimize first the number of vehicles, our method is also able to minimize the total distance travelled. The results on 56 classical instances are compared to those of the best metaheuristics. The efficiency of the MA is similar for the classical criterion, but it becomes the best algorithm available for the total distance, being much faster and improving 20 best-known solutions. Cet article concerne le problème de tournées de véhicules avec fenêtres horaires (Vehicle Routing Problem with Time Windows ou VRPTW). Ce problème consiste à déterminer un ensemble de tournées de coût total minimal pour servir des clients dans des fenêtres horaires spécifiques. Nous proposons un algorithme mémétique (MA, algorithme génétique hybridé avec une recherche locale) pour le résoudre. Contrairement à la plupart des articles sur le VRPTW, qui minimisent en priorité le nombre de véhicules, notre méthode peut aussi minimiser la distance totale parcourue. Les résultats sur 56 problèmes-tests classiques sont comparés à ceux des meilleures métaheuristiques. Pour le critère classique, le MA offre des performances similaires, mais il devient le meilleur algorithme disponible pour la distance totale, en étant bien plus rapide et en améliorant 20 des meilleures solutions connues.Keywords
This publication has 16 references indexed in Scilit:
- A genetic and set partitioning two-phase approach for the vehicle routing problem with time windowsComputers & Operations Research, 2007
- A two-phase hybrid metaheuristic for the vehicle routing problem with time windowsEuropean Journal of Operational Research, 2005
- Vehicle Routing Problem with Time Windows, Part II: MetaheuristicsTransportation Science, 2005
- Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search AlgorithmsTransportation Science, 2005
- Evolutionary Algorithms for the Vehicle Routing Problem with Time WindowsJournal of Heuristics, 2004
- A simple and effective evolutionary algorithm for the vehicle routing problemComputers & Operations Research, 2004
- A HYBRID SEARCH ALOGRITHM FOR THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWSInternational Journal on Artificial Intelligence Tools, 2001
- Heuristic methods for vehicle routing problem with time windowsArtificial Intelligence in Engineering, 2001
- Probabilistic diversification and intensification in local search for vehicle routingJournal of Heuristics, 1995
- Vehicle Routing with Time Windows using Genetic AlgorithmsPublished by Taylor & Francis Ltd ,1995