TDSP Details

The basic overview of Time Dependent Shortest Path (TDSP) Algorithm is as follows:

##1. The time dependent data will be queried from postgres database. We assume we have following database tables:

1. Ways: (On lines of the one in pgrouting-workshop)

• gid
• source
• target
• name
• the_geom
• static_length (In case time dependent routing is not used)
• any other attributes

2. TimeDepCosts

• gid
• start_time
• end_time
• travel_time

If only static shortest path query is made, then only table 1 is required. If time-dependent shortest path query is made, table 1 and 2 will be used.

Time Dependent SQL Query prototype:

    CREATE OR REPLACE FUNCTION 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;

2. The postgresql Server Programming Interface is used to retrieve data from database.

The time_dependent_shortest_path query is internally calls the dynamically loaded objects which are postgresql C functions. It is defined in tdsp.h [3]. The Server Programming Interface (SPI) is used to retrieve tuples from ways table into array of edge_columns, defined in tdsp.h. Similarly tuples from time_dep_costs table are retrieved into array of weight_map_elements. These are then passed on to the tdsp_wrapper() function which has following prototype:

     int tdsp_wrapper
     (		
        edge_columns_t *edges, 
        unsigned int edge_count, 
        weight_map_element_t *weight_map_elements, 
        int weight_map_element_count,
        int start_vertex, 
        int end_vertex,
            bool directed, 
            bool has_reverse_cost,
            path_element_t **path, 
            int *path_count, 
            char **err_msg
      );

The tdsp_wrapper internally calls the tdsp() function, details are given in next section.

Core function Assumption:

The core function assumes that the query_start_time is 0 and all the start_times in weight map are offset from the query_start_time. This makes the core function independent of the time units and data formats of the input data. To use the core function with any input data, we need to write wrapper functions that will convert the time_dep_cost entries into weight map entries which follow the above convention. This greatly simplifies the working of the core algorithm and makes the design very flexible and robust.

3. The core time dependent dijkstra algorithm.

The core algorithm is referred from [1].

The input to a time-dependent shortest path problem is a directed network G = (N,A) and an arrival time function aij(t) for every arc (i, j) ∈ A. The quantity aij(t) gives the time of arrival at j if one departs from i at time t. It is assumed that aij(t) ≥ t. The function aij(t)−t gives the travel time along arc (i, j) if one departs at time t.

If aij(t) is non-decreasing for all (i, j) ∈ A, we say that G is a FIFO network, since in this case commodities will travel through arcs in a First-In-First-Out manner. If this is not the case the problem will be NP Complete. We will therefore assume that G is a FIFO network.

Let P(s, d) denote the set of paths between a source node s and a destination node d. The function EAsd(t) = min{ap(t) : p ∈P(s, d)} gives the earliest arrival time at node d if one leaves s at time t The pseudo-code for solving the Single source – destination query is as follows:

###Initialization:

    For all i ∈ N{s}  
           EAsi(t)←∞

    EAss(t)←t

    S ←N

###Main Loop:

    While S != ∅

       Select i ∈ S minimizing EAsi(t) S ←S{i}

       For all j such that (i, j) ∈ A

	     EAsj(t) ← min{EAsj(t), aij(EAsi(t))}

The design overview is as follows:

Edge Wrapper

The edges retrieved from the ways table are fed to the edge wrapper. The edge wrapper provides wrapper functions that help answer queries like -

• Given an edge_id, what are the source and target vertex ids.
• Given source and target vertex ids, what is the edge id.

Weight Map

The weight map elements retrieved from the time_dep_costs table are fed to the Weight Map. It answers queries like -

• Given an edge_id and start_time, what is the travel time for the edge.

Binary Heap

It is used as priority queue while performing time dependent dijkstra search. It provides following functionality -

• Insert – Add a vertex to the heap.
• Decrease_Key – Given a vertex_id and delta value, decrease the key of that vertex by delta.
• Delete_min – Delete and return the vertex with minimum key value and rebalance the heap.

Boost Adjecency List Graph

It is the graph constructed from the edges retrieved from ways table. It is used to examine the out_edges from a vertex while running the time dependent dijkstra algorithm. It offers many flexible options. For more details refer the boost documentation [2].

4. The result:

The result is returned in form of path_elements which is similar to the result of the shortest_path() query of the original pgRouting dijkstra algorithm implementation.

5. References

[1] B Dean. Shortest Paths in FIFO Time-Dependent Networks : Theory and Algorithms, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.6765

[2] Boost Adjecency List. http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/adjacency_list.html