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

19 Citations (SciVal)

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

Funding

This research was partially supported by the Spanish Ministry of Economy and Competitiveness through grants EEBB-I-16-10670, MTM2015-68097-P, and MTM2015-63779-R (MINECO/FEDER), and by the Canadian Natural Sciences and Engineering Research Council under the grant 2015-06189 . This support is gratefully acknowledged. Thanks are due to the referees for their valuable comments.

Keywords

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

ASJC Scopus subject areas

General Computer Science
Modelling and Simulation
Management Science and Operations Research
Information Systems and Management

Access to Document

10.1016/j.ejor.2019.04.047

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 B.V.",

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

SN - 0377-2217

VL - 278

SP - 615

EP - 628

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

The Steiner Traveling Salesman Problem and its extensions

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this