Implicit depot assignments and rotations in vehicle routing heuristics

Implicit depot assignments and rotations in vehicle routing heuristics. Vidal, T., Crainic, T., Gendreau, M., & Prins, C. European Journal of Operational Research, 237(1):15–28, 2014.

Paper doi abstract bibtex

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.

@article{Vidal2012e,
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.},
author = {Vidal, T. and Crainic, T.G. and Gendreau, M. and Prins, C.},
doi = {10.1016/j.ejor.2013.12.044},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2014 - Implicit depot assignments and rotations in vehicle routing heuristics.pdf:pdf},
journal = {European Journal of Operational Research},
number = {1},
pages = {15--28},
title = {{Implicit depot assignments and rotations in vehicle routing heuristics}},
url = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2012-60.pdf},
volume = {237},
year = {2014}
}

Downloads: 0