Premium
A branch‐and‐price algorithm for the multivehicle covering tour problem
Author(s) -
Jozefowiez Nicolas
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21564
Subject(s) - computer science , mathematical optimization , algorithm , mathematics
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