Heuristics for the multi-vehicle covering tour problem

The multi-vehicle covering tour problem is defined on a graph G = (V ∪ W, E), where W is a set of vertices that must collectively be covered by up to m vehicles. The problem consists of determining a set of total minimum length vehicle routes on a subset of V, subject to side constraints, such that every vertex of W is within a prespecified distance from a route. Three heuristics are developed for this problem and tested on randomly generated and real data.