Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem

International audienceIn this paper, we address the Multi-Depot Open Vehicle Routing Problem (MDOVRP), which is a generalization of the Capacitated Vehicle Routing Problem (CVRP) where vehicles start from different depots, visit customers, deliver goods and are not required to return to the depot at the end of their routes. The goal of this paper is two-fold. First, we have developed a general Multiple Neighborhood Search hybridized with a Tabu Search (MNS-TS) strategy which is proved to be efficient and second, we have settled an unified view of ejection chains to be able to handle several neighborhoods in a simple manner. The neighborhoods in the proposed MNS-TS are generated from path moves and ejection chains. The numerical and statistical tests carried out over OVRP and MDOVRP problem instances from the literature show that MNS-TS outperforms the state-of-the-art methods