The covering tour problem
成果类型：
Article
署名作者：
Gendreau, M; Laporte, G; Semet, F
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.4.568
发表日期：
1997
页码：
568-576
关键词：
摘要：
The Covering Tour Problem (CTP) is defined on a graph G = (V boolean OR 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.