A Branch-and-Cut algorithm for the multiple Steiner TSP with order constraints

Raouia Taktak ()
Additional contact information
Raouia Taktak: Université de Sfax

Annals of Operations Research, 2025, vol. 351, issue 1, No 36, 993-1021

Abstract: Abstract This paper deals with a variant of the traveling salesman problem (TSP), called the multiple Steiner TSP with order constraints. This consists, given an undirected graph with nonnegative weights on the edges, and a set of salesmen such that with each salesman is associated a set of ordered terminals, in finding a minimum-cost subgraph containing for each salesman a tour going in order through its terminals. We propose an integer linear programming (ILP) formulation for the problem. We identify new families of valid inequalities and devise separation algorithms. Using this, we propose a Branch-and-Cut algorithm. The efficiency of our algorithm is shown through an extensive computational study.

Keywords: Steiner TSP; Order constraints; Integer linear programming; Valid inequality; Branch-and-Cut (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06003-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:351:y:2025:i:1:d:10.1007_s10479-024-06003-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06003-7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().