A memetic algorithm for the vehicle routing problem with time windows

Nacima Labadi; Christian Prins; Mohamed Reghioui

RAIRO - Operations Research (2008)

  • Volume: 42, Issue: 3, page 415-431
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Labadi, Nacima, Prins, Christian, and Reghioui, Mohamed. "A memetic algorithm for the vehicle routing problem with time windows." RAIRO - Operations Research 42.3 (2008): 415-431. <http://eudml.org/doc/250417>.

@article{Labadi2008,
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. },
author = {Labadi, Nacima, Prins, Christian, Reghioui, Mohamed},
journal = {RAIRO - Operations Research},
keywords = {memetic algorithm; vehicle routing problem; time window.; time window},
language = {eng},
month = {8},
number = {3},
pages = {415-431},
publisher = {EDP Sciences},
title = {A memetic algorithm for the vehicle routing problem with time windows},
url = {http://eudml.org/doc/250417},
volume = {42},
year = {2008},
}

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
DA - 2008/8//
PB - EDP Sciences
VL - 42
IS - 3
SP - 415
EP - 431
AB - 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.
LA - eng
KW - memetic algorithm; vehicle routing problem; time window.; time window
UR - http://eudml.org/doc/250417
ER -

References

top
  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 Intelligence1418. 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. Heuristics10 (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 Science39 (2005) 104–118.  
  7. O. Bräysy and M. Gendreau, Vehicle routing problem with time windows – Part II: metaheuristics. Transportation Science39 (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.  
  12. J.H. Holland, Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor (1975).  
  13. J. Homberger and H. Gehring, Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR37 (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.  
  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.  
  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.  
  20. C. Prins, A simple and effective evolutionary algorithm for the vehicle routing problem, Comput. Oper. Res.31 (2004) 1985–2002.  
  21. Y. Rochat and E.D. Taillard, Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics1 (1995) 147–167.  
  22. M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res.35 (1987) 254–265.  
  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 Science31 (1997) 170–186.  
  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.  
  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 Engineering15 (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. Tools10 (2001) 431–449.  

NotesEmbed ?

top

You must be logged in to post comments.