BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//pretalx//talks.staging.osgeo.org//foss4g-2022//speaker//QX8FMS
BEGIN:VTIMEZONE
TZID:CET
BEGIN:STANDARD
DTSTART:20001029T040000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20000326T030000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:pretalx-foss4g-2022-GRFEHG@talks.staging.osgeo.org
DTSTART;TZID=CET:20220826T113000
DTEND;TZID=CET:20220826T120000
DESCRIPTION:The Routing Engine Valhalla has been extended with a solution o
 f the Chinese Postman Problem (CPP). This means that the most efficient ro
 ute to travel all roads and paths in the area can now be calculated within
  a defined polygon.\nThe CPP is a well-known problem from graph theory\, w
 here the goal is to visit every edge in a graph while minimizing the dista
 nce traveled. In theory\, a graph can be either directed\, undirected\, or
  mixed.\n In this implementation\, the CPP has been implemented for direct
 ed graphs\, as this corresponds to the representation of graphs in Valhall
 a and the data structure of OpenStreetMap (OSM). The latter forms the data
  basis for the calculation of the CPP route.\nThe CPP is solved using the 
 following set of algorithms: the Floyd-Warshall algorithm\, the Hungarian 
 method\, and the Hierholzer method. After successfully implementing the th
 eoretical code base of the CPP\, the main challenge was to make the route 
 calculation executable using real-world road networks (OSM).\nA key proble
 m with the implementation of the theoretical CPP is that in real-world gra
 phs\, not every edge is always reachable by all other edges. Therefore\, v
 arious extensions had to be made to allow the computation of a CPP route u
 sing OSM data. For example\, within a larger area\, rarely all road segmen
 ts are accessible exclusively via the roads located in the area. It is oft
 en necessary to leave the area to access these otherwise inaccessible part
 s of the road network.\nEventually\, we were able to create a working prot
 otype of the CPP in Valhalla. In addition to the function of freely select
 ing the area to be traveled\, restricted zones\, so called no-go areas\,  
 can also be defined. After selecting the vehicle type (car\, bicycle\, ped
 estrian\, etc.)\, the CPP route can be calculated\, which also includes tu
 rn-by-turn navigation.
DTSTAMP:20260403T220248Z
LOCATION:Modulo 0
SUMMARY:Implementation of the Chinese Postman Problem in the Valhalla Routi
 ng Engine - Andreas Jobst\, Ismail Sunni
URL:https://talks.staging.osgeo.org/foss4g-2022/talk/GRFEHG/
END:VEVENT
END:VCALENDAR