Home > Research > Publications & Outputs > The Steiner travelling salesman problem with co...

Research

Associated organisational units

Links

Text available via DOI:

Keywords

View graph of relations

The Steiner travelling salesman problem with correlated costs

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

The Steiner travelling salesman problem with correlated costs. / Letchford, Adam; Nasiri, Saeideh.
In: European Journal of Operational Research, Vol. 245, No. 1, 16.08.2015, p. 62–69.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Letchford, A & Nasiri, S 2015, 'The Steiner travelling salesman problem with correlated costs', European Journal of Operational Research, vol. 245, no. 1, pp. 62–69. https://doi.org/10.1016/j.ejor.2015.02.044

APA

Letchford, A., & Nasiri, S. (2015). The Steiner travelling salesman problem with correlated costs. European Journal of Operational Research, 245(1), 62–69. https://doi.org/10.1016/j.ejor.2015.02.044

Vancouver

Letchford A, Nasiri S. The Steiner travelling salesman problem with correlated costs. European Journal of Operational Research. 2015 Aug 16;245(1):62–69. Epub 2015 Feb 27. doi: 10.1016/j.ejor.2015.02.044

Author

Letchford, Adam ; Nasiri, Saeideh. / The Steiner travelling salesman problem with correlated costs. In: European Journal of Operational Research. 2015 ; Vol. 245, No. 1. pp. 62–69.

Bibtex

@article{e5253a99068443369422dfbd5e11e35b,
title = "The Steiner travelling salesman problem with correlated costs",
abstract = "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.",
keywords = "travelling salesman problem, mean-variance optimisation, mixed-integer nonlinear programming",
author = "Adam Letchford and Saeideh Nasiri",
year = "2015",
month = aug,
day = "16",
doi = "10.1016/j.ejor.2015.02.044",
language = "English",
volume = "245",
pages = "62–69",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier Science B.V.",
number = "1",

}

RIS

TY - JOUR

T1 - The Steiner travelling salesman problem with correlated costs

AU - Letchford, Adam

AU - Nasiri, Saeideh

PY - 2015/8/16

Y1 - 2015/8/16

N2 - 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.

AB - 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.

KW - travelling salesman problem

KW - mean-variance optimisation

KW - mixed-integer nonlinear programming

U2 - 10.1016/j.ejor.2015.02.044

DO - 10.1016/j.ejor.2015.02.044

M3 - Journal article

VL - 245

SP - 62

EP - 69

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -