DocumentCode :
1335410
Title :
Efficient Routing on Large Road Networks Using Hierarchical Communities
Author :
Song, Qing ; Wang, Xiaofan
Author_Institution :
Dept. of Autom., Shanghai Jiao Tong Univ., Shanghai, China
Volume :
12
Issue :
1
fYear :
2011
fDate :
3/1/2011 12:00:00 AM
Firstpage :
132
Lastpage :
140
Abstract :
Efficient routing is essential in everyday life. Although various hierarchical algorithms exist for computing shortest paths, their heavy precomputation/storage costs and/or query costs hinder their application to large road networks. By detecting a hierarchical community structure in road networks, we develop a community-based hierarchical graph model that supports efficient route computation on large road networks. We then propose a new hierarchical routing algorithm that can significantly reduce the search space over the conventional algorithms with acceptable loss of accuracy. Experimental results on a New York road network demonstrate the performance of the algorithm.
Keywords :
graph theory; optimisation; roads; traffic engineering computing; New York road network; community-based hierarchical graph model; hierarchical routing algorithm; large road networks; shortest path problem; Community structure; heuristics; hierarchical routing; road networks;
fLanguage :
English
Journal_Title :
Intelligent Transportation Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1524-9050
Type :
jour
DOI :
10.1109/TITS.2010.2072503
Filename :
5585765
Link To Document :
بازگشت