{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T16:56:11Z","timestamp":1776444971931,"version":"3.51.2"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,2,8]],"date-time":"2018-02-08T00:00:00Z","timestamp":1518048000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2018,5,31]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3080575","type":"journal-article","created":{"date-parts":[[2018,2,9]],"date-time":"2018-02-09T13:14:02Z","timestamp":1518182042000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Risk-Sensitive Stochastic Orienteering Problems for Trip Optimization in Urban Environments"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7342-5745","authenticated-orcid":false,"given":"Pradeep","family":"Varakantham","sequence":"first","affiliation":[{"name":"Singapore Management University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akshat","family":"Kumar","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hoong Chuin","family":"Lau","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William","family":"Yeoh","sequence":"additional","affiliation":[{"name":"New Mexico State University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,2,8]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","volume-title":"Constrained Markov Decision Processes","author":"Altman Eitan","DOI":"10.1201\/9781315140223"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.02.021"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10100-008-0080-0"},{"key":"e_1_2_2_4_1","first-page":"49","article-title":"The capacitated team orienteering and profitable tour problems","volume":"13","author":"Archetti C.","year":"2008","journal-title":"Journal of the Operational Research Society"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276919"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622591.1622597"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645464"},{"key":"e_1_2_2_8_1","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS). 1026--1032","author":"Boyan Justin","year":"2001"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-011-0895-2"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)00289-4"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1070.0457"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 1326--1331","author":"Dmitri"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.10.2.133"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2839345.2839350"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387915.2387917"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-014-9242-5"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.04.059"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 1522--1538","author":"Gupta Anupam"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/2296431"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS). 136--144","author":"Hou Ping","year":"2014"},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI). 143--148","author":"Huang Jinbo","year":"2006"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/07408170701592481"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90100-Q"},{"key":"e_1_2_2_25_1","volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI). 448--458","author":"Lau Hoong Chuin","year":"2012"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728487"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)90247-X"},{"key":"e_1_2_2_28_1","first-page":"249","article-title":"Research on team orienteering problem with dynamic travel times","volume":"7","author":"Li Jin","year":"2012","journal-title":"Journal of Software"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 1175--1180","author":"Li Lihong","year":"2005"},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS). 453--460","author":"Liu Yaxin","year":"2008"},{"key":"e_1_2_2_31_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 1049--1055","author":"Marecki Janusz","year":"2008"},{"key":"e_1_2_2_32_1","first-page":"77","article-title":"Portfolio selection","volume":"7","author":"Markowitz Harry","year":"1952","journal-title":"Journal of Finance"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.13.6.930"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/321043.321046"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.1.27"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-009-9523-6"},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI). 459--468","author":"Park James","year":"2003"},{"key":"e_1_2_2_38_1","unstructured":"Andras Prekopa. 2003. Probabilistic programming. In Stochastic Programming Andrzej Ruszczynski and Alexander Shapiro (Eds.). Elsevier.  Andras Prekopa. 2003. Probabilistic programming. In Stochastic Programming Andrzej Ruszczynski and Alexander Shapiro (Eds.). Elsevier."},{"key":"e_1_2_2_39_1","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"Puterman Martin"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.2.155"},{"key":"e_1_2_2_41_1","volume-title":"Artificial Intelligence: A Modern Approach","author":"Russell Stuart","year":"1995"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-009-0029-5"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2010.09.012"},{"key":"e_1_2_2_44_1","volume-title":"Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS). 393--401","author":"Smith David","year":"2004"},{"key":"e_1_2_2_45_1","volume-title":"Optimization for Machine Learning","author":"Sontag David"},{"key":"e_1_2_2_46_1","first-page":"1","article-title":"A genetic algorithm with an adaptive penalty function for the orienteering problem","volume":"4","author":"Tasgetiren M. Faith","year":"2001","journal-title":"Journal of Economic and Social Research"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1984.162"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2010.03.045"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41575-3_30"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000001"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02098284"},{"key":"e_1_2_2_52_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 1436--1442","author":"Weinstein Ari","year":"2013"},{"key":"e_1_2_2_53_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 411--417","author":"Yeoh William","year":"2013"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1006\/jmaa.1998.6015"},{"key":"e_1_2_2_55_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 1982--1989","author":"Yuan Changhe","year":"2009"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3080575","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3080575","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:58Z","timestamp":1750217818000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3080575"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,8]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,5,31]]}},"alternative-id":["10.1145\/3080575"],"URL":"https:\/\/doi.org\/10.1145\/3080575","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,8]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}