A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems

• 成果类型: Article
• 署名作者: Vidal, Thibaut; Crainic, Teodor Gabriel; Gendreau, Michel; Lahrichi, Nadia; Rei, Walter
• 署名单位: Universite de Montreal; Universite de Montreal; Universite de Montreal; University of Quebec; University of Quebec Montreal; University of Quebec; University of Quebec Montreal; Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1120.1048
• 发表日期: 2012
• 页码: 611-624
• 关键词: variable neighborhood search; tabu search; evolutionary algorithms; depot

摘要

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.