The Covering Tour Problem

Michel Gendreau, Gilbert Laporte and Frédéric Semet
Additional contact information
Michel Gendreau: Université de Montréal, Montréal, Canada
Gilbert Laporte: Université de Montréal, Montréal, Canada
Frédéric Semet: Université de Montréal, Montréal, Canada

Operations Research, 1997, vol. 45, issue 4, 568-576

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 (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (56)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.4.568 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:4:p:568-576

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().