# zbMATH — the first resource for mathematics

The covering tour problem. (English) Zbl 0887.90122
Summary: The covering tour problem (CTP) is defined on a graph $$G= (V\cup 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.

##### MSC:
 90C10 Integer programming
Full Text: