Skip to Main content Skip to Navigation
Journal articles

Implicit depot assignments and rotations in vehicle routing heuristics

Abstract : Vehicle routing variants with multiple depots and mixed fleet present intricate combinatorial aspects related to sequencing choices, vehicle type choices, depot choices, and depots positioning. This paper introduces a dynamic programming methodology for efficiently evaluating compound neighborhoods combining sequence-based moves with an optimal choice of vehicle and depot, and an optimal determination of the first customer to be visited in the route, called rotation. The assignment choices, making the richness of the problem, are thus no more addressed in the solution structure, but implicitly determined during each move evaluation. Two meta-heuristics relying on these concepts, an iterated local search and a hybrid genetic algorithm, are presented. Extensive computational experiments demonstrate the remarkable performance of these methods on classic benchmark instances for multi-depot vehicle routing problems with and without fleet mix, as well as the notable contribution of the implicit depot choice and positioning methods to the search performance. New state-of-the-art results are obtained for multi-depot vehicle routing problems (MDVRP), and multi-depot vehicle fleet mix problems (MDVFMP) with unconstrained fleet size. The proposed concepts are fairly general, and widely applicable to many other vehicle routing variants.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02494263
Contributor : Daniel Gavrysiak <>
Submitted on : Friday, February 28, 2020 - 3:27: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. Implicit depot assignments and rotations in vehicle routing heuristics. European Journal of Operational Research, Elsevier, 2014, 237 (1), pp.15-28. ⟨10.1016/j.ejor.2013.12.044⟩. ⟨hal-02494263⟩

Share

Metrics

Record views

41