Discovering time-dependent shortest path on traffic graph for drivers towards green driving

Green transportation technologies that reduce fuel consumption, idling, and vehicle miles traveled while reducing acute congestion could play a significant role in reducing greenhouse gas emissions, particularly in major cities, around ports and freight hubs, and on major roads and corridors. The key to support green transportation is to discover real-time shortest path for drivers. A time-dependent traffic graph, generated from history traffic data can be used to predict the traveling time and to find the shortest path for drivers dynamically. There are two different types of queries on shortest paths: Query_FiST for starting at a fixed time and reaching the destination as early as possible and Query_BeST for choosing the best starting time to avoid the rush hours. Taking advantage of traffic graph's characteristics of sparsity and hierarchy, we propose two algorithms: Heap-based Bellman-Ford algorithm for Query_FiST and Extended Bellman-Ford algorithm for Query_BeST respectively. We prove the correctness of the algorithms and discuss their time complexity. A series of experiments are implemented on an open data set of real traffic collected from taxis and the results show that our algorithms outperform all existing algorithms practically.