We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Implementation of the Chinese Postman Problem in the Valhalla Routing Engine

Formal Metadata

Title
Implementation of the Chinese Postman Problem in the Valhalla Routing Engine
Title of Series
Number of Parts
351
Author
Contributors
License
CC Attribution 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language
Production Year2022

Content Metadata

Subject Area
Genre
Abstract
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.
Keywords