Variable Neighborhood Search based Set Covering ILP Model for the Vehicle Routing Problem with Time Windows

In this paper we propose a hybrid metaheuristic based on General Variable Neighborhood search and Integer Linear Programming for solving the vehicle routing problem with time windows (VRPTW). The problem consists in determining the minimum cost routes for a homogeneous fleet of vehicles to meet the demand of a set of customers within a specified time windows. The proposed heuristic, called VNS-SCP is considered as a matheuristic where the hybridization of heuristic (VNS) and exact (Set Covering Problem (SCP)) method is used in this approach as an intertwined collaborative cooperation manner. In this approach an initial solution is first created using Solomon route-construction heuristic, the nearest neighbor algorithm. In the second phase the solutions are improved in terms of the total distance traveled using VNS-SCP. The algorithm is tested using Solomon benchmark. Our findings indicate that the proposed procedure outperforms other local searches and metaheuristics.