Hi Max,
The bad news:
There are bugs in v1.03 and v1.05 for the shooting star algorithm to the extent that it is pretty much broken at the moment. In addition to that the developer that was working on it has moved on is no longer supporting it. While I was testing this, I found out that the code is also running 3-5 times slower than Dijkstra when we thought it should be running faster, so we are not sure if this is symptomatic of the bugs or just that the algorithm is slower.
The good news:
If you need to support multiple turn restrictions as just developed and added an new branch to git:
https://github.com/pgRouting/pgrouting/tree/trsp
Sorry there is no doc for this yet, but it works and is only marginally slow than Dijkstra.
The big differences at the moment between trsp and shooting star are:
1. trsp is a Dijkstra style solver based on nodes and shooting star is an edged based solver
2. trsp takes a second query string to load the restrictions rather than loading the edge multiple times with different rules
3. The order of the edges in the rules are reversed in the via_path for trsp vs shooting* rules. See the trsp_rest table below. So for example:
target_id: 27
via_path : 1,3,4,5
rule : 5,4,3,1
This might get changed before we release it officially to so both of these are consistent.
As soon as we can get someone to look at the shooting star code we will, but given that we have a faster algorithm already, I could see us potentially drop support for that in the future. Although we have not even discussed that at the PSC or with the user community yet.
Thanks,
-Steve
Here are some examples of how I have used this:
nav11=# \d trsp_rest
Table "data.trsp_rest"
Column | Type | Modifiers
-----------+------------------+-----------
to_cost | double precision |
target_id | integer |
via_path | text |
the_geom | geometry |
rule | text |
Indexes:
"trsp_rest_gidx" gist (the_geom)
I also just extended it to be useful with shooting_path.
to_cost - is the turn cost and the same for shooting_star and for trsp
target_id - is the target edge id where this rule applies
via_path - restriction path for trsp (edge ids)
rule - restriction path for shooting_star (edge ids)
the_geom - this is the_geom of the target_id for bbox searches
How can these be used?
For the trsp we would generate a query like:
SELECT count(*) FROM turn_restrict_shortest_path(
'select edges',
start_node_id,
end_node_id,
directed,
has_reverse_cost,
'select restrictions');
And here is a real query that will work in nav11
SELECT count(*) FROM turn_restrict_shortest_path(
'SELECT link_id as id, source::integer, target::integer, cost_time::double precision as cost,
x1::double precision, y1::double precision, x2::double precision, y2::double precision ,
rcost_time as reverse_cost
FROM st
WHERE setSRID(''BOX3D(-0.208393768115942 51.4715162318841 -0.072463768115942,0.063713768115942 51.6644037681159 0.072463768115942)''::BOX3D,
4326) && the_geom',
'67230',
'214167',
'true',
'select to_cost, target_id, via_path
from trsp_rest
where setSRID(''BOX3D(-0.208393768115942 51.4715162318841 -0.072463768115942,0.063713768115942 51.6644037681159 0.072463768115942)''::BOX3D,
4326) && the_geom' ), st
where edge_id = link_id;
Here is a basic shooting_star query without restrictions:
SELECT count(*) FROM shortest_path_shooting_star(
'SELECT gid as id, source::integer, target::integer, cost_time::double precision as cost,
x1::double precision, y1::double precision, x2::double precision, y2::double precision,
rule::varchar, to_cost::double precision , rcost_time as reverse_cost
FROM st
WHERE setSRID(''BOX3D(-0.208393768115942 51.4715162318841 -0.072463768115942,0.063713768115942 51.6653837681159 0.072463768115942)''::BOX3D,
4326) && the_geom', '1423847' , '2183259' , 'true', 'true' ), st where edge_id = gid;
Which follow this schema:
SELECT count(*) FROM shortest_path_shooting_star(
'select edges',
start_node_id,
end_node_id,
directed,
has_reverse_cost);
And expects the rules and to_cost to be passed with the edges and if there are multiple rules
then the same edge gets passed multiple times. So we can join the edges with the restriction
table as follows:
SELECT gid as id,
source::integer,
target::integer,
cost_time::double precision as cost,
x1::double precision,
y1::double precision,
x2::double precision,
y2::double precision,
b.rule::varchar,
b.to_cost::double precision,
rcost_time as reverse_cost
FROM st a left outer join trsp_rest b on a.link_id=b.target_id
WHERE setSRID('BOX3D(-0.208393768115942 51.4715162318841 -0.072463768115942,0.063713768115942 51.6653837681159 0.072463768115942)'::BOX3D, 4326) && a.the_geom;
And the same embedded in the shooting_star query:
SELECT count(*) FROM shortest_path_shooting_star(
'SELECT gid as id, source::integer, target::integer, cost_time::double precision as cost,
x1::double precision, y1::double precision, x2::double precision, y2::double precision,
b.rule::varchar, b.to_cost::double precision, rcost_time as reverse_cost
FROM st a left outer join trsp_rest b on a.link_id=b.target_id
WHERE setSRID(''BOX3D(-0.208393768115942 51.4715162318841 -0.072463768115942,0.063713768115942 51.6653837681159 0.072463768115942)''::BOX3D,
4326) && a.the_geom', '1423847' , '2183259' , 'true', 'true' ),st where edge_id = gid;
On 1/11/2012 10:11 AM, Max Weninger wrote:
Hi
Thanks for providing the shooting star algorithm.
I am using your shooting star code. The only difference
is that I use a sqlite3 DB instead of postgres. So I only
"adapted" the code of fetching the data from DB to use
the sqlite3 API. The rest of the code is as it is in the
git repository at the moment.
The routing works find in general I only have problems
using certain "types" of turn restrictions. In special
as soon as there is more then one rule for an edge
It seems that it only "respects" the first rule for
turn restrictions and always ignore the other ones.
I correctly provide the "same" edge for every rule and AFAIKT
adjacent_edges is correctly filled with all the rules for this edge.
After that I am "lost" how the "boost" algorithm actually works
and at which point the information from adjacent_edges is used
during routing.
I also tried the same "osm data" with the "original" code
from a postgres DB and the result is the same
An example where it happens is here
routing from http://www.openstreetmap.org/browse/way/34849107
to http://www.openstreetmap.org/browse/way/96379178
As you can see it is not allowed to go "straight" on
still shooting star returns exactly this route
way http://www.openstreetmap.org/browse/way/96379178 has two rules with
to_cost> 100000
from http://www.openstreetmap.org/browse/way/96379173 (only straight on)
and as a second one
from http://www.openstreetmap.org/browse/way/34849107 (only styraight
on)but the second one seems to be ignored and thefore choosen for the route
The correct routing would be to go right to the next roundabout
and back which definitly has a lower cost.
So maybe you can give me some hints how I can debug where the
rules are "evaluated" to see if my "assumptions" are correct
Regards
max
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
