TDSP Tutorial and Example

###Pre-requisites:

Compile and install the code from the github gsoc-tdsp branch.

    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 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 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.