Shortest Path Search
in your Database

... and more with pgRouting

Created by Daniel Kastl / @dkastl

  • Geographer, Mapper, Software Developer
  • Maintainer of the pgRouting Project
  • Founder of Georepublic
  • Living in Germany and Japan
  • Enjoy Open Source FOSS4G

Commercial Services

  • FOSS4G Development
  • Mobile Apps & LBS
  • Open Data & Open Government
  • Training & Consulting
  • Hackathons (Code4Japan)
  • OpenStreetMap

pgRouting Project

An Open Source project, ...

Ein Open Source Projekt, ...

A Library providing ...

A Library providing ...

  • Shortest Path Algorithm
    • Dijkstra, A-Star, One-to-many, All-pair SP.
    • Alternative Routes & Turn Restrictions
  • Traveling Salesperson Algorithm
  • Drivetime Analysis
  • Vehicle Route Problem Solver

Routing in the Database

Create a Database

pgRouting extends PostgreSQL/PostGIS


CREATE DATABASE routing;
\c routing
CREATE EXTENSION postgis;
CREATE EXTENSION pgrouting;
	    				

SQL Query


SELECT * FROM pgr_dijkstra('
      SELECT gid as id,
             source::integer,
             target::integer,
             length::float8 as cost
        FROM ways',
    30, 60, false, false);
	    				

Query Result


seq | node | edge |        cost         
----+------+------+---------------------
  0 |   30 |   53 |  0.0591267653820616
  1 |   44 |   52 |  0.0665408320949312
  2 |   14 |   15 |  0.0809556879332114
  3 |   13 |   14 |   0.072694271986776
  4 |   12 |   13 |   0.081239348480584
  5 |   11 |   12 | 0.00746935522787469
  6 |   10 | 6869 |  0.0164274192597773
  7 |   59 |   72 |  0.0109385169537801
  8 |   60 |   -1 |                   0
(9 rows)
	    				

Flexibility vs. Speed

Variable Costs

Quelle: http://imgs.xkcd.com/comics/goto.png

Custom Functions


CREATE OR REPLACE FUNCTION pgr_fromAtoB(
    IN tbl varchar,
    IN x1 float, IN y1 float,
    IN x2 float, IN y2 float,
)
RETURNS SETOF record AS $$
BEGIN
    FOR rec IN EXECUTE sql LOOP
        RETURN NEXT;
    END LOOP;
END;
$$ LANGUAGE 'plpgsql' VOLATILE STRICT;
	    				

Tour Planning

The Goal

Find the best schedule and route
to visit and complete all tasks?

pgr_vrpOneDepot

Vehicle Routing Problem Solver


SELECT * FROM pgr_vrpOneDepot(
    	'SELECT * FROM vorders'::text,
    	'SELECT * FROM vvehicles'::text,
    	'SELECT * FROM vdistance'::text,
    1 ); 
	    				

(Currently available in "develop" branch))

Sample Application

Optimized Schedule

demo.smartvrp.com

Garbage Collection

Complex Optimization Problem

  • Depot to empty trucks
  • Various vehicle types
  • Different garbage types
  • U-turns prohibited
  • Road-access constraints
  • Special requirements

http://imaptools.com:8080/tt/5

GSoC Project since 2010

  • Multimodal Routing
  • Time-Dependent Shortest Path
  • Graph Partitioning
  • VRP with Time Windows
  • New osm2pgrouting (import, export, OSRM profiles)

Towards v3.0

Goals

  • Better use of Boost
  • Removal of duplicate code
  • Support for big integer
  • Vertex ID handling
  • Smarter "undirected with reverse cost"

An Idea

Keep the graph in memory
to speedup subsequent requests

Interested in pgRouting?