A new large neighborhood search based matheuristic framework for rich vehicle routing problems

In this paper a New Large Neighborhood Search Based Matheuristic Framework for Rich Vehicle Routing Problems is presented. The innovative aspect of the proposed approach concern the possibility to address large neighborhoods in reasonably small computational time exploiting the search directly by the mathematical model. In this way it is possible to obtain the local minimum respect to the addressed neighborhood, which make the intensification phase of the algorithm more powerful and precise. The method is extremely flexible and can be adapted to many rich vehicle routing problems. This procedure can be used as a stand alone heuristic or can be embedded in a more complex metaheuristic framework such as Variable Neighborhood Search (VNS) and Adaptive Large Neighborhood Search (ALNS). The proposed algorithm has been tested on a new rich Vehicle Routing Problem arising in real life context, the Multi Depot Multi Period Vehicle Routing Problem with Heterogeneous Fleet. Computational results on realistic instances, showing the effectiveness of the proposed method, are provided.