Risk-sensitive stochastic orienteering problems for trip optimization in urban environments - VARAKANTHAM, Pradeep (Institutional Knowledge at Singapore Management University, 2018)
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.