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

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, i.e., the constraint on the length is relaxed. The problem is solved by a branch-and-cut algorithm and a metaheuristic. To develop the branch-and-cut algorithm, we use a new integer programming formulation based on a two-commodity flow model. The metaheuristic is based on the evolutionary local search (ELS) method proposed in [23]. Computational results are reported for a set of test problems derived from the TSPLIB.

► We solve the multi-vehicle covering tour problem with particular constraints.
► We present an exact method using a branch-and-cut algorithm.
► Results for instances with up to 200 vertices are reported.
► Our branch-and-cut algorithm outperforms the only exact method recently published.
► A metaheuristic giving high quality solutions is developed.