Shortest Path search in your Database and more with pgRouting

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
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
Open Source Geospatial Foundation (OSGeo)
Production Year
Production Place
Portland, Oregon, United States of America

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.
Keywords pgRouting shortest path PostGIS networks routing
Word Open source Multiplication sign Software developer Projective plane Software maintenance Social class
Computer animation Database Product (business)
Presentation of a group Goodness of fit Service (economics) Software Lecture/Conference Relational database Forcing (mathematics) Self-organization Wave packet
Algorithm Open source Lecture/Conference Projective plane Variance Extension (kinesiology) Cartesian coordinate system Library (computing)
Web page Shortest path problem Algorithm Observational study Multiplication sign Source code Bit Database Functional (mathematics) Goodness of fit Exterior algebra Extension (kinesiology) Routing Arithmetic progression
Software Query language Statement (computer science) Set (mathematics) Parameter (computer programming) Mereology Functional (mathematics)
Point (geometry) Lecture/Conference Parameter (computer programming) Attribute grammar
Process (computing) Query language Buffer solution Set (mathematics) Resultant
Length Multiplication sign Sound effect Database Parameter (computer programming) Shape (magazine) Mereology Cartesian coordinate system Food energy System call Preprocessor Shooting method Software Internetworking Semiconductor memory Query language Different (Kate Ryan album) Personal digital assistant Computer configuration Cycle (graph theory) Geometry
Overlay-Netz Pulse (signal processing) Code Direction (geometry) Database Parameter (computer programming) Cartesian coordinate system Functional (mathematics) Attribute grammar Goodness of fit Process (computing) Entropie <Informationstheorie> Routing Writing Geometry
Point (geometry) Transportation theory (mathematics) Multiplication sign Real number Polygon Combinational logic Sampling (statistics) Shape (magazine) Dirac delta function Category of being Software Lecture/Conference Software testing Office suite
Computer animation Query language Calculation Polygon Core dump Electronic mailing list Distance Functional (mathematics)
Functional (mathematics) Scheduling (computing) Logistic distribution Projective plane Planning Database Parameter (computer programming) Distance Cartesian coordinate system Functional (mathematics) Preprocessor Uniform resource locator Computer animation Term (mathematics) Order (biology) Core dump Matrix (mathematics) Software testing Quicksort Routing Mathematical optimization Task (computing)
Group action Channel capacity Sampling (statistics) Student's t-test
Computer animation Multiplication sign Closed set Order (biology) Electronic mailing list Total S.A. Open set Data structure Distance 2 (number)
Point (geometry) Scheduling (computing) Algorithm Graph (mathematics) Software developer Multiplication sign Branch (computer science) Bit Student's t-test Parameter (computer programming) Distance Rule of inference Prototype Mathematics Software Lecture/Conference Matrix (mathematics) Software testing Quicksort Arithmetic progression Family Mathematical optimization Window
Email Electronic mailing list Cartesian coordinate system
in hello around them so I see some only faces here I didn't see maybe that's because I missed the last class for the conference in a lot of time and so just a few words about me so I'm and you prefer on the Mapper and I became a softer develop over time and I am and the maintainer of the European project and I found that the company has was which name is due public and so I actually live and work in Germany and Japan mainly in Japan and because there most of all work and I really enjoyed the open source software development and the conference here so we do not only Puritan we have it's during the boat because quake you're involved in some rescue or like GS-activity
ch PDD but In the last
year and we do like you see a lot of a Japanese stuff but I'm 1 of my hobbies and also 1 of the products we started with this bureau from which is the rooting in the database and so
you can find it also on almost your life so if you want to try it out and well and we we provide all the services for related force for the software and training and organize hackathons so I'm now I wanted to do I want to show you what you want enhance and did
anybody use it already but so many so that's good so I I can start that's than the right presentation actually of the bureau thing is the
extension from like POS jails but it drew it requires some the JS so it's an extension of an extension and I of course it's an open source project so that it's released under GPL license them and it's a library that some applications so you you don't get something like Google Maps API for rooting but you can
build it so it's a library that provides the variance shortest path algorithms and for example like stronger
than a star a 1 to many and shortest paths all-pairs shortest shortest-path alternative routes or time restrictions and then you can do to speed actually his personal an algorithm and um there's a drive time analyzes function and I'm what is currently my main interest is the good problem solvers
them it's not released but this study work in progress and I will show you a bit about this later and you will find all the source code and uh workshops and documentation on on the butene page on the top and yeah so I 1st want to tell you what Putin actually does so it's rooting the database and so therefore that you need to create a database 1st and then you have to install these 2 extensions of PostGIS and
Putin and then you have a set of functions I think all was 1 thousand functions altogether and as you can do in SQL query and this can vary from for the bike's front risen looks like this for example and the most interesting part is the right 1 was a red color and because it defines which they tell you load a which network
data you don't have to load all network data you that you know the data you want to and from in this select statement that is the 1st argument of the function you can do everything that SQL allows you to do and so you can select only highways only
and their roles or you can exclude some roles some and then the last 4 parameters of the ball but that but the and that's just the start point and the end point and some
other attributes so after you run such
a flexed select query and you get the query result and that 1 looks like this so it's everyone who used the postcritical Porteous knows that kind of uh look and we get a
result set and this results that you can also post process however you like you can make drawings you can make a buffer is you can make anything that you want to do the and and are that
means that the shootings very flexible so you can do a lot of things but 1 thing a dozen to a dozen preprocess and because it doesn't preprocess it cannot compete for this and in memory and preprocessed rooting engines like um always RM or and that that's maybe a different use case but for example if you change something new database if some energy would change immediately that takes effect was the next query and so for example about this uh Google Maps you might not be able to rule such a such a scenario and so you the whole the speed of calls I don't know if these paths are actually part of the of the rooting network so in some countries in the world and you don't have so nice highways like here in North America so maybe you have just tracks and and they're not part of the of the routine applications we use a more if you have other kind of network so it could be a hiking network it could be from a river network that could be channels um Internet network so putin can be used for anything other than network and the other advantages that um so always tries to minimize
costs and what what costs are is up to you and so the easiest uh cost is the length of the geometry so then you really get the shortest path but I you could uh for example I multiply and your cost with your own parameter so if you can define what this a nice possible cycling then you can make the most beautiful most preferable way for cycling of hiking or on their their their so many options that here if you have some some you'd use case you get this variable costs give you the opportunity to to make some different rooting then price for example of books or some good will allow you to do and the cost can be virtually anything so it could be time that could be gasoline consumption it could be the lengths and of so you can also define uh the the length of the the costs according to the shape of your old network so for example in this case when you drive down your foster probably than a new drive up especially if you use a bicycle so you
have a cost a his directions which are different or the costs can also change at all depending on the time so that if this nice weather and good weather conditions disorders from the very easy to pass but am when there is that there was some rains and it becomes very difficult to to get up the hill and and you could
over the so for example was was porches roster you could maybe overlay your weather data and Mr. geometries and adjust the Costa Book accordingly so what you can do this pulse chase you can do is be wanting to and you can write custom functions so you can um some create for example a function that calculates the route from a to B and doesn't take this complicated looking attributes there are arguments that I showed before but some that it could be just the coordinates of the start and the end point and then internally in this function on a lot of processing is done so this function has been living in a database and you don't have to keep it in your application code so we have done for example draft and analyzes so this was a quite complicated
way to come to calculate a drive time in Denmark using public transportation and uh OpenStreetMap not road network and that we want to see how far you can get from from which place and it was but rather than that was a combination of a lot of false JS and and you wanting to get very detailed from the shape of this time polygon or on this 1 this an example I I hope it works so and for testing
purposes and I think it was a customer in the North America office to for property of the property the real estate abdication and adjusted an API where you don't we have to specify the start point and that the drive time and it is the sample data that you start from this coordinate and then you choose the unit impulse on you want to uh goal and you have a
comma separated list of distances and the query off custom function would look like this and internally it just uses all the core functions and when you start the calculation it and returns you I like 3 drive-time polygons the that's not really difficult actually to to to do some the from what I'm currently
very interested in is adding more functionality in terms of logistics and optimization and and that's because I'm always computing is compared with Google Maps rooting API and here it's just a different different topic from so we it knows no preprocessing so there's no way to to compare this directly from but there's not much available in terms of tour planning and um therefore we and we we set the goal of find for example the best schedule and route to visit and complete by a bunch of tasks and was a assigned locations and um there was was some of core project I'm already last year and it did the 1st attempts that optimizes in some way not really so we good but good enough I think and this function is called uh PGR via a P 1 people and it takes 3 arguments and the 1st is a select of all data of a few orders in your database and the 2nd 1 is select of all the because you have and the sort 1 is a distance matrix and I I will also show you they will again here so from I tried
to this kind of the the testing application made some the from here so you have
because and that have a vehicle ID capacity and decay such abuse action and used by even don't know exactly what the student wanted to do with that and so just sample data like that the 80 those with a capacity of 200 and you have
a single the poll was coordinates and start an opening time in the closing time which defines the the total time span and then you have a list of orders from with there but have to follow a certain structure and I define them as C C is we can use the formant here and then when I when I run this kid you hear it from it
calculates from on the ball and it because it's so 3 orders and the yeah 1 good solution and you see that it calculated uh over 1 thousand distances in I think it takes less than 2 seconds and it doesn't use p wittingly because
using would not be fast enough to do that but for some I showed you that the last argument was a distance matrix and we just use an also around because it's also good enough to get the yet to get rough distances between the points and to do the optimisation the so come down and then you get like your rules displayed and on and there's still some work in progress and you it shows you the schedule in very from that just testing for debugging good so in this last part and after that was of code in 2013 and also in 2014 so am dairy we have some some development uh yeah that's kind of a Q of things that have been developed but are not integrated was because many students have finished at the money and then have a lot than they don't say hello anymore and so we have started multimodal rooting and it lives in a branch I hope that somebody will pick it up and integrated because it's quite some work always and then there's also time-dependent shot shortest path and that uh should there is working as a prototype that means and your your network can change will work during your during a routine time so that when you start it takes into account changes after your start time in the network
and um another thing we read we had just last year was the graph partitioning that's as far as I know or something uh oracle thus Oracle Spatial and and this year to students working on the improvement of the VOP algorithm with time windows and if somebody interested in this this kind of work we have to integrate it in there to make a really sort of this which is quite some work all this so if you need that we're looking for sponsors who can actually come here who help a little bit financially that we can focus on that otherwise after the good on the weekend and my family and it's not so happy about that yeah so if you're interested in imputing I can just talk to
me during the conference on and you go on the website uh you can try the workshops so that that this shows you the basics and I hope to hear from you at least maybe the main list or it could develop something that I sent me an e-mail because I never know if an application uses because it's it's running on the server and
and it's impossible to see so yeah if you have questions from the free to ask the