Shortest Path search for real road networks with pgRouting

Session Type: 
Tech Session
Presenter(s): 
Daniel Kastl, Georepublic
Anton Patrushev

pgRouting adds routing functionality to PostGIS. This presentation will show the inside and current state of pgRouting development. 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 learn about difficulties and limitations of implementing routing functionality in GIS applications, the difference between algorithms and their performance.

pgRouting includes:

  • Shortest path search (3 algorithms: Dijkstra, A-Star, Shooting Star)
  • Traveling salesperson problem solver (TSP) - Driving distance calculation
  • NEW: Dial-a-ride-problem solver (DARP)
  • NEW: All-pair-shortest-path algorithm (APSP)

pgRouting is an extension of PostgreSQL and PostGIS. A predecessor of pgRouting – pgDijkstra, written by Camptocamp, was later extended by Orkney and renamed to pgRouting. The project is now supported by Georepublic and a broad user community.

Speaker Bio: 

Daniel Kastl is founder and CEO of Georepublic UG and works in Germany and Japan. He is moderating and promoting the pgRouting community and development. He's an active OSM contributor in Japan and an initial foundation member of the Japanese local chapter.

Schedule info

Time slot: 
Wed, 09/14/2011 - 2:00pm - 2:30pm
Room: 
Tower Court D