A note on computational aspects of the Steiner traveling salesman problem

• Date: 01 July 2019
• Author: Markus Sinnl,Eduardo Álvarez‐Miranda
• DOI: http://doi.org/10.1111/itor.12592
• Published date: 01 July 2019

Intl. Trans. in Op. Res. 26 (2019) 1396–1401

DOI: 10.1111/itor.12592

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A note on computational aspects of the Steiner traveling

salesman problem

Eduardo ´

Alvarez-Mirandaaand Markus Sinnlb

aDepartment of Industrial Engineering, Universidad de Talca, Merced 437, 334000 Curic´

o, Chile

bFaculty of Business, Economics and Statistics, Department of Statistics and Operations Research,

University of Vienna, Oskar-Morgenstern-Platz1, 1090 Vienna, Austria

E-mail: ealvarez@utalca.cl [ ´

Alvarez-Miranda]; markus.sinnl@univie.ac.at [Sinnl]

Received 11 June2018; received in revised form 15 August 2018; accepted 20 August 2018

Abstract

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.

Keywords:traveling salesman problem; Steiner tree problem; computational study;problem transformation

1. Introduction and methodology

The traveling salesman problem (TSP) is one of the most prominent problems in combinatorial

optimization, and in mathematical optimization in general. The TSP and its variants have many

application areas, for example, routing problems in logistics and transportation contexts. Given a

set of nodes and distances between them, the undirected version of the TSP consists of finding a

minimum distance tour that visits each node (which might represent a final client, a retailer, or a

city) exactly once and returns to the first node. Mathematically, the TSP can be defined as follows:

given a graph G=G(V,E), and an edge distance function c:E→R|E|

≥0, find a minimum total

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.