An Iterated Local Search Algorithm for the Multi-Vehicle Covering Tour Problem

Given two sets of vertices V and W, where each vertex in V covers a subset of W, the multi-vehicle covering tour problem asks to determine a number of vehicle routes on a subset of V so as to minimize the total distance under the constraint that every vertex in W must be covered by vertices in the routes. We propose an iterated local search algorithm that features two procedures to improve solutions: one consists of three operations to remove or insert vertices from or into a route; the other is path reconstruction that replaces a partial path with an optimal one, for which we propose a dynamic programming algorithm. We also propose efficient methods to reduce the computation time to search for improved solutions in neighborhoods. The computational results on benchmark instances show that our algorithm performs better than existing methods and is efficient for large-scale instances.