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.

The multi-path Traveling Salesman Problem with stochastic travel costs / Tadei, R.; Perboli, G.; Perfetti, F.. - In: EURO JOURNAL ON TRANSPORTATION AND LOGISTIC. - ISSN 2192-4376. - STAMPA. - 6:1(2017), pp. 3-23. [10.1007/s13676-014-0056-2]

The multi-path Traveling Salesman Problem with stochastic travel costs

Tadei R.;Perboli G.;Perfetti F.
2017

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.
File in questo prodotto:
File Dimensione Formato  
2017-EJTR-The multi-path Traveling Salesman Problem uncertainty.pdf

accesso aperto

Descrizione: Final version of the paper
Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Creative commons
Dimensione 757.31 kB
Formato Adobe PDF
757.31 kB Adobe PDF Visualizza/Apri
mpTSP.pdf

Riservato

Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: PUBBLICO - Tutti i diritti riservati
Dimensione 529.47 kB
Formato Adobe PDF
529.47 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2859024