Orienteering Problems (OPs) are used to model many routing and trip planning problems. OPs are a variant of the well-known traveling salesman problem where the goal is to compute the highest reward path that includes a subset of vertices and has an overall travel time less than a specified deadline. However, the applicability of OPs is limited due to the assumption of deterministic and static travel times. To that end, Campbell et al. extended OPs to Stochastic OPs (SOPs) to represent uncertain travel times (Campbell et al. 2011). In this article, we make the following key contributions: (1) We extend SOPs to Dynamic SOPs (DSOPs), which allow for time-dependent travel times; (2) we introduce a new objective criterion for SOPs and DSOPs to represent a percentile measure of risk; (3) we provide non-linear optimization formulations along with their linear equivalents for solving the risk-sensitive SOPs and DSOPs; (4) we provide a local search mechanism for solving the risk-sensitive SOPs and DSOPs; and (5) we provide results on existing benchmark problems and a real-world theme park trip planning problem.
https://doi.org/10.1145/3080575Cite as:
@article{Varakantham_2018,
doi = {10.1145/3080575},
url = {https://doi.org/10.1145%2F3080575},
year = 2018,
month = {feb},
publisher = {Association for Computing Machinery ({ACM})},
volume = {9},
number = {3},
pages = {1--25},
author = {Pradeep Varakantham and Akshat Kumar and Hoong Chuin Lau and William Yeoh},
title = {Risk-Sensitive Stochastic Orienteering Problems for Trip Optimization in Urban Environments},
journal = {{ACM} Transactions on Intelligent Systems and Technology}
}