{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:09:37Z","timestamp":1765544977598,"version":"3.28.2"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>The availability of massive vehicle trajectory data enables the modeling of road-network constrained movement as travel-cost distributions rather than just single-valued costs, thereby capturing the inherent uncertainty of movement and enabling improved routing quality. Thus, stochastic routing has been studied extensively in the edge-centric model, where such costs are assigned to the edges in a graph representation of a road network. However, as this model still disregards important information in trajectories and fails to capture dependencies among cost distributions, a path-centric model, where costs are assigned to paths, has been proposed that captures dependencies better and provides an improved foundation for routing. Unfortunately, when applied in this model, existing routing algorithms are inefficient due to two shortcomings that we eliminate. First, when exploring candidate paths, existing algorithms only consider the costs of candidate paths from the source to intermediate vertices, while disregarding the costs of travel from the intermediate vertices to the destination, causing many noncompetitive paths to be explored. We propose two heuristics for estimating the cost from an intermediate vertex to the destination, thus improving routing efficiency. Second, the edge-centric model relies on stochastic dominance-based pruning to improve efficiency. This pruning assumes that costs are independent and is therefore inapplicable in the path-centric model that takes dependencies into account. We introduce a notion of virtual path that effectively enables stochastic dominance-based pruning in the path-based model, thus further improving efficiency. Empirical studies using two real-world trajectory sets offer insight into the properties of the proposed solution, indicating that it enables efficient stochastic routing in the path-centric model.<\/jats:p>","DOI":"10.14778\/3681954.3681971","type":"journal-article","created":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T16:23:36Z","timestamp":1725035016000},"page":"2893-2905","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Efficient Stochastic Routing in Path-Centric Uncertain Road Networks"],"prefix":"10.14778","volume":"17","author":[{"given":"Chenjuan","family":"Guo","sequence":"first","affiliation":[{"name":"East China Normal University"}]},{"given":"Ronghui","family":"Xu","sequence":"additional","affiliation":[{"name":"East China Normal University"}]},{"given":"Bin","family":"Yang","sequence":"additional","affiliation":[{"name":"East China Normal University"}]},{"given":"Ye","family":"Yuan","sequence":"additional","affiliation":[{"name":"Aalborg University"}]},{"given":"Tung","family":"Kieu","sequence":"additional","affiliation":[{"name":"Aalborg University"}]},{"given":"Yan","family":"Zhao","sequence":"additional","affiliation":[{"name":"Aalborg University"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aalborg University"}]}],"member":"320","published-online":{"date-parts":[[2024,8,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Georgi Andonov and Bin Yang. 2018. Stochastic Shortest Path Finding in Path-Centric Uncertain Road Networks. In MDM. 40--45.","DOI":"10.1109\/MDM.2018.00020"},{"key":"e_1_2_1_2_1","unstructured":"Russell Bent and Pascal Van Hentenryck. 2007. Waiting and Relocation Strategies in Online Stochastic Vehicle Routing. In IJCAI. 1816--1821."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494142"},{"key":"e_1_2_1_4_1","volume-title":"Path Cost Distribution Estimation Using Trajectory Data. PVLDB 10, 3","author":"Dai Jian","year":"2017","unstructured":"Jian Dai, Bin Yang, Chenjuan Guo, Christian S. Jensen, and Jilin Hu. 2017. Path Cost Distribution Estimation Using Trajectory Data. PVLDB 10, 3 (2017)."},{"key":"e_1_2_1_5_1","first-page":"96","article-title":"Speeding up Stochastic Dynamic Programming with Zero-delay Convolution","volume":"5","author":"Dean Brian C","year":"2010","unstructured":"Brian C Dean. 2010. Speeding up Stochastic Dynamic Programming with Zero-delay Convolution. Algorithmic Oper. Res. 5, 2 (2010), 96--104.","journal-title":"Algorithmic Oper. Res."},{"key":"e_1_2_1_6_1","volume-title":"Algorithm Design","author":"Goodrich Michael T","year":"2006","unstructured":"Michael T Goodrich and Roberto Tamassia. 2006. Algorithm Design: Foundation, Analysis and Internet Examples. John Wiley & Sons."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2694428.2694432"},{"key":"e_1_2_1_8_1","volume-title":"Jensen","author":"Guo Chenjuan","year":"2024","unstructured":"Chenjuan Guo, Ronghui Xu, Bin Yang, Ye Yuan, Tung Kieu, Yan Zhao, and Christian S. Jensen. 2024. Efficient Stochastic Routing in Path-Centric Uncertain Road Networks - Extended Version. arXiv:2407.06881 [cs.DS] https:\/\/arxiv.org\/abs\/2407.06881"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-014-0221-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Chenjuan Guo Bin Yang Ove Andersen Christian S. Jensen and Kristian Torp. 2015. EcoSky: Reducing vehicular environmental impact through eco-routing. In ICDE. 1412--1415.","DOI":"10.1109\/ICDE.2015.7113389"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00608-7"},{"key":"e_1_2_1_12_1","first-page":"179","article-title":"Risk-aware Path Selection with Time-varying","volume":"27","author":"Hu Jilin","year":"2018","unstructured":"Jilin Hu, Bin Yang, Chenjuan Guo, and Christian S. Jensen. 2018. Risk-aware Path Selection with Time-varying, Uncertain Travel Costs: A Time Series Approach. VLDB J. 27, 2 (2018), 179--200.","journal-title":"Uncertain Travel Costs: A Time Series Approach. VLDB J."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Ming Hua and Jian Pei. 2010. Probabilistic Path Queries in Road Networks: Traffic Uncertainty Aware Path Selection. In EDBT. 347--358.","DOI":"10.1145\/1739041.1739084"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002941"},{"key":"e_1_2_1_15_1","volume-title":"Jensen","author":"Kieu Tung","year":"2022","unstructured":"Tung Kieu, Bin Yang, Chenjuan Guo, Razvan-Gabriel Cirstea, Yan Zhao, Yale Song, and Christian S. Jensen. 2022. Anomaly Detection in Time Series with Robust Variational Quasi-Recurrent Autoencoders. In ICDE. 1342--1354."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Tung Kieu Bin Yang Chenjuan Guo Christian S. Jensen Yan Zhao Feiteng Huang and Kai Zheng. 2022. Robust and Explainable Autoencoders for Unsupervised Time Series Outlier Detection. In ICDE. 3038--3050.","DOI":"10.1109\/ICDE53745.2022.00273"},{"key":"e_1_2_1_17_1","unstructured":"Julia Letchner John Krumm and Eric Horvitz. 2006. Trip Router with Individualized Preferences (TRIP): Incorporating Personalization into Route Planning. In AAAI. 1795--1800."},{"key":"e_1_2_1_18_1","first-page":"11528","article-title":"Deep Reinforcement Learning for the Electric Vehicle Routing Problem With Time Windows","volume":"23","author":"Lin Bo","year":"2022","unstructured":"Bo Lin, Bissan Ghaddar, and Jatin Nathwani. 2022. Deep Reinforcement Learning for the Electric Vehicle Routing Problem With Time Windows. TITS 23, 8 (2022), 11528--11538.","journal-title":"TITS"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.113593"},{"key":"e_1_2_1_20_1","volume-title":"Jensen","author":"Ma Yu","year":"2014","unstructured":"Yu Ma, Bin Yang, and Christian S. Jensen. 2014. Enabling Time-Dependent Uncertain Eco-Weights For Road Networks. In GeoRich@SIGMOD. 1--6."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Paul Newson and John Krumm. 2009. Hidden Markov Map Matching through Noise and Sparseness. In SIGSPATIAL. 336--343.","DOI":"10.1145\/1653771.1653818"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1177\/0361198106196400121"},{"volume-title":"Tractable Pathfinding for the Stochastic On-time Arrival Problem","author":"Niknami Mehrdad","key":"e_1_2_1_23_1","unstructured":"Mehrdad Niknami and Samitha Samaranayake. 2016. Tractable Pathfinding for the Stochastic On-time Arrival Problem. In SEA. Springer, 231--245."},{"key":"e_1_2_1_24_1","volume-title":"Karger","author":"Nikolova Evdokia","year":"2006","unstructured":"Evdokia Nikolova, Matthew Brand, and David R. Karger. 2006. Optimal Route Planning under Uncertainty. In ICAPS. 131--141."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-022-03456-w"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397248"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00585-6"},{"key":"e_1_2_1_28_1","volume-title":"Jensen","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. 1910--1913."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617500"},{"key":"e_1_2_1_30_1","volume-title":"Bayen","author":"Sabran Guillaume","year":"2014","unstructured":"Guillaume Sabran, Samitha Samaranayake, and Alexandre M. Bayen. 2014. Precomputation Techniques for the Stochastic on Time Arrival Problem. In ALENEX 2014. 138--146."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342265"},{"key":"e_1_2_1_32_1","volume-title":"UAI1995","author":"Wellman Michael P.","year":"1995","unstructured":"Michael P. Wellman, Matthew Ford, and Kenneth Larson. 1995. Path Planning under Time-Dependent Uncertainty. In UAI1995. 532--539."},{"key":"e_1_2_1_33_1","first-page":"153","article-title":"PACE","volume":"27","author":"Yang Bin","year":"2018","unstructured":"Bin Yang, Jian Dai, Chenjuan Guo, Christian S. Jensen, and Jilin Hu. 2018. PACE: A PAth-CEntric Paradigm for Stochastic Path Finding. VLDB J. 27, 2 (2018), 153--178.","journal-title":"A PAth-CEntric Paradigm for Stochastic Path Finding. VLDB J."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536375"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","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--147.","DOI":"10.1109\/ICDE.2014.6816646"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.89"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","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--3292.","DOI":"10.24963\/ijcai.2021\/452"},{"key":"e_1_2_1_38_1","volume-title":"Jensen","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--2885."},{"key":"e_1_2_1_39_1","first-page":"3153","article-title":"Context-Aware Path Ranking in Road Networks","volume":"34","author":"Yang Sean Bin","year":"2022","unstructured":"Sean Bin Yang, Chenjuan Guo, and Bin Yang. 2022. Context-Aware Path Ranking in Road Networks. IEEE Trans. Knowl. Data Eng. 34, 7 (2022), 3153--3168.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_40_1","volume-title":"Jensen","author":"Yang Sean Bin","year":"2023","unstructured":"Sean Bin Yang, Jilin Hu, Chenjuan Guo, Bin Yang, and Christian S. Jensen. 2023. LightPath: Lightweight and Scalable Path Representation Learning. In KDD. 2999--3010."},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Sean Bin Yang and Bin Yang. 2020. Learning to Rank Paths in Spatial Networks. In ICDE. 2006--2009.","DOI":"10.1109\/ICDE48307.2020.00225"},{"key":"e_1_2_1_42_1","volume-title":"Ni","author":"Zheng Jiangchuan","year":"2013","unstructured":"Jiangchuan Zheng and Lionel M. Ni. 2013. Time-Dependent Trajectory Regression on Road Networks via Multi-Task Learning. In AAAI. 1048--1055."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3681954.3681971","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T15:13:06Z","timestamp":1732720386000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3681954.3681971"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":42,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.14778\/3681954.3681971"],"URL":"https:\/\/doi.org\/10.14778\/3681954.3681971","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"2024-08-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}