pgRouting/pgrouting — Issue #52: Driving Distance vs AStar Path issue
Author: woodbri
Created: 2012-02-14 15:37:06+00:00
State: open

Samuel Schembri reports on 2012-01-16:

I used pgrouting 1.02 on postgres 8.2.17. At this time, I can't update Postgresql.

There is a different comportment between 'shortest_path_astar' and 'driving_distance' functions when I use reverse_cost column.

Here are graphe conditions :

For each edge without one-way : cost=reverse_cost=length
For each edge with one-way similar to digitalisation way : cost=length reverse_cost=-1 (or 100000)
For each edge with one-way inverse of digitalisation way : cost=-1 (or 100000) reverse_cost=length
All another edges are not in graphe.

shortest_path_astar:

has_reverse_cost = false :
Edges with 'cost=-1' are forbiden and Pgrouting don't used them. 'Reverse_cost' information is not used.

has_reverse_cost = true:
Edges with 'cost=-1' are used if 'reserve_cost' is more than 0. Cost used by pgrouting is 'reserve_cost' column.
Edges with 'reverse_cost=-1' are used if 'cost' is more than 0. Cost used by pgrouting is 'cost' column.

T his computing is correct.

Driving_distance:

has_reverse_cost = false :
Edges with 'cost=-1' are forbiden and Pgrouting don't used them. 'Reverse_cost' information is not used.

has_reverse_cost = true :
Case one : Edge with 'cost=-1' and 'reverse_cost=length':
Edge can be traveled on digitalisation way ( cost =-1!!). Cost used by pgrouting is 'Reverse_cost' column.

Case two : Edge with cost=length and reverse_cost=-1:
Edge can be traveled on inverse digitalisation way. More, Cost used by pgrouting is 'cost' column.

In this two case, pgrouting don't respect restrictions. This computing is not correct.

Why I would like to used this method. I prefer driving-distance functions because when we must compute a lot of distances with same departure point, this method is more fast than 'shortest_path_astar' method. After, I can get distance with nodes directly.

Example : get distance between shop and 100 customers.

I can create little graphe ,function, and snapshot.

This is zip file with:

*Bug1.png You can see :

- Shortest_path function result : Green line
- Graph with digitalisation sens
- Id of vertex
- One way of 2 edges : red arrows

To go to vertex(48) since vertex (540), pgrouting is doing good choice because the edge (2: gid 51) has a big cost value . Full distance is 1159 meters.

*Bug2.png You can see :

- Driving distance result: blue labels and variant color : Distance ( meters)
- Edges used by pgrouting : blue line
- One way of 2 edges : red arrows

To go to vertex(48) since vertex(540), pgrouting takes the edge (2) with big cost value and he used reverse_cost value to calculate full distance.

Distance vertex must be egal to 1159.

*Dump with my graphe . (create a tif1104 schema before import)

Query:

select *
from shortest_path('
select
id
,source
,target
,cost
,reverse_cost,
to_cost
,rule

from
tif1104.graphe
where
statut is true
order by id',
540,
48,
false,
true )

select
*
from
driving_distance('
select
id
,source
,target
,cost
,reverse_cost
,to_cost
,rule
from
tif1104.graphe
where
statut is true
order by id',
540,
2000,
false,
true)