A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems

Thibaut Vidal (), Teodor Gabriel Crainic (), Michel Gendreau (), Nadia Lahrichi () and Walter Rei ()
Additional contact information
Thibaut Vidal: CIRRELT and Département d'informatique et de recherche opérationnelle, Université de Montréal, Montréal, Quebec H3C 3J7, Canada
Teodor Gabriel Crainic: CIRRELT and Département de management et technologie, École des sciences de la gestion, University of Quebec in Montréal, Montréal, Quebec H3C 3P8, Canada
Michel Gendreau: CIRRELT and Département de mathématiques et génie industriel, École Polytechnique, Montréal, Quebec H3C 3A7, Canada
Nadia Lahrichi: CIRRELT and Département de mathématiques et génie industriel, École Polytechnique, Montréal, Quebec H3C 3A7, Canada
Walter Rei: CIRRELT and Département de management et technologie, École des sciences de la gestion, University of Quebec in Montréal, Montréal, Quebec H3C 3P8, Canada

Operations Research, 2012, vol. 60, issue 3, 611-624

Abstract: We propose an algorithmic framework that successfully addresses three vehicle routing problems: the multidepot VRP, the periodic VRP, and the multidepot periodic VRP with capacitated vehicles and constrained route duration. The metaheuristic combines the exploration breadth of population-based evolutionary search, the aggressive-improvement capabilities of neighborhood-based metaheuristics, and advanced population-diversity management schemes. Extensive computational experiments show that the method performs impressively in terms of computational efficiency and solution quality, identifying either the best known solutions, including the optimal ones, or new best solutions for all currently available benchmark instances for the three problem classes. The proposed method also proves extremely competitive for the capacitated VRP.

Keywords: multidepot; multiperiod vehicle routing problems; hybrid population-based metaheuristics; adaptive population diversity management (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (100)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1048 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:3:p:611-624

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().