Title

Optimization Approaches for Solving Chance Constrained Stochastic Orienteering Problems

Publication Type

Conference Proceeding Article

Publication Date

2013

Abstract

Orienteering problems (OPs) are typically used to model routing and trip planning problems. OP is a variant of the well known traveling salesman problem where the goal is to compute the highest reward path that includes a subset of nodes and has an overall travel time less than the specified deadline. Stochastic orienteering problems (SOPs) extend OPs to account for uncertain travel times and are significantly harder to solve than deterministic OPs. In this paper, we contribute a scalable mixed integer LP formulation for solving risk aware SOPs, which is a principled approximation of the underlying stochastic optimization problem. Empirically, our approach provides significantly better solution quality than the previous best approach over a range of synthetic benchmarks and on a real-world theme park trip planning problem.

Discipline

Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Decision Analytics

Publication

Algorithmic Decision Theory: Third International Conference, ADT 2013, Bruxelles, Belgium, November 12-14, 2013, Proceedings

Volume

8176

First Page

387

Last Page

398

ISBN

9783642415753

Identifier

10.1007/978-3-642-41575-3_30

Publisher

Springer Verlag

City or Country

Brussels, Belgium

Additional URL

http://dx.doi.org/10.1007/978-3-642-41575-3_30