The Probabilistic Orienteering Problem (POP) is a variant of the orienteering problem where customers are available with a certain probability. In a previous work, we approximated its objective function value by using a Monte Carlo Sampling method. A heuristic speed-up criterion is considered in the objective function evaluator. In this work we study systematically the impact of the heuristic speed-up criterion in terms of precision and speed on the Monte Carlo evaluator, as well as the performance of a POP solver we propose, based on the embedding of the Monte Carlo evaluator into a Random Restart Local Search metaheuristic algorithm.
Chou, X., Gambardella, L., Montemanni, R. (2019). A Metaheuristic Algorithm for the Probabilistic Orienteering Problem. In ACM International Conference Proceeding Series (pp.30-34). Association for Computing Machinery [10.1145/3366750.3366761].
A Metaheuristic Algorithm for the Probabilistic Orienteering Problem
Chou, X;
2019
Abstract
The Probabilistic Orienteering Problem (POP) is a variant of the orienteering problem where customers are available with a certain probability. In a previous work, we approximated its objective function value by using a Monte Carlo Sampling method. A heuristic speed-up criterion is considered in the objective function evaluator. In this work we study systematically the impact of the heuristic speed-up criterion in terms of precision and speed on the Monte Carlo evaluator, as well as the performance of a POP solver we propose, based on the embedding of the Monte Carlo evaluator into a Random Restart Local Search metaheuristic algorithm.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
