Paper Info
Title
Discovering time-dependent shortest path on traffic graph for drivers towards green driving.
Abstract
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 graphs characteristics of sparsity and hierarchy, we propose two algorithms: Heap-based BellmanFord algorithm for Query_FiST and Extended BellmanFord 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. For the Query_FiST, we propose Heap-based BellmanFord algorithm to find the shortest path in a dynamically changing traffic graph and it works efficiently in practical implementations. Although in the worst case, the time complexity of our algorithm is worse than that of algorithms based on Dijkstras algorithm, our algorithm works better in practical performance by taking advantages of the two characteristics of traffic graphs to avoid the worst case.For the Query_BeST, we propose Extended BellmanFord algorithm to discover a shortest path with the best starting time in the traffic graph. The time complexity of our algorithm is O(kE*a(T)), where a(T) is the time cost to do several operations between two functions and is inevitable in every algorithm focusing on this problem. The proposed algorithm for Query_BeST performs better than other previous ones because the mentioned characteristics in traffic graphs guarantee a smaller constant k. The experiment results confirm this assertion.A series of experiments are implemented and the results show that our algorithms outperform existing solutions in terms of efficiency respectively.
Year
DOI
Venue
2017
10.1016/j.jnca.2015.10.018
J. Network and Computer Applications
Keywords
Field
DocType
Shortest path problem,Optimization,Green driving
Shortest path problem,Computer science,Constrained Shortest Path First,Yen's algorithm,Shortest Path Faster Algorithm,Time complexity,Longest path problem,Dijkstra's algorithm,K shortest path routing,Distributed computing
Journal
Volume
Issue
ISSN
83
C
1084-8045
Citations 
PageRank 
References 
6
0.47
11
Authors
4
Name
Order
Citations
PageRank
Yunchuan Sun153454.06
Xinpei Yu260.47
Rongfang Bie354768.23
Houbing Song41771172.26