Efficient shortest path computation in real road network is essential to the Intelligent Transportation System (ITS) or other navigation services. It is not an easy task nowadays to find the optimal route to travel in the massive and complicated road network of a modern city or country. Direct application of conventional shortest path algorithms always deteriorates due to the huge size of the real road network. This paper proposes an efficient method to compute shortest paths in real road network. The entire network is organized into a 2-level hierarchical structure. In the meanwhile, the pre-computation technique is adopted to improve the time efficiency. An optimal shortest path algorithm is developed based on the hierarchical network structure. The computation results will show the e...[ Read more ]

Efficient shortest path computation in real road network is essential to the Intelligent Transportation System (ITS) or other navigation services. It is not an easy task nowadays to find the optimal route to travel in the massive and complicated road network of a modern city or country. Direct application of conventional shortest path algorithms always deteriorates due to the huge size of the real road network. This paper proposes an efficient method to compute shortest paths in real road network. The entire network is organized into a 2-level hierarchical structure. In the meanwhile, the pre-computation technique is adopted to improve the time efficiency. An optimal shortest path algorithm is developed based on the hierarchical network structure. The computation results will show the efficiency of our method applied in the real road network of Hong Kong. Moreover, the performances of different partition methods are compared in term of time efficiency and memory size required. The integration of our method into a commercial navigation system will be shown, as well as the real application demonstration.