Valhalla Routing Engine
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 266 | |
| Author | ||
| License | CC Attribution 3.0 Germany: 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 | 10.5446/66588 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
RoutingPresentation of a groupWordQuicksortStudent's t-testSoftwareInformation technology consultingGoodness of fitComputer animation
01:18
Maxima and minimaMoment (mathematics)Plug-in (computing)SoftwareCore dumpProjective planeSet (mathematics)Theory of relativityBit1 (number)Software developerSoftware maintenanceMappingRoutingLecture/ConferenceMeeting/Interview
02:17
ArchitectureClosed setSoftware developerPlanningCuboidLevel (video gaming)Computer architectureMereologyMappingComputer fontProfil (magazine)RoutingComputer animation
04:02
Projective planeProfil (magazine)Core dumpService (economics)Right angleMultiplication signFormal languageTheoryDigital photographyAndroid (robot)Bit1 (number)Computer fontRoutingoutputOpen sourceSummierbarkeitTraffic reportingGraph (mathematics)Computer architectureMatrix (mathematics)Vector potentialKeyboard shortcutTesselationLevel (video gaming)Server (computing)Band matrixRaw image formatReal-time operating systemPoint (geometry)MiniDiscUniform resource locatorLibrary (computing)Line (geometry)CodeMultilaterationDirection (geometry)Thread (computing)Normal (geometry)Lecture/ConferenceMeeting/Interview
08:55
Graph (mathematics)HierarchyComputerObject (grammar)Level (video gaming)TesselationHierarchyBitDegree (graph theory)Multiplication signNeuroinformatikPredictabilitySoftware testingUniform resource locatorGraph (mathematics)Row (database)Sinc functionProcess (computing)AlgorithmCASE <Informatik>VideoconferencingRight angleComputer fileData structureAdditionGroup actionCategory of beingTwitterAttribute grammarType theoryRoutingExtension (kinesiology)Normal (geometry)Subject indexingComputer animationEngineering drawing
14:47
Graph (mathematics)HierarchyMaxima and minimaPopulation densityWeightAlgorithmPopulation densityMaxima and minimaSinc functionTesselationMultiplication signGraph (mathematics)Parallel portCategory of beingKeyboard shortcutWorkstation <Musikinstrument>Computer architectureHierarchyTheoryPhysical systemParameter (computer programming)Integrated development environmentDifferent (Kate Ryan album)AlgorithmCore dumpDivisorCellular automatonService (economics)RoutingCasting (performing arts)MathematicsFilm editingMereologyUniform resource locatorComplete metric spaceWeightVirtual memoryComputer filePoint (geometry)Type theoryStructural loadAttribute grammarDialectDependent and independent variablesRaster graphicsCalculationSurjective functionSemiconductor memoryIntrusion detection systemArtistic renderingBuildingVector spaceComputer animation
19:49
Endliche ModelltheorieDistanceRoutingQuicksortElectronic mailing listProfil (magazine)SurfaceRight angleComputer configurationParameter (computer programming)Message passingMultiplication signRow (database)InformationLecture/ConferenceMeeting/Interview
21:18
Extension (kinesiology)View (database)Default (computer science)WeightMaxima and minimaConnected spaceRoutingBridging (networking)Shape (magazine)View (database)PolygonTerm (mathematics)SoftwareThermal expansionLimit (category theory)CASE <Informatik>Parameter (computer programming)Right angleGraph coloringGoodness of fitData analysisGroup actionComputer animation
23:12
Visualization (computer graphics)Multiplication sign
23:37
Instance (computer science)ParsingGraph (mathematics)CASE <Informatik>Level (video gaming)Electric generatorBuildingMultiplication signMultiplicationProcess (computing)Lecture/ConferenceMeeting/Interview
24:36
Plug-in (computing)Keyboard shortcutServer (computing)Entire functionRippingUniform resource locatorProjective planeTheory of relativityBitOpen sourceKeyboard shortcutDemo (music)Instance (computer science)Medical imagingServer (computing)Plug-in (computing)Web 2.0Computer animation
25:30
RippingEntire functionXMLUMLComputer animation
Transcript: English
00:08
hello everyone thank you for being here now we have needs nowadays who will be
00:20
visiting about ours praise the Lord Israel means he's treating us somebody and uh students do it yourself thank you very much thank you very much all for coming so
00:42
I'm going to present Valhalla today um I'm gonna start with the cliche so who used Valhalla before okay who tried to use it and was utterly confused and how to okay good just one is good okay so um Valhalla I think
01:01
um everyone sort of has heard about it before um but also there hasn't been a Public Presentation in an International Conference for like seven years now uh so I tried I I thought I will try to you know make up for that so just a few um words about us so we're a small
01:21
software comes out and see based in Berlin um obviously we're mostly dealing with routing and routing related projects we started off with very broad geospatial software development but then double down on routing I became a Valhalla maintainer and we are also I think one of our more core benefits is that we can
01:42
also make arbitrary data sets relative osm ingesting routing engines which are all the Autosource ones we do also like to work with other routing engines such as osrm um PG routing and we do also like to do qgs plugins we
02:00
have a couple not very well maintained at the moment there is the one coming up that we're working on since two years but it's a bit of a yeah I will announce when it's that far so um Valhalla is wait a second yeah now so in 2014 the brief history of it in 2014
02:22
um map Zen um maps and developers had the idea for Valhalla actually Maps then was scooping up a whole routing team from MapQuest um and those guys were having the idea for the architecture of a lot of and then in 2015 it was actually published
02:41
to um published on GitHub and to the public and uh then in 2018 for three years there was a lot of feature development going on in 2018 Madison had to close map box got lucky enough to get the Valhalla Engineers that map then got from Mapquest before
03:02
and then in 2019 my plan and including Valhalla became part of the Linux Foundation which um to this day not quite so sure what that really means and in 2020 um we came in and what I have known back
03:20
then what how much effort it would be to work myself into C plus plus and Valhalla and routing I'm not sure if I uh would have sacrificed at all it was really a rough one and a half years but I made it and now I actually made it to maintainer so there's a few the most well-known
03:40
Balada users probably is Tesla who uses it in their um in car navigation engine and that box is almost 100 relying on valada these days um yeah but both are not contributing back very much lately Tesla never met box not since two years
04:04
um a lot of profile just give a broad outline so it's in C plus plus 17 uh obviously it consumes openstreetmap data it has an interesting architecture kind of offsets it from the other routing engines that are out there
04:21
so that's a hierarchical and a tiled routing graph so that means it's um it's kind of aching to map to map back to tiles and it also has a very highly flexible request parameterization so that means the user who wants to request the route can influence the route finding in many many ways but I'm going
04:42
to show you more of that later so um just to talk a bit about the high level features I find what Valhalla like objectively not only because I like it a lot objectively Valhalla is the most feature-rich routing engine I think at the time right now uh there's open source so we of course have all the
05:02
routing apis like normal A to B routing isochrons Matrix map matching we have a couple of other apis like for elevation we can adjust situation and you can query for the altitude at a certain location more of an entire line
05:20
um we have a very excellent navigation engine so that is for um instructions when should the user turn um at what point in the route and it's like um yeah it's like an erasing right but what what the real-time navigation does that's for you and um a totally translated into almost 30
05:42
languages almost 100 percent um that's also the main reason why Tesla and mapbox shows Valhalla as a routing engine and then we have time dependent routing so that's um that's not entirely unique but it is very well implemented in
06:01
Valhalla so apart from all the access restrictions that we have in osm and Theory which are not very well populated but we could consider all the access restrictions the time-based ones but it also naturally leads to um something like public transport that was a Google sum of core project last
06:20
year where we could ingest some raw gtfs data into Valhalla directly that's finished and it's better working um then also leads to traffic consideration of course so we can consider historical and real-time traffic information
06:41
which is not mobile data usually and we have python bindings which makes it very easy to use the C plus Library directly from python instead of going via HTTP route and we also that was one of the core principles I think when Valhalla was
07:02
designed is that it is usable on mobile phones so since it's a C plus plus project we can compile the valve IOS and Android and it can also be used offline and finally I think it's worth noting that we don't only have a Json API but
07:21
we also have a photograph API so that helps a little bit with lower bandwidth usage and there is a potential for um grpc but that's not really implemented yet so well it's probably most interesting for someone who wants to run while I love themselves is a bit about the
07:40
requirements that the server needs to have if you want to there's two different scenarios right so one is you want to build a graph and one is he wants to serve the graph and actually answer requests so you build a graph once in a while like every week or two and you can do it on the server that has a brown 60 gigabyte RAM for the entire planet
08:00
uh it will take like 36 hours approximately on 16 so that's that's what I know from the openstreetmap service and um it requires around 300 gigabytes um SSD disk like the faster it is the better obviously um and then the service if you want to run it as a service so once you have to
08:21
once you've built the tiles and you're going to transfer the tiles to another server that doesn't need to be as big now you can actually run it like it has many more requirement of like 50 megabyte approximately which makes it ideal for an offline scenario and uh well still pretty performant it's
08:41
not also I'm performing um but it takes like a few milliseconds for shortest route and like a second from Madrid's Moscow which is like 15 now 2000 kilometers probably more so the Valhalla graph um there's two things you should remember about maybe
09:02
in the end is once it's tiled and the other one is that has hierarchies so it's a bit like map tiles um so that's it's Aiken to to zoom levels I would say now we have three hierarchies which are based on the highway OS and tags and um so we have a level of zero this
09:23
has this is the biggest tile size that has a four degree um four degree child size and there all the motorway Trend and primary um highway road and then we have the level one tile has a one degree tile size and it has all
09:42
the secondary and territory tiles and you can see the extent of it and the over Germany so this is like 80 tiles I think or 70. and then we have um level two and three so level two is still used for normal um Road routing
10:00
um that we have all the low level unclassified residential everything that um that is very common like just the most common Highway attacks and on level 3B it's like an addition that was done after the initial um graph structure was there level three has all
10:20
the transit nodes all the transit nodes and Transit edges um so the thing in like the Valhalla graph it's uh it's it's tile based right and each tile is represented by by one file on your computer and
10:40
um all like the we organize it in such a way that one tile on graph tile has all the edges that start in that graph type and we have like abundant properties and attributes um for for every Edge and that is what makes palala also very flexible
11:02
um so since it's a it's one file on a computer each each of these tiles and for example if you see the level zero outside there it has a um has an idea of 3286 and that just means that because we index our um our graph in a way that we
11:20
start at minus 80 minus 180 minus 90 degrees and then we just go row based so it's like zero ID 0 id1 id2 and so on and then we go up to like uh 180 degrees and then we jump on row up one row up and
11:41
um so this is like um yeah you can you can basically you can calculate the lap long from the title ID since it's predictable so we have a 40 degree tile size you know it's the 3286 tile ID so you know it's uh
12:03
actually it's lower left corner is at 54 degree North 40 degrees east and the hierarchy so the hierarchies are right the level zero one and two tiles and they are connected via special notes
12:22
we call them transition nodes and that actually makes also like we have a very actually a very un performance routing algorithm it's just an a star in the end but these hierarchies and the ability that we can transition between them is what makes
12:42
this um fairly performant so on the next one I'm going to show you a small video which shows how Valhalla will load the titles so we're gonna start here and there and it's a in this case it's a
13:01
unidirectional so we're gonna be linearly following this path and we're going to have an intermediate location around here so in the beginning what happens is that we're going to start no so we're going to start at the um on level two tiles so that might be
13:21
some residential Road someone wants to route from home to his friend and we're gonna load a very small level two tiles that have a lot of edges in them but then as soon as as long as the road the route progresses and the routing algorithm progresses we're going to very soon switch to the level one tiles which
13:42
have less edges in them so it's it's easier like it's not as much run intense it's a lot of them and they also have the edges and the roads that are progressing faster right because they have a higher hearing so
14:01
then it wants to jump as quickly as it can from level two to level one time and eventually landing on the on the level zero test and that is where all the motorways are located and uh and then since there's an intermediate location it will have to do the reverse process
14:22
again so we'll go for a metal V level zero down to level one and eventually to level two tiles where we'll find uh um intermediate location and then going towards the end it has to again do the other thing go from level two to level one to level zero and eventually
14:43
getting to the destination yeah and what time is it how much service all right so a thousand hero piece
15:00
um actually that does give quite a lot of nice properties so we can use to um make it easier and nicer to work with Valhalla in the graph so you can cut Regional extracts since we know that Thailand is refer in the end to locations to let lungs we can actually use them um we can use that
15:20
property to just take a complete Valhalla graph and just cut Regional extracts so we just package a bunch of tile files and that will represent the graph that Valera can wrap with um then it's also very resource friendly like that was one of the core principles that was um responsible for the
15:41
architecture of it Valhalla only loads ties into rum which it needs to find a route and since it's using memory mapping um it's a it's a system that will decide on what to cash and what's wrong what's on cash and we can actually build a padala graph
16:02
and parallel so that decreases build time quite a lot so you could do it in theory very little people do it um then it's also we still even though we use um just a a star and I start
16:20
um we're still quite performing and that's because of the hierarchies and the shortcuts that we do um and well in the future we want to have some we want to have some some improvements on the on the graph itself so incremental updates would be nice to have so we can only rebuild tiles which
16:43
actually happens I'm seeing changes and uh mvt endpoint would be also nice because um then you can use Valhalla to build to build Vector cells for rendering and um yeah so the next thing the graph
17:01
is one thing but we can use that graph which the richly attribute the graph um to do some extra routing and one of the other core things Valhalla is really good at is flexible costing so casting is really what will eventually find the route
17:22
every Edge has like it really boils down it really boils down to an edge as a time and a cost and the time is what's and what is really important to use to users right like that's um contributing to the to the ETA
17:41
and the cost is what the routing algorithm will um really look at look at to decide which path will be part of the final route so we have many attributes stored on the graph for each Edge
18:01
and one of them is for example maximum weight we also inflate it with elevation raster type files to get the maximum and minimum slope we do also extract admin the administrative features to get um to get the attribute of is an edge crossing a border
18:21
and we even do a density calculation to determine whether we probably rural or rather Urban environment and we have like three different parameter categories one is like fixed costs which does impact both cost and
18:40
time so this is added to the final team so the final ETA but it's also influencing the routing algorithm itself for example a tall station you would add 10 minutes and then the routing algorithm would say okay this is more expensive and probably rather avoiding it but you also would
19:00
add 10 minutes to the finely da then there's a penalty that is only like a fixed time that is added to the cost for example you want to avoid Service Roads with 20 minutes that tells the routing algorithm like don't go over Service Roads but if you do have to then don't add it to the finely finally ga
19:24
uh then the factor the factors are multiplying cost um it's usually between zero and one uh the factor of zero will often avoid things and the factor of one will often favor things for example you can again
19:41
avoid tall roads by setting used talls of 0.0 if you decide to use thousand one point zero you will actually favor 12 rows we have a bunch of um profiles we call them clustering models um they're like the fixed sort of the fixed parameters that you
20:02
cannot influence so for example a pedestrian cannot go on a Motorway right or on a freeway but then we have all these costing options that you can send per request and that will actually influence how the route will look like in the end so you have a maneuver penalty for
20:21
example which is like an additional cost to do a turn or maneuver you can forward favor or avoid slopes you can do an actual shortest route a distance instead of um which will ignore all other custom costing options
20:41
um you can pass time information for departure and arrival which if you have traffic we'll obviously take that into account you can for a bike only um costing model you can avoid bad surfaces such as cobblestones you can tell for pedestrian route to
21:02
rather prefer lit roads so I'm inside the tunnel for example you don't you don't necessarily want to walk through a dark tunnel many many more there's a full list in the API reference so just to show a few of the it's just a
21:22
showcasing um so this is like extra polygons if we place a polygon right where it actually would like to route with all other parameters being the same but just um avoid it and you go another route then we have something called top speed
21:40
so that is um the default is 140 kilometers it's basically saying how fast do you maximum want to go with your vehicle and if you put it for example 60 then the route will change from not taking a highway because we're also most bad colors we
22:00
also um like if you we will penalize roads that have a maximum speed limit of higher than 60 kilometers if you set that up so we'll prefer non-highways um max weight 10 tons is obvious we're going to avoid everything that's um not liking anything above that
22:23
for example there's a little bridge in Berlin let me have something called expansion um I think in Asbury terms it's called Network View it's mostly producing pretty pictures but it can also be very relevant for data analysis uh very recently
22:41
multi-modal again which is based on gtfs and this is really not looking that good um but it's it's it's pedestrian and Transit right so in this case you only see the direct connections because there wasn't any shapes attached to the gtfs
23:02
and uh yeah it's quite obvious what it does but we're very happy that it's enabled again and there's traffic um I'm just going to show this because we it's pretty and so this is like the heartbeat of um Berlin where
23:22
depending on the time of the day the isochrons you know you will have a further reachability while in the morning in the afternoon in rush hour it's the reachability is quite low I really like this visualization so we got some possible improvements
23:42
um our graph building is not as good as it could be we have a single threaded osm passing stage in the beginning of the graph build which takes 12 hours currently and it's almost impossible to speed up right now but we want to mod the process or multi correct that
24:01
eventually then there's incremental graph that's already talked about it which could be very interesting for humanitarian use cases there is MBT generation I already talked about that as well and we want to improve the gtfs ingestion um which currently just takes an awful
24:21
lot of time and it's not going to be fit for a global instance yet just because it would take weeks to generate of course if anyone wants to fund I'm here um so we have a couple of related resources
24:42
and projects I did find the very beginning it's a daunting experience to start with Valhalla so our company or specifically focuses on making a bit more accessible we actually foscus the German of German how you say Foundation is
25:03
sponsoring the cost for it but we are maintaining and running the server for the public Valhalla instance we have the web address which is open source we have a Docker image we have a qgs plugin we have the package hyphen bindings
25:21
and and there's also some demos and that's it thank you very much