A Resolution Adaptive Algorithm for the Stochastic Orienteering Problem with Chance Constraints

Abstract

We study a stochastic version of the classic orienteering problem where the time to traverse an edge is a continuous random variable. For a given temporal deadline B, our solution produces a policy, i.e., a function that, based on the current position along a solution path and the elapsed time, decides whether to continue along the path or take a shortcut to avoid missing the deadline. The solution is based on a formulation using constrained Markov decision processes to ensure that the deadline is met with a preassigned confidence level. To expedite the computation, a Monte Carlo simulation on an open loop policy is run to determine how to adaptively discretize the temporal dimension and therefore reduce the number of states and the number of optimization variables in the associated linear program. Our results show that the adaptive algorithm matches the performance of the non-adaptive one while taking significantly less time.