THE COVERING TOUR PROBLEM

The Covering Tour Problem (CTP) is defined on a graph G = (V boolean O R W, E), where W is a set of vertices that must be covered. The CTP co nsists of determining a minimum length Hamiltonian cycle on a subset o f V such that every vertex of W is within a prespecified distance from the cycle. The problem is first formulated as an integer linear progr am, polyhedral properties of several classes of constraints are invest igated, and an exact branch-and-cut algorithm is developed. A heuristi c is also described. Extensive computational results are presented.