Home > Research > Publications & Outputs > The Steiner travelling salesman problem with co...
View graph of relations

The Steiner travelling salesman problem with correlated costs

Research output: Contribution to Journal/MagazineJournal articlepeer-review

<mark>Journal publication date</mark>16/08/2015
<mark>Journal</mark>European Journal of Operational Research
Issue number1
Number of pages8
Pages (from-to)62–69
Publication StatusPublished
Early online date27/02/15
<mark>Original language</mark>English


The Steiner Travelling Salesman Problem (STSP) is a variant of the TSP that is suitable for instances defined on road networks. We consider an extension of the STSP in which the road traversal costs are both stochastic and correlated. This happens, for example, when vehicles are prone to delays due to rush hours, road works or accidents. Following the work of Markowitz on portfolio selection, we model this problem as a bi-objective mean-variance problem. Then, we show how to approximate the efficient frontier via integer programming. We also show how to exploit certain special structures in the correlation matrices. Computational results indicate that our approach is viable for instances with up to 100 nodes. It turns out that minimum variance tours can look rather different from minimum expected cost tours.