The Covering Tour Problem
Michel Gendreau, Gilbert Laporte, Frédéric Semet
Operations Research · 1997 · Volume 45 · Issue 4
Abstract
The Covering Tour Problem (CTP) is defined on a graph G = ( V ∪ W , E ), where W is a set of vertices that must be covered. The CTP consists of determining a minimum length Hamiltonian cycle on a subset of V such that every vertex of W is within a prespecified distance from the cycle. The problem is first formulated as an integer linear program, polyhedral properties of several classes of constraints are investigated, and an exact branch-and-cut algorithm is developed. A heuristic is also described. Extensive computational results are presented.
Keywords
transportation, route selection, programming, integer applications
Enable JavaScript for citation tools and additional paper interactions.