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.
2013
40
7
1661
1670
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]
Weyland, Dennis; Montemanni, Roberto; Gambardella Luca, Maria
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1176202
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 16
social impact