The orienteering problem with stochastic weights

In the Orienteering Problem (OP), a set of nodes is given, each with a profit. The goal is to determine a tour, limited in length, that visits a subset of nodes and maximizes the sum of the collected profits. In this paper, the Orienteering Problem with Stochastic Weights (OPSW) is used to reflect uncertainty in real-life applications. This problem is approached by the Two-Stage Orienteering Problem (TSOP). Hereby, the problem is formulated as a two-stage stochastic model with recourse for the OPSW where the capacity constraint is hard. An existing heuristic for this TSOP is described and tested on 29 problem instances. The computational results are presented in detail.