[pgrouting-users] Problem with way restrictions in shooting star if you have more then one rule for an edge

Stephen Woodbridge woodbri at swoodbridge.com
Wed Jan 11 10:52:54 EST 2012 

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',
    '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 at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users

More information about the Pgrouting-users mailing list