Shortest Path search in your Database and more with pgRouting

Video thumbnail (Frame 0) Video thumbnail (Frame 2607) Video thumbnail (Frame 3687) Video thumbnail (Frame 4487) Video thumbnail (Frame 6706) Video thumbnail (Frame 7762) Video thumbnail (Frame 8393) Video thumbnail (Frame 9304) Video thumbnail (Frame 9837) Video thumbnail (Frame 10642) Video thumbnail (Frame 12451) Video thumbnail (Frame 13076) Video thumbnail (Frame 13765) Video thumbnail (Frame 14684) Video thumbnail (Frame 15463) Video thumbnail (Frame 16830) Video thumbnail (Frame 17393) Video thumbnail (Frame 18341) Video thumbnail (Frame 19376) Video thumbnail (Frame 19903) Video thumbnail (Frame 20870) Video thumbnail (Frame 24359) Video thumbnail (Frame 25165) Video thumbnail (Frame 25997) Video thumbnail (Frame 26604) Video thumbnail (Frame 28072) Video thumbnail (Frame 28731) Video thumbnail (Frame 30465) Video thumbnail (Frame 40598)
Video in TIB AV-Portal: Shortest Path search in your Database and more with pgRouting

Formal Metadata

Shortest Path search in your Database and more with pgRouting
Title of Series
Part Number
Number of Parts
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.
Release Date

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.
Presentation of a group Software developer Database Real-time operating system Database Mereology Variable (mathematics) Neuroinformatik Mathematics Computer animation Chain Core dump Right angle Maize
Algorithm Open source Algorithm Interface (computing) Open source Similarity (geometry) Cartesian coordinate system Special unitary group Computer animation Software Interface (computing) Energy level Energy level Extension (kinesiology) Freeware Optical disc drive Library (computing) Posterior probability Library (computing)
Area Electronic data interchange Multiplication sign Travelling salesman problem Distance Mathematical optimization Neuroinformatik
Area Metropolitan area network Complex (psychology) Topology Distribution (mathematics) Functional (mathematics) Graph (mathematics) File format Graph (mathematics) Multiplication sign Projective plane Analytic set Arm Revision control Exterior algebra Computer animation Repository (publishing) Function (mathematics) Network topology System programming Routing Window
Web page Medical imaging Software bug Computer animation
Multiplication Software Bit rate Meeting/Interview Real number Energy level Curve fitting Junction (traffic)
Area Computer animation Software Personal digital assistant Mathematical optimization Power (physics)
Type theory Dependent and independent variables Type theory Computer animation Condition number Condition number
Fibonacci number Computer animation Multiplication sign Range (statistics) Database Physical law Database Extension (kinesiology) Extension (kinesiology)
Point (geometry) Source code Functional (mathematics) Information Source code Length Parameter (computer programming) Mereology Number Frequency Computer animation Software Meeting/Interview Personal digital assistant Query language Network topology Query language Statement (computer science) 5 (number) Resultant
Computer animation Software 4 (number) Maxima and minima Endliche Modelltheorie
Mathematics Software Oval Meeting/Interview Direction (geometry) Mereology
Computer animation Software Multiplication sign Average
Computer animation Software Meeting/Interview Length Multiplication sign 5 (number)
Point (geometry) Ocean current Mathematics Web service Service (economics) Software Personal digital assistant Speech synthesis Computer network
Process (computing) Computer animation Software Meeting/Interview Source code Installable File System
Execution unit Functional (mathematics) Computer animation Function (mathematics) Bit Function (mathematics) Geometry
Point (geometry) Functional (mathematics) Multiplication sign Execution unit Polygon Distance System call Proper map Computer animation Personal digital assistant Query language output Software testing Office suite Table (information) Summierbarkeit
Functional (mathematics) Code Channel capacity Source code Maxima and minima Design by contract Real-time operating system Parameter (computer programming) Mereology Product (business) Hierarchy Graph (mathematics) Core dump Software framework Software testing Vertex (graph theory) Algorithm Dataflow Channel capacity Software developer Constructor (object-oriented programming) Projective plane Feedback Moment (mathematics) Computer network Kontraktion <Mathematik> Type theory Computer animation Software Software framework output Resultant Directed graph
Execution unit Arithmetic mean Computer animation Software Personal digital assistant Linearization Reduction of order Design by contract Computer network Mereology Linear map Kontraktion <Mathematik>
Metropolitan area network Scheduling (computing) Feedback First-order logic Design by contract Computer network Distance Kontraktion <Mathematik> Planning Computer animation Lattice (group) Meeting/Interview Software testing Metric system Mathematical optimization Linear map
Point (geometry) Metropolitan area network Scheduling (computing) Multiplication sign Source code Projective plane Speicherbereinigung Cartesian coordinate system Arm Mathematical optimization
Coding theory Computer animation Source code Projective plane Feedback Website Coma Berenices
Axiom of choice Email Presentation of a group Context awareness Code Multiplication sign Design by contract Set (mathematics) Medical imaging Semiconductor memory Different (Kate Ryan album) Computer network Area Metropolitan area network Algorithm Constructor (object-oriented programming) Electronic mailing list Stress (mechanics) Data storage device Instance (computer science) Right angle Heuristic Resultant Reading (process) Point (geometry) Web page Overhead (computing) Open source Distance Rule of inference Binary file Twitter Number Frequency Goodness of fit Term (mathematics) Energy level Software testing Gamma function Dependent and independent variables Graph (mathematics) Projective plane Counting Database Volume (thermodynamics) Limit (category theory) Computer animation Software Query language Logic Personal digital assistant Network topology 5 (number) Hydraulic jump
Computer animation
it the money in my name is and
so in the end of the chain to this session we have 3 presentations the first one is titled shutter part stage in your database and more which PG written by Daniel cast and he gave very little are from June Republic this the colonies disagrees to real time with the to by OpenStreetMap be Juergen and hopefully by Daniel would die and fluorine sorry but if you don't get this pronunciation right my teammates solutions International the and dealing with change all exiled envisioned 5 by just the my books so the the presentations of 120 minutes as that which you would see 5 minutes of questions before which he knew what to do next presented so may I introduce to you the 1st presented you hello everyone and my name is Daniel and I I made this presentation together is making variables in the beauty of it will post Putin core developers and it is in Mexico and I'm usually in Japan and so only I made it to Germany and I want to talk about computing which approach is rooting in the database yeah so
what what is feuding this is the global acute defined and
it's an extension as an extension for post-Christian in a similar way like posteriors and it also requires posted so 1st you have to install the posters and then the beauty and of course it's free software that's why I present here it's open source under the reason the GPL license it's only a low level interface to the algorithms it's not application is library so as to make an application and then you have you have to build it yourself is just provides the tools to do that and that
everybody knows that it can do shortest path search it can do about shortest path search and that there is already a feature that exists for quite a while many yes there are the same as the
driving distance so you can compute catchment areas and I can do as a Crohn's it's also something that is not what you and you can do some optimization for some time already have to be consulted TSP problem the traveling salesperson problem and but there a lot more and my
hand doesn't have enough fingers so I just missed a few things that's that might be of interest so that you can do you can model quite complex time restrictions and the function is called spurious B and now you can also do one-to-many many-to-one or many-to-many shortest paths various alternative routes are possible as well and there are a couple of functions to do this switching topologies to check them to create them and the wouldn't topology for Putin is not but complicated is very simple actually and there's some functions for graph analytics and something that is very yeah they're useful for everyone working was always in data this area there's a imports to a similar to ours into p is here and it can import was wasn't the time in the right format and more and more prebuilt packages that exist so I heard that also windows installation additional was very easy and you can find packages for but there are many Linux distributions and so on I think also that wasn't that Putin is now also in the Debian repositories of the post risk is project and is the quite active community for a rather small project actually and of course this commercial support available if you need that that
very soon we will release a new version and some of them using that later so why why why
would use you I mean you can use
Google Maps like maybe it's not so difficult to convince you this audience not to use Google Maps but but there are many reasons not to use
it but then you could say that's used OpenStreetMap the opportunity cost is reading page and you can this is only the image but you can select was a random and graph by and you know about the priority of by wanting to was available so why why not use them then actually very happy that they exist that because I also
use them sometimes and so in general everybody is rooting for rodent that everybody but most people use it for road networks and road networks that are sometimes
very complex very that you have like crazy junctions all the place where I live and you have much
more to be multiple levels slots high rate is a real highway and than other places
in the world that you're road network looks totally different so I'm not sure this is uh it's possible to to it in this area this Google Maps and but they're there many to use cases we maybe don't think about and
then you also can have when they will recall costs so How do you know what you're doing is always optimization is always and minimizing the costs and the costs can be and many things for example for the cyclist uh this is a problem this is difficult to what people but for power it doesn't really matter what if you go downhill people
from a to B it is a much faster if you go down the you from B to a if you write a bicycle and there are many many
worlds types so sometimes you have restrictions and that you cannot write the spikes selected all responses always because trucks and they also different conditions so this road maybe
this easy to access if the weather conditions if there was no rain but if there's a range and maybe you can't get to the top or it takes much much more time so butane
like I said before is working in the database and so to the to start rooting after you installed at all you have to do is you create a database and a collection of database and then and you have to add to extensions postures and you would think and I'm not doing the workshop again like yesterday but a typical PU
inferior looks like this but it's like a select statement and and and then we have the functions that always start with PG of our and in this case this is the dykstra function and you have a few arguments and usually the 1st argument is a select statement it's a text and and it requires a certain return to a number of problems returned and it's totally up to you how you I make this how you write the select statement so you this is very flexible and this is probably the most interesting part of the reading and then the other arguments is start point and end point and if you're network is directed or undirected a query results usually looks like this so that looks like that just result looks like and and the results you can you can then useful for the period so you don't have to stop here you can take as a result of enjoying it something 1 again aggregator or whatever you want to do so 2 2 things are
important including you always need a source and a network and the source and the target and this is the only information that is necessary in in the you takes topology so it's actually very simple those you in your new
network you have things like traffic lights that nodes for example with traffic lights and you you can make a model that so that traffic lights
slow down your own and you're you're free to do that and I put a penalty for example every node and you can handle one-way
streets solution only go 1 way and the other 1 is modeled if you write a car but in this example
you can go in this direction not in the opposite along and the interest in
most of the interesting part is that costs can be dynamic so we don't pre-calculate every
anything if it is a change in your network and this is only temporary like a road is closed for example or if there was an accident or
if any restriction applies that
is only for some time then you can take care of this and there are many
many ways how this can happen and I don't think that it is important for you then puting is probably a good tool and other other on rooting out what would software might not work so for
example you could also worried about the data you can hand the rest of the time post-Christian as well so if you have the data that is changing the way that you could apply costs the depending on the weather conditions and the cost
can be virtually anything that can be time it can be that doesn't consumption the length that could be the beauty of the world so if you want to make sure that tourism side you could try to define what is beautiful in your network and you make a find the most beautiful that would and if something changed
and the good point is you don't need to rebuild rebuild the network so every change in your network cable and that this has taken care about immediately
and this then this problem that Putin and there's always the problem of flexibility was speech because there's nothing precomputed it might not be a good replacement for your current Google Maps API service so if you if you have big traffic and long-distance rooting and you're not able to to reduce here that the selected network that in this case and but you could you think is not fast enough for you but there are many cases where speed is not so big issue we don't have a web service and then the flexibility might be what you're looking for and also you
you are not restricted to road networks so that it works for anything that is and that has a source and the target and then analyzed in data so it could be candles and rivers and they could be hiding process that also very in
OpenStreetMap and that could be
trained on our new cable like that electricity and what telephone cables and what
what I most what I like a lot of work in this post Christian and posters and you would think that you can use all these functions together you can also build your custom functions like I said before the only the only provides low-level functions that may be produced by a little bit boring output and that you can visualize because the roads geometry is not returned but you you can use everything that SQL provides so you can create your own function
and there's an example a government uh we have to strive time polygons and new user input that is supposed to be 3 distances and instead of making 3 calls I wrote the proper function that does this in 1 function and used to simplify the query to to the documents you need but in this case and you just have a start point and you expect from the table and 3 distances and with the distance you usually have to know in which unit it is so this the time like I was on the test or something else and if
you are interested in computing works and there's a workshop just for this conference it was so there was a major rewrite so a lot of things have changed and it should work also from your home or office so if you're interested what you can do you can try this workshop
there's always some new development and some of this will be there will be a preview in the next release so puting always takes part in the of coordinative every year and this year we're lucky and you have to to to students and and there were exceptionally good and I'm very happy about the result that there there is the product just think of rhythm of code just finish this we have innovation and but we are happy that a preview of these new functions will be already available in this new release so 1 1 thing that
are always wanted to have already is that support for fuel algorithms so at the moment shortest paths was only up there you really of what costs but we couldn't care about the capacity of the network and you might think this is something for reversible what types but they could be altered could be also used to have this is to take and real-time traffic into account like vehicles hold if no on that I think there are plenty of ideas and so this was finally implemented and I think it's possible to do so you have a sink and you have this so the source and a sink and you from there it takes it takes care about the capacity that you you pass as an extra argument here and you can also also provide multiple sources this is currently available only for preview so that be the documentation is not perfect maybe something's going to change in the future and we're very happy about some feedback and the other exciting projects is symmetric contraction so you maybe have heard about contraction hierarchies and all it's usually the secret of all these fast forwarding engines they try to reduce the network size and then it usually helps to speed up large graphs and so we were thinking how can be how can we implement this algorithm imputing and this year and this was uh there was this was tried to the school some of the core project and a contraction hierarchies that the idea is that you you reduce the network size was excluding parts that are not not needed and we tried to have some flexible framework dates not so difficult is it easy to add like new new ways how to how to apply a new operations and currently had 2 operations have been implemented 1 is that contraction and 1 of the linear construction so this was the origin of the test data we have and visited and construction
and try to reduce network parts that are not needed because it's a dead end and linear contractions you can try to reduce the nodes that you tried to to aggregator nodes that are that lives in this case a b and c can be actually and reduces to 81 and on that is the network size is getting smaller
and the network actually in the end only looks like this In this case there are a means by which operations you apply to the 1st operation in our case where the and didn't contraction the
2nd 1 contraction and I
think there needs to be a lot of testing so there's is only now available and the documentation is actually quite good and so we are happy if somebody reads that and tries it out and give some feedback and something I'm personally
very interested is to apply and so besides doing the the easy from start to end you retain that I'm trying to get trying to provide the scheduling and optimization therefore that we also need to attain likely distance metrics lattices but we we tried to that that do things like
here that that's the and like a list of vehicles trucks lorries straight and you have 1 start point and from this point you have to visit multiple applications and do something there also the time you need to take into account and so this is called the include problem solver the tries to optimize on the schedule for each truck and return but that the scheduled for obstructing the best and there's also some the some work going on and we did some projects that should optimize garbage collection and will talk today about this definition so it's not it's partly related to Putin and we want to is a source code available that
has not been put into PUT yet so but this is something I I think that is very valuable for the project the future so if
you if you're interested that the
source code is like so many project is on the top and you can find work from their website there wasn't a Puritan you can find their hands up if something doesn't work like you think that
that we really happy about comments and feedback and pull requests there there's no stupid question question so you can you can ask anything if you ask it on the community channels and
then if you have some question you don't want us there you can also contact me directly and this is the images that you can contact me or you can share it on Twitter come yeah I think this is all about trying to finish at 11 20 so we have some time for questions to you 2 and we have presented some numerical solving the Nicholson for you to ask questions at any questions before greater very much and I had a question around you to about the network contract contraction
of M and was wondering what's the kind of overhead for oak tree in contracted network and that is any way to store cached up so that you don't have to do that every time that you call and then the idea is that you don't do that all the time you write that creating a topology but we didn't test that so much of is really just finished the multiple projects so it's not tested with large data and count term much it was a feature that many people wanted that was a long long time and I think it was some of called topic list of so I think there's there's another point that that these and the other so from that other watching engines to of course they also store everything in memory yet so we we try to reduce the network size is 1 thing but we still we still build used to create a graph with every request right and so we don't keep things we don't build some binary format and loaded in memory but for the system so that we also think about something like this that we can continue to do multiple queries and you don't have to build your graph with every request but construction is just reducing the list size following some operations another possibility of only works there's also this is like what the network itself OK and I have another question such as What which is what kind of uh Aldric's Isely's died Scheffer TG reading is that other kind of heuristics I started things executives at times of algorithms the bi-directional isn't a stars and a lot of a lot of them were were added to the the through the summer of code project so many to get more and more contributions from from people in into the project and based on was added in the hope to speed up things but eventually speeds up something but still the the bottleneck is not the algorithm right so there's not much difference then I must say that I don't use it you have right my question is about the limits them 2 weeks level situation William of the network is still practical to use pages and where to where it was that was the limit by saying for instance as an idea so numbers that they need for the whole planet this works for the whole planet but you need like maybe a hundred gigabytes of of France will be the limit for opportunity that you take a CT or a small country large country look at it I think there's no there's no limit accepted database the problem is that the 1 thing is how much time do you is OK for you to wait for the results so do you ask about like 100 ms 200 was written human is 1 minute OK this is what want 1 this year and next this so you only select the area you care about so you can store a big network in your database but maybe you want to know whether you only would in a small area and so always select what you need that if you make a long distance period you you can apply some some logic like that if my queries long by I started this industry queries and only use like highways for long distance and to connected I raise I make too small period so loading the whole network in memory the the this and aluminum it is I founded on problem to use data sets have from up to half a million and millions nodes was depends on your awareness of 100 but that was something that I'm OK when renewable 1 million know their roles in the network then to then thereafter reduces size visited very carefully the dialog that the user just takes a start point and the end point but internationally how far this is already sent around so that you have to reduce this is more the reducing the size of the the volume that you select this fast year response this but you can store as much as you want in the database at their home what you notice is that takes a more questions this is based all thank you for the presentation I was wondering when using some graph database like new foraging 1 you 1 because when i started Putin there was only a or so this is an extension for post-Christian it doesn't work along that has worked with all this it's like that that but positive posters also it's a different there's a different that project and I think in way of forgery also has a inside of it I don't know if they they can support for example to restrictions but not a lot of time left or maybe even more complicated things I didn't try it of the some advantages to using stress as opposed to some dedicated prior to the the database good but there are cases where you store your data networking and and for me right why I want you know for this because it's an open source I care about you want to have a popular well supported projects and for me was critical posters is probably 1 of them is so that the choice when I can do much more you that's 1 way of choosing the data and the more questions so the point that I is also time to the next 1 of the most people and they have the same almost just because the mean time we have to care that that people can change the rules as well so the general questions just the union of