Minimal On-Road Time Route Scheduling on Time-Dependent Graphs

Lei Li, Wen Hua, Xingzhong Du, Xiaofang Zhou

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

44 Citations (Scopus)


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 prede-fined 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.

Original languageEnglish
Title of host publicationPVLDB 2017 - Proceedings of the 43rd International Conference on Very Large Data Bases
PublisherVLDB Endowment
Number of pages12
Publication statusPublished - 1 Aug 2017
Externally publishedYes
Event43rd International Conference on Very Large Data Bases, VLDB 2017 - Munich, Germany
Duration: 28 Aug 20171 Sept 2017

Publication series

NameProceedings of the VLDB Endowment
PublisherVery Large Data Base Endowment Inc.
ISSN (Print)2150-8097


Conference43rd International Conference on Very Large Data Bases, VLDB 2017

ASJC Scopus subject areas

  • Information Systems


Dive into the research topics of 'Minimal On-Road Time Route Scheduling on Time-Dependent Graphs'. Together they form a unique fingerprint.

Cite this