A Fast Algorithm for Stochastic Orienteering with Chance Constraints

Abstract

We consider the Stochastic Orienteering Problem with random traversal time for edges. In this scenario the length of the path is a random variable and we consider a formulation with chance constraints, i.e., a bound on the probability that the length of the path exceeds the allotted budget. Our proposed solution casts the problem as an instance of a suitably defined Constrained Markov Decision Process and uses a Lagrangian formulation to solve it. In particular, exploiting some structural properties of the associated decision process we can solve the Markov Decision Process using a Lagrangian approach and efficiently determine the optimal Lagrange multiplier. Our method is experimentally evaluated and demonstrated to be significantly faster than previous solutions using a linear programming approach to solve the Stochastic Orienteering Problem with chance constraints.