The probabilistic orienteering problem

The probabilistic orienteering problem (POP) is defined on a directed graph where a cost is associated with each arc and a prize is associated with each node. Moreover, each node will be available for visit only with a certain probability. A server starts from a fixed origin, has a given budget to visit a subset of nodes, and ends at a fixed destination. In a first stage, a node subset has to be selected and a corresponding a priori path has to be determined such that the server can visit all nodes in the subset and reach the destination without exceeding the budget. The list of available nodes in the subset is then revealed. In a second stage, the server follows the a priori path by skipping the absent nodes. The POP consists in determining a first-stage solution that maximizes the expected profit of the second-stage path, where the expected profit is the difference between the expected total prize and the expected total cost. We discuss the relevance of the problem and formulate it as a linear integer stochastic problem. We develop a branch-and-cut approach for the POP and several matheuristic methods, corresponding to different strategies to reduce the search space of the exact method. Extensive computational tests on instances with up to 100 nodes show the effectiveness of the exact method and the efficiency of the matheuristics in finding high quality solutions in a few minutes. Moreover, we provide an extended analysis on a subset of instances to show the value of explicitly modeling the stochastic information in the problem formulation