The Probabilistic Orienteering Problem is a variant of the orienteering problem where customers are available with a certain probability. Given a solution, the calculation of the objective function value is complex since there is no linear expression for the expected total cost. In this work we approximate the objective function value with a Monte Carlo Sampling technique and present a computational study about precision and speed of such a method. We show that the evaluation based on Monte Carlo Sampling is fast and suitable to be used inside heuristic solvers. Monte Carlo Sampling is also used as a decisional tool to heuristically understand how many of the customers of a tour can be effectively visited before the given deadline is incurred.

Monte Carlo Sampling for the Probabilistic Orienteering Problem / Chou, Xiaochen; Gambardella Luca, Maria; Montemanni, Roberto. - 1:(2018), pp. 169-177. (Intervento presentato al convegno ODS 2018 tenutosi a Taormina, Italy nel September 2018) [10.1007/978-3-030-00473-6_19].

Monte Carlo Sampling for the Probabilistic Orienteering Problem

Montemanni Roberto
2018

Abstract

The Probabilistic Orienteering Problem is a variant of the orienteering problem where customers are available with a certain probability. Given a solution, the calculation of the objective function value is complex since there is no linear expression for the expected total cost. In this work we approximate the objective function value with a Monte Carlo Sampling technique and present a computational study about precision and speed of such a method. We show that the evaluation based on Monte Carlo Sampling is fast and suitable to be used inside heuristic solvers. Monte Carlo Sampling is also used as a decisional tool to heuristically understand how many of the customers of a tour can be effectively visited before the given deadline is incurred.
2018
ODS 2018
Taormina, Italy
September 2018
1
169
177
Chou, Xiaochen; Gambardella Luca, Maria; Montemanni, Roberto
Monte Carlo Sampling for the Probabilistic Orienteering Problem / Chou, Xiaochen; Gambardella Luca, Maria; Montemanni, Roberto. - 1:(2018), pp. 169-177. (Intervento presentato al convegno ODS 2018 tenutosi a Taormina, Italy nel September 2018) [10.1007/978-3-030-00473-6_19].
File in questo prodotto:
File Dimensione Formato  
Chou2018_Chapter_MonteCarloSamplingForTheProbab.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 482.03 kB
Formato Adobe PDF
482.03 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
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/1176625
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? ND
social impact