[pgrouting-dev] Time dependent data and input format

[Jay Mahadeokar]

Hi,

My thoughts on points made by Stephen:

Firstly, the main goal of the time dependent shortest path project as per my
GSoc proposal is to extend the static dijkstra algorithm, to work with time
dependent graphs. I made a wiki page for that and we can keep modifying it
as the ideas become concrete:
https://github.com/pgRouting/pgrouting/wiki/TDSP-Details



>
>  *Input format for time dependent data:
>>
>
> I would think that you need:
>
>  start_time_and_date,
>  start_location,
>  end_location,
>  options
>
> It you wanted to get fancy, it might be nice to be able to do the reverse
> and say:
>
>  start_location,
>  end_location,
>  arrival_time,
>  options



This looks good.
A tuple will denote the arrival_time which will be time required if we start
from source_location at time denoted by start_time and travel to
end_location.

So, basically we can assume that the edge weights are the time required to
traverse the edge. The core time-dependent dijkstra will assume it can call
a function like:

getCurrentEdgeCost( edge_id, start_time_and_date, arrival_time)   - edge can
be denoted by start_location and end_location. The arrival_time will be
returned by function.

While relaxing the edge in dijkstra algorithm, instead of static cost, the
above function will be called each time to know the arrival_time for that
instant.



> In this version you would have to figure on the route starting at the end
> and working backwards to the start location to figure on the route and the
> required start time.
>
>  *There has already been a brief discussion on this topic before. A quick
>>
>>
> User - application developer, the person build an application using our
> finished pgRouting product.
>
> Client - the person using the application built by "User"
>
> 1. the User will take data like from MassGIS and load the network data and
> prep it for pgRouting.
> 2. the User will take the MBTA bus and train and subway schedules and load
> them into tables the closely reflect the underlying schedule data.
> 3. the User will develop a stored procedure to read the schedule data and
> morph it into some predefined notion whatever that might be. This could be
> to load it into a more normalized table or it might be to service a specific
> query and return a normalized record.
> 4. the Client make a route request
> 5. a wrapper script queries the networks and the schedules and this data
> gets built into a temporary boost graph structures to service this request.
> 6. results are returned to the Client and stuff is cleaned up.
>
> I think this is basically the same flow we use today in pgRouting with the
> exception of the schedules or whatever time dependent data we have.
>
> And with we are not using schedules and only looking at time dependent turn
> restrictions and oneway streets then I think using the same approach is
> still valid but instead of loading schedule information, we would load the
> turn restriction.
>


I did not understand how we will be using bus and train schedules in this
algorithm. I guess, the basic aim at this moment is just to extend dijkstra
for time-dependent scenario, right?  Dealing with schedules will need
provision for multimodal routing I guess. Can you please clarify this point?

I was not exactly aware of concept of turn restrictions, so I referred here:
http://wiki.openstreetmap.org/wiki/Relation:restriction

I guess to provide support for time dependent turn restriction will just
need a slight modification in original approach as per the GSoc proposal. We
will just have to make sure if we are allowed to turn to particular road at
that particular time, before we relax it in dijkstra algorithm.

Thoughts?



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