Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

11-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.

Keywords

Travel Time, Local Search, Travel Salesman Problem, Constraint Violation, Chance Constraint

Discipline

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

Research Areas

Intelligent Systems and Optimization

Publication

Algorithmic Decision Theory: Third International Conference, ADT 2013, Bruxelles, Belgium, November 12-14, 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

Cham

Additional URL

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

Download

Share

COinS