A hybrid adaptive large neighbourhood search for multi-depot open vehicle routing problems

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.

Keywords:

• open vehicle routing problem
• multiple depots
• adaptive large neighbourhood search
• transportation
• logistics optimisation

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.

Additional information

Funding

This research was partly supported by grant IRG 16119 from Alfaisal University and grant 2014-05764 from the Canadian Natural Sciences and Engineering Research Council.