{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T03:47:36Z","timestamp":1780544856952,"version":"3.54.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2021,12,16]],"date-time":"2021-12-16T00:00:00Z","timestamp":1639612800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61728204, 62172351"],"award-info":[{"award-number":["61728204, 62172351"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Key Laboratory of Safety-Critical Software Ministry of Industry and Information Technology","award":["NJ2018014"],"award-info":[{"award-number":["NJ2018014"]}]},{"name":"Fundamental Research"},{"name":"Ford Motor URP Funding"},{"name":"CCF-Huawei Database System Innovation Research Plan","award":["CCF-HUAWEI DBIR2020001A"],"award-info":[{"award-number":["CCF-HUAWEI DBIR2020001A"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>The problem of route planning on road network is essential to many Location-Based Services (LBSs). Road networks are dynamic in the sense that the weights of the edges in the corresponding graph constantly change over time, representing evolving traffic conditions. Thus, a practical route planning strategy is required to supply the continuous route optimization considering the historic, current, and future traffic condition. However, few existing works comprehensively take into account these various traffic conditions during the route planning. Moreover, the LBSs usually suffer from extensive concurrent route planning requests in rush hours, which imposes a pressing need to handle numerous queries in parallel for reducing the response time of each query. However, this issue is also not involved by most existing solutions. We therefore investigate a parallel traffic condition driven route planning model on a cluster of processors. To embed the future traffic condition into the route planning, we employ a GCN model to periodically predict the travel costs of roads within a specified time period, which facilitates the robustness of the route planning model against the varying traffic condition. To reduce the response time, a Dual-Level Path (DLP) index is proposed to support a parallel route planning algorithm with the filter-and-refine principle. The bottom level of DLP partitions the entire graph into different subgraphs, and the top level is a skeleton graph that consists of all border vertices in all subgraphs. The filter step identifies a global directional path for a given query based on the skeleton graph. In the refine step, the overall route planning for this query is decomposed into multiple sub-optimizations in the subgraphs passed through by the directional path. Since the subgraphs are independently maintained by different processors, the sub-optimizations of extensive queries can be operated in parallel. Finally, extensive evaluations are conducted to confirm the effectiveness and superiority of the proposal.<\/jats:p>","DOI":"10.1145\/3459099","type":"journal-article","created":{"date-parts":[[2021,12,16]],"date-time":"2021-12-16T17:05:53Z","timestamp":1639674353000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["PARP: A Parallel Traffic Condition Driven Route Planning Model on Dynamic Road Networks"],"prefix":"10.1145","volume":"12","author":[{"given":"Tianlun","family":"Dai","sequence":"first","affiliation":[{"name":"College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, Jiangsu, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bohan","family":"Li","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Key Laboratory of Safety-Critical Software, Ministry of Industry and Information Technology, and Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing, Jiangsu, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ziqiang","family":"Yu","sequence":"additional","affiliation":[{"name":"School of Computer and Control Engineering, Yantai University, Yantai, Shandong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiangrong","family":"Tong","sequence":"additional","affiliation":[{"name":"School of Computer and Control Engineering, Yantai University, Yantai, Shandong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meng","family":"Chen","sequence":"additional","affiliation":[{"name":"School of software, Shandong University, Jinan, Shandong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gang","family":"Chen","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, Jiangsu, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,12,16]]},"reference":[{"issue":"1","key":"e_1_3_1_2_2","first-page":"113","article-title":"Self-driving cars: A survey","volume":"165","author":"Badue Claudine","year":"2020","unstructured":"Claudine Badue, R\u00e2nik Guidolini, Raphael Vivacqua Carneiro, Pedro Azevedo, Vinicius Brito Cardoso, Avelino Forechi, Luan Jesus, Rodrigo Berriel, Thiago Meireles Paix\u00e3o, Filipe Mutz et al. 2020. Self-driving cars: A survey. Exp. Syst. Applic. 165, 1 (2020), 113\u2013816.","journal-title":"Exp. Syst. Applic."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1030.0062"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2020.06.065"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/2035253.2035263"},{"key":"e_1_3_1_6_2","unstructured":"DIMACS. 2006. 9th DIMACS Implementation Challenge - Shortest Paths. Retrieved from http:\/\/users.diag.uniroma1.it\/challenge9\/."},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3063386.3063767"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/3294771.3294869"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_3_1_10_2","article-title":"Dynamic discretization discovery algorithms for time-dependent shortest path problems","author":"He Edward","year":"2019","unstructured":"Edward He, N. Boland, G. Nemhauser, M. Savelsbergh, and H. Stewart. 2019. Dynamic discretization discovery algorithms for time-dependent shortest path problems. In Proceeding of CPAIOR 2018.","journal-title":"In Proceeding of CPAIOR 2018."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412239"},{"key":"e_1_3_1_12_2","volume-title":"Proceedings of the Conference on Learning Representations","author":"Kipf Thomas N.","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In Proceedings of the Conference on Learning Representations."},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVT.2019.2893173"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-020-00142-0"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2016.01.007"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767844"},{"key":"e_1_3_1_17_2","unstructured":"OpenStreetMap. 2021. OpenStreetMap. Retrieved from https:\/\/www.openstreetmap.org\/#map=10\/39.8342\/116.4957\/."},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377371"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2064959.2064965"},{"issue":"1","key":"e_1_3_1_20_2","first-page":"1","article-title":"ReFOCUS+: Multi-layers real-time intelligent route guidance system with congestion detection and avoidance","volume":"22","author":"Rezaei Mahboobe","year":"2019","unstructured":"Mahboobe Rezaei, Hamed Noori, Mohsen Mohammadkhani Razlighi, and Mohsen Nickray. 2019. ReFOCUS+: Multi-layers real-time intelligent route guidance system with congestion detection and avoidance. IEEE Trans. Intell. Transport. Syst. 22, 1 (2019), 1\u201314.","journal-title":"IEEE Trans. Intell. Transport. Syst."},{"issue":"1","key":"e_1_3_1_21_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1155\/2017\/5098183","article-title":"Electric vehicle routing problem with charging time and variable travel time","volume":"2017","author":"Shao Sai","year":"2017","unstructured":"Sai Shao, Wei Guan, Bin Ran, Zhengbing He, and Jun Bi. 2017. Electric vehicle routing problem with charging time and variable travel time. Math. Prob. Eng. 2017, 1 (2017), 1\u201313.","journal-title":"Math. Prob. Eng."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICC.2017.7996757"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-019-0093-9"},{"key":"e_1_3_1_24_2","article-title":"Multi-modal route planning in road and transit networks","volume":"1809","author":"Tischner Daniel","year":"2018","unstructured":"Daniel Tischner. 2018. Multi-modal route planning in road and transit networks. CoRR abs\/1809.05481 (2018).","journal-title":"CoRR"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236211"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733027"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3378889"},{"issue":"1","key":"e_1_3_1_28_2","article-title":"Deep learning for spatio-temporal data mining: A survey","volume":"1","author":"Wang S.","year":"2020","unstructured":"S. Wang, J. Cao, and P. Yu. 2020. Deep learning for spatio-temporal data mining: A survey. IEEE Trans. Knowl. Data Eng. 1, 1 (2020).","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3412054"},{"key":"e_1_3_1_30_2","first-page":"129","volume-title":"Proceedings of the International Conference on Machine Learning and Intelligent Communications","author":"Wu Siwei","year":"2016","unstructured":"Siwei Wu, Demin Li, Guanglin Zhang, Chang Guo, and Leilei Qi. 2016. Density-based dynamic revision path planning in urban area via VANET. In Proceedings of the International Conference on Machine Learning and Intelligent Communications. 129\u2013138."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29038-1_41"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-019-0095-7"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00098"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389735"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020462"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869807"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0457-6"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00089"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2703848"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377374"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2879819"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459099","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3459099","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:02Z","timestamp":1750193222000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459099"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,16]]},"references-count":40,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3459099"],"URL":"https:\/\/doi.org\/10.1145\/3459099","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,16]]},"assertion":[{"value":"2020-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}