Lei Li
Abstract
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 FIFO 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 v is determined by the arrival time of its in-neighbor u, which does not hold in our scenario since we also consider the waiting time on u if u 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 FIFO property. To cope with this challenging problem, we propose two efficient algorithms using minimum on-road travel cost function 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.
- E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische mathematik, vol. 1, no. 1, pp. 269--271, 1959. Google Scholar
Digital Library
- A. V. Goldberg and C. Harrelson, "Computing the shortest path: A search meets graph theory," in Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2005, pp. 156--165. Google ScholarDigital Library
- L. Wu, X. Xiao, D. Deng, G. Cong, A. D. Zhu, and S. Zhou, "Shortest path and distance queries on road networks: An experimental evaluation," Proceedings of the VLDB Endowment, vol. 5, no. 5, pp. 406--417, 2012. Google ScholarDigital Library
- S. Wang, X. Xiao, Y. Yang, and W. Lin, "Effective indexing for approximate constrained shortest path queries on large road networks," PVLDB, vol. 10, no. 2, pp. 61--72, 2016. Google ScholarDigital Library
- S. E. Dreyfus, "An appraisal of some shortest-path algorithms," Operations research, vol. 17, no. 3, pp. 395--412, 1969. Google ScholarDigital Library
- E. Kanoulas, Y. Du, T. Xia, and D. Zhang, "Finding fastest paths on a road network with speed patterns," in Data Engineering, 2006. ICDE'06. Proceedings of the 22nd International Conference on. IEEE, 2006, pp. 10--10. Google ScholarDigital Library
- B. Ding, J. X. Yu, and L. Qin, "Finding time-dependent shortest paths over large graphs," in Proceedings of the 11th international conference on Extending database technology: Advances in database technology. ACM, 2008, pp. 205--216. Google ScholarDigital Library
- I. Chabini, "Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time," Transportation Research Record: Journal of the Transportation Research Board, no. 1645, pp. 170--175, 1998.Google ScholarCross Ref
- A. Orda and R. Rom, "Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length," Journal of the ACM (JACM), vol. 37, no. 3, pp. 607--625, 1990. Google ScholarDigital Library
- U. Demiryurek, F. Banaei-Kashani, C. Shahabi, and A. Ranganathan, "Online computation of fastest path in time-dependent spatial networks," in Advances in spatial and temporal databases. Springer, 2011, pp. 92--111. Google ScholarDigital Library
- X. Cai, T. Kloks, and C.-K. Wong, "Time-varying shortest path problems with constraints," Networks, vol. 29, no. 3, pp. 141--150, 1997.Google ScholarCross Ref
- H. Wu, J. Cheng, S. Huang, Y. Ke, Y. Lu, and Y. Xu, "Path problems in temporal graphs," Proceedings of the VLDB Endowment, vol. 7, no. 9, pp. 721--732, 2014. Google ScholarDigital Library
- S. Wang, W. Lin, Y. Yang, X. Xiao, and S. Zhou, "Efficient route planning on public transportation networks: A labelling approach," in Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 2015, pp. 967--982. Google ScholarDigital Library
- B. Zheng, H. Su, W. Hua, K. Zheng, X. Zhou, and G. Li, "Efficient clue-based route search on road networks," IEEE Transactions on Knowledge and Data Engineering, 2017.Google ScholarCross Ref
- K. L. Cooke and E. Halsey, "The shortest route through a network with time-dependent internodal transit times," Journal of mathematical analysis and applications, vol. 14, no. 3, pp. 493--498, 1966.Google ScholarCross Ref
- R. Geisberger, "Contraction of timetable networks with realistic transfers," in Experimental Algorithms. Springer, 2010, pp. 71--82. Google ScholarDigital Library
- 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.Google Scholar
- A. Orda and R. Rom, "Minimum weight paths in time-dependent networks," Networks, vol. 21, no. 3, pp. 295--319, 1991.Google ScholarCross Ref
- L. Foschini, J. Hershberger, and S. Suri, "On the complexity of time-dependent shortest paths," Algorithmica, vol. 68, no. 4, pp. 1075--1097, 2014.Google ScholarCross Ref
- X. Cai, T. Kloks, and C. Wong, "Shortest path problems with time constraints," in International Symposium on Mathematical Foundations of Computer Science. Springer, 1996, pp. 255--266. Google ScholarDigital Library
- G. V. Batz, D. Delling, P. Sanders, and C. Vetter, "Time-dependent contraction hierarchies," in Proceedings of the Meeting on Algorithm Engineering & Expermiments. Society for Industrial and Applied Mathematics, 2009, pp. 97--105. Google ScholarDigital Library
- D. Delling, "Time-dependent sharc-routing," Algorithmica, vol. 60, no. 1, pp. 60--94, 2011.Google ScholarCross Ref
- L. Li, X. Zhou, and K. Zheng, "Finding least on-road travel time on road network," in Australasian Database Conference. Springer, 2016, pp. 137--149.Google Scholar
- Y. Yang, H. Gao, J. X. Yu, and J. Li, "Finding the cost-optimal path with time constraint over time-dependent graphs," Proceedings of the VLDB Endowment, vol. 7, no. 9, pp. 673--684, 2014. Google ScholarDigital Library
- M. L. Fredman and R. E. Tarjan, "Fibonacci heaps and their uses in improved network optimization algorithms," Journal of the ACM (JACM), vol. 34, no. 3, pp. 596--615, 1987. Google ScholarDigital Library
- D. J. Watts and S. H. Strogatz, "Collective dynamics of small-worldnetworks," nature, vol. 393, no. 6684, pp. 440--442, 1998.Google Scholar
Recommendations
Time-Dependent Solution of a Priority Queue with Bulk Arrival
The time-dependent distribution of the number of customers in the queue and the lapsed service time is obtained, in terms of Laplace transforms, for a head-of-the-line priority queue in which both classes of customer arrive in bunches. From this we ...
One-Dependent Regenerative Processes and Queues in Continuous Time
Motivated by the study of queues in continuous time, a "one-dependent" regenerative process is defined and its ergodic properties are given. We show that a continuous time Harris recurrent Markov process HRMP is of this type and give a different proof ...
Queues with waiting time dependent service
Motivated by service levels in terms of the waiting-time distribution seen, for instance, in call centers, we consider two models for systems with a service discipline that depends on the waiting time. The first model deals with a single server that ...
Comments