The multi-path Traveling Salesman Problem with stochastic travel costs

Roberto Tadei (), Guido Perboli () and Francesca Perfetti ()
Additional contact information
Roberto Tadei: Politecnico di Torino
Guido Perboli: Politecnico di Torino
Francesca Perfetti: Politecnico di Torino

EURO Journal on Transportation and Logistics, 2017, vol. 6, issue 1, No 2, 3-23

Abstract: Abstract Given a set of nodes, where each pair of nodes is connected by several paths and each path shows a stochastic travel cost with unknown probability distribution, the multi-path Traveling Salesman Problem with stochastic travel costs aims at finding an expected minimum Hamiltonian tour connecting all nodes. Under a mild assumption on the unknown probability distribution, a deterministic approximation of the stochastic problem is given. The comparison of such approximation with a Monte Carlo simulation shows both the accuracy and the efficiency of the deterministic approximation, with a mean percentage gap around 2% and a reduction of the computational times of two orders of magnitude.

Keywords: TSP; Multiple paths; Stochastic travel costs; Deterministic approximation (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s13676-014-0056-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjtl:v:6:y:2017:i:1:d:10.1007_s13676-014-0056-2

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13676

DOI: 10.1007/s13676-014-0056-2

Access Statistics for this article

EURO Journal on Transportation and Logistics is currently edited by Michel Bierlaire

More articles in EURO Journal on Transportation and Logistics from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().