Skip to Main content Skip to Navigation
Journal articles

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

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.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02476430
Contributor : Daniel Gavrysiak <>
Submitted on : Wednesday, February 12, 2020 - 4:33:04 PM
Last modification on : Monday, July 20, 2020 - 12:34:52 PM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Christian Prins. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers and Operations Research, Elsevier, 2013, 40 (1), pp.475-489. ⟨10.1016/j.cor.2012.07.018⟩. ⟨hal-02476430⟩

Share

Metrics

Record views

45