The Covering Tour Problem

TLDR

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 study formulates the CTP as an integer linear program, investigates polyhedral properties of constraints, and develops an exact branch‑and‑cut algorithm. The authors model the CTP as an integer linear program, seek a minimum‑length Hamiltonian cycle covering all W within a given distance, and propose both an exact branch‑and‑cut algorithm and a heuristic. Extensive computational results are presented, illustrating the performance of the exact and heuristic approaches.

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.