Combining hierarchical and heuristic techniques for high-speed route computation on road networks

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.