Comparison of Objective Function Evaluators for a Stochastic Orienteering Problem

The Orienteering Problem is a combinatorial optimization problem where a set of potential customers, each one with an associated profit, is given together with a deadline. The target is to select the customers to be visited in the available time, maximizing the profit of the visited customers. In this paper we consider a variant of the problem where travel and service times are affected by uncertainty, and are expressed through probabilities. For such a problem, the computational bottleneck is the calculation of the objective function value associated with each solution. In this paper we show how hybrid sampling-based objective functions evaluators can be effectively embedded into a state-of-the-art metaheuristic algorithm (a Variable Neighborhood Search method). Our conclusions are supported by extensive experimental results.