A layered compact formulation for the Multiple Steiner TSP with Order constraints

In this paper we study a network design problem that consists in finding a minimum weight subgraph containing solutions for multiple Steiner Traveling Salesman Problems with Order constraints. We propose a layered compact ILP formulation for the problem. Experimental results show that it is reasonably effective and can solve to optimality medium-sized instances. Lage-scale instances are more difficult, and does not reach optimal solutions within a time limit of 3 hours. In order to improve our formulation, we investigate valid inequalities efficiency using a column-generation-based approach.