Abstract
In this paper we address the multi-depot open vehicle routing problem (MDOVRP), a complex and difficult problem arising in several real-life applications. In the MDOVRP vehicles start from several depots and do not need to return to the depot at the end of their routes. We propose a hybrid adaptive large neighbourhood search algorithm to solve the MDOVRP coupled with improvement procedures yielding a hybrid metaheuristic. The performance of the proposed metaheuristic is assessed on various benchmark instances proposed for this problem and its special cases, containing up to 48 customers (single-depot version) and up to six depots and 288 customers. The computational results indicate that the proposed algorithm is very competitive compared with the state-of-the-art methods and improves 15 best-known solutions for multi-depot instances and one best-known solution for a single-depot instance. A detailed sensitivity analysis highlights which components of the metaheuristic contribute most to the solution quality.
Acknowledgments
This support is gratefully acknowledged. We also thank Calcul Québec for providing computing facilities and implementation support. We thank an associate editor and two anonymous referees who have provided valuable comments on an earlier version of this paper.
Disclosure statement
No potential conflict of interest was reported by the authors.
Supplemental data
Supplemental data for this article can be accessed https://doi.org/10.1080/00207543.2019.1572929.