Implicit depot assignments and rotations in vehicle routing heuristics - Archive ouverte HAL Access content directly
Journal Articles European Journal of Operational Research Year : 2014

Implicit depot assignments and rotations in vehicle routing heuristics

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

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

Dates and versions

hal-02494263 , version 1 (28-02-2020)

Identifiers

Cite

Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Christian Prins. Implicit depot assignments and rotations in vehicle routing heuristics. European Journal of Operational Research, 2014, 237 (1), pp.15-28. ⟨10.1016/j.ejor.2013.12.044⟩. ⟨hal-02494263⟩

Collections

CNRS UTT LOSI
10 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More