A Dynamic Programming Approach to the Orienteering Problem with Deterministic-Stochastic Weights

In this paper a new variant of the Orienteering Problem with StochasticWeights (OPSW) is introduced: the Orienteering Problem with Deterministic-Stochastic Weights (OPDSW), where the weights on the arcs are a mix of a deterministic weight plus a non-negative stochastic weight. The problem is solved exactly using a Dynamic Programming (DP) approach and multiple state pruning algorithms are proposed with the goal of making the DP algorithm more efficient. Specific combinations of these algorithms are tested in a case study with a dataset of 30 nodes. The pruning algorithms have a substantial positive effect on the runtime of the DP algorithm, while the optimal tour remains mostly unchanged. The combination of using the End-Of-Tour method plus the relaxed Completion Bound method (a pruning method that is unique for the OPDSW) results in the biggest reduction of the runtime. This reduction increases even further if an initial solution is used and if the relaxed Completion Bound algorithm is only applied on specific states, which are determined by some decision rule.