[pgrouting-dev] Re: Implementation of core Time Dependent Dijkstra function

[Jay Mahadeokar]

Hi,

I have outlined possible design and implementation of the time-dependent
algorithm on basis of feedback received till now:

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
   - day_of_week
   - time_of_day
   - travel_time / arrival_time

     3. TurnRestrictions (Time dependent)

   - node/source


   - time_from
   - time_to
   - node_to
   - ancestors


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.
If in time-dependent shortest path query with turn restrictions is made ,
all 3 tables will be used.

*SQL Structures and Queries*

//Same as normal dijkstra - Return type
CREATE TYPE path_result AS (vertex_id integer, edge_id integer, cost
float8);


-----------------------------------------------------------------------
-- Core function for time dependent shortest_path computation
-- See README for description
-----------------------------------------------------------------------
CREATE OR REPLACE FUNCTION time_dependent_shortest_path(sql text, source_id
integer,
        target_id integer, directed boolean, has_reverse_cost boolean,
day_of_week integer, time_of_day double precision)
        RETURNS SETOF path_result
        AS '$libdir/librouting'
        LANGUAGE 'C' IMMUTABLE STRICT;


TODO: Decide what wrapper functions will be required, including bounding box
and sliding window functionality.

*Code Design*

Additional DS to be used besides normal dijkstra:
    typedef struct Time_Dependent_Costs
     {
          int edgeId,
          int day_of_week
          double time_of_day
          double travel_time
     } time_dep_cost_t;


*Time_dependent_dijkstra.c*

Will contain the main PG_FUNCTION like: time_dependent_shortest_path.
This will call compute_time_dependent_shortest_path. The compute shortest
path function can be defined as follows: static int
compute_shortest_time_dependent_path(char* sql, int start_vertex,
                                 int end_vertex, bool directed,
                                bool has_reverse_cost,
                                 path_element_t **path, int *path_count, int
day_of_week, double time_of_day)
It will first query ways table as per sql passed, and populate edge_t with
the edges.
Then it will query the TimeDepCosts table and generate the time_dep_costs_t
Next it will call the boost_time_dep_dijkstra() from
time_dep_boost_wraper.cpp.

*time_dep_boost_wrapper.cpp*

Main function:
int boost_time_dep_dijkstra(edge_t *edges, unsigned int edge_count,
time_dep_cost_t *edges, unsigned int time_dep_cost_count,
int start_vertex, int end_vertex,
bool directed, bool has_reverse_cost,
path_element_t **path, int *path_count, char **err_msg);

It  will generate the boost graph using the information in edge_t.
It will generate the WeightMap using information in time_dep_cost_t.

WeightMap:
It is a type of Boost::PropertyMap.
The key will be Boost::Tuple<unsigned int,int,double>  - representing
<edgeId,day_of_week,time_of_day>
The value will be cost (double)

Then it will call the dijkstra_time_dep_shortest_path() defined in
time_dep_dijkstra_shortest_path.hpp

*time_dep_dijkstra_shortest_path.hpp *

This will be coded on lines of dijkstra_shortest_path.hpp. Instead of
default static weight map, the newly defined weight map will be used.

TODO:  dijkstra_shortest_path uses very neat and robust design, including
named parameters and other design patterns.
Examine if these are necessary, or same thing can be done in a simpler way.


For getting started, I will assume that we will query all the
timeDependentCosts at once and generate the WeightMap.   Once this is done,
we can go for the sliding window idea discussed earlier which may save
space.

The support for time-dependent turn restrictions can also be implemented
later. (If not during GSoc, maybe after that)

Eagerly awaiting any thoughts / suggestions. I will try and design the
internal time_dependent_dijkstra code asap, and update the list.


-- 
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110517/18a51df0/attachment.html