Shortest Path search in your Database and more with pgRouting
Formal Metadata
Title 
Shortest Path search in your Database and more with pgRouting

Title of Series  
Part Number 
14

Number of Parts 
193

Author 

License 
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. 
Identifiers 

Publisher 

Release Date 
2016

Language 
English

Content Metadata
Subject Area  
Abstract 
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.

Related Material
00:00
Presentation of a group
Software developer
Database
Realtime operating system
Database
Variable (mathematics)
Mereology
Neuroinformatik
Mathematics
Computer animation
Core dump
Chain
Right angle
Maize
01:44
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
Freeware
Extension (kinesiology)
Optical disc drive
Library (computing)
Posterior probability
Library (computing)
02:27
Area
Electronic data interchange
Multiplication sign
Travelling salesman problem
Distance
Mathematical optimization
Neuroinformatik
02:59
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
04:34
Web page
Medical imaging
Software bug
Computer animation
05:10
Multiplication
Software
Bit rate
Meeting/Interview
Real number
Energy level
Curve fitting
Junction (traffic)
05:36
Area
Computer animation
Software
Personal digital assistant
Mathematical optimization
Power (physics)
06:12
Type theory
Dependent and independent variables
Type theory
Computer animation
Condition number
Condition number
06:33
Fibonacci number
Computer animation
Multiplication sign
Range (statistics)
Database
Physical law
Database
Extension (kinesiology)
Extension (kinesiology)
07:06
Point (geometry)
Source code
Functional (mathematics)
Information
Source code
Length
Parameter (computer programming)
Mereology
Number
Frequency
Computer animation
Software
Meeting/Interview
Query language
Personal digital assistant
Network topology
Query language
Statement (computer science)
5 (number)
Reading (process)
Resultant
08:34
Computer animation
Software
4 (number)
Maxima and minima
Endliche Modelltheorie
08:58
Mathematics
Software
Oval
Meeting/Interview
Direction (geometry)
Mereology
09:19
Computer animation
Software
Multiplication sign
Average
09:47
Computer animation
Software
Meeting/Interview
Length
Multiplication sign
5 (number)
10:19
Point (geometry)
Ocean current
Mathematics
Web service
Service (economics)
Software
Personal digital assistant
Speech synthesis
Computer network
11:13
Process (computing)
Computer animation
Software
Meeting/Interview
Source code
Installable File System
11:36
Execution unit
Functional (mathematics)
Computer animation
Function (mathematics)
Bit
Function (mathematics)
Geometry
12:14
Point (geometry)
Functional (mathematics)
Multiplication sign
Polygon
Execution unit
Distance
System call
Proper map
Computer animation
Query language
Personal digital assistant
output
Software testing
Office suite
Table (information)
Summierbarkeit
13:16
Functional (mathematics)
Code
Channel capacity
Source code
Maxima and minima
Design by contract
Realtime 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
Projective plane
Feedback
Moment (mathematics)
Constructor (objectoriented programming)
Computer network
Kontraktion <Mathematik>
Type theory
Computer animation
Software
Software framework
output
Resultant
Directed graph
16:14
Execution unit
Arithmetic mean
Computer animation
Software
Personal digital assistant
Reduction of order
Linearization
Design by contract
Computer network
Mereology
Linear map
Kontraktion <Mathematik>
17:02
Metropolitan area network
Scheduling (computing)
Feedback
Firstorder logic
Design by contract
Computer network
Distance
Kontraktion <Mathematik>
Planning
Computer animation
Lattice (group)
Meeting/Interview
Software testing
Metric system
Mathematical optimization
Linear map
17:44
Point (geometry)
Metropolitan area network
Scheduling (computing)
Multiplication sign
Source code
Projective plane
Speicherbereinigung
Cartesian coordinate system
Arm
Mathematical optimization
18:54
Coding theory
Computer animation
Projective plane
Source code
Feedback
Website
Coma Berenices
19:26
Axiom of choice
Email
Context awareness
Presentation of a group
Code
Multiplication sign
Design by contract
Set (mathematics)
Medical imaging
Semiconductor memory
Different (Kate Ryan album)
Computer network
Area
Metropolitan area network
Algorithm
Constructor (objectoriented programming)
Electronic mailing list
Data storage device
Stress (mechanics)
Instance (computer science)
Right angle
Heuristic
Reading (process)
Resultant
Point (geometry)
Web page
Overhead (computing)
Open source
Distance
Binary file
Rule of inference
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
Logic
Query language
Personal digital assistant
Network topology
5 (number)
Hydraulic jump
27:04
Computer animation
00:00
it the money in my name is and
00:11
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
01:47
what what is feuding this is the global acute defined and
01:52
it's an extension as an extension for postChristian 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
02:29
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
02:40
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
03:04
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 onetomany manytoone or manytomany 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
04:29
very soon we will release a new version and some of them using that later so why why why
04:36
would use you I mean you can use
04:39
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
04:48
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
05:11
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
05:21
very complex very that you have like crazy junctions all the place where I live and you have much
05:28
more to be multiple levels slots high rate is a real highway and than other places
05:36
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
05:52
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
06:13
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
06:23
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
06:35
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
06:47
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
07:08
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
08:20
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
08:36
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
08:45
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 oneway
08:53
streets solution only go 1 way and the other 1 is modeled if you write a car but in this example
09:00
you can go in this direction not in the opposite along and the interest in
09:05
most of the interesting part is that costs can be dynamic so we don't precalculate every
09:11
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
09:22
if any restriction applies that
09:25
is only for some time then you can take care of this and there are many
09:31
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
09:48
example you could also worried about the data you can hand the rest of the time postChristian 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
10:02
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
10:22
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
10:34
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 longdistance 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
11:15
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
11:32
OpenStreetMap and that could be
11:36
trained on our new cable like that electricity and what telephone cables and what
11:46
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 lowlevel 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
12:15
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
12:57
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
13:18
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
13:56
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 realtime 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
16:17
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
16:48
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
17:04
2nd 1 contraction and I
17:06
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
17:21
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
17:45
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
18:44
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
18:55
you if you're interested that the
18:58
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
19:10
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
19:27
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
20:20
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 bidirectional 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 postChristian 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