[pgrouting-dev] Re: Implementation of core Time Dependent Dijkstra
function
Stephen Woodbridge
woodbri at swoodbridge.com
Tue May 17 15:14:44 EDT 2011
Jay,
This is an excellent job! I found it to be very clear and detailed. I
think you have done an excellent job of capturing all the input and
presenting it in a nice clean design.
Would it be possible to support turn restrictions in the static Dijkstra
also? I'm thinking just use all the same structures but ignore the the
time components to keep things simple. So if the the turn restrictions
table is present we use it, otherwise assume no restrictions. If doing
static shortest path with turn restrictions then ignore the time
components otherwise we use them. And it is up to the user to make sure
the turn restriction table is valid for the analysis being requested.
For time definitions in your tables I think you need to probably define
some common structure for handling a time entry.
For example time_from and time_to might need to be defined as a
structure that includes day_of_week. day_of week might take values like:
-3 - holidays
-2 - weekend days
-1 - week days
0 - all days
1..7 - Sun,...,Sat
or making this is a bit field. Holidays are trickier, and imply another
table to that defines holidays that would be local to the region. I
think commenting on holidays in the design is adequate for now and can
be left to a future effort if it is needed.
time_from - when to apply this
time_to - implies a duration from the start,
but might be equal to time_from or null to imply an instant
So for:
schedules:
day_of_week: 0, time_from = time_to = HH:MM
turn_restrictions:
day_of_week: -1, time_from: 07:00, time_to: 10:00
speed_restriction:
day_of_week: -1, time_from: 00:01, time_to: 06:59, 55mph
day_of_week: -1, time_from: 07:00, time_to: 10:00, 30mph
day_of_week: -1, time_from: 10:01, time_to: 16:30, 55mph
day_of_week: -1, time_from: 16:31, time_to: 19:30, 30mph
day_of_week: -1, time_from: 19:31, time_to: 24:00, 55mph
day_of_week: -2, time_from: 00:01, time_to: 24:00, 55mph
day_of_week: -3, time_from: 00:01, time_to: 24:00, 55mph
Anyway I think this gets the idea across. Time is a tricky thing to
represent. You should model what you feel is reasonable for your effort
to be successful and we can document the rest for a future project if
needed.
You have made solid progress and I like what I am seeing.
Best regards,
-Steve
On 5/17/2011 12:50 PM, Jay Mahadeokar wrote:
> 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
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
More information about the pgrouting-dev
mailing list