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

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.