Abstract
We consider the n‐city traveling salesman problem (TSP), symmetric or asymmetric,with the following attributes. In one case, a positive integer k and an ordering (1,..., n) ofthe cities is given, and an optimal tour is sought subject to the condition that for any pairi, j ∈ (1..., n), if j ≥ i + k, then i precedes j in the tour. In another case, position i in the tourhas to be assigned to some city within k positions from i in the above ordering. This case isclosely related to the TSP with time windows. In a third case, an optimal tour visiting m outof n cities is sought subject to constraints of the above two types. This is a special case ofthe Prize Collecting TSP (PCTSP). In any of the three cases, k may be replaced by city‐specificintegers k(i), i = 1,..., n. These problems arise in practice. For each class, we reducethe problem to that of finding a shortest source‐sink path in a layered network with a numberof arcs linear in n and exponential in the parameter k (which is independent of the problemsize). Besides providing linear time algorithms for the solution of these problems, the reductionto a shortest path problem also provides a compact linear programming formulation.Finally, for TSPs or PCTSPs that do not have the required attributes, these algorithms canbe used as heuristics that find in linear time a local optimum over an exponential‐sizeneighborhood.
Similar content being viewed by others
References
N. Ascheuer, L.F. Escudero, M. Grötschel and M. Stoer, On identifying in polynomial time violated subtour elimination and precedence forcing constraints for the sequential ordering problem, in: Integer Programming and Combinatorial Optimization, (Proceedings of IPCO 1), eds. R. Kannan and W.R. Pulleyblank, University of Waterloo Press, 1990, pp. 19-28.
E. Balas, The Prize Collecting Traveling Salesman Problem, ORSA/TIMS Meeting, Los Angeles, Spring 1986.
E. Balas, The Prize Collecting Traveling Salesman Problem, Networks 19(1989)621-636.
E. Balas, The Prize Collecting Traveling Salesman Problem: II. Polyhedral results, Networks 25(1995)199-216.
E. Balas, M. Fischetti and W.R. Pulleyblank, The precedence constrained asymmetric Traveling Salesman Polytope, Mathematical Programming 68(1995)241-265.
E. Balas and C.H. Martin, Combinatorial optimization in steel rolling (Extended Abstract), Workshop on Combinatorial Optimization in Science and Technology (COST), RUTCOR, Rutgers University, April 1991.
E. Balas and N. Simonetti, Linear time dynamic programming algorithms for new classes of restricted TSPs: A computational study, MSRR No. 625, GSIA, Carnegie Mellon University, October 1997.
X. Berenguer, A characterization of linear admissible transformations for the m-Traveling Salesman Problem, European Journal of Operations Research 3(1979)232-249.
V.Ya. Burdyuk and V.N. Trofimov, Generalization of the results of Gilmore and Gomory on the solution of the Traveling Salesman Problem (in Russian), Izv. Akad. Nauk SSSR, Tech. Kibernet, 3(1976)16-22 [English translation in Engineering Cybernetics 14(1976)12-18].
R.E. Burkard and W. Sandholzer, Efficiently solvable special cases of the Bottleneck Traveling Salesman Problem, Discrete Applied Mathematics 32(1991)61-67.
R.E. Burkard and J.A.A. van der Veen, Universal conditions for algebraic Travelling Salesman Problems to be efficiently solvable, Optimization 22(1991)787-814.
R.E. Burkard and V.G. Deineko, Polynomially solvable cases of the Traveling Salesman Problem and a new exponential neighborhood, Computing 54(1995)191-211.
R. van Dal, J.A.A. van der Veen and G. Sierksma, Small and large TSP: Two well-solvable cases of the Traveling Salesman Problem, Eur. J. of Oper. Res. 69(1993)107-120.
G. Cornuéjols, D. Naddef and W.R. Pulleyblank, Halin graphs and the Traveling Salesman Problem, Mathematical Programming 26(1983)287-294.
V.M. Demidenko, The Traveling Salesman Problem with asymmetric matrices (in Russian), Vestsi Ak. Navuk BSSR, Ser. Fiz.-Mat. Navuk 1(1979)29-35.
L. Escudero, M. Guidnard and K. Malik, On identifying and lifting valid cuts for the sequential ordering problem with precedence relationships and deadlines, University of Madrid and IBM Spain, 1991.
W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, Wiley, 1957.
M.T. Fiala and W.R. Pulleyblank, Precedence in constrained routing and helicopter scheduling: Heuristic design, Interfaces 22(1992)100-111.
M. Fischetti and P. Toth, An additive approach for the optimal solution of the Prize Collecting Traveling Salesman Problem, in: Vehicle Routing: Methods and Studies, eds. B.L. Golden and A.A. Assad, North-Holland, 1988, pp. 319-343.
S. Fuller, An optimal drum scheduling algorithm, IEEE Trans. Comput. C-21(1972)1153-1165.
E.Ya. Gabovich, The small Traveling Salesman Problem (in Russian), Trudy Vychisl Tsentra Tartu, Gos. Univ. 19(1970)27-51.
E.Ya. Gabovich, Constant discrete programming problems on substitution sets (in Russian), Kibernetika 5(1976)128-134 [translation: Cybernetics 12(1977)786-793].
N.E. Gaikov, On the minimization of a linear form on cycles (in Russian), Vestsi Ak. Navuk BSSR, Ser. Fiz.-Mat. Navuk 4(1980)128.
R.S. Garfinkel, Minimizing wallpaper waste: A class of Traveling Salesman Problems, Operations Research 25(1977)741-751.
P.C. Gilmore and R.E. Gomory, Sequencing a one state variable machine: A solvable case of the Traveling Salesman Problem, Operations Research 12(1964)655-679.
P.C. Gilmore, E.L. Lawler and D. Shmoys, Well-solved special cases, in: The Traveling Salesman Problem: A Guided Tour to Combinatorial Optimization, eds. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D. Shmoys, Wiley, 1985, chap. 4.
K. Kalmanson, Edgeconvex circuits and the Traveling Salesman Problem, Canadian Journal of Mathematics 27(1975)1000-1010.
P.S. Klyaus, Structure of the optimal solution of certain classes of Traveling Salesman Problems (in Russian), Vestsi Akad. Navuk BSSR, Ser. Fiz.-Mat. Navuk 6(1976)95-98.
E.L. Lawler, A solvable case of the Traveling Salesman Problem, Mathematical Programming 1(1971)267-269.
J.K. Park, A special case of the n-vertex Traveling Salesman Problem that can be solved in O(n) time, Inform. Process. Lett. 40(1991)247-254.
H.D. Ratliff and A.S. Rosenthal, Order picking in a rectangular warehouse: A solvable case of the Traveling Salesman Problem, Operations Research 31(1983)507-521.
N. Simonetti and E. Balas, Implementation of a linear time algorithm for certain generalized Traveling Salesman Problems, in: Integer Programming and Combinatorial Optimization (Proceedings of IPCO~5), eds. W.H. Cunningham, T.S. McCormick and M. Queyranne, Springer, 1996, pp. 316-329.
F. Supnick, Extreme Hamiltonian lines, Annals of Mathematics 65(1957)179-201.
J.A.A. van der Veen, Solvable cases of the Travelling Salesman Problem with various objective functions, Ph.D. Thesis, Nijenrode University, 1992.
J.A.A. van der Veen, G. Sierksma, R. van Dal, Pyramidal tours and the Travelling Salesman Problem, European Journal of Operational Research 69(1993)107-120.
Rights and permissions
About this article
Cite this article
Balas, E. New classes of efficiently solvable generalized Traveling Salesman Problems. Annals of Operations Research 86, 529–558 (1999). https://doi.org/10.1023/A:1018939709890
Issue Date:
DOI: https://doi.org/10.1023/A:1018939709890