Optimization Approaches for Solving Chance Constrained Stochastic Orienteering Problems
Conference Proceeding Article
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.
Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Decision Analytics
Algorithmic Decision Theory: Third International Conference, ADT 2013, Bruxelles, Belgium, November 12-14, 2013, Proceedings
City or Country
VARAKANTHAM, Pradeep Reddy; KUMAR, Akshat; and NG, Wee Keong.
Optimization Approaches for Solving Chance Constrained Stochastic Orienteering Problems. (2013). Algorithmic Decision Theory: Third International Conference, ADT 2013, Bruxelles, Belgium, November 12-14, 2013, Proceedings. 8176, 387-398. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1930