An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices

Abstract

The multi-vehicle covering tour problem (m-CTP) involves finding a minimum-length set of vehicle routes passing through a subset of vertices, subject to constraints on the length of each route and the number of vertices that it contains, such that each vertex not included in any route lies within a given distance of a route. This paper tackles a particular case of m- CTP where only the restriction on the number of vertices is considered, ie, the constraint on the length is relaxed. The problem is solved by a branch-and-cut algorithm and a ...