TDSP Tutorial and Example - pgRouting/pgrouting GitHub Wiki
###Pre-requisites:
Compile and install the code from the github gsoc-tdsp branch.
This project was built against pgRouting 1.x and will need some work to convert it to compile under the 2.0, 2.1, or 2.2 build structure.
It does compile using Boost 1.43
cmake -DWITH_DD=ON
sudo make install
To make sure the time_dependent_shortest_path function is installed, log in to pgrouting-worskhop database.
Psql pgrouting-workshop
Now, to make sure you have installed the tdsp function, type:
\df+ 'time_dependent_shortest_path'
It should show the installed function. If not perform the following command:
CREATE OR REPLACE FUNCTION pgr_time_dependent_shortest_path
(
sql text,
source_id integer,
target_id integer,
directed boolean,
has_reverse_cost boolean,
time_dep_sql text,
query_start_time integer
)
RETURNS SETOF path_result AS '$libdir/librouting_tdsp'
LANGUAGE 'C' IMMUTABLE STRICT;
Along with the ways table in pgrouting-workshop, we need an additional table time_dep_costs. Give the following command:
create table time_dep_costs
(
edge_id integer,
start_time integer,
end_time integer,
travel_time double precision
);
Now we create a function which will populate the time_dep_costs table with time_dependent_data:
create function generate_time_dep_data() returns integer as $$
declare
way ways%rowtype;
BEGIN
FOR way IN SELECT gid,class_id,length from ways
LOOP
IF way.class_id in (101,111,102) THEN
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 0, 6, (1 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 6, 7, (1.10 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 7, 8, (1.25 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 8, 9, (1.55 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 9, 10, (1.45 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 10, 11, (1.15 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 11, 17, (1 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 17, 18, (1.15 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 18, 19, (1.30 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 19, 20, (1.55 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 20, 21, (1.45 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 21, 22, (1.10 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 22, 24, (1 * way.length));
END IF;
IF way.class_id in (106,108,109,110,100) THEN
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 0, 6, (1 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 6, 7, (1.05 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 7, 8, (1.20 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 8, 9, (1.50 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 9, 10, (1.40 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 10, 11, (1.10 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 11, 17, (1 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 17, 18, (1.10 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 18, 19, (1.25 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 19, 20, (1.50 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 20, 21, (1.40 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 21, 22, (1.05 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 22, 24, (1 * way.length));
END
IF;
IF way.class_id in (112,119,117,114,122,401) THEN
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 0, 6, (1 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 6, 7, (1 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 7, 8, (1.10 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 8, 9, (1.15 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 9, 10, (1.15 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 10, 11, (1.05 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 11, 17, (1 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 17, 18, (1.05 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 18, 19, (1.10 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 19, 20, (1.15 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 20, 21, (1.15 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 21, 22, (1 * way.length));
INSERT INTO time_dep_costs(edge_id,start_time,end_time,travel_time) values (way.gid, 22, 24, (1 * way.length));
END
IF;
END
LOOP;
RETURN 1;
END;
$$ language plpgsql;
You can play around with the values and times. Example to disable the roads with class_id 106 from 9 AM to 10 AM, perform following command:
update time_dep_costs set travel_time = 100000 where edge_id in (select gid from ways where class_id = 106) and start_time = 9;
Now we are ready to try out the queries.
Perform the following query:
SELECT * FROM pgr_time_dependent_shortest_path(' SELECT gid as id, source::integer, target::integer, length::double precision as cost FROM ways', 81, 359, true, false,'SELECT edge_id, start_time ,travel_time from time_dep_costs',14);
Expected output:
vertex_id | edge_id | cost
-------+---------+------------------
81 | 76 | 0.676679124019778
82 | 2685 | 0.0142730120969233
2025 | 2686 | 0.0527643566935966
2026 | 2687 | 0.0503186783997734
1352 | 2688 | 0.040045224972895
891 | 2689 | 0.102585749616445
2027 | 2690 | 0.00393013769016461
2028 | 2691 | 0.0783080282246671
2029 | 2692 | 0.00809624716133584
2030 | 2693 | 0.0549300905337169
2031 | 2694 | 0.00932766708191147
206 | 2934 | 0.0649937724873396
2153 | 3606 | 0.0243462412382438
2435 | 3607 | 0.0121329190032456
1528 | 3608 | 0.0275302530244288
2436 | 3611 | 0.0157673263340369
2437 | 3612 | 0.0237076055549008
565 | 3613 | 0.0592997162617984
358 | 366 | 0.120471497765379
359 | -1 | 0
(20 rows)
Now if you perform the following query:
SELECT * FROM pgr_time_dependent_shortest_path('SELECT gid as id, source::integer, target::integer, length::double precision as cost FROM ways', 81, 359, true, false,'SELECT edge_id, start_time ,travel_time from time_dep_costs',9);
The outputs are different. The path returned by second query where query_start_time is 9 avoids the edge (81,82) since its cost is too high, its class_id = 106, and instead takes a longer route of 39 hops. On other hand, path returned by 1st query where query_start_time is 14 returns shortest path of 20 hops.