Program > By author > Vindigni Michele

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; each node will be available for visit only with a certain probability. A server starts from a fixed origin, visits a subset of nodes, and ends at a fixed destination. In a first stage, a node subset is selected and a corresponding a priori path is determined such that the server can visit all nodes in the subset and reach the destination without exceeding a time limit. In a second stage, after the list of available nodes is revealed, 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, i.e., 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 modelling the stochastic information in the problem formulation.