HieraRoute: A Dynamic and Hierarchical Road Routing Algorithm Based on Real-Time Information

Abstract

As mobile computing technology undergoes rapid advancement, automobile navigation system costs are plummeting and are no longer considered expensive luxuries. Indeed, many people now use these gadgets on a daily basis and carry them constantly. However, the computing power of car navigation device is usually limited. In this paper, we utilize the hierarchical concept dividing the road information into two levels to reduce the overall computation complexity; the Low-Level Graph adopts each intersection as a node and each road connecting two nodes as an edge. The node used in the High-Level Graph is called a PopNode (Popular Node), which refers to the most frequently used in low-level node. Our proposed algorithm adopts the two levels information to calculate the route and proof that our algorithm can reduce the computational complexity but also generate the route that is closed to the optimal result. We also imply random function and dynamic concepts into the algorithm to improve the driving experience.