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.

Chou, X., Gambardella, L., Montemanni, R. (2018). Monte Carlo Sampling for the Probabilistic Orienteering Problem. In P. Daniele, L. Scrimali (a cura di), New Trends in Emerging Complex Real Life Problems ODS, Taormina, Italy, September 10–13, 2018 (pp. 169-177). Springer Nature [10.1007/978-3-030-00473-6_19].

Monte Carlo Sampling for the Probabilistic Orienteering Problem

Chou, Xiaochen;
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.
Capitolo o saggio
Heuristic algorithms; Monte Carlo Sampling; Probabilistic Orienteering Problem;
English
New Trends in Emerging Complex Real Life Problems ODS, Taormina, Italy, September 10–13, 2018
Daniele, P; Scrimali, L
30-dic-2018
2018
9783030004729
1
Springer Nature
169
177
Chou, X., Gambardella, L., Montemanni, R. (2018). Monte Carlo Sampling for the Probabilistic Orienteering Problem. In P. Daniele, L. Scrimali (a cura di), New Trends in Emerging Complex Real Life Problems ODS, Taormina, Italy, September 10–13, 2018 (pp. 169-177). Springer Nature [10.1007/978-3-030-00473-6_19].
none
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/10281/467083
Citazioni
  • Scopus 10
  • ???jsp.display-item.citation.isi??? ND
Social impact