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
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)