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
fDate :
3/1/2011 12:00:00 AM
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;
Journal_Title :
Intelligent Transportation Systems, IEEE Transactions on
DOI :
10.1109/TITS.2010.2072503