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

00:00

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
202
Thumbnail
1:16:05
226
242
Open sourceProjective planeOpen sourceBriefträgerproblemImplementationMereologyField (computer science)Data managementOffice suiteLevel (video gaming)Different (Kate Ryan album)Plug-in (computing)XMLComputer animation
Open sourceStaff (military)Component-based software engineeringCodeMachine visionStack (abstract data type)Open setComputer networkLetterpress printingServer (computing)Plug-in (computing)CalculationPoint (geometry)Extension (kinesiology)DatabaseVector spaceOpen sourceMultiplication signData modelTerm (mathematics)Parameter (computer programming)TesselationBriefträgerproblemLink (knot theory)Domain nameStandard deviationConnected spaceAreaMereologyRoutingFunctional (mathematics)InternetworkingFlow separationDistanceCloud computingSemiconductor memoryProjective planeMenu (computing)Different (Kate Ryan album)QuicksortLaptopStudent's t-testRegular graphService (economics)AlgorithmRevision controlExtension (kinesiology)CASE <Informatik>Open setGraph (mathematics)GeometryCalculationINTEGRALLevel (video gaming)Machine visionSoftware bugMatrix (mathematics)Differenz <Mathematik>Film editingRootPoint (geometry)Plug-in (computing)Right angleLine (geometry)Computer animation
BriefträgerproblemCovering spaceAreaPersonal digital assistantMaxima and minimaView (database)Multiplication signPoint (geometry)CASE <Informatik>Universe (mathematics)outputBriefträgerproblemProfil (magazine)RoutingTime zoneLine (geometry)Row (database)Cartesian coordinate systemDistanceResultantMereologyTerm (mathematics)Graph (mathematics)Service (economics)AreaPolygonMedical imagingGreatest elementIdeal (ethics)ImplementationNumberComputer networkDifferent (Kate Ryan album)SoftwareAlgorithmGoogle Street ViewWeb pageComputer fileAsynchronous Transfer ModeRootExecution unitLevel (video gaming)Associative propertyTheorySummierbarkeitGoodness of fitStandard deviationXML
BriefträgerproblemSoftware testingCASE <Informatik>Message passingAreaMultiplication signBitLine (geometry)RoutingComputer animation
Computer networkMereologyIterationCalculationVertex (graph theory)TheoryBriefträgerproblemStandard deviationGeometryAlgorithmRead-only memoryLink (knot theory)Revision controlBeta functionRoutingPlug-in (computing)CASE <Informatik>PolygonGeometryVideo gameReal numberProjective planeImplementationRevision controlOcean currentMobile appRepository (publishing)RoutingLink (knot theory)IterationCalculationAreaDirection (geometry)Standard deviationMultiplicationUniform resource nameMultiplication signMessage passingPoint (geometry)AlgorithmSemiconductor memoryRight angleTheoryComputer animation
Transcript: English(auto-generated)
Like that, okay Yeah, so Andreas Jobst Thanks for the introduction project manager at Camp2Camp doing all kinds of projects, but quite a few in the QGIS field and also some geomapfish projects for different customers and
Yeah today I want to talk about the the Chinese postman problem in implementation That was done by my colleague Ismail Sunni And before we start
Yeah, just a quick overview I also want to talk about the project the larger project built around the Chinese postman part and We developed a routing plug-in for the desktop GIS CADAS Want to talk about that as well and and then we'll we'll look at the Chinese postman problem and
To start yeah, I came to camp just showing you the map there I work from the from the Munich office it's been almost four years now and Yeah, quite a few quite a few geospatial colleagues
In Camp2Camp over 40 now and Yeah doing more and more projects using Open-source technologies and This is still our
vision of the open source world and it also I think applies to most of geo projects where we have different levels all the way from from Standard users to integrators all the way up to the PSC and
Yeah, we have people in different layers and that in the pyramid all right The the project was actually funded by Amazon's with The idea was to have An offline routing solution so for the Swiss military students
they would have the standard laptop and In case of no internet connection. They'd still be able to do all kinds of different routing things and
They already have desktop GS CADAS the link is there and To add some functionality we worked on this routing plug-in so one part is the well the UI the the plug-in built into CADAS in
written in Python CADAS itself is based on QGIS for those of you don't know CADAS, it's a simplified version and The The data we use
OpenStreetMap data and Then there was the question which routing engine to use and I'll show you after why we chose Valhalla and Yeah, so it's it's it doesn't have some crazy Cloud infrastructure because it's simple offline solution, but yeah, we we have CADAS and
the parameters go By a command line to The routing engine and we have different databases one for the Valhalla tiles the
Graph tiles which are pretty much vector tiles, and we have all the the CADAS data in a separate database So why did we choose? Valhalla and Well, it's been tested to work well with open OpenStreetMap data
so we knew we're going to work with OpenStreetMap data for a start so That was an argument for it The data model is quite efficient in terms of memory use and Valhalla is suited for offline routing and
And What we'll see is that the Chinese postman problem solution consists of different of different algorithms and One of them we could actually use without changing hardly anything The time and distance matrix service that is already part of Valhalla. So that was another reason why we chose it
And of course Because it's a substantial part of this whole Chinese postman thing We will benefit from bug fixes and extensions of this service in the future. So Yeah
Right and Valhalla is used by quite a few integrators and users. I put up some examples here Besides Arma Swiss Could also name Mapillary, Mapbox the small company that produces electric cars and
Sidewalk Labs and it's still under a regular MIT open source license. This is the the sort of menu inside CADAS Apart from the Chinese postman problem. We have different functionalities in there in this routing plug-in
So isochrones as distances standard route calculation Also for where several waypoints No-go areas. So if you don't want to pass a certain area this can be
defined and we also have some basic navigation working already and Also a data portal where you can download the OpenStreetMap data for your For your domain. All right. So what is the Chinese postman problem? It's really about
It's as simple as You draw an area and you want to cover every single road or in that network so it's a bit different than the traveling salesman because you really want to cover all all the lines and
In this case, we also had to cover both sides of the road, so we can't just say oh, it's all Once we've gone through a certain road. No, it's it's not enough. You need to cover both sides And of course this is under the efficiency
So that the aim to to make this in as Short amount of time as possible. So so far. We haven't minimized the distance Use cases in this particular case. It was for in case of emergency
Patruling mode we decided to call it but obviously there is many applications of it Like Services by city councils and even Street View recordings The Theory it's quite well explained at the University
page of the TU in Munich and this was quite useful to for my colleague to start working on the algorithm implementation and Without going into too much detail there is a bunch of algorithms
the first one looks at So you you look at all the nodes in the network and then you you make as many pairs as you can create and Then it it's for each pair. It calculates the shortest path then it finds the
optimal pairs and then the it goes down to the next level where you you order the pairs and the most efficient way and Then in the end the end result is the Euler tour and all edges have to be contained at least once and
The sum has to be minimized because every edge has a cost associated to it and in an ideal world It's as simple as going straight to the bottom of the image And But in reality we have quite often a non ideal graph so a
Ideal graph is every node has an ingoing and an outgoing edge or the same number of ingoing and outgoing Edges, but quite often. This is not the case, and that's why there has to be all those extra steps Including the floyd-warshall
part and this is the one I mentioned that is taken care of by the Time and distance service of Valhalla and in terms of inputs, so Yeah, you need to define the the start point at end point
They should be inside the Area of interest You can define no-go zones and what's called here the Chinese polygon. That's the area of interest
And then the costing is coming from Because we have different profiles as well. So it's pedestrian cyclists and standard car and Yeah, so all this goes into
Valhalla and It provides as a result the Chinese postman route and
the route actually comes as a JSON file, so Yeah, all you what we thought would be useful is shown here the start point and point and turn by turn instructions and Then for each maneuver the time it takes the distance in kilometers and
The cost which I don't think it has an actual unit And this can be used so I think this is Quite good. It can be used by the end application in different ways for navigation
This is how it looks like in CADAS for for one example. So yeah, we we see I Show later we still have some issues and It's not always the case that all roads are covered. There's still some some issues what that we're that we're working on
but this is a good example where the no-go area in the middle was avoided and We we cover most of those roads and importantly a blue line is not just Yeah a single pass but it could be as many as four or five passes so
That's where we said. Okay in reality actually It's it's most likely the it's also hard to test this kind of behavior but it's most likely still the the most efficient route, but if you really want to cover both sides of a road you could pass it quite a few times in a
Area that is a bit larger like this one and then so we had the Theoretical the algorithm implemented and we just realized that okay There's a few points and I was actually in the beginning quite confident
I Started Exporting one of those routes and I thought let's let's try one of those navigation apps on my phone and I went on the bicycle and After two turns I realized oh it it doesn't really it doesn't really work
so That was my naive Understanding and Yeah, so there's there's different issues where you see it's a little more complicated if you want to use it in things in real life and one was actually
a Some notes that you can only reach Let's say in this example. The upper road is a one-way street going inside the Polygon so you can only reach it from the outside and that's where the first implementation failed. So
Is my Sunni had to do some extra step and Now this is working. So it doesn't iterative calculation to see from which other note this note could be reached best and
Then and now we can actually leave the area of interest and re re re enter it and then the idea was of course to the use case to use it for navigation and We also realized that yeah, there is there is more work to do so
first of all So that all fits into what I said earlier when I first tried to follow the the standard course and It just turns out that the standard navigation apps can't deal with multiple passes on the same edge
So you need a memory you need to get rid of segments you need to introduce Several segments for the same street. So you you know how many times you've passed it already You Turn Issues. Yeah, we go back sometimes the edge is used for going in both directions then
GPS gets confused because the geometry is identical and and then a kind of Another obvious one the GPS accuracy, so
Yeah, you need a very high accuracy so to know where you are if you've passed a certain note Otherwise it will keep sending you back to that note. So yeah, still some some work to do and Regardless it's available. We said the label it as a better version
Put the link of the current pull request Which is almost When almost went through and and also link to the cutters rooting plug-in repository and we want to thank also the Valhalla community, of course and
Arma Swiss Who sponsored the this project? All right That's it. Thanks