New Steiner Travelling Salesman Problem Formulation and its multi-depot extension
Jessica Rodriguez-Pereira  1, *@  , Elena Fernández  2@  , Gilbert Laporte  1@  , Enrique Benavent  3@  , Antonio Martinez-Sykora  4@  
1 : HEC Montréal
3000 Chemin de la Côte-Sainte-Catherine, Montréal, QC H3T 2A7 -  Canada
2 : Technical University of Catalonia  (UPC)  -  Website
1-3 Jordi Girona Street 08034 Barcelona -  Spain
3 : Universidad de Valencia
4 : University of Southampton [Southampton]  -  Website
University Road Southampton SO17 1BJ -  United Kingdom
* : Corresponding author

The purpose of this work is to present a new compact formulation and efficient exact solution algorithm for the Steiner Traveling Salesman Problem (STSP) on an undirected network and its multi-depot extension. The STSP is an uncapacitated node-routing problem looking for a minimum-cost route that visits a known set of customers with service demand, placed at vertices of a given network, which is assumed to be uncomplete. The multi-depot extension, MDSTSP, studies the case when there are several depots and the allocations of customers has to be decided as well. 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.

Online user: 1 RSS Feed