pgRouting with Shooting-Star algorithm¶

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.