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.

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.

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.

DOI : 10.1051/ro:2008021
Classification : 90B06
Mots-clés : memetic algorithm, vehicle routing problem, time window 
@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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ro:2008021/

[1] G.B. Alvarenga, G.R. Mateus and G. De Tomi, A genetic and set partitioning two-phase approch for the vehicle routing problem with time windows. Comput. Oper. Res. 34 (2007) 1561-1584.

[2] J. Berger, M. Barkaoui and O. Bräysy, A route-directed hybrid genetic approach for the vehicle routing problem with time windows. Inf. Syst. Oper. Res. 41 (2003) 179-194.

[3] J. Berger, M. Salois and R. Begin, A hybrid genetic algorithm for the vehicle routing problem with time windows. Lecture Notes in Artificial Intelligence 1418. Springer, Berlin (1998) 114-127.

[4] J.L. Blanton and R.L. Wainwright, Multiple vehicle routing with time and capacity constraints using genetic algorithms, Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, San Francisco (1993) 452-459.

[5] O. Bräysy, W. Dullaert and M. Gendreau, Evolutionary algorithms for the vehicle routing problem with time windows. J. Heuristics 10 (2005) 587-611.

[6] O. Bräysy and M. Gendreau, Vehicle routing problem with time windows - Part I: route construction and local search algorithms. Transportation Science 39 (2005) 104-118.

[7] O. Bräysy and M. Gendreau, Vehicle routing problem with time windows - Part II: metaheuristics. Transportation Science 39 (2005) 119-139.

[8] G. Clarke and J.W. Wright, Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12 (1964) 568-581.

[9] H. Gehring and J. Homberger, A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows, Proceedings of EUROGEN 99, University of Jyväskylä, Finland (1999) 57-64.

[10] H. Gehring and J. Homberger, Parallelization of a two-phase metaheuristic for routing problems with time windows. Asia-Pacific J. Oper. Res. 18 (2001) 35-47.

[11] B.E. Gillett and L.R. Miller, A heuristic algorithm for the vehicle dispatch problem. Oper. Res. 22 (1974) 340-349. | Zbl

[12] J.H. Holland, Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor (1975). | MR | Zbl

[13] J. Homberger and H. Gehring, Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR 37 (1999) 297-318.

[14] J. Homberger and H. Gehring, A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. Eur. J. Oper. Res. 162 (2005) 220-238. | Zbl

[15] S. Jung and B.R. Moon, A hybrid genetic algorithm for the vehicle routing problem with time windows, Proceedings of Genetic and Evolutionary Computation Conference. Morgan Kaufmann, San Francisco (2002) 1309-1316.

[16] G.A.P. Kindervater and M.W.P. Savelsbergh, Vehicle routing: handling edge exchanges. edited by E.H.L. Aarts and J.K. Lenstra, Local search in combinatorial optimization. Wiley, Chichester (1997) 311-336. | MR | Zbl

[17] D. Mester, An evolutionary strategies algorithm for large scale vehicle routing problem with capacitate and time windows restrictions, Working paper, Institute of Evolution, University of Haifa, Israel (2002).

[18] P. Moscato, Memetic algorithms: a short introduction, edited by D. Corne, M. Dorigo and F. Glover, New Ideas in Optimization. McGraw-Hill, New York (1999) 219-234.

[19] J.Y. Potvin and S. Bengio, The vehicle routing with time windows - Part II: genetic search. INFORMS J. Comput. 8 (1996) 165-172. | Zbl

[20] C. Prins, A simple and effective evolutionary algorithm for the vehicle routing problem, Comput. Oper. Res. 31 (2004) 1985-2002. | MR | Zbl

[21] Y. Rochat and E.D. Taillard, Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1 (1995) 147-167. | Zbl

[22] M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35 (1987) 254-265. | MR | Zbl

[23] E. Taillard, P. Badeau, M. Gendreau, F. Guertin and J.Y. Potvin, Tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science 31 (1997) 170-186. | Zbl

[24] K.C. Tan, L.H. Lee and K. Ou, Hybrid genetic algorithms in solving ehicle routing problems with time window constraints. Asia-Pacific J. Oper. Res. 18 (2001) 121-130. | MR | Zbl

[25] K.C. Tan, L.H. Lee and K. Ou, A messy genetic algorithm for the vehicle routing problem with time window constraints, Proceedings of the 2001 Congress on Evolutionary Computation, IEEE, Piscataway (2001) 679-686.

[26] K.C. Tan, L.H. Lee, Q.L. Zhu and K. Ou, Heuristic methods for the vehicle routing problem with time windows. Artificial Intelligence in Engineering 15 (2001) 281-295.

[27] S. Thangiah, Vehicle routing with time windows using genetic algorithms. edited by L. Chambers, Application handbook of genetic algorithms: new frontiers, Vol II. CRC Press, Boca Raton (1995) 253-277.

[28] H. Wee Kit, J. Chin and A. Lim, A hybrid search algorithm for the vehicle routing problem with time windows. Int. J. Art. Intell. Tools 10 (2001) 431-449.

Cité par Sources :