Steiner travelling salesman problem

Last updated May 27, 2025

The Steiner traveling salesman problem (Steiner TSP, or STSP) is an extension of the traveling salesman problem. Given a list of cities, some of which are required, and the lengths of the roads between them, the goal is to find the shortest possible walk that visits each required city and then returns to the origin city.^[1] During a walk, vertices can be visited more than once, and edges may be traversed more than once.^[2]

References

↑ Interian, Ruben; Ribeiro, Celso C. (15 July 2017). "A GRASP heuristic using path-relinking and restarts for the Steiner traveling salesman problem" . International Transactions in Operational Research. 24 (6): 1307–1323. doi:10.1111/itor.12419.
↑ Álvarez-Miranda, Eduardo; Sinnl, Markus (2019-09-05). "A note on computational aspects of the Steiner traveling salesman problem" . International Transactions in Operational Research. 26 (4): 1396–1401. doi:10.1111/itor.12592. S2CID 71717255.

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.
Huili Zhang, Weitian Tong, Yinfeng Xu, and Guohui Lin. The steiner traveling salesman problem with online edge blockages. European Journal of Operational Research, 243(1):30–40, 2015.
Gerard Cornuejols, Jean Fonlupt, and Denis Naddef. The traveling salesman problem on a graph and some related integer polyhedra. Mathematical Programming, 33(1):1–27, 1985.
S. Borne, A.R. Mahjoub, and R. Taktak. A branch-and-cut algorithm for the multiple steiner TSP with order constraints. Electronic Notes in Discrete Mathematics, 41:487–494, 2013.
Huili Zhang, Weitian Tong, Yinfeng Xu, and Guohui Lin. The steiner traveling salesman problem with online advanced edge blockages. Computers & Operations Research, 70:26–38, 2016.
Adam N. Letchford, Saeideh D. Nasiri, and Dirk Oliver Theis. Compact formulations of the steiner traveling salesman problem and related problems. European Journal of Operational Research, 228(1):83–92, 2013.
Adam N. Letchford and Saeideh D. Nasiri. The steiner travelling salesman problem with correlated costs. European Journal of Operational Research, 245(1):62–69, 2015.
Juan-Jos´e Salazar-Gonz´alez. The steiner cycle polytope. European Journal of Operational Research, 147(3):671–679, 2003.

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Interian, Ruben; Ribeiro, Celso C. (15 July 2017). "A GRASP heuristic using path-relinking and restarts for the Steiner traveling salesman problem" . International Transactions in Operational Research. 24 (6): 1307–1323. doi:10.1111/itor.12419.

[2] Álvarez-Miranda, Eduardo; Sinnl, Markus (2019-09-05). "A note on computational aspects of the Steiner traveling salesman problem" . International Transactions in Operational Research. 26 (4): 1396–1401. doi:10.1111/itor.12592. S2CID 71717255.

[1]

[2]