The objective of the stochastic multi-path Traveling Salesman Problem is to determine the expected minimum-cost Hamiltonian tour in a network characterized by the presence of different paths between each pair of nodes, given that a random travel cost with an unknown probability distribution is associated with each of these paths. Previous works have proved that this problem can be deterministically approximated when the path travel costs are independent and identically distributed. Such an approximation has been demonstrated to be of acceptable quality in terms of the estimation of an optimal solution compared to consolidated approaches such as stochastic programming with recourse, completely overcoming the computational burden of solving enormous programs exacerbated by the number of scenarios considered. Nevertheless, the hypothesis regarding the independence among the path travel costs does not hold when considering real settings. It is well known, in fact, that traffic congestion influences travel costs and creates dependence among them. In this paper, we demonstrate that the independence assumption can be relaxed and a deterministic approximation of the stochastic multi-path Traveling Salesman Problem can be derived by assuming just asymptotically independent travel costs. We also demonstrate that this deterministic approximation has strong operational implications because it allows the consideration of realistic traffic models. Computational tests on extensive sets of random and realistic instances indicate the excellent efficiency and accuracy of the deterministic approximation.

The stochastic multi-path traveling salesman problem with dependent random travel costs / Fadda, Edoardo; Fotio Tiotsop, Lohic; Manerba, Daniele; Tadei, Roberto. - In: TRANSPORTATION SCIENCE. - ISSN 0041-1655. - 54:5(2020), pp. 1372-1387. [10.1287/trsc.2020.0996]

The stochastic multi-path traveling salesman problem with dependent random travel costs.

Fadda, Edoardo;Fotio Tiotsop, Lohic;Tadei, Roberto
2020

Abstract

The objective of the stochastic multi-path Traveling Salesman Problem is to determine the expected minimum-cost Hamiltonian tour in a network characterized by the presence of different paths between each pair of nodes, given that a random travel cost with an unknown probability distribution is associated with each of these paths. Previous works have proved that this problem can be deterministically approximated when the path travel costs are independent and identically distributed. Such an approximation has been demonstrated to be of acceptable quality in terms of the estimation of an optimal solution compared to consolidated approaches such as stochastic programming with recourse, completely overcoming the computational burden of solving enormous programs exacerbated by the number of scenarios considered. Nevertheless, the hypothesis regarding the independence among the path travel costs does not hold when considering real settings. It is well known, in fact, that traffic congestion influences travel costs and creates dependence among them. In this paper, we demonstrate that the independence assumption can be relaxed and a deterministic approximation of the stochastic multi-path Traveling Salesman Problem can be derived by assuming just asymptotically independent travel costs. We also demonstrate that this deterministic approximation has strong operational implications because it allows the consideration of realistic traffic models. Computational tests on extensive sets of random and realistic instances indicate the excellent efficiency and accuracy of the deterministic approximation.
File in questo prodotto:
File Dimensione Formato  
The_multi_path_Traveling_Salesman_Problem_with_stochastic_dependent_travel_costs-52.pdf

accesso aperto

Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: PUBBLICO - Tutti i diritti riservati
Dimensione 467.76 kB
Formato Adobe PDF
467.76 kB Adobe PDF Visualizza/Apri
trsc.2020.0996.pdf

non disponibili

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 858 kB
Formato Adobe PDF
858 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento 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/2840521