Risk-sensitive stochastic orienteering problems for trip optimization in urban environments

• Main Authors: VARAKANTHAM, Pradeep, KUMAR, Akshat, LAU, Hoong Chuin, YEOH, William
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2018
• Subjects: Orienteering problems; risk-sensitive optimization; sample average approximation; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/3990; https://ink.library.smu.edu.sg/context/sis_research/article/4992/viewcontent/Risk_SensitiveStochasticOrienteeringProblems_2018_afv.pdf
• Institution: Singapore Management University

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.