zbMATH — the first resource for mathematics

An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices. (English) Zbl 1292.90050
Summary: 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. Computational results are reported for a set of test problems derived from the TSPLIB.

90B06 Transportation, logistics and supply chain management
90C10 Integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX Cite
Full Text: DOI