A variable neighborhood search for solving the multi-vehicle covering tour problem

In this article, we consider a transportation problem with different kinds of locations: V, T, and W. The set T⊂V consists of vertices that must be visited through the use of potential locations in V and W consists of locations that must be covered. The problem consists in minimizing vehicle routes on a subset of V including T. We develop a variable neighborhood search heuristic based on a variable neighborhood descent in which a set of locations must be visited, whereas another subset must be close enough to the planned routes. We tested and compared our algorithm on datasets based on TSP Library instances.