Chinese Postman Problem Implementation on Valhalla Routing Engine

Continuing from the previous article about Kadas Routing, we now want to compute the shortest route for patrolling all roads in a selected region with the options to include areas that need to be avoided.

This problem is known as the Chinese Postman Problem (CPP) or Route Inspection Problem in graph theory, where the goal is to find the shortest path while visiting every edge in the graph.

It can be solved in a polynomial time for directed and undirected graphs. For a mixed graph, the problem becomes an NP-Complete problem.

As for the other functionalities developed for Kadas Routing, the underlying routing engine Valhalla was extended with a solution of the CPP.

In this implementation, we work with the directed graph because it corresponds to the graph representation in Valhalla for OpenStreetMap data. The CPP algorithm has already been developed for ideal graphs and as part of academic studies. For example, it can be explored with this visualization from Technische Universität München (TUM). Currently 3 algorithms are needed to solve the problem: Floyd-Warshall algorithm, Hungarian Method, and Hierholzer Method. For Floyd-Warshall, we use an existing cost-matrix algorithm inherent to Valhalla.

The biggest challenge is integrating CPP to Valhalla and handling some real-world cases. The existing algorithms or implementations only handle an ideal situation (i.e. the graph is strongly connected). This is not the case with real-world data, so we have to do several improvements and additions to the theoretical algorithm, which includes leaving the area of interest to visit parts of the network that can not be reached from within.

In the end, we managed to create a working prototype of a CPP solver in Valhalla. Users can draw the area they want to visit, an area that must not be visited, and the type of vehicle to be used. The CPP solver returns a route with turn-by-turn navigation, just like a standard routing algorithm. This means the processed route can also be used for navigation.

The next plan is to merge this feature to the master branch of the Valhalla project so that it can be used and tested further by the community.

We would like to thank the customer and funder of this project Armasuisse.