Turn Restricted Shortest Path (TRSP)
The turn restricted shortest path algorithm is similar to the Shooting Star algorithm in that you can specify turn restrictions, but executes significantly faster. In addition, at the time of this writing, the pgRouting releases 1.03 and 1.05 both had severely broken versions of Shooting Star.
The TRSP setup is mostly the same as Dijkstra Shortest path with the addition of an optional turn restriction table. This makes adding turn restrictions to a road network much easier than trying to add them to Shooting Star where you had to add the same edges multiple times if it was involved in a restriction.
Below is a sample trsp test data that you can use to create a simple graph with turn restrictions and run it.
$ cat trsp-test-data.sql
--
-- PostgreSQL database dump
--
SET client_encoding = 'UTF8';
SET standard_conforming_strings = off;
SET check_function_bodies = false;
SET client_min_messages = warning;
SET escape_string_warning = off;
SET search_path = public, pg_catalog;
SET default_tablespace = '';
SET default_with_oids = false;
--
-- Name: edges1; Type: TABLE; Schema: public; Owner: -; Tablespace:
--
CREATE TABLE edges1 (
eid integer NOT NULL,
dir character varying,
source integer,
target integer,
cost double precision,
reverse_cost double precision,
x1 double precision,
y1 double precision,
x2 double precision,
y2 double precision,
to_cost double precision,
rule text,
the_geom geometry,
CONSTRAINT enforce_dims_the_geom CHECK ((st_ndims(the_geom) = 2)),
CONSTRAINT enforce_geotype_the_geom CHECK (((geometrytype(the_geom) = 'LINESTRING'::text) OR (the_geom IS NULL))),
CONSTRAINT enforce_srid_the_geom CHECK ((st_srid(the_geom) = (-1)))
);
--
-- Name: restrictions1; Type: TABLE; Schema: public; Owner: -; Tablespace:
--
CREATE TABLE restrictions1 (
rid integer NOT NULL,
to_cost double precision,
teid integer,
feid integer,
via text
);
--
-- Name: restrictions1_rid_seq; Type: SEQUENCE; Schema: public; Owner: -
--
CREATE SEQUENCE restrictions1_rid_seq
INCREMENT BY 1
NO MAXVALUE
NO MINVALUE
CACHE 1;
--
-- Name: restrictions1_rid_seq; Type: SEQUENCE OWNED BY; Schema: public; Owner: -
--
ALTER SEQUENCE restrictions1_rid_seq OWNED BY restrictions1.rid;
--
-- Name: restrictions1_rid_seq; Type: SEQUENCE SET; Schema: public; Owner: -
--
SELECT pg_catalog.setval('restrictions1_rid_seq', 1, true);
--
-- Name: restrictions1a; Type: TABLE; Schema: public; Owner: -; Tablespace:
--
CREATE TABLE restrictions1a (
rid integer,
to_cost double precision,
teid integer,
feid integer,
via text
);
--
-- Name: rid; Type: DEFAULT; Schema: public; Owner: -
--
ALTER TABLE restrictions1 ALTER COLUMN rid SET DEFAULT nextval('restrictions1_rid_seq'::regclass);
--
-- Data for Name: edges1; Type: TABLE DATA; Schema: public; Owner: -
--
COPY edges1 (eid, dir, source, target, cost, reverse_cost, x1, y1, x2, y2, to_cost, rule, the_geom) FROM stdin;
1 B 1 2 1 1 2 0 2 1 \N \N 010200000002000000000000000000004000000000000000000000000000000040000000000000F03F
2 TF 2 3 -1 1 2 1 3 1 \N \N 0102000000020000000000000000000040000000000000F03F0000000000000840000000000000F03F
3 TF 3 4 -1 1 3 1 4 1 \N \N 0102000000020000000000000000000840000000000000F03F0000000000001040000000000000F03F
4 B 2 7 1 1 2 1 2 2 \N \N 0102000000020000000000000000000040000000000000F03F00000000000000400000000000000040
5 FT 3 8 1 -1 3 1 3 2 \N \N 0102000000020000000000000000000840000000000000F03F00000000000008400000000000000040
6 B 5 6 1 1 0 2 1 2 \N \N 01020000000200000000000000000000000000000000000040000000000000F03F0000000000000040
7 B 6 7 1 1 1 2 2 2 \N \N 010200000002000000000000000000F03F000000000000004000000000000000400000000000000040
8 B 7 8 1 1 2 2 3 2 \N \N 0102000000020000000000000000000040000000000000004000000000000008400000000000000040
9 B 8 9 1 1 3 2 4 2 \N \N 0102000000020000000000000000000840000000000000004000000000000010400000000000000040
10 B 7 10 1 1 2 2 2 3 \N \N 0102000000020000000000000000000040000000000000004000000000000000400000000000000840
11 FT 8 11 1 -1 3 2 3 3 \N \N 0102000000020000000000000000000840000000000000004000000000000008400000000000000840
12 FT 10 11 1 -1 2 3 3 3 \N \N 0102000000020000000000000000000040000000000000084000000000000008400000000000000840
13 FT 11 12 1 -1 3 3 4 3 \N \N 0102000000020000000000000000000840000000000000084000000000000010400000000000000840
14 B 10 13 1 1 2 3 2 4 \N \N 0102000000020000000000000000000040000000000000084000000000000000400000000000001040
15 B 9 12 1 1 4 2 4 3 \N \N 0102000000020000000000000000001040000000000000004000000000000010400000000000000840
16 B 4 9 1 1 4 1 4 2 \N \N 0102000000020000000000000000001040000000000000F03F00000000000010400000000000000040
\.
--
-- Data for Name: restrictions1; Type: TABLE DATA; Schema: public; Owner: -
--
COPY restrictions1 (rid, to_cost, teid, feid, via) FROM stdin;
1 100 7 4 \N
2 4 8 3 5
3 100 9 16 \N
\.
--
-- Data for Name: restrictions1a; Type: TABLE DATA; Schema: public; Owner: -
--
COPY restrictions1a (rid, to_cost, teid, feid, via) FROM stdin;
1 100 7 4 \N
\.
--
-- Name: edges1_pkey; Type: CONSTRAINT; Schema: public; Owner: -; Tablespace:
--
ALTER TABLE ONLY edges1
ADD CONSTRAINT edges1_pkey PRIMARY KEY (eid);
--
-- Name: restrictions1_pkey; Type: CONSTRAINT; Schema: public; Owner: -; Tablespace:
--
ALTER TABLE ONLY restrictions1
ADD CONSTRAINT restrictions1_pkey PRIMARY KEY (rid);
--
-- PostgreSQL database dump complete
--
The following are some sample queries and results:
select * from turn_restrict_shortest_path(
'select eid as id, source::integer, target::integer,cost, reverse_cost from edges1',
1, -- edge_id for start
0.5, -- midpoint of edge
6, -- edge_id of route end
0.5, -- midpoint of edge
true, -- directed graph?
true, -- has_reverse_cost?
null); -- no turn restrictions
vertex_id; edge_id; cost
-1; 1; 0.5
2; 4; 1
7; 7; 1
6; 6; 0.5
select * from turn_restrict_shortest_path(
'select eid as id, source::integer, target::integer,cost, reverse_cost from edges1',
1, -- node_id of start
5, -- node_id of end
true, -- directed graph?
true, -- has_reverse_cost?
null); -- no turn restrictions
vertex_id; edge_id; cost
1; 1; 1
2; 4; 1
7; 7; 1
6; 6; 1
5; -1; 0
select * from turn_restrict_shortest_path(
'select eid as id, source::integer, target::integer,cost, reverse_cost from edges1',
1, -- edge_id for start
0.5, -- midpoint of edge
6, -- edge_id of route end
0.5, -- midpoint of edge
true, -- directed graph?
true, -- has_reverse_cost?
-- include the turn restrictions
'select to_cost, teid as target_id, feid||coalesce('',''||via,'''') as via_path from restrictions1');
vertex_id; edge_id; cost
-1; 1; 0.5
2; 4; 1
7; 8; 1
8; 9; 1
9; 16; 1
4; 3; 1
3; 5; 1
8; 8; 1
7; 7; 1
6; 6; 0.5
select * from turn_restrict_shortest_path(
'select eid as id, source::integer, target::integer,cost, reverse_cost from edges1',
1, -- node_id of start
5, -- node_id of end
true, -- directed graph?
true, -- has_reverse_cost?
-- include the turn restrictions
'select to_cost, teid as target_id, feid||coalesce('',''||via,'''') as via_path from restrictions1');
vertex_id; edge_id; cost
1; 1; 1
2; 4; 1
7; 8; 1
8; 9; 1
9; 16; 1
4; 3; 1
3; 5; 1
8; 8; 1
7; 7; 1
6; 6; 1
5; -1; 0
The following is from an email thread of March 8, 2012 where I discussed using TRSP.
For those people that are using or trying to use the new trsp function, I want to highlight the difference between rule and via_path.
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
What I do in my turn restriction tables is to have both columns and if you already have a rule column here is some SQL to create a via_path column:
-- add a new column via_path
alter table my_turns add column via_path text;
-- need a helper function for the update
CREATE OR REPLACE FUNCTION array_reverse(anyarray)
RETURNS anyarray AS
$BODY$
SELECT ARRAY(
SELECT $1[i]
FROM generate_series(
array_lower($1,1),
array_upper($1,1)
) AS s(i)
ORDER BY i DESC
);
$BODY$
LANGUAGE sql IMMUTABLE STRICT
COST 100;
-- populate the via_path column
update my_turns set via_path=array_to_string(array_reverse(string_to_array(rule,',')),',');
One more common issue that is easy to get caught up in, is consistency of edge ids. When data is imported via shapefiles, you get a handy "gid" as the primary key and a lot of people use this to reference records. If you also load a restriction table or assemble it from your vendors data edges will typically be referred to be some edge_id that is NOT the "gid" the the shapefile loader dynamically adds when the data is loaded.
So if you vendor data uses a column "object_id" as the edge identifier, then it is likely that your restriction data will be defined in terms of "object_id" also. Therefore when you construct your query it needs to be something like:
select * from turn_restrict_shortest_path(
'select object_id as id, source, target, ...',
1234, -- start NODE_ID
5678, -- end NODE_ID
true,
true,
'select to_cost, object_id as target_id, via_path from my_turns');
I would also recommend the people use the following version of trsp because it can handle oneway conditions and restrictions at the start and end of the route that can not be detected using the above.
select * from turn_restrict_shortest_path(
'select object_id as id, source, target, ...',
1234, -- start EDGE_ID
0.5, -- position along edge
5678, -- end EDGE_ID
0.5, -- position along edge
true,
true,
'select to_cost, object_id as target_id, via_path from my_turns');
Notice that this uses EDGE_IDs and not NODE_IDs as the first does. Also position along the edge is a float from 0.0 to 1.0 where 0.0 is the start of the edge and 1.0 is the end of the edge. The postGIS linear referencing functions will return a value suitable for this by dropping a point on and edge and returning the percentage along that edge.
I hope this helps people use this new function.
