A branch‐and‐price algorithm for the multivehicle covering tour problem. Issue 3 (15th September 2014) - Jozefowiez, Nicolas
<x xml:space="preserve">Abstract</x> 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. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 160–168 2014