Bestand wählen
Merken

Shortest Path search in your Database and more with pgRouting

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
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
Softwarewartung
Open Source
Klasse <Mathematik>
Projektive Ebene
Wort <Informatik>
Softwareentwickler
Datenhaltung
Code
Datenhaltung
Biprodukt
Computeranimation
Offene Menge
Dienst <Informatik>
Wellenpaket
Forcing
Software
Selbst organisierendes System
Code
Güte der Anpassung
Relativitätstheorie
Mobiles Internet
Vorlesung/Konferenz
Dienst <Informatik>
Kombinatorische Gruppentheorie
Standortbezogener Dienst
Open Source
Algorithmus
Open Source
Programmbibliothek
Vorlesung/Konferenz
Projektive Ebene
Kartesische Koordinaten
Maßerweiterung
Varianz
Beobachtungsstudie
Algorithmus
Lineares Funktional
Bit
Codierungstheorie
Datenhaltung
Güte der Anpassung
Quellcode
Homepage
Kürzester-Weg-Problem
Dijkstra-Algorithmus
Algorithmus
Arithmetische Folge
Tourenplanung
Äußere Algebra eines Moduls
Programmbibliothek
Maßerweiterung
Dijkstra-Algorithmus
Parametersystem
Lineares Funktional
Befehl <Informatik>
Menge
Datennetz
Mereologie
Abfrage
Maßerweiterung
Routing
Bildschirmfenster
Datenhaltung
Parametersystem
Punkt
Vorlesung/Konferenz
Bildschirmfenster
Attributierte Grammatik
Resultante
Retrievalsprache
Puffer <Netzplantechnik>
Prozess <Physik>
Menge
Abfrage
Soundverarbeitung
Parametersystem
Shape <Informatik>
Dicke
Subtraktion
Präprozessor
Schießverfahren
Datennetz
Datenhaltung
Abfrage
Systemaufruf
Kartesische Koordinaten
Räumliche Anordnung
Konfiguration <Informatik>
Internetworking
Energiedichte
Festspeicher
Dreiecksfreier Graph
Mereologie
Lineares Funktional
Parametersystem
Prozess <Physik>
Datenhaltung
Güte der Anpassung
Schreiben <Datenverarbeitung>
Kartesische Koordinaten
Räumliche Anordnung
Overlay-Netz
Code
Richtung
Puls <Technik>
Funktion <Mathematik>
Formale Sprache
Loop
Schwimmkörper
Tourenplanung
Entropie
Attributierte Grammatik
Softwaretest
Deltafunktion
Shape <Informatik>
Punkt
Datennetz
Reelle Zahl
Kategorie <Mathematik>
Stichprobenumfang
Schaltnetz
Vorlesung/Konferenz
Transportproblem
Polygon
Office-Paket
Lineares Funktional
Stellenring
Einheit <Mathematik>
Meter
Abfrage
Rechnen
Mailing-Liste
Speicherabzug
Abstand
Rechnen
Polygon
Chi-Quadrat-Verteilung
Computeranimation
Softwaretest
Matrizenrechnung
Lineares Funktional
Parametersystem
Präprozessor
Datenhaltung
Minimierung
Automatische Handlungsplanung
Programmschema
Kartesische Koordinaten
Automatische Handlungsplanung
Term
Quick-Sort
Computeranimation
Task
Scheduling
Task
Tourenplanung
MIDI <Musikelektronik>
Logistische Verteilung
Projektive Ebene
Speicherabzug
Abstand
URL
Ordnung <Mathematik>
Stichprobenumfang
Gruppenoperation
t-Test
Kanalkapazität
Datensatz
Reihenfolgeproblem
Total <Mathematik>
Offene Menge
Zwei
Abgeschlossene Menge
Mailing-Liste
Abstand
Datenstruktur
Ordnung <Mathematik>
Computeranimation
Softwaretest
Parametersystem
Matrizenrechnung
Bit
Punkt
Graph
Datennetz
Mathematisierung
Familie <Mathematik>
t-Test
Verzweigendes Programm
Schlussregel
Quick-Sort
Code
Scheduling
Algorithmus
Arithmetische Folge
Globale Optimierung
Bildschirmfenster
Vorlesung/Konferenz
Abstand
Softwareentwickler
Prototyping
Rohdaten
Mathematisierung
Kartesische Koordinaten
Mailing-Liste
E-Mail

Metadaten

Formale Metadaten

Titel Shortest Path search in your Database and more with pgRouting
Serientitel FOSS4G 2014 Portland
Autor Kastl, Daniel
Lizenz CC-Namensnennung 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
DOI 10.5446/31616
Herausgeber FOSS4G, Open Source Geospatial Foundation (OSGeo)
Erscheinungsjahr 2014
Sprache Englisch
Produzent FOSS4G
Open Source Geospatial Foundation (OSGeo)
Produktionsjahr 2014
Produktionsort Portland, Oregon, United States of America

Inhaltliche Metadaten

Fachgebiet Informatik
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.
Schlagwörter pgRouting
shortest path
PostGIS
networks
routing

Ähnliche Filme

Loading...
Feedback