Combining hierarchical and heuristic techniques for high-speed route computation on road networks
George Rosario Jagadeesh, T.H. Quek, Thambipillai Srikanthan · Computing & Control Engineering Journal · 2002
The performance of conventional route computation algorithms tends to deteriorate as the size of the network increases. A series of experiments were conducted on a real city road network to evaluate a heuristic technique before incorporating it into a hierarchical route-finding algorithm based on road types. The improved hierarchical algorithm computes a near optimal route in a fast and efficient manner by restricting the route computation to small subnetworks. The solutions provided by the algorithm are comparable to the optimal solutions.