Open Source Street Routing With PgRouting For Local Government - Dynamic Data and Performance
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Teil | 54 | |
| Anzahl der Teile | 193 | |
| Autor | ||
| Lizenz | CC-Namensnennung 3.0 Deutschland: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. | |
| Identifikatoren | 10.5446/20336 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache | ||
| Produktionsort | Bonn |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
| |
| Schlagwörter |
FOSS4G Bonn 201654 / 193
8
20
21
27
28
34
39
51
53
56
61
64
66
68
72
75
78
79
80
84
104
108
112
120
123
126
130
131
134
135
140
142
143
145
146
153
154
157
160
165
182
183
188
190
00:00
GasströmungGenerator <Informatik>FaserbündelOffene MengeVollständiger VerbandRoutingInnerer PunktOvalDreiElektronischer DatenaustauschDienst <Informatik>AppletProjektive EbeneSummengleichungComputeranimation
00:19
LESQuick-SortArchitektur <Informatik>Befehl <Informatik>Gebundener ZustandTablet PCLokales MinimumSystem FProzess <Informatik>Prädikatenlogik erster StufeWellenlehreSoftwareProjektive EbeneBridge <Kommunikationstechnik>Nichtlinearer OperatorGarbentheorieBitComputerarchitekturStatistikResultanteUmwandlungsenthalpieMereologieOpen SourceSondierungSoftwareentwicklerSchreiben <Datenverarbeitung>Office-PaketProzess <Informatik>TransportproblemIntegralOffene MengeVorlesung/Konferenz
01:42
Gewicht <Ausgleichsrechnung>Prozess <Informatik>UmwandlungsenthalpieAlgebraisch abgeschlossener KörperKonditionszahlLokales MinimumInverser LimesAdressraumWendepunktVisualisierungRichtungPunktOpen SourceFeuchteleitungRichtungAlgebraisch abgeschlossener KörperMereologieSoftwareVisualisierungAdressraumKonditionszahlPunktGewicht <Ausgleichsrechnung>Bridge <Kommunikationstechnik>Projektive EbeneWindkanalPhysikalisches SystemTransportproblemBeweistheorieFunktion <Mathematik>RoutingZentralisatorComputeranimation
02:57
BenutzerbeteiligungMereologieTelekommunikationProzess <Informatik>ZentralisatorRoutingComputeranimation
03:24
MAPGesetz <Physik>SondierungOffene MengeOvalOpen SourceMachsches PrinzipVirtuelle MaschineARM <Computerarchitektur>Hierarchische StrukturKontraktion <Mathematik>DatenmodellMaschinencodeCOMZeiger <Informatik>SinusfunktionROM <Informatik>InformationsspeicherungAuswahlverfahrenVerhandlungs-InformationssystemTransformation <Mathematik>AppletPROMKlasse <Mathematik>Endliche ModelltheorieGewicht <Ausgleichsrechnung>Rechter WinkelSCI <Informatik>RichtungWeitverkehrsnetzInnerer PunktDreiDienst <Informatik>W3C-StandardWrapper <Programmierung>AnwendungsdienstanbieterDesign by ContractMulti-Tier-ArchitekturHalbleiterspeicherMultiplikationsoperatorHierarchische StrukturPhysikalisches SystemMaschinencodeZahlenbereichBitSkriptspracheInformationOpen SourceRouterCoxeter-GruppeQuelle <Physik>AppletLaufzeitfehlerEndliche ModelltheorieAlgebraisch abgeschlossener KörperProfil <Aerodynamik>Physikalische TheorieRobotikKonfiguration <Informatik>Wrapper <Programmierung>ZeichenketteSoftwareDienst <Informatik>Algorithmische ProgrammierspracheOffene MengeElementargeometrieRechter WinkelAutomatische IndexierungSchreiben <Datenverarbeitung>Prozess <Informatik>Klasse <Mathematik>BitrateTeilbarkeitEDV-BeratungSystemaufrufVisualisierungProjektive EbeneQuaderRichtungFigurierte ZahlFolge <Mathematik>p-BlockAdditionUnrundheitComputerarchitekturFortsetzung <Mathematik>SoftwareentwicklerMaßerweiterungMAPAdressraumBridge <Kommunikationstechnik>Formale SpracheInterface <Schaltung>TabelleSpannweite <Stochastik>MomentenproblemPolygonzugWindkanalSpiegelung <Mathematik>Gewicht <Ausgleichsrechnung>Mailing-ListeEinfügungsdämpfungMapping <Computergraphik>SondierungKeller <Informatik>Kategorie <Mathematik>GraphAggregatzustandEntscheidungstheorieDatenstrukturAlgorithmusNP-hartes ProblemListenprogrammgeneratorRoutingVollständigkeitIntegralImplementierungTermGüte der AnpassungFeuchteleitungTesselationVorlesung/Konferenz
11:51
Lokales MinimumQuelle <Physik>Dienst <Informatik>Wrapper <Programmierung>FünfW3C-StandardBootenImplementierungSystemaufrufGewicht <Ausgleichsrechnung>AnwendungsdienstanbieterVierDatentypElementargeometrieOpen SourceShape <Informatik>DickeTeilmengeSystemaufrufGewicht <Ausgleichsrechnung>RoutingDatenmodellGruppenoperationTabelleEinfügungsdämpfungInformationRechter WinkelRichtungMinimumWurzel <Mathematik>Computeranimation
12:30
MehragentensystemSummierbarkeitGanze ZahlGesetz <Physik>Lokales MinimumCASE <Informatik>Metropolitan area networkZeichenketteRechenschieberBitAppletRoutingCASE <Informatik>TabelleNegative ZahlPhysikalismusOrdnung <Mathematik>Computeranimation
12:54
ZeichenketteCASE <Informatik>Shape <Informatik>Negative ZahlMereologieVorzeichen <Mathematik>MultigraphRoutingComputeranimation
13:09
CASE <Informatik>Lokales MinimumZeichenketteKreisbogenMetropolitan area networkRechenwerkMengentheoretische TopologieDatenverwaltungGewicht <Ausgleichsrechnung>W3C-StandardFeuchteleitungRechenbuchInverser LimesMAPVektorpotenzialDesintegration <Mathematik>Prozess <Informatik>Transformation <Mathematik>MultiplikationGeradeEinfache GenauigkeitAbfrageGlobale OptimierungDatenbankLastHardwareProjektive EbeneInverser LimesMAPInformationEndliche ModelltheorieKonzentrizitätEinfache GenauigkeitTermGewicht <Ausgleichsrechnung>MinimumBitrateRichtungMapping <Computergraphik>Web SiteRechter WinkelIntegralMultiplikationsoperatorProzess <Informatik>Kartesische KoordinatenTopologieBeweistheorieLastZweiMereologieAbfrageBitGrundraumPaarvergleichMultiplikationEinfach zusammenhängender RaumRoutingComputeranimation
15:47
CASE <Informatik>Umsetzung <Informatik>RoutingInformationsspeicherungSoftwareschwachstelleGoogolTermProjektive EbeneGewicht <Ausgleichsrechnung>Open SourceDesign by ContractHalbleiterspeicherMinkowski-MetrikFokalpunktGraphKategorie <Mathematik>Schreiben <Datenverarbeitung>Hierarchische StrukturInverser LimesKlasse <Mathematik>BildschirmmaskeFormale SprachePhysikalisches SystemProdukt <Mathematik>ComputeranimationVorlesung/Konferenz
18:01
Computeranimation
Transkript: Englisch(automatisch erzeugt)
00:09
All right. Well, welcome everybody. My name is Joe Miller. I'm a professional services engineer with Boundless. I'm a Java developer, but they mostly throw me at projects where
00:23
they need to integrate open source, other open source projects. So, routing and geocoding is part of it. I also get to have a lot of fun with GeoServer, OpenLayers, GeoShape, GeoGig, you name it. I'm going to talk a little bit about a project we did a couple of months ago with the New York City Department of Transportation in support
00:42
of their large vehicle permitting process. So, I'll talk a little bit about what exactly they were asking of us, what they approached us about, what assets they had to help us out. We did a survey of open source routing software with specific criteria. So, I'm going to go through quickly the results of that survey, tell you a little bit about the
01:01
technologies that we ended up picking, the architecture that resulted or at least the beginnings of an architecture that resulted, what we've accomplished so far and what we're hoping to do in the near future. So, just by way of background, I mean, I think most folks are aware that New York City has a large transportation network. Some statistics, 6,000 miles, 800 bridges, 24-7 operation of the Staten Island Ferry,
01:26
and then they have 12,000 intersections and 300,000 street lights. So, it's not a small municipal network. Right now, if you have a large vehicle that you want to drive through the city of New York, you're required to go to an office, talk with, I
01:41
guess you would call it an analyst, request an over-dimensional permit, and then specify exactly what your route in and out of the city is going to be. So, the route has to account for the vehicle weight, it has to account for the vehicle height, and it has to also take into account road conditions and closures. So, this is a manual in-person process, and what the Department of Transportation is looking to do is start
02:03
to automate this and then maybe make it available online. So, the goals of this project, it was primarily a proof of concept, but was to show them that with the open source software, we could do point-to-point routing, we could take into account designated truck routes that they've specified, addresses, points of
02:21
interest, like the bridges and tunnels that take you into Manhattan, latitude and longitude, that we could route them around barriers, that we could route them around road closures that are permitted by the department so they know they're there, emergency road closures that they receive notice of, we could route vehicles around those height and weight restrictions and turn restrictions, some of which are temporal, so like nine to five, you can't turn
02:44
right, you know, into Central Park. I mean, some folks who've been to New York have seen those signs. And output of the system needed to be visualization of the route and turn-by-turn directions. So, this is just an example of a couple of months ago, the Pope visits the city, the city shuts down a
03:01
huge chunk of Central Manhattan, just highly trafficked. As you might imagine, this had a large impact on the truck permitting process and the business that people have to do in the city that day. These are the truck routes. So, this is a large part of how the department communicates to people right now on the web. It's PDFs that show that there's a grid of
03:23
truck routes that you are required to travel on until you get into within a couple of blocks of your final destination. So, in addition to the well-defined truck routes, they actually have a topologically complete street data set that includes the Z-levels that take you from bridges to tunnels.
03:40
So, they actually have pretty good data, includes the street names, it includes the address ranges, it includes information about where the bridges and tunnels are. They asked us to do that survey, as I mentioned earlier, these are the criteria. They wanted software that was low or no cost, they're not particularly familiar with, you know, free and open source, but obviously, I think that's what they intended. They asked us for systems that could take
04:04
lion. So, they didn't want open street map, they didn't want Google, they didn't want Tom Tom or here, they wanted a system where you could bring your own data. They wanted a system that was flexible, so they don't want downtime in their system and they don't want for re-indexing. They want it to be flexible enough that if someone shuts down a road that they can immediately have that be reflected in the solutions from the system.
04:25
They wanted performant, which ultimately, I'll talk about a little bit, there just ended up being a trade-off between flexibility and performance and they had to make some hard decisions. And then lastly, they wanted low cost of integration and for them, that meant they had primarily
04:41
C-sharp .NET developers in-house, people who have some SQL knowledge, but not a lot of C++ or Java developers, so that made this an especially challenging project. So, this is the software that we considered, the Open Source Routing Machine, Graph Hopper, PG Routing and Valhalla by Mapsyn. So, first Open Source Routing
05:03
Machine, BSD license, written in C++, there's a LUIS scripting, folks who saw the presentation earlier about it and learned a little bit more about how powerful those LUIS scripts can be. And then it's built primarily around open street map. So, this is why the city felt like it fit. It's a fast, very, very fast system, you know,
05:24
10 millisecond was the number thrown around this morning and we easily saw that. Very fast and easy to install. You have this option to switch between cost profiles, so we were able to set up a truck profile and use that. And in theory, you could use that profiling system to insert other information about road
05:40
closures and restrictions. The cost profiles are customizable as well using LUIS scripting. So, even though they don't have LUIS scripters in-house, that didn't seem like a high barrier for the developers at the city. So, I just wanted to throw a mention about contraction hierarchies, just that it's a
06:00
way in which you get more performance out of your routing systems. OSRM uses it. Graph Hopper uses it. That allows you to remove nodes out of your solution without losing the underlying cost data. So, how long does it take me to get from node A over to node E or node B? Well, we keep that information, but we decide that we don't need node C in
06:23
the final solution. That's how you get a lot of performance. But the flip side of that is that you have to bring the system down. And I think the number I heard cited earlier was for Planet, it was hours, like nine hours. For a city size thing, maybe it's 10, 15 or 20 minutes. But in the middle of a busy day, that may not be an acceptable
06:40
solution. So, that's a trade-off that we saw in our research. So, the challenges with OSRM, it's Open Street Map-centric, and it's challenging to use a custom model like Lion with OSRM. And then it has a C++ code base. So, that turned off some people at the city. Valhalla was the
07:01
next thing we looked at. It has an MIT license written in C++. Again, primarily an Open Street Map facing solution. So, Valhalla has some incredible features. It's fast and has a low memory footprint. It's not as fast as some of the contraction hierarchy models, but it's a little more flexible in that, first of all, they store
07:20
their routes as tiles. And I think they are targeting people who are going to use this on mobile phones eventually. I mean, I think they've been very clear about that, that people who have offline mobile devices will still have access to their routing using the system. They have lots of costing models, which are similar to the profiles we saw with OSRM. And then
07:40
they have a system called SIF that allows you to apply at runtime, without downtime, new information about road closures or restrictions. So, that was a very attractive option. On the other hand, though, their profiles that you apply are written in C++. So, again, we ran into this roadblock where the city just didn't feel like they could maintain it. And probably the biggest challenge with Valhalla is that it isn't so obvious.
08:03
There's no path other than a lot of custom coding to incorporate something like Lion instead of Open Street Map. We looked at Graphopper, which is written in Java. It was the only one of these solutions that was written in Java. Also, somewhat focused on Open Street Map, but a little more flexible than some of the others. We found it was very fast, has a
08:23
low memory footprint. When you do contraction hierarchies, very quick and easy to install. There's a Java API that has great features, like that you extend a reader class and then you get to include your custom data in there. So, they've made a very clear path forward on how you can use something other than Open Street Map. And they also, when you turn off the indexing, then you
08:43
have the option to do on-the-fly traversal costs and turn restrictions as well. So, that's a very positive thing. Nonetheless, extending the reader would have been a significant effort, would have taken more resources than we had. It was something we were drawn to when we looked into, but ultimately had to decide against. But really the second factor, that they have a Java code
09:03
base, represented a challenge for a .NET shop, frankly. The last thing we looked at was PG Routing. I think a lot of folks are familiar with PG Routing. Written in C++, it's a Postgres and PostGIS extension. So, the city liked PG Routing
09:22
as an option a lot because it has a very simple data schema. Their folks, even with basic SQL skills, could figure out what they needed to do to get data in and out of it. It exists in the right place in the architecture, so rather than a middle tier solution, where you've got your C Sharp or C++ developers trying to figure things out, anyone who had SQL knowledge could be
09:40
writing stuff against customization of PG Routing. And it's straightforward to implement custom traversal costs and term restrictions. It really is about populating the right tables, and I'll show that in a moment. So it's very, very slow. Even the solutions that had the indexing turned off were significantly faster. And then
10:00
some really big challenges are that it doesn't come with spoken language, driving directions, and there's no REST or JavaScript API associated with it as well. So you've got to do a lot of rolling of your own stuff on the interface side. This is the technology stack that the city ended up going with. On the front end, jQuery and Leaflet for visualization, and the middle tier, GeoServer for some of the
10:22
base maps, and Spring and Tomcat sitting on top of Java. And then a custom driving directions API, which I'll talk about in a moment, written in PLPG SQL as a function so that we could then wrap it around our PG Routing calls. And then we found some good uses for PostGIS and PostgreSQL as well.
10:41
So I'm not going to go into this in any kind of detail, but Stephen Woodbridge, one of the contributors to PG Routing, was kind enough to send us the beginnings of stuff with turn-by-turn directions. And I definitely would refer everyone who's interested in this problem with PG Routing to take a look at the high level algorithm that he's written up and put in GitHub. I mean, it explains step-by-step
11:03
how things to look out for, learning about how to do turnabouts, reordering of the geometry so you get things in the right sequence and make sure that you don't have repetitious names, et cetera, et cetera. And that was incredibly useful on the project. Luckily, we didn't have to do a lot of roundabout coding. Again, earlier I heard
11:20
an OSRM talk where folks were talking about the challenges of that. Just a little bit of trivia, there's only six of them or so in New York City, which is kind of shocking, but Columbus Circle is one of them. The service wrapper ended up being one of the easiest things we had to do on the project. It's like Spring Boot, as many people are familiar with it. Gives you a lot of stuff out of the box, makes writing services
11:41
very, very easy. And even though we were Java consultants coming in to work with C Sharp people, we wrote them as simple, straightforward JDBC calls so that we could eventually hand things over and give them the SQL and it would be relatively easy to do the transition. This was effectively 90% of our data model.
12:00
And that's what makes, I think, PG Routing so attractive. This is a subset of Lion. On the upper right hand side, we've got the truck routes, all we need is the segment ID and maybe a little information about what kind of route it is. And on the bottom right hand table was just where we told people, hey, insert your restrictions in here. And, you know, label them with weight and height. And that's all we needed to do really
12:21
to make this stuff work from a data model perspective. This is, the call is a little big and it's a little hard to read, but effectively we're wrapping that driving direction call around a PG Routing call. And then the stuff in red, I'll show on the next slide, is what we're dynamically inserting with just a little bit of Java.
12:41
So we're just calling, we're pulling stuff from the physical restriction table and the truck route table. And in the case of the physical restriction table, we don't want people to use those segments. So we're just giving it a negative number. And PG Routing is smart enough to say anything with a negative number for cost, I'm gonna avoid it. And likewise, we gave a very small positive number to the truck routes.
13:00
And PG Routing is smart enough to then take that and route vehicles onto those segments. And they're kind of an attractor, you know. They make those the most attractive segments for the route. This is the application when it was done. The, you know, on the left-hand side you can see the driving directions. On the right-hand side, in the map, you can see two routes going to the same place.
13:23
One of them is using the height and weight restrictions, the other one is not. So one is being sent through the carry tunnel due to height and weight restrictions. The other one is, you know, going on Brooklyn Bridge, which has lots of those kinds of restrictions. And I just want to draw attention to the bottom right-hand corner. One of the most important things we did for this project, and I highly recommend this for anyone
13:41
who ever does this kind of work, is that we created a very simple QA QC tool as well, where users could click on different segments and get all of the information back from the model. So they could find out that a segment was part of a truck route, or they could find out that a segment was not topologically connected in a way that they might think it was because of Z levels. So we conveyed that information.
14:01
And then we just gave basic cost information as well. And so we had a lot of people initially coming up to us and saying, when I use Google Maps, I get this route, why am I getting this? And after like five minutes of clicking around here, they would understand, they'd have some understanding of it. And if it was the model that was at fault, then we could go in and start fixing it. So it saved us a lot of time and heartache.
14:22
So the future steps, where we want to take this project, we don't take into account speed limits or historical traffic data yet. And those are things that could be relatively easily incorporated, but would come at a cost in terms of data. So that's something we're pitching the city. And we also want to expand that QATC tool
14:40
I was talking about as well, and make it so that you don't even have to click on it. You will highlight using styles where there are disconnects in terms of the topology, or we would highlight where the height and weight restrictions are. So that's another thing we like to do. But I think the most important thing that we want to do, and I need to find PG routing people,
15:00
is figure out if there is an approach to partitioning that can allow us to distribute the load across multiple machines. Because even for a city like New York, it was over a second, maybe two or three seconds to do these kinds of queries. And the city was obviously not happy with that performance when they saw it in comparison with OSRM. So I feel like we could close the gap, but this is something we need to investigate
15:21
and learn a little bit more. And then lastly, the last thing that we'd like to do, of course, is go from proof of concept into integration to the overall permitting process. So having users log in, have users go through this process, and then have users pay all in a single couple of steps on a website, I think we could save the city a whole lot of money.
15:42
And so with that, any questions?
16:04
So given the, taking away the customer restrictions, what would you feel just overall is the best routing platform? Oh, open source. I'm excited. I think that's why a lot of people are here, is just we're curious about what you found is the,
16:22
like overall, without these restrictions, without .NET influences, what would you choose? So I had a conversation earlier with someone. I mean, so I'm gonna give somewhat of a mealy mouth answer, right? I think they all have their strengths and weaknesses. But talking to someone earlier, I think there are a lot more use cases out there,
16:40
especially since we're not trying to compete with the Googles or the, there is some well-established stuff for doing basic routing. So a lot of the stuff that we run into requires flexibility. And so I think, for those folks who are willing to accept the performance limitations, PG Routing still is the strongest player
17:00
in terms of that flexibility. But on the other hand, there's a lot you can do also with Graph Hopper as well. So I was very, very impressed with the Graph Hopper, what they were offering, that they were allowing you to do both the contraction hierarchy-driven, like really fast stuff, as well as the flexible on-the-fly stuff.
17:21
I think for those who are looking in the mobile space, I think Valhalla has really got it to it themselves. I don't know of any other open source projects that are really that focused on minimizing the memory footprint, the storage footprint for doing your routing. And they do a lot of cool stuff as well. So I don't know if that's exactly the answer
17:41
you were looking for, but those are the things we found. Well, thank you.