The Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) is a Stochastic Vehicle Routing Problem with a computationally demanding objective function. In this work we propose an approximation for that objective function based on Monte Carlo Sampling and using the novel approach of quasi-parallel evaluation of samples. We perform comprehensive computational studies that reveal the efficiency of this approximation. Additionally, we examine different Local Search Algorithms and present a Random Restart Local Search Algorithm for solving the PTSPD together with an extensive computational study on a large set of benchmark instances.
Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling / Weyland, Dennis; Montemanni, Roberto; Gambardella Luca, Maria. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 40:7(2013), pp. 1661-1670. [10.1016/j.cor.2012.12.015]
Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling
Montemanni Roberto;
2013
Abstract
The Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) is a Stochastic Vehicle Routing Problem with a computationally demanding objective function. In this work we propose an approximation for that objective function based on Monte Carlo Sampling and using the novel approach of quasi-parallel evaluation of samples. We perform comprehensive computational studies that reveal the efficiency of this approximation. Additionally, we examine different Local Search Algorithms and present a Random Restart Local Search Algorithm for solving the PTSPD together with an extensive computational study on a large set of benchmark instances.Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris