<div><span style="font-size: small;">Hi, <br><br>I have outlined possible design and implementation of the time-dependent algorithm on basis of feedback received till now:<br><br>We assume we have following database tables:</span><br clear="none">
<span style="font-size: small;"></span><ol><li>
<span style="font-size: small;">Ways: (On lines of the one in pgrouting-workshop)</span></li></ol></div>
<ul><li><span style="font-size: small;">gid</span></li><li><span style="font-size: small;">source</span></li><li><span style="font-size: small;">target</span></li><li><span style="font-size: small;">name</span></li><li><span style="font-size: small;">the_geom</span></li>
<li><span style="font-size: small;">static_length (In case time dependent routing is not used)</span></li><li><span style="font-size: small;">any other attributes..</span></li></ul>
<div><span style="font-size: small;"> 2. TimeDepCosts </span></div>
<ul><li><span style="font-size: small;">gid</span></li><li><span style="font-size: small;">day_of_week</span></li><li><span style="font-size: small;">time_of_day</span></li><li><span style="font-size: small;">travel_time / arrival_time</span></li>
</ul>
<div><span style="font-size: small;"> 3. TurnRestrictions (Time dependent)</span></div>
<ul><li><span style="font-size: small;">node/source</span></li></ul>
<div>
<ul><li><span style="font-size: small;">time_from </span></li><li><span style="font-size: small;">time_to </span></li><li><span style="font-size: small;">node_to </span></li><li><span style="font-size: small;">ancestors</span></li>
</ul>
</div>
<div><br clear="none"><span style="font-size: small;">If only static shortest path query is made, then only table 1 is required.</span><br clear="none"><span style="font-size: small;"> If time-dependent shortest path query is made, table 1 and 2 will be used.</span><br clear="none">
<span style="font-size: small;">If in time-dependent shortest path query with turn restrictions is made , all 3 tables will be used.</span><br clear="none"><span style="font-size: small;"></span></div>
<div><span style="font-size: small;"><b>SQL Structures and Queries</b></span></div>
<div><br clear="none"></div>
<div><span style="font-size: small;">//Same as normal dijkstra - Return type<br clear="none"></span></div>
<div><span style="font-size: small;">CREATE TYPE path_result AS (vertex_id integer, edge_id integer, cost float8); <br clear="none"></span></div>
<div><br clear="none"></div>
<div><br clear="none"></div>
<div><span style="font-size: small;">-----------------------------------------------------------------------</span><br clear="none"><span style="font-size: small;">-- Core function for time dependent shortest_path computation </span><br clear="none">
<span style="font-size: small;">-- See README for description</span><br clear="none"><span style="font-size: small;">-----------------------------------------------------------------------</span><br clear="none"><span style="font-size: small;">CREATE OR REPLACE FUNCTION time_dependent_shortest_path(sql text, source_id integer, </span><br clear="none">
<span style="font-size: small;"> target_id integer, directed boolean, has_reverse_cost boolean, day_of_week integer, time_of_day double precision)</span><br clear="none"><span style="font-size: small;"> RETURNS SETOF path_result</span><br clear="none">
<span style="font-size: small;"> AS '$libdir/librouting'</span><br clear="none"><span style="font-size: small;"> LANGUAGE 'C' IMMUTABLE STRICT;</span></div>
<div><br clear="none"></div>
<div><br></div><div><span style="text-decoration: underline;"><span style="font-size: small;">TODO:</span></span> <span style="font-size: small;">Decide what wrapper functions will be required, including bounding box and sliding window functionality.</span></div>
<div><br></div><div><span style="font-size: small;"><b>Code Design</b></span></div><div><br></div><div><span style="font-size: small;">Additional DS to be used besides normal dijkstra:<br> typedef struct Time_Dependent_Costs</span></div>
<div><span style="font-size: x-small;"> {</span></div>
<div><span style="font-size: x-small;"> int edgeId,</span></div><div><span style="font-size: x-small;"> int day_of_week</span></div><div><span style="font-size: x-small;"> double time_of_day</span></div>
<div><span style="font-size: x-small;"> double travel_time</span><br></div><div><span style="font-size: x-small;"> } time_dep_cost_t;</span></div><div><br></div><div><br></div><div><b><span style="text-decoration: underline;"><span style="font-size: small;">Time_dependent_dijkstra.c</span></span></b></div>
<div><br></div><div><span style="font-size: small;">Will contain the main PG_FUNCTION like: time_dependent_shortest_path.</span></div><div><span style="font-size: small;"></span><span style="font-size: small;">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, </span><span style="font-size: small;"></span></div><div><span style="font-size: small;"> int end_vertex, bool directed,</span><span style="font-size: small;"> </span></div>
<div><span style="font-size: small;"> bool has_reverse_cost, </span><span style="font-size: small;"></span></div><div><span style="font-size: small;"> path_element_t **path, int *path_count, int day_of_week, double time_of_day)</span><span style="font-size: small;"></span></div>
<div><span style="font-size: small;">It will first query ways table as per sql passed, and populate edge_t with the edges.</span></div><div><span style="font-size: small;">Then it will query the TimeDepCosts table and generate the time_dep_costs_t<br>
</span></div><div><span style="font-size: small;">Next it will call the boost_time_dep_dijkstra() from time_dep_boost_wraper.cpp.<br>
</span></div>
<div><br></div><div><b><span style="text-decoration: underline; font-size: small;">time_dep_boost_wrapper.cpp</span></b></div><div><br></div><div><span style="font-size: small;">Main function:</span><br></div><div><span style="font-size: small;">int boost_time_dep_dijkstra(edge_t *edges, unsigned int edge_count, time_dep_</span><span style="font-size: small;">cost_t *edges, unsigned int time_dep_cost_count,</span><span style="font-size: small;"></span></div>
<div><span style="font-size: small;">int start_vertex, int end_vertex,</span><br>
<span style="font-size: small;">bool directed, bool has_reverse_cost,</span><span style="font-size: small;"></span></div><div><span style="font-size: small;">path_element_t **path, int *path_count, char **err_msg);</span></div>
<div><br></div><div><span style="font-size: small;">It will generate the boost graph using the information in edge_t. </span></div><div><span style="font-size: small;">It will generate the WeightMap using information in time_dep_cost_t.</span></div>
<div><br></div><div><span style="font-size: small;">WeightMap:</span></div><div><span style="font-size: small;">It is a type of Boost::PropertyMap.</span></div><div><span style="font-size: small;">The key will be Boost::Tuple<unsigned int,int,double> - representing <edgeId,day_of_week,time_of_day></span></div>
<div><span style="font-size: small;">The value will be cost (double)</span></div><div><br></div><div><span style="font-size: small;">Then it will call the dijkstra_time_dep_shortest_path() defined in time_dep_dijkstra_shortest_path.hpp</span></div>
<div><br></div><div><b><span style="text-decoration: underline;"><span style="font-size: small;">time_dep_dijkstra_shortest_path.hpp</span></span><span style="font-size: small;"> </span></b></div><div><br></div><div><span style="font-size: small;">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.</span></div><div><br></div><div><span style="font-size: small;">TODO: dijkstra_shortest_path uses very neat and robust design, including named parameters and other design patterns.</span></div>
<span style="font-size: small;">Examine if these are necessary, or same thing can be done in a simpler way.</span><br><br><br>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.<br>
<br>The support for time-dependent turn restrictions can also be implemented later. (If not during GSoc, maybe after that)<br><br>Eagerly awaiting any thoughts / suggestions. I will try and design the internal time_dependent_dijkstra code asap, and update the list.<br>
<br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>