FOSS4G 2022 general tracks

The Routing Engine Valhalla has been extended with a solution of the Chinese Postman Problem (CPP). This means that the most efficient route to travel all roads and paths in the area can now be calculated within a defined polygon.
The CPP is a well-known problem from graph theory, where the goal is to visit every edge in a graph while minimizing the distance traveled. In theory, a graph can be either directed, undirected, or mixed.
In this implementation, the CPP has been implemented for directed graphs, as this corresponds to the representation of graphs in Valhalla and the data structure of OpenStreetMap (OSM). The latter forms the data basis for the calculation of the CPP route.
The CPP is solved using the following set of algorithms: the Floyd-Warshall algorithm, the Hungarian method, and the Hierholzer method. After successfully implementing the theoretical code base of the CPP, the main challenge was to make the route calculation executable using real-world road networks (OSM).
A key problem with the implementation of the theoretical CPP is that in real-world graphs, not every edge is always reachable by all other edges. Therefore, various extensions had to be made to allow the computation of a CPP route using OSM data. For example, within a larger area, rarely all road segments are accessible exclusively via the roads located in the area. It is often necessary to leave the area to access these otherwise inaccessible parts of the road network.
Eventually, we were able to create a working prototype of the CPP in Valhalla. In addition to the function of freely selecting the area to be traveled, restricted zones, so called no-go areas, can also be defined. After selecting the vehicle type (car, bicycle, pedestrian, etc.), the CPP route can be calculated, which also includes turn-by-turn navigation.