Publication Type

Journal Article

Version

publishedVersion

Publication Date

2-2018

Abstract

Orienteering Problems (OPs) are used to model many routing and trip planning problems. OPs are a variantof the well-known traveling salesman problem where the goal is to compute the highest reward path thatincludes a subset of vertices and has an overall travel time less than a specified deadline. However, the applicabilityof OPs is limited due to the assumption of deterministic and static travel times. To that end, Campbellet al. extended OPs to Stochastic OPs (SOPs) to represent uncertain travel times (Campbell et al. 2011). Inthis article, we make the following key contributions: (1) We extend SOPs to Dynamic SOPs (DSOPs), whichallow for time-dependent travel times; (2) we introduce a new objective criterion for SOPs and DSOPs torepresent a percentile measure of risk; (3) we provide non-linear optimization formulations along with theirlinear equivalents for solving the risk-sensitive SOPs and DSOPs; (4) we provide a local search mechanismfor solving the risk-sensitive SOPs and DSOPs; and (5) we provide results on existing benchmark problemsand a real-world theme park trip planning problem.

Keywords

Orienteering problems, risk-sensitive optimization, sample average approximation

Discipline

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

Research Areas

Intelligent Systems and Optimization

Publication

ACM Transactions on Intelligent Systems and Technology

Volume

9

Issue

3

First Page

24-1

Last Page

25

ISSN

2157-6904

Identifier

10.1145/3080575

Publisher

ACM

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1145/3080575

Download

Share

COinS