Hybrid sampling-based evaluators for the orienteering problem with stochastic travel and service times

Stochastic Combinatorial Optimization Problems (SCOPs) are many times used to model more accurately realistic situations. However, the stochasticity introduced also perplexes the computation of the objective function making it either difficult to solve or in our case very time-consuming. In this paper, we present different techniques of evaluating the objective function of the Orienteering Problem with Stochastic Travel and Service Times, that combine analytical, sampling and deterministic parts. We then compare these methods experimentally on well-known datasets.