Minimal on-road time route scheduling on time-dependent graphs
Open Access
- 1 August 2017
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 10 (11) , 1274-1285
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.Keywords
This publication has 20 references indexed in Scilit:
- On the Complexity of Time-Dependent Shortest PathsAlgorithmica, 2012
- Contraction of Timetable Networks with Realistic Transfers2010
- Time-Dependent SHARC-RoutingAlgorithmica, 2009
- Discrete Dynamic Shortest Path Problems in Transportation Applications: Complexity and Algorithms with Optimal Run TimeTransportation Research Record: Journal of the Transportation Research Board, 1998
- Minimum weight paths in time‐dependent networksNetworks, 1991
- Shortest-path and minimum-delay algorithms in networks with time-dependent edge-lengthJournal of the ACM, 1990
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Shortest route with time dependent length of edges and limited delay possibilities in nodesMathematical Methods of Operations Research, 1977
- The shortest route through a network with time-dependent internodal transit timesJournal of Mathematical Analysis and Applications, 1966
- A note on two problems in connexion with graphsNumerische Mathematik, 1959