A branch-and-price algorithm for the multivehicle covering tour problem

This article proposes a mathematical model and a branch‐and‐price algorithm for the multivehicle covering tour problem. This problem consists in finding a set of routes on a weighted graph such that a set of nodes that cannot be visited is covered. A node is covered if it lies within a predefined distance of a visited node. The subproblem encountered during the column generation is a variant of the profitable tour problem. It is reduced to a ring star problem and a branch‐and‐cut algorithm is developed. Computational results are reported on randomly generated instances.