Optimization Approaches for Solving Chance Constrained Stochastic Orienteering Problems

• Main Authors: VARAKANTHAM, Pradeep, KUMAR, Akshat
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2013
• Subjects: Travel Time; Local Search; Travel Salesman Problem; Constraint Violation; Chance Constraint; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/1930; https://ink.library.smu.edu.sg/context/sis_research/article/2929/viewcontent/DSOPADT.pdf
• Institution: Singapore Management University

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.