The Steiner Traveling Salesman Problem and its extensions

Jessica Rodríguez-Pereira; Elena Fernández; Gilbert Laporte; Enrique Benavent; Antonio Martínez-Sykora

doi:10.1016/j.ejor.2019.04.047

The Steiner Traveling Salesman Problem and its extensions

Jessica Rodríguez-Pereira, Elena Fernández, Gilbert Laporte, Enrique Benavent, Antonio Martínez-Sykora

Research output: Contribution to journal › Article › peer-review

Abstract

This paper considers the Steiner Traveling Salesman Problem, an extension of the classical Traveling Salesman Problem on an incomplete graph where not all vertices have demand. Some extensions including several depots or location decisions are introduced, modeled and solved. A compact integer linear programming formulation is proposed for each problem, where the routes are represented with two-index decision variables, and parity conditions are modeled using cocircuit inequalities. Exact branch-and-cut algorithms are developed for all formulations. Computational results obtained confirm the good performance of the algorithms. Instances with up to 500 vertices are solved optimally.

Original language	English
Pages (from-to)	615-628
Number of pages	14
Journal	European Journal of Operational Research
Volume	278
Issue number	2
DOIs	https://doi.org/10.1016/j.ejor.2019.04.047
Publication status	Published - 16 Oct 2019

Keywords

Branch-and-cut
Integer linear programming
Steiner Traveling Salesman Problem
Valid inequalities

ASJC Scopus subject areas

Computer Science(all)
Modelling and Simulation
Management Science and Operations Research
Information Systems and Management

Access to Document

10.1016/j.ejor.2019.04.047

Link to publication in Scopus

Fingerprint Dive into the research topics of 'The Steiner Traveling Salesman Problem and its extensions'. Together they form a unique fingerprint.

Cite this

@article{3d54bdbad4534debbe06629b27a6ee92,

title = "The Steiner Traveling Salesman Problem and its extensions",

abstract = "This paper considers the Steiner Traveling Salesman Problem, an extension of the classical Traveling Salesman Problem on an incomplete graph where not all vertices have demand. Some extensions including several depots or location decisions are introduced, modeled and solved. A compact integer linear programming formulation is proposed for each problem, where the routes are represented with two-index decision variables, and parity conditions are modeled using cocircuit inequalities. Exact branch-and-cut algorithms are developed for all formulations. Computational results obtained confirm the good performance of the algorithms. Instances with up to 500 vertices are solved optimally.",

keywords = "Branch-and-cut, Integer linear programming, Steiner Traveling Salesman Problem, Valid inequalities",

author = "Jessica Rodr{\'i}guez-Pereira and Elena Fern{\'a}ndez and Gilbert Laporte and Enrique Benavent and Antonio Mart{\'i}nez-Sykora",

year = "2019",

month = oct,

day = "16",

doi = "10.1016/j.ejor.2019.04.047",

language = "English",

volume = "278",

pages = "615--628",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - The Steiner Traveling Salesman Problem and its extensions

AU - Rodríguez-Pereira, Jessica

AU - Fernández, Elena

AU - Laporte, Gilbert

AU - Benavent, Enrique

AU - Martínez-Sykora, Antonio

PY - 2019/10/16

Y1 - 2019/10/16

N2 - This paper considers the Steiner Traveling Salesman Problem, an extension of the classical Traveling Salesman Problem on an incomplete graph where not all vertices have demand. Some extensions including several depots or location decisions are introduced, modeled and solved. A compact integer linear programming formulation is proposed for each problem, where the routes are represented with two-index decision variables, and parity conditions are modeled using cocircuit inequalities. Exact branch-and-cut algorithms are developed for all formulations. Computational results obtained confirm the good performance of the algorithms. Instances with up to 500 vertices are solved optimally.

AB - This paper considers the Steiner Traveling Salesman Problem, an extension of the classical Traveling Salesman Problem on an incomplete graph where not all vertices have demand. Some extensions including several depots or location decisions are introduced, modeled and solved. A compact integer linear programming formulation is proposed for each problem, where the routes are represented with two-index decision variables, and parity conditions are modeled using cocircuit inequalities. Exact branch-and-cut algorithms are developed for all formulations. Computational results obtained confirm the good performance of the algorithms. Instances with up to 500 vertices are solved optimally.

KW - Branch-and-cut

KW - Integer linear programming

KW - Steiner Traveling Salesman Problem

KW - Valid inequalities

UR - http://www.scopus.com/inward/record.url?scp=85065788588&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2019.04.047

DO - 10.1016/j.ejor.2019.04.047

M3 - Article

AN - SCOPUS:85065788588

VL - 278

SP - 615

EP - 628

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -