[pgrouting-dev] pgRouting and the Shortest Path Shooting Star
algorithm
Stephen Woodbridge
woodbri at swoodbridge.com
Thu Mar 8 09:21:12 EST 2012
Espen,
I have CC the list as there might be helpful information to others in my
response.
I get the following results on my Linux system. Is this what you are
getting on your system?
trsp_bug=# SELECT kollektivnett32.objid::integer, qry1.*
FROM turn_restrict_shortest_path(
'SELECT gid AS id,
source::int4,
target::int4,
minutes::double precision AS cost,
rminutes::double precision AS reverse_cost
FROM kollektivnett32',
17914,
24470,
true,
true,
'SELECT to_cost,
gid AS target_id,
rule AS via_path
FROM kollektivnett32_turns
WHERE costtype=''V''') qry1
inner join kollektivnett32
on qry1.edge_id=kollektivnett32.gid;
objid | vertex_id | edge_id | cost
-------+-----------+---------+-------------------
39510 | 17914 | 39553 | 1.22921517354843
39503 | 19542 | 39546 | 1.16385126125265
39502 | 15062 | 39545 | 1.13463764875839
39501 | 10238 | 39544 | 0.894134798291999
39495 | 19538 | 39538 | 0.866380394768565
39496 | 19468 | 39539 | 0.933687082563116
39497 | 19470 | 39540 | 0.657732599215612
39498 | 19473 | 39541 | 0.908336115840503
39499 | 19452 | 39542 | 0.375975675882557
39500 | 9999 | 39543 | 0.467548379399679
39493 | 18169 | 39536 | 0.722558560770379
39492 | 19474 | 39535 | 0.359215445372181
39491 | 18166 | 39534 | 0.372316300710597
39490 | 6151 | 39533 | 0.7529314841121
39514 | 14128 | 39557 | 0.247611717608335
39513 | 2820 | 39556 | 0.642005590638696
39494 | 19535 | 39537 | 1.08148812344578
39475 | 19518 | 39518 | 0.985412403126148
39476 | 19519 | 39519 | 1.00870667860245
39477 | 19524 | 39520 | 1.10356478488934
39478 | 7347 | 39521 | 2.31489365914156
2912 | 19418 | 2630 | 0.710630767866117
(22 rows)
Ok, I have a couple of observations:
1. the route does not get to the destination node which seems like that
might indicate a bug
2. I see you are using "rule AS via_path", is rule formatted the way you
would pass it to shooting_star? If so this is wrong. I unfortunately
implemented via_path to be a list of edges in the reverse order of rule.
IF for RULE:
target_id: 1, rule: 2,3,4,5
THEN for via_path
target_id: 1, via_path: 5,4,3,2
Since all your restrictions only involve a single edge this does not
matter. So moving on to the next potential problem. Consistency of edge
ids could be a problem.
For example, in the kollektivnett32_turns table what are the target_id
and rule ids? These should be the edge ids not the node ids and you
using: gid, objectid_1, objectid, or some other field for these values?
When you select your edges in the first query you have "gid as id", you
have to match the column used in the kollektivnett32_turns table as the
edge id to define the id in the first query. So if the
kollektivnett32_turns uses objectid values your first query needs to be
"objectid::integer as id"
Also it would be good it you can reduce the problem to a simple 10-20
node/edge graph that is easier to debug and understand. Most cases can
be demonstrated using a simple graph like:
o o
| |
| |
o---------o---o--------o
| | | |
| | | |
o-------o---------o---o--------o---------o
| | | |
| | | |
o---------o---o--------o
| |
| |
o o
Just label the nodes and the edges, and set up the restrictions, then
you can run simple tests to verify that it works as expected on simple
cases.
-Steve
On 3/8/2012 5:12 AM, Espen O wrote:
> Hi
>
> Here is our testdata http://dl.dropbox.com/u/525315/example.rar
>
> It contains the following:
>
> *File *
>
>
>
> *Description *
>
> Kollektivnett32.sql
>
>
>
> Network table
>
> kollektivnett32_turns.sql
>
>
>
> Turn restrictions table
>
> example_query.sql
>
>
>
> Example query from node 17914 to 24470
>
> expected_route.jpg
>
>
>
> Image of expected result (24,2 minutes including turn costs)
>
> Regards Espen
>
>
> > Date: Wed, 7 Mar 2012 10:43:50 -0500
> > From: woodbri at swoodbridge.com
> > To: pgrouting-dev at lists.osgeo.org
> > Subject: Re: [pgrouting-dev] pgRouting and the Shortest Path Shooting
> Star algorithm
> >
> > On 3/7/2012 8:39 AM, Espen O wrote:
> > > Hi
> > >
> > > We are very interested in version 1.03/1.05 of pgRouting and the
> > > Shortest Path Shooting Star algorithm. However, there is a problem with
> > > way restrictions in shooting star if there is more than one rule for an
> > > edge. It also doesn’t seem to take into account the reverse cost.
> We are
> > > interested in fixing these bugs.
> > >
> > > Stephen Woodbridge has developed an alternative
> > > “turn_restricted_shortest_path” which is very promising. We have tested
> > > the Windows version compiled by Sanak (2012/03/04), but it is very
> > > unstable and seems to return inconsistent answers when running the same
> > > input data multiple times.
> >
> > Hi Espen,
> >
> > I would like to get a copy of you graph and queries that return
> > inconsistent results. I have not seen this behavior and I think I need
> > to understand what is happening. If we have a bug I want to get it fixed.
> >
> > Can you dump your database something like:
> >
> > pg_dump -fP -Z0 -f mydump.sql.gz -t <table_1> -t <table_2> ... -U <user>
> > -h localhost <mydatabase>
> >
> > and email that and the queries you are running. I would be greatly
> > appreciated and I will analyze it and get any bugs fixed that we need to.
> >
> > Thanks,
> > -Steve
> >
> > > We are working on Windows 2008 server 32 bit, not Linux. Is there
> anyone
> > > who can give us the detailed setup for compiling on Windows (pgRouting
> > > 1.03 2010/01/30 by Martin is the most stable we have tested) so we can
> > > start to debug the source code? We have tried Sanaks recipe
> > > (/sanak/pgrouting/blob/master/BUILD.msvc90), but we get a lot of errors
> > > (Microsoft Visual C++ 2008 Express Edition and the required libraries).
> > >
> > > Regards
> > > Espen
> > >
> > >
> > > _______________________________________________
> > > pgrouting-dev mailing list
> > > pgrouting-dev at lists.osgeo.org
> > > http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
> >
> > _______________________________________________
> > pgrouting-dev mailing list
> > pgrouting-dev at lists.osgeo.org
> > http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
More information about the pgrouting-dev
mailing list