Premium
A GRASP heuristic using path‐relinking and restarts for the Steiner traveling salesman problem
Author(s) -
Interian Ruben,
Ribeiro Celso C.
Publication year - 2017
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.12419
Subject(s) - travelling salesman problem , grasp , heuristics , mathematical optimization , heuristic , traveling purchaser problem , computer science , shortest path problem , path (computing) , constructive , combinatorial optimization , node (physics) , 2 opt , mathematics , set (abstract data type) , polyhedron , theoretical computer science , combinatorics , graph , structural engineering , process (computing) , engineering , programming language , operating system
The traveling salesman problem (TSP) is one of the most studied problems in combinatorial optimization. Given a set of nodes and the distances between them, it consists in finding the shortest route that visits each node exactly once and returns to the first. Nevertheless, more flexible and applicable formulations of this problem exist and can be considered. The Steiner TSP (STSP) is a variant of the TSP that assumes that only a given subset of nodes must be visited by the shortest route, eventually visiting some nodes and edges more than once. In this paper, we adapt some classical TSP constructive heuristics and neighborhood structures to the STSP variant. In particular, we propose a reduced 2‐opt neighborhood and we show that it leads to better results in smaller computation times. Computational results with an implementation of a GRASP heuristic using path‐relinking and restarts are reported. In addition, ten large test instances are generated. All instances and their best‐known solutions are made available for download and benchmarking purposes.