Premium
A note on computational aspects of the Steiner traveling salesman problem
Author(s) -
ÁlvarezMiranda Eduardo,
Sinnl Markus
Publication year - 2019
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12592
Subject(s) - travelling salesman problem , mathematical optimization , solver , bottleneck traveling salesman problem , heuristic , integer programming , 2 opt , computer science , mathematics , greedy algorithm , steiner tree problem , graph , set (abstract data type) , theoretical computer science , programming language
The Steiner traveling salesman problem (StTSP) is a variant of the classical traveling salesman problem (TSP). In the StTSP, we are given a graph with edge distances, and a set of terminal nodes, which are a subset of all nodes. The goal is to find a minimum distance closed walk to visit each terminal node at least once. Two recent articles proposed solution approaches to the problem, namely, on the exact side, Letchford et al. proposed compact integer linear programming models, and on the heuristic side, Interian and Ribeiro proposed greedy randomized adaptive search procedure, enhanced with a local search. Using the exact approach, instances with up to 250 nodes could be solved to optimality, with runtimes up to 1400 seconds, and the heuristic approach was used to tackle instances with up to 3353 nodes, with runtimes up to 8500 seconds. In this note, we show that by transforming the problem to the classical TSP, and using a state‐of‐the‐art TSP solver, all instances from the literature can be solved to optimality within 20 seconds, most of them within a second. We provide optimal solution values for 14 instances, where the optimal solution was not known.