A New Hybrid Iterated Local Search for the Open Vehicle Routing Problem

Open vehicle routing problem (OVRP) aims to design a set of open vehicle routes with the least number of vehicles and the shortest total travel time, for serving a set of geographically distributed customers with known coordinates and demands. In this paper, a new hybrid iterated local search algorithm IVND is proposed for solving the OVRP. The IVND integrates a variable neighborhood descent (VND) procedure into the framework of iterated local search (ILS). Four different neighborhood structures, i.e., relocation, swap, 2-opt*, and 2-opt, are used in a VND procedure to improve the incumbent solution iteratively. A perturbation strategy is designed to help the search process jump from the local optima. Computational results on 16 benchmark problems instances show that the proposed algorithm can find the best known solutions for most of the problems within a short time, which indicates that the proposed hybrid metaheuristic algorithm is competitive with other state-of-the-art metaheuristics for solving the OVRP in terms of solution quality and efficiency.