{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T10:11:13Z","timestamp":1780049473324,"version":"3.53.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>\n            On time-dependent graphs, fastest path query is an important problem and has been well studied. It focuses on minimizing the total travel time (waiting time + on-road time) but does not allow waiting on any intermediate vertex if the\n            <jats:italic>FIFO<\/jats:italic>\n            property is applied. However, in practice, waiting on a vertex can reduce the time spent on the road (for example, resuming traveling after a traffic jam). In this paper, we study how to find a path with the minimal on-road time on time-dependent graphs by allowing waiting on some predefined parking vertices. The existing works are based on the following fact: the arrival time of a vertex\n            <jats:italic>v<\/jats:italic>\n            is determined by the arrival time of its in-neighbor\n            <jats:italic>u<\/jats:italic>\n            , which does not hold in our scenario since we also consider the waiting time on\n            <jats:italic>u<\/jats:italic>\n            if\n            <jats:italic>u<\/jats:italic>\n            allows waiting. Thus, determining the waiting time on each parking vertex to achieve the minimal on-road time becomes a big challenge, which further breaks\n            <jats:italic>FIFO<\/jats:italic>\n            property. To cope with this challenging problem, we propose two efficient algorithms using\n            <jats:italic>minimum on-road travel cost function<\/jats:italic>\n            to answer the query. The evaluations on multiple real-world time-dependent graphs show that the proposed algorithms are more accurate and efficient than the extensions of existing algorithms. In addition, the results further indicate, if the parking facilities are enabled in the route scheduling algorithms, the on-road time will reduce significantly compared to the fastest path algorithms.\n          <\/jats:p>","DOI":"10.14778\/3137628.3137638","type":"journal-article","created":{"date-parts":[[2017,9,7]],"date-time":"2017-09-07T13:35:53Z","timestamp":1504791353000},"page":"1274-1285","source":"Crossref","is-referenced-by-count":56,"title":["Minimal on-road time route scheduling on time-dependent graphs"],"prefix":"10.14778","volume":"10","author":[{"given":"Lei","family":"Li","sequence":"first","affiliation":[{"name":"The University of Queensland, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wen","family":"Hua","sequence":"additional","affiliation":[{"name":"The University of Queensland, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xingzhong","family":"Du","sequence":"additional","affiliation":[{"name":"The University of Queensland, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[{"name":"The University of Queensland, Australia and Soochow University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_2_1","first-page":"156","volume-title":"Society for Industrial and Applied Mathematics","author":"Goldberg A. V.","year":"2005"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140438"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3015274.3015277"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.3.395"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.71"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353371"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.3141\/1645-21"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.214078"},{"key":"e_1_2_1_10_1","first-page":"92","volume-title":"Online computation of fastest path in time-dependent spatial networks,\" in Advances in spatial and temporal databases","author":"Demiryurek U.","year":"2011"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199705)29:3<141::AID-NET2>3.0.CO;2-H"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732945"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749456"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2703848"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(66)90009-6"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"J. Halpern \"Shortest route with time dependent length of edges and limited delay possibilities in nodes \" Zeitschrift fuer operations research vol. 21 no. 3 pp. 117--124 1977.  J. Halpern \"Shortest route with time dependent length of edges and limited delay possibilities in nodes \" Zeitschrift fuer operations research vol. 21 no. 3 pp. 117--124 1977.","DOI":"10.1007\/BF01919767"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230210304"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9714-7"},{"key":"e_1_2_1_20_1","first-page":"255","volume-title":"Shortest path problems with time constraints,\" in International Symposium on Mathematical Foundations of Computer Science","author":"Cai X.","year":"1996"},{"key":"e_1_2_1_21_1","first-page":"97","volume-title":"Society for Industrial and Applied Mathematics","author":"Batz G. V.","year":"2009"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9341-0"},{"key":"e_1_2_1_23_1","first-page":"137","volume-title":"Finding least on-road travel time on road network,\" in Australasian Database Conference","author":"Li L.","year":"2016"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732941"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_26_1","volume-title":"Collective dynamics of small-worldnetworks,\" nature","author":"Watts D. J."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3137628.3137638","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:58:52Z","timestamp":1672221532000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3137628.3137638"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":26,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.14778\/3137628.3137638"],"URL":"https:\/\/doi.org\/10.14778\/3137628.3137638","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}