Machine Learning and Monte Carlo Sampling for the Probabilistic Orienteering Problem

The Probabilistic Orienteering Problem is a stochastic optimization problem about the delivery or goods to customers. Only a subset of the customer can be served in the given time, so the problem consists in the selection of the customers providing more revenues and in the optimization of a truck tour to serve them. The presence of the customers is however stochastic, and this has to be taken into account while evaluating the objective function of each solution. Due to the high computational complexity of such an objective function, Monte Carlo sampling method is used to estimate it in a fast way. There is one crucial parameter in a Monte Carlo sampling evaluator which is the number of samples to be used. More samples mean high precision, less samples mean high speed. An instance-dependent trade-off has to be found. The topic of this paper is a Machine Learning-based method to estimate the best number of samples, given the characteristics of an instance. Two methods are presented and compared from an experimental point of view. In particular, it is shown that a less intuitive and slightly more complex method is able to provide more precise estimations.