A Hybrid Genetic Algorithm for Multi-Depot and Periodic

A Hybrid Genetic Algorithm for Multi-Depot and Periodic Vehicle Routing Problems † Thibaut Vidal 1,2 , Teodor Gabriel Crainic 1,3,* , Michel Gendreau 1,4 , Nadia Lahrichi 1,3 , Walter Rei 1,3 1 Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation

(CIRRELT) 2 Department of Computer Science and Operations Research, Université de Montréal, P.O. Box 6128, Station Centre-ville, Montréal, Canada H3C 3J7 3 Department of Management and Technology, Université du Québec à Montréal, P.O. Box 8888, Station Centre-Ville, Montréal, Canada H3C 3P8 4 Department of Mathematics and Industrial Engineering, École Polytechnique de Montréal, P.O. Box 6079, Station Centre-ville, Montréal, Canada H3C 3A7 Abstract. We propose an algorithmic framework that successfully addresses three vehicle routing problems: the multi-depot VRP, the periodic VRP, and the multi-depot periodic VRP with capacitated vehicles and constrained route duration. The meta-heuristic combines the exploration breadth of population-based evolutionary search, the aggressive improvement capabilities of neighborhood-based meta-heuristics, 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. Multi-depot, multi-period, vehicle routing problems, hybrid populations-based meta-heuristics, adaptive population, diversity management. Acknowledgements. Partial funding for this project has been provided by the Natural Sciences and Engineering Research Council of Canada (NSERC), through its Industrial Research Chair and Discovery Grants programs, and by the partners of the Chair, CN, Rona, Alimentation Couche-Tard and the Ministry of Transportation of Québec, and by the Fonds québécois de la recherche sur la nature et les technologies (FQRNT) through its Team Research Project Program. † This version updates the CIRRELT-2010-34 Results and views expressed in this publication are the sole responsibility of the authors and do not necessarily reflect those of CIRRELT. Les résultats et opinions contenus dans cette publication ne reflètent pas nécessairement la position du CIRRELT et n'engagent pas sa responsabilité. _____________________________ * Corresponding author: Teodor.Gabriel@cirrelt.ca Dépôt légal – Bibliothèque et Archives nationales du Québec Bibliothèque et Archives Canada, 2011 © Copyright Vidal, Crainic, Gendreau, Lahrichi, Rei and CIRRELT, 2011 1 Introduction Vehicle Routing Problem (VRP) formulations are used to model an extremely broad range of issues in many application elds, transportation, supply chain management, production planning, and telecommunications, to name but a few (Toth and Vigo, 2002; Ho et al., 2010). Not surprisingly, starting with the seminal work of Dantzig and Ramser (1959), routing problems make up an extensively and continuously studied eld, as illustrated by numerous conferences, survey articles (e.g., Christo...

Website: www.cirrelt.ca | Filesize: -
No of Page(s): 44
Download A Hybrid Genetic Algorithm for Multi-Depot and Periodic ... - CIRRELT.pdf