A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows

A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Vidal, T., Crainic, T., Gendreau, M., & Prins, C. Computers & Operations Research, 40(1):475–489, 2013.

Paper doi abstract bibtex 52 downloads

The paper presents an efficient Hybrid Genetic Search with Advanced Diversity Control for a large class of time-constrained vehicle routing problems, introducing several new features to manage the temporal dimension. New move evaluation techniques are proposed, accounting for penalized infeasible solutions with respect to time-window and duration constraints, and allowing to evaluate moves from any classical neighbourhood based on arc or node exchanges in amortized constant time. Furthermore, geometric and structural problem decompositions are developed to address efficiently large problems. The proposed algorithm outperforms all current state-of-the-art approaches on classical literature benchmark instances for any combination of periodic, multi-depot, site-dependent, and duration-constrained vehicle routing problem with time windows.

@article{Vidal2012c,
abstract = {The paper presents an efficient Hybrid Genetic Search with Advanced Diversity Control for a large class of time-constrained vehicle routing problems, introducing several new features to manage the temporal dimension. New move evaluation techniques are proposed, accounting for penalized infeasible solutions with respect to time-window and duration constraints, and allowing to evaluate moves from any classical neighbourhood based on arc or node exchanges in amortized constant time. Furthermore, geometric and structural problem decompositions are developed to address efficiently large problems. The proposed algorithm outperforms all current state-of-the-art approaches on classical literature benchmark instances for any combination of periodic, multi-depot, site-dependent, and duration-constrained vehicle routing problem with time windows.},
author = {Vidal, T. and Crainic, T.G. and Gendreau, M. and Prins, C.},
doi = {10.1016/j.cor.2012.07.018},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2013 - A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with t.pdf:pdf},
journal = {Computers {\&} Operations Research},
keywords = {Decomposition,Diversity management,Hybrid genetic algorithm,Neighbourhood search,Time windows,vehicle routing problems},
mendeley-groups = {Metaheuristics/Decompositions},
number = {1},
pages = {475--489},
title = {{A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows}},
url = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2011-61.pdf},
volume = {40},
year = {2013}
}

Downloads: 52