pgRouting with Shooting-Star algorithm

Important

The content of this page is outdated and is for archiving purposes only.

Shooting-Star algorithm is the latest of pgRouting shortest path algorithms. Its speciality is that it routes from link to link, not from vertex to vertex as Dijkstra and A-Star algorithms do. This makes it possible to define relations between links for example, and it solves some other vertex-based algorithm issues like “parallel links”, which have same source and target but different costs.

Prepare routing table for Shooting-Star

For Shooting-Star you need to prepare your network table and add the “reverse_cost” and “to_cost” column. Like A-Star this algorithm also has a heuristic function, which prefers links closer to the target of the search.

ALTER TABLE ways ADD COLUMN reverse_cost double precision;
UPDATE ways SET reverse_cost = length;

ALTER TABLE ways ADD COLUMN to_cost double precision;
ALTER TABLE ways ADD COLUMN rule text;

Shortest Path Shooting-Star core function

Shooting-Star algorithm introduces two new attributes:

  • rule: a string with a comma separated list of edge IDs, which describes a rule for turning restriction (if you came along these edges, you can pass through the current one only with the cost stated in to_cost column)
  • to_cost: a cost of a restricted passage (can be very high in a case of turn restriction or comparable with an edge cost in a case of traffic light)
shortest_path_shooting_star( sql text,
                   source_id integer,
                   target_id integer,
                   directed boolean,
                   has_reverse_cost boolean )

Note:

  • Source and target IDs are link IDs.
  • Undirected graphs (“directed false”) ignores “has_reverse_cost” setting

Example for Shooting-Star “rule”

Shooting* algorithm calculates a path from edge to edge (not from vertex to vertex). Column vertex_id contains start vertex of an edge from column edge_id.

To describe turn restrictions:

 gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
-----+--------+--------+------+----+----+----+----+---------+------
  12 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 14

means that the cost of going from edge 14 to edge 12 is 1000, and

 gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
-----+--------+--------+------+----+----+----+----+---------+------
  12 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 14, 4

means that the cost of going from edge 14 to edge 12 through edge 4 is 1000.

If you need multiple restrictions for a given edge then you have to add multiple records for that edge each with a separate restriction.

 gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
-----+--------+--------+------+----+----+----+----+---------+------
  11 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 4
  11 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 12

means that the cost of going from either edge 4 or 12 to edge 11 is 1000. And then you always need to order your data by gid when you load it to a shortest path function..

Example of Shooting-Star core function

SELECT * FROM shortest_path_shooting_star('
                SELECT gid as id,
                         source::integer,
                         target::integer,
                         length::double precision as cost,
                         x1, y1, x2, y2,
                         rule, to_cost
                        FROM ways',
                293, 761, false, false);

 vertex_id | edge_id |        cost
-----------+---------+---------------------
          4232 |     293 |  0.0059596293824534
          3144 |     293 |  0.0059596293824534
          4232 |    4632 |  0.0846731039249787
           ... |     ... |  ...
            51 |     761 |  0.0305298478239596
(63 rows)

Wrapper function WITH bounding box

Wrapper functions extend the core functions with transformations, bounding box limitations, etc..

SELECT gid, AsText(the_geom) AS the_geom
        FROM shootingstar_sp('ways', 293, 761, 0.1, 'length', true, true);

  gid   |                              the_geom
--------+---------------------------------------------------------------
        293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833))
        293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833))
   4632 | MULTILINESTRING((18.4074149 -33.9443308,18.4077388 -33.9436183))
        ... | ...
        762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966))
        761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275))
(62 rows)

Note:

  • There is currently no wrapper function for A-Star without bounding box, since bounding boxes are very useful to increase performance. If you don’t need a bounding box Dijkstra will be enough anyway.
  • The projection of OSM data is “degree”, so we set a bounding box containing start and end vertex plus a 0.1 degree buffer for example.