An efficient route computation approach for large graphs

The problem of efficient routing arises in several applications such as transportation problems and network optimization. The increasing availability of large network data sets and the impact of networks on everyday life has set new standard to route computations, necessitating research for even faster and more accurate shortest path algorithms. A hierarchical graph model is developed based on an effective partition of graphs for decomposing the complex search problem. A new heuristic hierarchical routing algorithm is then proposed to significantly reduce the search space by pruning searches towards unpromising subgraph branches. Experimental results on New York City road network demonstrate the performance of the algorithm.