The problem of efficient path computation arises in several applications such as intelligent transportation and network routing. Although various algorithms exist for computing shortest paths, their heavy precomputation/storage costs and/or query costs hinder their application to real-time routing. By detecting hierarchical community structure in road networks, we develop a community-based hierarchical graph model that supports efficient path 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. Finally, we evaluate our approach experimentally using a large, real-world road network to show the gain in performance.
展开▼
