Premium
Locating a cycle in a transportation or a telecommunications network
Author(s) -
Laporte Gilbert,
Martín Inmaculada Rodríguez
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20170
Subject(s) - travelling salesman problem , hamiltonian path , computer science , graph , mathematical optimization , hamiltonian path problem , hamiltonian (control theory) , mathematics , theoretical computer science
Abstract Several problems arising in transportation and telecommunications can be cast in terms of optimally locating a cycle in a graph. This paper proposes a classification of cycle location problems under two main headings. In Hamiltonian problems, all vertices of the graph must belong to the cycle. The most important cases are the traveling salesman problem (TSP), the TSP with precedence constraints, the clustered TSP, the TSP with backhauls, the TSP with time windows, several classes of pickup and delivery problems, and stochastic TSPs. In non‐Hamiltonian problems, only a subset of vertices must be visited. These problems include the generalized TSP, the covering tour problem, the median cycle and ring star problems, and several cycle location problems with revenues. These problems are modeled within a unified framework and algorithmic strategies are provided, together with computational results. Several applications are also described. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 92–108 2007