{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:13:19Z","timestamp":1755839599930,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T00:00:00Z","timestamp":1700438400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"RESPONSE"},{"name":"Interreg Baltic Sea Region","award":["R101"],"award-info":[{"award-number":["R101"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>Arriving at a destination within a specific time window is important in many transportation settings. For example, trucks may be penalized for early or late arrivals at compact terminals, and early and late arrivals at general practitioners, dentists, and so on, are also discouraged, in part due to COVID. We propose foundations for routing with arrival-window constraints. In a setting where the travel time of a road segment is modeled by a probability distribution, we define two problems where the aim is to find a route from a source to a destination that optimizes or yields a high probability of arriving within a time window while departing as late as possible. In this setting, a core challenge is to enable comparison between paths that may potentially be part of a result path with the goal of determining whether a path is uninteresting and can be disregarded given the existence of another path. We show that existing solutions cannot be applied in this problem setting and instead propose novel comparison methods. Additionally, we introduce the notion of Stochastic Arrival-Window Contraction Hierarchies that enable accelerated query processing in the article\u2019s setting. Next, we present routing algorithms that exploit the above comparison methods in combination with so-called pivot paths and contraction hierarchies to enable efficient processing of the two types of queries. Finally, a detailed experimental study provides empirical insights that justify the need for the two types of routing and also offers insight into key characteristics of the problem solutions.<\/jats:p>","DOI":"10.1145\/3617500","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T11:28:10Z","timestamp":1692962890000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Stochastic Routing with Arrival Windows"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8426-9119","authenticated-orcid":false,"given":"Simon Aagaard","family":"Pedersen","sequence":"first","affiliation":[{"name":"Aalborg University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1658-1079","authenticated-orcid":false,"given":"Bin","family":"Yang","sequence":"additional","affiliation":[{"name":"Aalborg University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9697-7670","authenticated-orcid":false,"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aalborg University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0008-6890","authenticated-orcid":false,"given":"Jesper","family":"M\u00f8ller","sequence":"additional","affiliation":[{"name":"Aalborg University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,11,20]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Philippine Ports Authority. 2018. Terminal appointment booking system (TABS). Retrieved from https:\/\/www.ppa.com.ph\/sites\/default\/files\/issuances_docs\/AO%20006-2018.pdf"},{"issue":"2","key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s10479-016-2150-3","article-title":"Managing customer arrivals with time windows: A case of truck arrivals at a congested container terminal","volume":"244","author":"Chen Gang","year":"2016","unstructured":"Gang Chen and Liping Jiang. 2016. Managing customer arrivals with time windows: A case of truck arrivals at a congested container terminal. Ann. Operat. Res. 244, 2 (2016), 349\u2013365.","journal-title":"Ann. Operat. Res."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00585-6"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2009.01.008"},{"key":"e_1_3_3_6_2","first-page":"319","volume-title":"WEA","author":"Geisberger Robert","year":"2008","unstructured":"Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In WEA. 319\u2013333."},{"key":"e_1_3_3_7_2","first-page":"1","article-title":"Minimum time-dependent travel times with contraction hierarchies","volume":"18","author":"Batz G. Veit","year":"2013","unstructured":"G. Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. 2013. Minimum time-dependent travel times with contraction hierarchies. J. Exp. Algor. 18 (2013), 1\u20131.","journal-title":"J. Exp. Algor."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2012.06.008"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.2011.136"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2602465"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3078847"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2019.106125"},{"key":"e_1_3_3_13_2","first-page":"569","volume-title":"ICDE","author":"Liu Huiping","year":"2018","unstructured":"Huiping Liu, Cheqing Jin, Bin Yang, and Aoying Zhou. 2018. Finding top-k optimal sequenced routes. In ICDE. 569\u2013580."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.03.061"},{"issue":"1","key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.ejor.2018.11.020","article-title":"Vehicle routing with arrival time diversification","volume":"275","author":"Hoogeboom Maaike","year":"2019","unstructured":"Maaike Hoogeboom and Wout Dullaert. 2019. Vehicle routing with arrival time diversification. Eur. J. Operat. Res. 275, 1 (2019), 93\u2013107.","journal-title":"Eur. J. Operat. Res."},{"key":"e_1_3_3_16_2","first-page":"136","volume-title":"ICDE","author":"Yang Bin","year":"2014","unstructured":"Bin Yang, Chenjuan Guo, Christian S. Jensen, Manohar Kaul, and Shuo Shang. 2014. Stochastic skyline route planning under time-varying uncertainty. In ICDE. 136\u2013147."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0494-9"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397248"},{"key":"e_1_3_3_19_2","first-page":"40","volume-title":"MDM","author":"Andonov Georgi","year":"2018","unstructured":"Georgi Andonov and Bin Yang. 2018. Stochastic shortest path finding in path-centric uncertain road networks. In MDM. 40\u201345."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-016-0272-z"},{"key":"e_1_3_3_21_2","first-page":"1417","volume-title":"ICDE","author":"Hu Jilin","year":"2020","unstructured":"Jilin Hu, Chenjuan Guo, Bin Yang, Christian S. Jensen, and Hui Xiong. 2020. Stochastic origin-destination matrix forecasting using dual-stage graph convolutional, recurrent neural networks. In ICDE. 1417\u20131428."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0378-1"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00608-7"},{"key":"e_1_3_3_24_2","first-page":"1073","volume-title":"ICDE","author":"Guo Chenjuan","year":"2018","unstructured":"Chenjuan Guo, Bin Yang, Jilin Hu, and Christian S. Jensen. 2018. Learning to route with sparse trajectory sets. In ICDE. 1073\u20131084."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0491-4"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021926"},{"key":"e_1_3_3_27_2","first-page":"2010","volume-title":"ICDE","author":"Pedersen Simon Aagaard","year":"2020","unstructured":"Simon Aagaard Pedersen, Bin Yang, and Christian S. Jensen. 2020. A hybrid learning approach to stochastic routing. In ICDE. 2010\u20132013."},{"key":"e_1_3_3_28_2","first-page":"2900","volume-title":"ICDE","author":"Cirstea Razvan-Gabriel","year":"2022","unstructured":"Razvan-Gabriel Cirstea, Bin Yang, Chenjuan Guo, Tung Kieu, and Shirui Pan. 2022. Towards spatio- temporal aware traffic time series forecasting. In ICDE. 2900\u20132913."},{"key":"e_1_3_3_29_2","first-page":"1739","volume-title":"ICDE","author":"Cirstea Razvan-Gabriel","year":"2021","unstructured":"Razvan-Gabriel Cirstea, Tung Kieu, Chenjuan Guo, Bin Yang, and Sinno Jialin Pan. 2021. EnhanceNet: Plugin neural networks for enhancing correlated time series forecasting. In ICDE. 1739\u20131750."},{"key":"e_1_3_3_30_2","first-page":"1994","volume-title":"IJCAI","author":"Cirstea Razvan-Gabriel","year":"2022","unstructured":"Razvan-Gabriel Cirstea, Chenjuan Guo, Bin Yang, Tung Kieu, Xuanyi Dong, and Shirui Pan. 2022. Triformer: Triangular, variable-specific attentions for long sequence multivariate time series forecasting. In IJCAI, Luc De Raedt (Ed.). 1994\u20132001."},{"issue":"4","key":"e_1_3_3_31_2","first-page":"971","article-title":"AutoCTS: Automated correlated time series forecasting","volume":"15","author":"Wu Xinle","year":"2022","unstructured":"Xinle Wu, Dalin Zhang, Chenjuan Guo, Chaoyang He, Bin Yang, and Christian S. Jensen. 2022. AutoCTS: Automated correlated time series forecasting. Proc. VLDB Endow. 15, 4 (2022), 971\u2013983.","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"e_1_3_3_32_2","first-page":"97:1\u201397:26","article-title":"AutoCTS+: Joint neural architecture and hyperparameter search for correlated time series forecasting","volume":"1","author":"Wu Xinle","year":"2023","unstructured":"Xinle Wu, Dalin Zhang, Miao Zhang, Chenjuan Guo, Bin Yang, and Christian S. Jensen. 2023. AutoCTS+: Joint neural architecture and hyperparameter search for correlated time series forecasting. Proc. ACM Manage. Data 1, 1 (2023), 97:1\u201397:26.","journal-title":"Proc. ACM Manage. Data"},{"key":"e_1_3_3_33_2","volume-title":"12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems","author":"Samaranayake Samitha","year":"2012","unstructured":"Samitha Samaranayake, Sebastien Blandin, and Alex Bayen. 2012. Speedup techniques for the stochastic on-time arrival problem. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_3_34_2","first-page":"136","volume-title":"ICDE","author":"Yang Bin","year":"2014","unstructured":"Bin Yang, Chenjuan Guo, Christian S. Jensen, Manohar Kaul, and Shuo Shang. 2014. Stochastic skyline route planning under time-varying uncertainty. In ICDE. 136\u2013147."},{"key":"e_1_3_3_35_2","first-page":"131","article-title":"Optimal route planning under uncertainty","author":"Nikolova Evdokia Velinova","year":"2006","unstructured":"Evdokia Velinova Nikolova, Matthew Brand, and David R. Karger. 2006. Optimal route planning under uncertainty. In ICAPS, 131\u2013141.","journal-title":"ICAPS"},{"key":"e_1_3_3_36_2","first-page":"532","volume-title":"UAI","author":"Wellman Michael P.","year":"1995","unstructured":"Michael P. Wellman, Matthew Ford, and Kenneth Larson. 1995. Path planning under time-dependent uncertainty. In UAI. 532\u2013539."},{"key":"e_1_3_3_37_2","first-page":"15:1\u201315:10","volume-title":"ACM SIGSPATIAL","author":"Aljubayrin Saad","year":"2016","unstructured":"Saad Aljubayrin, Bin Yang, Christian S. Jensen, and Rui Zhang. 2016. Finding non-dominated paths in uncertain road networks. In ACM SIGSPATIAL. 15:1\u201315:10."},{"key":"e_1_3_3_38_2","volume-title":"ICAPS","author":"Storandt Sabine","year":"2012","unstructured":"Sabine Storandt. 2012. Route planning for bicycles\u2013exact constrained shortest paths made practical via contraction hierarchy. In ICAPS."},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3362693"},{"key":"e_1_3_3_41_2","first-page":"3286","volume-title":"IJCAI","author":"Yang Sean Bin","year":"2021","unstructured":"Sean Bin Yang, Chenjuan Guo, Jilin Hu, Jian Tang, and Bin Yang. 2021. Unsupervised path representation learning with curriculum negative sampling. In IJCAI. 3286\u20133292."},{"key":"e_1_3_3_42_2","first-page":"2873","volume-title":"ICDE","author":"Yang Sean Bin","year":"2022","unstructured":"Sean Bin Yang, Chenjuan Guo, Jilin Hu, Bin Yang, Jian Tang, and Christian S. Jensen. 2022. Weakly-supervised temporal path representation learning with contrastive curriculum learning. In ICDE. 2873\u20132885."}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617500","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3617500","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:45:58Z","timestamp":1750178758000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617500"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,20]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3617500"],"URL":"https:\/\/doi.org\/10.1145\/3617500","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2023,11,20]]},"assertion":[{"value":"2021-12-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}