Highway Node Routing

A routing server stands and falls with the routing algorithm behind it. In today’s world, where waiting times are less and less tolerated, it is all the more important to keep the response time as short as possible. After all, if the query takes too long, users are more likely to switch providers than wait for the result. The more queries the system has to process, the more serious the problem becomes. The Dijkstra algorithm quickly comes to mind as a solution. However, this reaches its limits with larger traffic graphs, as we will see later. A more sophisticated solution is required here: the highway node routing method introduced by D. Schultes. We will look at this approach step by step and check whether it satisfies the requirements of our problem. The idea behind this method is to add a hierarchy to the traffic graph. Each layer is a subset of the lower layers, maintaining the property of the optimal route. During the query, we move step by step to a higher layer, whereby fewer and fewer nodes and edges have to be taken into account, thereby achieving a significant acceleration. This idea emerges from the traffic network. Assume that all roads are in the lowest layer. The first layer contains state and federal roads and motorways. The second layer contains federal roads and motorways and the last layer contains only motorways. Routing in such a hierarchy no longer provides the correct result, but it represents the basic idea of the algorithm. In this bachelor thesis we will look at how we can calculate a correct hierarchy and elaborate the advantages and disadvantages of this approach.