Given a graph G = (N, E), N representing the set of nodes associated with Normally distributed random profits and E representing the set of edges with associated travel times, we define the Orienteering Problem with Stochastic Profits (OPSP) as the problem of finding a tour that visits a subset of N within a prespecified time limit and maximizes the probability of collecting more than a prespecified target profit level. We develop an exact solution scheme based on a parametric formulation of the problem and present a bi-objective genetic algorithm. We also analyze the characteristics of the problem and test the algorithms computationally. The experimental results identify conditions under which the OPSP results in significant improvements in reaching the target profit when compared with the solution from the deterministic variant of the problem.
