{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:54:05Z","timestamp":1792072445479,"version":"4.4.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T00:00:00Z","timestamp":1607299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["III-1526499, III-1763325, III-1909323, CNS-1930941"],"award-info":[{"award-number":["III-1526499, III-1763325, III-1909323, CNS-1930941"]}]},{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology Taiwan","doi-asserted-by":"crossref","award":["109-2218-E-009-014, 109-2218-E-009-014"],"award-info":[{"award-number":["109-2218-E-009-014, 109-2218-E-009-014"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,2,28]]},"abstract":"<jats:p>\n            Route planning satisfied multiple requests is an emerging branch in the route planning field and has attracted significant attention from the research community in recent years. The prevailing studies focus only on seeking a route by minimizing a single kind of Travel Cost, such as trip time or distance, among others. In reality, most users would like to choose an appropriate route, neither fastest nor shortest route. Usually, a user may have multiple requirements, and an appropriate route would satisfy all requirements requested by the user. In fact, planning an appropriate route could be formulated as a problem of\n            <jats:italic>Multi-weight Multi-destination Route Planning with Deadlines Constraints<\/jats:italic>\n            (MWMDRP-DC). In this article, we propose a framework, namely, MWMD-Router, which addresses the MWMDRP-DC problem comprehensively. To consider the travel costs with time-variation, we propose not only four novel dynamic graph miner to extract travel costs that reveal users\u2019 requirements but also two new algorithms, namely,\n            <jats:italic>Basic MWMD Route Planning<\/jats:italic>\n            and\n            <jats:italic>Advanced MWMD Route Planning<\/jats:italic>\n            , to plan a route that satisfies deadline requirements and optimizes another criterion like travel cost with time-variation efficiently. To the best of our knowledge, this is the first work on route planning that considers handling multiple deadlines for multi-destination planning as well as optimizing multiple travel costs with time-variation simultaneously. Experimental results demonstrate that our proposed algorithms deliver excellent performance with respect to efficiency and effectiveness.\n          <\/jats:p>","DOI":"10.1145\/3412363","type":"journal-article","created":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T19:04:16Z","timestamp":1607367856000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Dynamic Graph Mining for Multi-weight Multi-destination Route Planning with Deadlines Constraints"],"prefix":"10.1145","volume":"15","author":[{"given":"Yu","family":"Huang","sequence":"first","affiliation":[{"name":"National Chiao Tung University, Hsinchu, Taiwan, ROC"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Josh Jia-Ching","family":"Ying","sequence":"additional","affiliation":[{"name":"National Chung Hsing University, Taichung, Taiwan, ROC"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philip S.","family":"Yu","sequence":"additional","affiliation":[{"name":"University of Illinois at Chicago, Chicago, Illinois"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vincent S.","family":"Tseng","sequence":"additional","affiliation":[{"name":"National Chiao Tung University, Hsinchu, Taiwan, ROC"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,12,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2013.50"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/IVS.2012.6232304"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90008-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007385"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITSC.2014.6957876"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 16th IEEE International Conference on Mobile Data Management.","volume":"1","author":"Ceikute Vaida","unstructured":"Vaida Ceikute and Christian S. Jensen . 2015. Vehicle routing with user-generated trajectory data . In Proceedings of the 16th IEEE International Conference on Mobile Data Management. Vol. 1 . IEEE, 14--23. Vaida Ceikute and Christian S. Jensen. 2015. Vehicle routing with user-generated trajectory data. In Proceedings of the 16th IEEE International Conference on Mobile Data Management. Vol. 1. IEEE, 14--23."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2006.91"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/EIT.2017.8053395"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934328.2934338"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835918"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360774.3360824"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/MPRV.2008.80"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPACIAL\u201916)","author":"Hoang Minh X.","unstructured":"Minh X. Hoang , Yu Zheng , and Ambuj K. Singh . 2016. FCCF: Forecasting citywide crowd flows based on big data . In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPACIAL\u201916) . Association for Computing Machinery, New York, NY, Article 6, 10 pages. DOI:https:\/\/doi.org\/10.1145\/2996913.2996934 10.1145\/2996913.2996934 Minh X. Hoang, Yu Zheng, and Ambuj K. Singh. 2016. FCCF: Forecasting citywide crowd flows based on big data. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPACIAL\u201916). Association for Computing Machinery, New York, NY, Article 6, 10 pages. DOI:https:\/\/doi.org\/10.1145\/2996913.2996934"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739084"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 18th IEEE International Conference on Mobile Data Management. IEEE, 228--233","author":"Huang Yu","unstructured":"Yu Huang , Bo-Hau Lin , and Vincent S. Tseng . 2017. Efficient multi-destinations route planning with deadlines and cost constraints . In Proceedings of the 18th IEEE International Conference on Mobile Data Management. IEEE, 228--233 . Yu Huang, Bo-Hau Lin, and Vincent S. Tseng. 2017. Efficient multi-destinations route planning with deadlines and cost constraints. In Proceedings of the 18th IEEE International Conference on Mobile Data Management. IEEE, 228--233."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2015.1462"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.021136"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.71"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447845"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_16"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jclepro.2018.09.051"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989734.1989741"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3277868.3277870"},{"key":"e_1_2_1_25_1","first-page":"45","article-title":"Traffic flow theory","volume":"62","author":"Lieu Henry","year":"1999","unstructured":"Henry Lieu , N. Gartner , C. J. Messer , and A. K. Rathi . 1999 . Traffic flow theory . Public Roads 62 (1999), 45 -- 47 . Henry Lieu, N. Gartner, C. J. Messer, and A. K. Rathi. 1999. Traffic flow theory. Public Roads 62 (1999), 45--47.","journal-title":"Public Roads"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"e_1_2_1_27_1","volume-title":"Modeling crash-flow-density and crash-flow-V\/C ratio relationships for rural and urban freeway segments. Accident Analysis 8 Prevention 37, 1","author":"Lord Dominique","year":"2005","unstructured":"Dominique Lord , Abdelaziz Manar , and Anna Vizioli . 2005. Modeling crash-flow-density and crash-flow-V\/C ratio relationships for rural and urban freeway segments. Accident Analysis 8 Prevention 37, 1 ( 2005 ), 185--199. Dominique Lord, Abdelaziz Manar, and Anna Vizioli. 2005. Modeling crash-flow-density and crash-flow-V\/C ratio relationships for rural and urban freeway segments. Accident Analysis 8 Prevention 37, 1 (2005), 185--199."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 14th International Conference on Mobile Data Management.","volume":"1","author":"Hsueh-Chan Lu Eric","unstructured":"Eric Hsueh-Chan Lu , Huan-Sheng Chen , and Vincent S. Tseng . 2013. Efficient approaches for multi-requests route planning in urban areas . In Proceedings of the 14th International Conference on Mobile Data Management. Vol. 1 . IEEE, 36--45. Eric Hsueh-Chan Lu, Huan-Sheng Chen, and Vincent S. Tseng. 2013. Efficient approaches for multi-requests route planning in urban areas. In Proceedings of the 14th International Conference on Mobile Data Management. Vol. 1. IEEE, 36--45."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/AINA.2004.1283747"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1363686.1363886"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13369-020-04340-w"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 2014 IEEE SENSORS. IEEE, 1722--1725","author":"Siegel J.","unstructured":"J. Siegel , R. Bhattacharyya , A. Deshpande , and S. Sarma . 2014. Vehicular engine oil service life characterization using on-board diagnostic (OBD) sensor data . In Proceedings of the 2014 IEEE SENSORS. IEEE, 1722--1725 . J. Siegel, R. Bhattacharyya, A. Deshpande, and S. Sarma. 2014. Vehicular engine oil service life characterization using on-board diagnostic (OBD) sensor data. In Proceedings of the 2014 IEEE SENSORS. IEEE, 1722--1725."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442942.2442947"},{"key":"e_1_2_1_34_1","volume-title":"Driver fatigue and highway driving: A simulator study. Physiology 8 behavior 94, 3","author":"Ting Ping-Huang","year":"2008","unstructured":"Ping-Huang Ting , Jiun-Ren Hwang , Ji-Liang Doong , and Ming-Chang Jeng . 2008. Driver fatigue and highway driving: A simulator study. Physiology 8 behavior 94, 3 ( 2008 ), 448--453. Ping-Huang Ting, Jiun-Ren Hwang, Ji-Liang Doong, and Ming-Chang Jeng. 2008. Driver fatigue and highway driving: A simulator study. Physiology 8 behavior 94, 3 (2008), 448--453."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Paolo Toth and Daniele Vigo (Eds.). 2001. The Vehicle Routing Problem. Society for Industrial and Applied Mathematics USA.  Paolo Toth and Daniele Vigo (Eds.). 2001. The Vehicle Routing Problem. Society for Industrial and Applied Mathematics USA.","DOI":"10.1137\/1.9780898718515"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/MeMeA.2014.6860025"},{"key":"e_1_2_1_37_1","volume-title":"Stacy Cagle Davis, and Robert Gary Boundy","author":"Williams Susan E.","year":"2017","unstructured":"Susan E. Williams , Stacy Cagle Davis, and Robert Gary Boundy . 2017 . Transportation Energy Data Book: Edition 36. Technical Report. Oak Ridge National Lab (ORNL), Oak Ridge, TN. Susan E. Williams, Stacy Cagle Davis, and Robert Gary Boundy. 2017. Transportation Energy Data Book: Edition 36. Technical Report. Oak Ridge National Lab (ORNL), Oak Ridge, TN."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869857"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816646"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the International Conference on Geoinformatics. IEEE, 1--6.","author":"Yue Yang","year":"2009","unstructured":"Yang Yue , Yan Zhuang , Qingquan Li , and Qingzhou Mao . 2009 . Mining time-dependent attractive areas and movement patterns from taxi trajectory data . In Proceedings of the International Conference on Geoinformatics. IEEE, 1--6. Yang Yue, Yan Zhuang, Qingquan Li, and Qingzhou Mao. 2009. Mining time-dependent attractive areas and movement patterns from taxi trajectory data. In Proceedings of the International Conference on Geoinformatics. IEEE, 1--6."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2621104"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526816"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3412363","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3412363","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:25:01Z","timestamp":1750195501000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3412363"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,7]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2,28]]}},"alternative-id":["10.1145\/3412363"],"URL":"https:\/\/doi.org\/10.1145\/3412363","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,7]]},"assertion":[{"value":"2019-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}