A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows - Archive ouverte HAL Access content directly
Journal Articles Computers and Operations Research Year : 2013

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

(1, 2) , (1) , (1) , (2)
1
2

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.
Not file

Dates and versions

hal-02476430 , version 1 (12-02-2020)

Identifiers

Cite

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, 2013, 40 (1), pp.475-489. ⟨10.1016/j.cor.2012.07.018⟩. ⟨hal-02476430⟩

Collections

CNRS UTT LOSI
34 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More