Voir la notice de l'article provenant de la source Numdam
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.
@article{RO_2008__42_3_415_0,
author = {Labadi, Nacima and Prins, Christian and Reghioui, Mohamed},
title = {A memetic algorithm for the vehicle routing problem with time windows},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {415--431},
publisher = {EDP-Sciences},
volume = {42},
number = {3},
year = {2008},
doi = {10.1051/ro:2008021},
mrnumber = {2444496},
zbl = {1152.90334},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2008021/}
}
TY - JOUR AU - Labadi, Nacima AU - Prins, Christian AU - Reghioui, Mohamed TI - A memetic algorithm for the vehicle routing problem with time windows JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2008 SP - 415 EP - 431 VL - 42 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro:2008021/ DO - 10.1051/ro:2008021 LA - en ID - RO_2008__42_3_415_0 ER -
%0 Journal Article %A Labadi, Nacima %A Prins, Christian %A Reghioui, Mohamed %T A memetic algorithm for the vehicle routing problem with time windows %J RAIRO - Operations Research - Recherche Opérationnelle %D 2008 %P 415-431 %V 42 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro:2008021/ %R 10.1051/ro:2008021 %G en %F RO_2008__42_3_415_0
Labadi, Nacima; Prins, Christian; Reghioui, Mohamed. A memetic algorithm for the vehicle routing problem with time windows. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 415-431. doi: 10.1051/ro:2008021
Cité par Sources :