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 journalArticlepeer-review

17 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 languageEnglish
Pages (from-to)615-628
Number of pages14
JournalEuropean Journal of Operational Research
Volume278
Issue number2
DOIs
Publication statusPublished - 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

Fingerprint

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

Cite this