Route Planning in your Database with pgRouting


Formal Metadata

Route Planning in your Database with pgRouting
Title of Series
Vergara, Vicky
CC Attribution - NonCommercial - ShareAlike 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 and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this license.
FOSS4G, Open Source Geospatial Foundation (OSGeo)
Release Date
Production Year
Production Place
Seoul, South Korea

Content Metadata

Subject Area
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide shortest path search and other network analysis functionality. This presentation will show the inside and current state of the pgRouting development, from its wide range of shortest path search algorithms to driving distance calculation or Traveling Sales Person (TSP) optimization. Additionally we will give a brief outlook and introduction of upcoming new features like the Vehicle Routing Problem (VRP) solver, and what we have in mind for future releases. We will explain the shortest path search in real road networks and how the data structure is important to get better routing results. Furthermore we will show how you can improve the quality of the search with dynamic costs and make the result look closer to the reality. You will also learn about difficulties and limitations of the library, and when pgRouting might not be not the right tool to solve your routing problem.
Point (geometry) Arithmetic mean Computer animation Mapping Key (cryptography) Integrated development environment Database Letterpress printing Quantum Planning Line (geometry) Mereology
Graph (mathematics) Open source Software developer Cellular automaton Database Projective plane Functional (mathematics) Library (computing)
Read-only memory Collision Graph (mathematics) Presentation of a group Length Transformation (genetics) State of matter Multiplication sign Scientific modelling Online help Parameter (computer programming) Weight Mereology Graph (mathematics) Food energy Field (computer science) Number Revision control Video game Computer cluster Causality Computer configuration Database Extension (kinesiology) Metropolitan area network Social class Graph (mathematics) Information Software developer Moment (mathematics) Cartesian coordinate system Grass (card game) Functional (mathematics) Sequence System call Table (information) Graph coloring Personal digital assistant output Routing Row (database)
Web page Read-only memory Game controller Graph (mathematics) Process (computing) Code Multiplication sign Planning Line (geometry) Mereology Cartesian coordinate system Graph (mathematics) Functional (mathematics) Connected space Query language Database output Flag Resultant Library (computing) Reverse engineering
Pairwise comparison Augmented reality Control flow Distance Functional (mathematics)
Graph (mathematics) Process (computing) Information File format Gene cluster Line (geometry) Weight Graph (mathematics) Frequency Numeral (linguistics) Database Arrow of time Reverse engineering
Sampling (statistics) Weight Functional (mathematics) Resultant Power (physics) Table (information) Reverse engineering Condition number
Default (computer science) Graph (mathematics) Graph (mathematics) Causality Multiplication sign Weight Bounded variation Reverse engineering Electronic signature
Functional (mathematics)
Algorithm Graph (mathematics) Code Software developer Moment (mathematics) Parallel port Mass System call Connected space Degree (graph theory) Flow separation Summation Root Lecture/Conference Duality (mathematics) Formal grammar Representation (politics) Resultant
and thank you I'm going to talk about this shortest bad 13 your database and more part of the more is a love of my work to what I do so the 1st thing I'm going to show you is upon 1 quantum that red in Spanish said the mean and they fumbled where euphytica amino another month them 90 like amino sensor coming on a map which in English what your foot prints of the path and nothing more there is no path the path is made when walking and that plan these from environment so after that point let's start presenting myself I am city everything about anarchist I am an economy used the ideas that's why there's a line there that acts and known as the key so please sit and call me begins when you find the underweight my name's pretty long and
I'm going to talk about that PU routing project I'm going to give to focuses 1 use like for the developer for they I end users the other 1 is going to be like focusing for developer of an other functionality for the Pew routing so the 1st thing is I'm going to arms say thank you to all those open source projects that because they are we can be so thanks tuples rescue outposts induced I have a C + + graph library around thanks to them we're also proud to be also
an open source project please don't forget to focus on the top 1st thing that's this year the routing is salivary that's going to provide functionality in the database for routing the I which might await took me here I wanted to run out when they from my house to my that cells and that's why I'm here right now that was like 3 years ago the truth is that they could sing
along row so let's start routing and when you want to rout you want to see what's your application and then you go to the man 1 C 0 I have all these options so right now my application these I want to make this presentation and then choosing from all these functions extract so let's try to blow that routing with Newton the 1st thing we have to do we have to create or database i'm because we are an extension of PostGIS we need to create bolss use extension and then we create our extension that is peter out it was well after that we need to vote our day that maybe wasn't transformations and we can go and SQL queries I in this case we chose Dykstra and we have in these these 4 parameters the 1st parameter is that Beck's that's going to give of the information on the enough formant emphatic ASQ help and about the edges of the graph that we're going to be using true to dwell writing routing then there 30 is that I I want to rout from . 30 that stick it sounds and I want to go to 0 . 60 that is the is father's house using an undirected graph maybe we're going walking so it doesn't matter if I call or come from it out the what's that came pretty ugly here but if there's a table and you can see how we get a sequence of edges so we can get a sequence of models we get that cost and we get an aggregated cost so let's analyze a little and going from node 30 to node 44 we're using edge 53 the and the cost of that x is these are 591 10 thousands and then aggregated cause you can see that it's all over to the next row because the aggregated coast of which you know 30 because I'm starting from 0 38 well it's 0 I have been moved the so we should remember these because I'm going to mention that I remember that table will it will be the state so when and that I am an economist I told you right so this lack part of the field this everything is linked together costs because can be virtually anything whatever you want and Titan length energy so let's see 1st hand that say that is like a handle my course will be based on mangled I conceived for these edge a and that if I go down well even in they could in the balls while so I'm going faster if I go up I've inspired so I multiply them by doing a different and number or a revision also it's the same things does written differently and then I modify the cause of the length it's like the end goal it's going and going to reduce the cost the next example it's and well this trait is not so pretty and it's collide kind of Monday so this 1 is based on the time maybe a how about time parameter somewhere in my database and I'm going to multiply by a weight penalty because it's very what OK now we want to rout the house and pals we're not going to rattle them in a residential area so how are we going to tell PT routing that we don't want these cows the goal in front of my house and we're going to tell it using a negative sign because our functions will not to even insert edges that have a negative value they and in this case we're saying that the reverse class the Coast Guard or the cows come will be the same on the rural edges finally all the other day somebody's took me hiking and things but it wasn't snowing out we can also are used the value that probably we didn't even think in this case and thinking about color it's the cost is going to be based on color so going out more calories going down this calories than always things gluttony deviance no I in a life OK so this is and then all that 1st part it's about they they user and going to do these routing so and In the easiest of what's going on it includes something about the final user and a lot about they a developer that wants to do more functionality each year routing so it's Taoists version 3 . 0 and we have some calls goes for developers I the most functions for the graphs graph are and very easy to follow so we want to make these the I use of directed and on they rectum graph of wars moreover to mean on more nice for belabor sarin used to code in C + + and we want to create an internal library for of those that we have for our users is to support begin to get like all the data from OSM and have that ADB into here is like everybody wants BigInteger there's no for all we must do it now we want to avoid clutter user contradictory input but you will see why in a moment and that means that
India we want to keep the grass in memory to speed up sub-sequences blessed have about where you want to let it takes too long so here's our rolled and
we want to minimized minimize and find our path to go from 2 . 0 for the future this is how routing works you have your application you make a query to the database the database may set connection there with the connection the graph is starts to be built and the more edges your graph the more time it's going to take and so they have more or in this talk is going to be handed even pages got some leaping 1 of the graph the loading we can't Brussels at we give the result back the connection disappears and if we want to make the same query well we have to go through all that process again so that's part of they will want to keep the graph in memory to make subsequence requests without being it having to a graph again that is 1 the salt
another thing that is focused on the blockers we had this goal code and we'll need and doing this new complicated cold and I saw that the mother routing function there's these 500 wines of complicated go that I can use so and make a copy with control going to to and like this and what happens well that complicated cold it was 500 lines and not going to find the unresolved issues so what is happening but it's that that come that oversold each tool has been spreading around now let's talk about the use of contradictory input and here is our the flag that says that I don't have reversed course column and what do you see here reverse course columns so do I have or I don't and has a appear routing well the make and whatever because you're not decided In here will here's a troll and I don't see it so what what do I have to do remove that flat and even very if if I see it then you the user wants to use that if I don't see it then they use of performance please so we have a plan and our plant east of 1st of all make precise definitions of graphs and however the gradual creation of that internal library that will avoid that copy paste with a very oversold issue and incremental releases uh from the last time now routing from this wasn't 2013 while that the previous to the last and so in 2 years nothing was them a lot because there was these kind of issue that the them allow us to do more so we have this is 2 . 0 we want to get here using a library approach so the routing would cover library the and EPU routing is a library for for the database so it is kind of a library of the library now 2
. 1 2 . 1 was released like this 7 of this month so just before coming to their could be a orient and
this is what it has but for his release because it was made so fast was decided that they're augmentation will remain so that the people can have the chance to compare what was it about want to be using their functions that were modified the functionality that was modified was driving distance and Dykstra so of course for backwards compatibility the functionality remains whether the commentation you will be able to see how it was before so that you can make these comparisons at all yes we're getting somewhere and whenever it is possible I will be adding more functionality especially when it doesn't break more
so we have here that not only we can make use begin to we can basically make use of any kind of in way and in turn ID or any numerical twenties cluster reverse cos
columns and we also would be the Our precise definition of what is a weighted undirected graph here period means when those that says that simple we have no from readers 6 closed 48 and the reverse clusters 38 from 3 to weights when 5 so this is how we store they in formation in the database and this is what you the interpreted when we're processing it which are too very different things these air divides the same is this is precise information of a weight undirected graphs and now for the weighted undirected graph with the same there that I that I showed you can see that there are all going and coming Our shown in each 1 hour I'm going to be representing that with a line without arrows animation that's
what now also this is a precise definition of what the results of the dykstra will be interpreted on their table remember that table that I told you remember the table at the beginning this is basically saying mathematical what I said verbally describing that table the there in the recommendation we always use of a sample that power over the conditions of what I call it and all the functions of there examples using that sample that that so I actually made although there are possibilities for that sampled that the how it looks weighted with reversed course on weighted without reverse cost so that you can see
what happens if you say I
want to work my data with all um an undirected graph we've of weighted we've reversed cause for what happens if I don't put reverse cost self now let's see how they signature looks yeah I can see the reverse cost here so I want to use that so that says with reverse cost and then the flat I have to worry is they undirected or their there at flat in here it says false so I don't want they directed graph I want the undirected I don't see reverse got and then still working in an undirected graph so
let's see what happens with a directed the same thing the reverse cause there I want to use it is not there I don't want to use that there's a truth I want to use and their active graph but also there is the default if you right that's true the default is going to be true and the reason for that is that as you could well and and say that we the reason for that is that when you have a a graph and you can represent an undirected graph on a directed graph of not the country so my time is running out would have many variations one-to-many many-to-one many-to-many
and I'm going to say that for 2 . 2 this will be the functionality but the documentation of the 2 . 0 will disappear so we're keeping their about watts compatibility they the eventually will will
reach tool 3 . 0
and this is how I want a final thing to
that's the famous stadium OK I think my 10 solar thank you very much the
thanks very much thanks for that In metaphor and Representation questions please yes please e-mail opinion some all disputing other they're more likely that a star like it did occur so that is how to implement a year parallel style I mean with where not of our you CPU him multi-core but I think the do if there was some mass of the pool implemented PUT in 1 of the you know other 0 million parallel empowered away OK measured in Mosul for they the algorithms about routing thereof of for solving very complex problems and i years I had been thinking all I want to use probably somebody if you go to their documentation about their connection with POS grows it tells you draw on its dual problem the sum non spin bones 38 out an there are reasons that their unknown for mean these moments but 1 of the that's why I want these are the that's meant to be done eventually like OK call pose grammars for once and then everything's in there then eventually I will be able to make our yeah routing to run in parallel and use several costs and depression thank you for the food of sorry i in the pores of tried to use the duality linkages and degrees under really know it's getting any headway but when I try to limit 100 despotically uploading used and graph rather then graph root you noticed under result was quite incredibly their way don't need these interviews all of you is that would kill he's at the developer forward there until his later for PG routing and he's not right now I leave them also he developed but for sure and sure that they've you're using a small dataset you're noticing very weird things remember the copy that code with an unsolved issue they down results each are still there you have notice their mistake if you are using a lot dataset yeah OK thank you very much taking if


  550 ms - page object


AV-Portal 3.11.0 (be3ed8ed057d0e90118571ff94e9ca84ad5a2265)