Add to Watchlist

Open Source Street Routing With PgRouting For Local Government - Dynamic Data and Performance

75 views

Citation of segment
Embed Code
Purchasing a DVD Cite video

Formal Metadata

Title Open Source Street Routing With PgRouting For Local Government - Dynamic Data and Performance
Title of Series FOSS4G Bonn 2016
Part Number 54
Number of Parts 193
Author Miller, Joseph (Boundless)
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.
DOI 10.5446/20336
Publisher FOSS4G, Open Source Geospatial Foundation (OSGeo)
Release Date 2016
Language English
Production Place Bonn

Content Metadata

Subject Area Computer Science
Abstract A recap of a prototype project that was created for the NYC Department of Transportation to demonstrate the utility of Open Source routing applications in support of large vehicle permitting processes. The DOT asked us to review software options to support the creation of street route and turn by turn directions solutions for large vehicles entering the city of New York. They needed the solution to be performant, scalable, and to support the use of the city's LION dataset with the dynamic inclusion of street closures, turn restrictions, and weight and height restrictions based on analyst and height restrictions based on analyst data entry. This session will cover the Open Source software we reviewed, our analysis process, and why we ultimately selected PgRouting from a group of candidates that included Open Source Routing Machine (OSRM), Valhalla, and GraphHopper. In particular we will discuss the tradeoffs between schema, data, link traversal costs, and restriction flexiblity and the performance gains offered by indexing solutions using Contraction Hiearchies.
Keywords Boundless
Series
Annotations
Transcript
Loading...
the I don't want to everybody and it is
Joe Miller and professional services engineering balance the
job of the developer but the most prominent projects were and they need integrate open source of from some writing and geocoding as part of it also going to have a lot of fun with GeoServer local-area Jewish children again you name I'm gonna talk a little bit about a project we did a couple months ago with the New York City Department of Transportation in support of their large vehicle permitting process so all talk a little bit about what exactly they were asking about the approaches about what assets they had to to help us and we did a survey of open source routing software with specific criteria someone go through quickly the results of that survey and tell you a little bit about the technologies that we did up picking the the architecture that resulted in release the beginnings of an architecture that resulted in what we've accomplished so far and what we're hoping to do in the in the new feature just by way of background and I think most folks here are aware of the New York City has a large transportation network some statistics 6 thousand miles 800 bridges 24 7 operations that are very many of 12 thousand of sections and 3 thousand light so it's not a small municipal network right now
if if you have a lot of people that you want drive through the city of New York required to go to an office park with like legacy call an analyst
and requested over dimensional permanent and specify exactly what you out in and out of the cities and so is that the rat has to account for the people way has account for the vehicle and has to also take into account road conditions include so this is a manual in-person process and with the department transportation is looking to do is to start on this then they can maybe make it available online so the goal of this project it was primarily a proof of of concept
was to show them that with open source software we could be point-to-point routing and we can take into account designated from crops that they specify addresses points of interest like the bridges and tunnels that taking a Manhattan latitude and longitude that we can run them around a barrier that we grant them around the road closures that have permitted by the performance they know their emergency road closures that they receive notice of and we can write vehicles around those high weight restrictions and turn restrictions some of which are temporal so like 95 you can't turn right you know in the central part of some books of the New York State Science and the output of the system needed to be visualization of the rod and turn-by-turn directions so this is just an example of a couple months ago the
pope visits the city the city shuts down a huge chunk of central manhattan is highly trafficked as you might imagine that a large impact on the truck permitting process and the business of people to do in the city that these are the truck grounds so this is a large part of how the common arbitrary communicates to people right now on the web and new PDFs added that shows that there is a greater truck grounds that they you were required to
travel on until you get so within a couple blocks your final destination so in addition to the well defined from across the actually have a topological complete streets dataset includes as the levels take from bridges 2 tunnels so that they actually have a pretty good data includes the street names includes the address ranges and includes information about where the bridges and tunnels they asked us to do their surveys I mentioned earlier they these are the criteria that 1 itself that was lowered across the not particularly familiar with you know free and open source but obviously I think that's what the intended and they asked us for systems that can take alliance of 1 OpenStreetMap didn't want Google that in what time of year they wanted the system where you can bring your own data they want this is the most flexible so they want they don't want downturn in the system and they don't want for a re indexing and they wanted to be flexible enough that if someone shuts down the road at the immediately have that be reflected in the solutions from the system and they wanted performance which ultimately all talk about a little this ended up being a tradeoff between flexibility in formants And we they had indexing hard decisions and unless they wanted will cost of integration and for that means then that meant that they have primarily c sharp . net developers enhanced people who have some sequel knowledge but not a lot of C + + Java developers that made this an especially challenging so this is the softer that we considered the open source routing machine grasshopper he writing in Valhalla by Masson so 1st open-source router machine obviously license written in C + + there's a Lewis scripting code to the presentation earlier about an hour and a little bit more about how powerful those little scripts can be and still primarily around so this is why the city fell I could fit and it's a fast very very fast system and you know 10 millisecond was the number from around this morning and we usually so that very fast and easy to install and you have this option to switch between Cross profile so we were able to set up a truck profile and use that in theory you could use that profiling system to to insert other information of road closures and restrictions the cost profiles customizable as well using list so even if they don't have Lewis structures in house that didn't seem like a high barrier for for the developers of the state so I just want to draw a mention to about contraction hierarchies just that it's in the way which you get more performance out your writing system so assigned users that graph properties is that uh that allows you to remove nodes out of your solution without losing underlying so how long does it take to world get from node a over to note we know the we keep that information but we decided we don't need don't see in the final solution that's performance but the flip side of that is that you have to bring the system down and I think the number cited earlier was for planets and it was hours like 9 hours for a city size thing maybe maybe it's 10 15 20 minutes but in the middle of a busy day that may not be an acceptable solutions that's a tradeoff that we saw in our research and so the challenges that there was around OpenStreetMap center and it's challenging user-customizable like aligned with the West and then it has a C + + code base that turned off some people the Valhalla and the next thing we looked at as an MIT license are written in C + + again primarily in OpenStreetMap facing solutions to Valhalla has an incredible features it's fast as low memory footprint not as fast as the contraction of the models but it's a lot more flexible in that time 1st of all they store the robots as files and and I think they're they're targeting people are going to use on mobile phones is mentioned in the very clear about that that people who are offline mobile devices will still have access to the routing using the system they lots of costing my costing models which is similar to the profiles itself was around and then use a simple if that allows you to apply at runtime without downtime new information about road closures restrictions so that I was very very attractive option and on the other hand the profiles that you acquire written in C + + so again we ran into this robot procedures and feel like they can maintain and probably the biggest challenge with about is that it isn't so obvious there's no pass and other than a lot of custom code it incorporates something like blind instead of open strings Wade we looked at graphite which is written in Java was the only 1 of the solutions written Java also someone focused on OpenStreetMap but a little more flexible than the other and we found it was very fast has a low memory footprint when you do contraction are these very quick and easy to install there's a Java together as great features like that that you extend a reader class and then you get to include your custom so they they made a very clear afterward and I knew something other than OpenStreetMap and they also when you turn off the the indexing then you have the option to do on bit-reversal false turn restrictions as well so that it's a very positive and the nonetheless extending the reader would have been a significant effort with would take more resources than we had something we were drawn to what we looked into but ultimately decide against really the 2nd factor that they they have a job at the base represented a challenge for a document and the last thing we looked at the PG rating and I think a lot of folks are familiar with the writing and written in C + + it's the process and post GIS extension so this city lights that writing as an option a lot because there is a very simple data schema and their folks even with basic sequel skills to figure out what they needed to do to get data in and out of that exist in the right place in the architecture so rather than a middle tier solution where you got see sharper C + + developers from figure things out anyone who lexical knowledge could be writing stuff against customization of year round and it's straightforward implement custom traverse apart from reflections really is about and populating the right tables and and I'll show that moment as it's very very slow even the solutions that have the indexing turned off significantly faster and and in some really big challenges of our that it doesn't come spoken language driving directions and there's no rest JavaScript API associated with that as well so you gotta a lot of rolling your own stuff In short on the interface this is a technology stack at the city ended up going with on the front and J. aquarium leaflet for for visualization and the middle tier GeoServer force the base maps and spring in time that sitting on top of Java and then a custom driving directions API which I'll talk about in a moment written in the OPT sequel as as a function so that we could then rapid around RPG falls and then we found that uses for posters and world well so I'm not going to use any kind of detail but as the Woodbridge 1 of 1 of the contributors to teaching routing was kind enough to to send us the beginnings of stuff we're turn-by-turn directions and I don't want refer everyone is interested in this problem would be to run it take a look at the level algorithm that he's written up in putting it and then explain step by step how things to look out for learning about how turnabouts reordering of geometry see things in the right and this sequence initially i repetition etc. etc. that was incredibly useful on the and luckily enough to do a
lot around the world and again earlier I heard it was around software books at talking of the challenges that just a little bit attributed only 6 of are so in your city which is kind of shocking but in Columbus Circle is 1 of the and the service wrapper
ended up being 1 of the easiest thing to do other projects as many people are familiar with with gives you a lot of stuff out of the box makes writing services very easy and and you know we were Java consultants coming in to work with C sharp people we wrote a simple straightforward GDC call so that we could eventually hand things over and give them the
simple and and it would be relatively easy to do the transition this is effectively 90 % of our
data model and that's what makes routing so attractive this is a subset of lions and on the upper right hand side uh we've got the truck routes only the 2nd idea maybe a little information about what kind of root is and on the bottom right hand side of the table is just where we told people certain restrictions in and you know label them with weight height and that's all we needed to do really to make this stuff work from a from a data model respect this is the call is a little baby and
it's a little but effectively we're wrapping that driving directions for around
G radical and in the subbands rattle show on the next slide is what we're dynamically inserting with just a little bit of John so we're
just calling there were police stuff from the physical restriction table and the truck Roundtable In the case of the physical restriction table we don't want people to use the segments so orders were giving a negative number and PG routing smart enough to say anything
with a negative number for cost and then avoiding and likewise very small positive number to the truck graphs and the driving this part of the and take that and run vehicles onto those segments and in the common attractive you know they make they make the most attractive
segments for around this is the application where was done
the on the left hand side you can see the driving directions on the right hand side in the mapping secure out going to the same place and 1 of them is using the height and weight restrictions belongs not to what is being sent to the Kerry tunnel due to high with restrictions the other 1 is going on in Brooklyn Bridge which has lots of those concentrations and I just want to draw attention to the bottom right hand corner 1 of the most important things we did for this project highly recommended for anyone ever does this kind work is that we created a very simple QA QC tools well where users to click on different segments and get all the information back from the model so that it find out the segment was part of a truck or they could find out of segment was not topologically connected in a way that they might think it was because of the levels so that we can make that information and then we just the basic cost information as well and so we had a lot of people initially coming up to us and when I use Google Maps I get this right why am I getting this and after like 5 minutes of clicking around here they would they would understand that have some understanding of it and it was the model that is the following you go in search fixed so it's there's a lot of time an and so In the future steps where we want to take this project we
don't take into account the limits of historical traffic data 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 going to and we also want to stand back and QA QC was talking about as well and make it so that you need to click on it you will you will highlight using styles where there are disconnect in terms of the topology all we would highlight where the height and weight restrictions on so that's that's another thing like you but I think a lot of the most important thing that we want to do and I need to find
PG rating people is figure out if there is a weapon approach partitioning the can allow us to distribute the load across all to machines the university like work it was over a 2nd to 3 seconds to do these kinds of queries and the city was you know obviously not happy with that performance when they saw thinking person was circulated to close the gap but this is something we need to investigate and learn a little bit more and lastly the last thing that would like to do cost is go from proof of concept and integration of the overall permitting process so you know how users login have users go through this process and have users pay all in a single single couple of steps on a website I think we see city on a whole lot of money and so that key questions the that
he have so given the to take
away the customer restrictions what you what would you feel just over all the best right class 0 open source and exactly as he has 100 years languages and with his hands the without these restrictions have done influences what would you which choose so I had a conversation earlier was someone I mean there's so many gives some of really Malpensa practically all others for its weaknesses but talking to someone earlier I think there are a lot more use cases out there such systems were not trying to compete with the Google search you know if there some well established stuff for doing basic products so a lot of the stuff that we run into requires flexibility and so I think is enough for those folks who are willing to accept other forms emitted limitations PG running still has the strongest player in terms of of that flexibility but on the other hand there's a lot you can do also with graph upper as well so I was I was very impressed with that the graph property you know what what they're offering them that they were allowed to do both the contraction hierarchy driven like really fast as well as the flexible on-the-fly stuff but I think for those who were looking in the mobile space I think the following is is really got to themselves I don't know of any other open-source projects that are really that focus on minimizing the memory footprint the storage footprint for doing your writing and they do a lot of cool stuff as well so that the 2nd answer you're looking for but those those those are the things we OK
Electronic data interchange
Service (economics)
Computer animation
Oval
Fiber bundle
Chemical equation
Lattice (order)
Interior (topology)
Aerodynamics
Electric generator
Open set
Routing
Statistics
Transportation theory (mathematics)
Open source
Sheaf (mathematics)
Archaeological field survey
First-order logic
Bound state
Mereology
Architecture
Wave
Latent heat
Tablet computer
Meeting/Interview
Bridging (networking)
Operator (mathematics)
Statement (computer science)
Process (computing)
Office suite
Quicksort
Computer architecture
Process (computing)
Software developer
Projective plane
Ferry Corsten
Bit
Maxima and minima
Software
Large eddy simulation
Computer network
Resultant
Writing
Point (geometry)
Vapor barrier
Transportation theory (mathematics)
Open source
Direction (geometry)
Limit (category theory)
Function (mathematics)
Mereology
Weight
Bridging (networking)
Algebraic closure
Visualization (computer graphics)
Process (computing)
Address space
Condition number
Physical system
Direction (geometry)
Point (geometry)
Projective plane
Weight
Maxima and minima
Inflection point
Proof theory
Latent heat
Wind tunnel
Computer animation
Algebraic closure
Visualization (computer graphics)
Software
Condition number
Address space
Java applet
Model theory
Scientific modelling
Programmable read-only memory
Range (statistics)
Archaeological field survey
Traverse (surveying)
Data model
Pointer (computer programming)
Roundness (object)
Computer configuration
Electronic meeting system
Physical law
Physical system
Social class
Scalable Coherent Interface
Mapping
Block (periodic table)
Software developer
Multitier architecture
Interior (topology)
Electronic mailing list
Interface (computing)
Bit
Sequence
Virtual machine
Category of being
Oval
Telecommunication
Figurate number
Writing
Wide area network
Sequel
Open source
Computer file
Robot
Open set
Number
Profil (magazine)
Bridging (networking)
Hierarchy
Energy level
Scripting language
Data structure
Router (computing)
Address space
Computer architecture
Graph (mathematics)
Information
Direction (geometry)
Coma Berenices
Table (information)
Kontraktion <Mathematik>
Spring (hydrology)
Visualization (computer graphics)
Algebraic closure
NP-hard
State of matter
Multiplication sign
Decision theory
Direction (geometry)
Design by contract
Insertion loss
Mereology
Stack (abstract data type)
Weight
Machine code
Formal language
Web 2.0
Bit rate
Data storage device
Extension (kinesiology)
Algorithm
Process (computing)
Reflection (mathematics)
Moment (mathematics)
Open source
Open set
Hierarchy
Right angle
Energy level
Procedural programming
IBM RPG
Read-only memory
Presentation of a group
Divisor
Geometry
Theory
Mach's principle
Social class
Centralizer and normalizer
Read-only memory
String (computer science)
Right angle
Run time (program lifecycle phase)
Addition
Sine
Archaeological field survey
Java applet
Weight
Machine code
Transformation (genetics)
Casting (performing arts)
Subject indexing
Wind tunnel
Computer animation
Vertex (graph theory)
Service (economics)
Application service provider
Service (economics)
Wrapper (data mining)
Wrapper (data mining)
Java applet
Projective plane
Bit
System call
Information technology consulting
Software
Cuboid
World Wide Web Consortium
Application service provider
Group action
Greatest element
System call
Wrapper (data mining)
Weight
Subset
Spring (hydrology)
Root
Implementation
World Wide Web Consortium
Data type
Service (economics)
Information
Geometry
Open source
Length
Weight
System call
Shape (magazine)
Table (information)
Maxima and minima
Data model
Computer animation
4 (number)
Right angle
5 (number)
Booting
Summation
Slide rule
Computer animation
Multi-agent system
Physical law
Bit
Integer
Metropolitan area network
Physicalism
Graph (mathematics)
Mereology
Shape (magazine)
Table (information)
Maxima and minima
Sign (mathematics)
Computer animation
Personal digital assistant
String (computer science)
Order (biology)
Negative number
Metropolitan area network
Greatest element
Mapping
Information
Concentric
Direction (geometry)
Multiplication sign
Scientific modelling
Projective plane
Cartesian coordinate system
Weight
Mereology
Maxima and minima
Computer animation
String (computer science)
Energy level
Right angle
Units of measurement
Arc (geometry)
Topology
Query language
Mapping
Process (computing)
Structural load
INTEGRAL
Line (geometry)
Disintegration
Calculation
Limit (category theory)
Weight
Vector potential
2 (number)
Data management
Bit rate
Term (mathematics)
Single-precision floating-point format
Multiplication
World Wide Web Consortium
Process (computing)
Structural load
Bit
Weight
Transformation (genetics)
Limit (category theory)
Single-precision floating-point format
Proof theory
Computer animation
Network topology
Database
Query language
Computer hardware
Universe (mathematics)
Website
Mathematical optimization
Vapor barrier
Read-only memory
Focus (optics)
Graph (mathematics)
Product (category theory)
Spacetime
Open source
Projective plane
Design by contract
Limit (category theory)
Formal language
Category of being
Computer animation
Meeting/Interview
Data storage device
Term (mathematics)
Personal digital assistant
Hierarchy
Data conversion
Writing
Physical system
Form (programming)
Vulnerability (computing)
Social class
Computer animation
Loading...
Feedback

Timings

  472 ms - page object

Version

AV-Portal 3.8.0 (dec2fe8b0ce2e718d55d6f23ab68f0b2424a1f3f)