A GRASP heuristic using path‐relinking and restarts for the Steiner traveling salesman problem

• Date: 01 November 2017
• Author: Ruben Interian,Celso C. Ribeiro
• Published date: 01 November 2017
• DOI: http://doi.org/10.1111/itor.12419

Intl. Trans. in Op. Res. 24 (2017) 1307–1323

DOI: 10.1111/itor.12419

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A GRASP heuristic using path-relinking and restarts for the

Steiner traveling salesman problem

Ruben Interian and Celso C. Ribeiro

Institute of Computing, Universidade Federal Fluminense, Niter´

oi, RJ 24210-346, Brazil

E-mail: rinterian@ic.uff.br [Interian]; celso@ic.uff.br [Ribeiro]

Received 31 July2016; received in revised form 31 December 2016; accepted 28 February 2017

Abstract

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 constructiveheuristics 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.

Keywords:Steiner traveling salesman problem; travelingsalesman problem; GRASP; path-relinking; restarts

1. Introduction

The traveling salesman problem (TSP) is one of the fundamental combinatorial optimization prob-

lems (Garey and Johnson, 1979; Zhang et al., 2015) and has numerous real-life applications in

transportation, logistics, vehicle routing, genome sequencing, and other areas. In its undirected

version it consists in, given a set of nodes and the distances between them, find the shortest route

that visits each node exactly once and returns to the first city. Mathematically, the TSP can be

defined as follows (Cornu´

ejols et al., 1985). Given a graph G=(V,E)and a function w:E→R

that associates a weight w(e)to each edge e∈E, the goal is to find a Hamiltonian cycle of minimum

total weight (or cost). The TSP is NP-hard, since its decision version is proven to be NP-complete

by a simple reduction from the Hamiltonian cycle problem (Garey and Johnson, 1979).

However, in many practical applications it is more frequent to find the following variant of the

TSP. A set VR⊆Vof required nodes is given. Instead of searching for a Hamiltonian cycle visiting

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies

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

USA.

1308 R. Interian and C.C. Ribeiro / Intl. Trans. in Op. Res. 24 (2017) 1307–1323

Fig. 1. Instance of Steiner TSP with nine nodes: the six required nodes are darkened.

all nodes, a minimum-weight closed walk is requested that visits only the required nodes. Since

only a walk is sought, nodes can be visited more than once and edges may be traversed more than

once. The so-called Steiner TSP (STSP, for short) was first proposed in Cornu´

ejols et al. (1985) and

Fleischmann (1985), where its NP-hardness is also proved. The Steiner TSP is specially suitable to

model network design (Borne et al., 2013), package delivery (Zhang et al., 2015, 2016), and routing

(Letchford et al., 2013) problems. All of them are typically modeled using sparse graphs. Figure 1

illustrates an instance of the Steiner TSP with nine nodes, six of which are required.

Most studies on the Steiner TSP focus on integer programming formulations and valid inequal-

ities. The STSP is solved efficiently (in linear time) for series-parallel graphs in Cornu´

ejols et al.

(1985). Compact, polynomial size integer programming formulations of the TSP are extended to

the STSP in Letchford et al. (2013). An extension of the Steiner TSP that adds penalties to the

nodes not visited by the cycle is proposed in Salazar-Gonz´

alez (2003). A network design problem

consisting of multiple Steiner TSPs with order constraints is studied in Borne et al. (2013), using an

integer linear programming formulation and a branch-and-cut algorithm. An extension of the STSP

in which the edge traversal costs are stochastic and correlated is studied in Letchford and Nasiri

(2015). An online algorithm is proposed in Zhang et al. (2015, 2016) to solve another extension of

the STSP considering real-time edge blockages.

This paper is organized as follows. In the next section, adaptive greedy constructive heuristics

for the Steiner TSP are presented. Section 3 reports local search strategies that are explored by

the GRASP with path-relinking heuristic presented in Section 4. Computational experiments are

reported in Section 5 and extended in Section 6, where an improved strategy exploring periodical

restarts is developed. In addition, ten large test instances are generated and their best-known

solutions are made available for download and benchmarking purposes in Section 7. Concluding

remarks are drawn in the last section.

2. Greedy algorithms for the Steiner TSP

The following strategy can be applied as a heuristic for the Steiner TSP (Letchford et al., 2013).

First, the instance of the STSP is reduced to a TSP instance in a complete graph defined by the

set of required nodes, in which the new distances correspond to the shortest paths between every

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies