Shortest path search for real road networks and dynamic costs with pgRouting

Shortest path search for
real road networks

Anton Patrushev

Real road networks

How do they look like?

What makes them real?

traffic lights signs road marking

gid,
source,
source target,
cost,
reverse_cost,
x1, y1,
x2, y2,
rule,
to_cost

target

Traffic lights make you slower.

It means we should increase costs.

B
C
1min
A
D
cost(A)=cost(A)+30sec
cost(B)=cost(B)+30sec
cost(C)=cost(C)+30sec
cost(D)=cost(D)+30sec

Signs tell you about

restrictions and road types.

cost(A)=length(A)
reverse_cost(A)=∞

A

Sometimes the
costs have
different
meaning.

cost(A)=length(A)/2
reverse_cost(A)=length(A)*2

cost(B)=length(B)*3
reverse_cost(B)=length(B)/3

B

A

Turn restrictions
obviously restrict
turns.

B
C
1min
A
D
cost(A)=cost(A)+1min
cost(B)=cost(B)+1min
rule(A)="D"
cost(C)=cost(C)+1min
to_cost(A, D)=∞

cost(D)=cost(D)+1min

Road type signs
can be used for
cost calculation.

Not only types, but
also conditions.

What about road
marking?

...specifies road
types, ...

... and restrictions.

C
A D
B

E

rule(D)="A, B"

to_cost(D)=∞

And you know what's cool about
pgRouting?

All costs are dynamic.
Which is opposite to pre-calculated.

... a sign with
restrictions limited
in time, ...

... bad weather conditions, ...

You don't need to
rebuild and reload

your network...

You only need to adjust the cost for
this particular road.
And next search will go another way.

Cost can be virtually

anything.

It is possible to use pgRouting
with OSM data.

pgRouting can be used for different
kinds of networks.

... or any other
kind of network.

Thanks to sxc.hu for being the best free
photo stock.

Thanks to people who put their photos to
flickr under Creative Commons license.

Just want you to remember

pgrouting.org
georepublic.de
openvrp.com

Recommended