[pgrouting-dev] Time dependent data and input format

[Stephen Woodbridge]

On 4/30/2011 1:27 PM, Jay Mahadeokar wrote:
> 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?

The multi-modal aspects are probably more important to Kishore's 
project, but in general this is also just a time dependent problem. Both 
these problems have the same issue of tracking time along the solution 
wave-front and at nodes you have to evaluate what out-bound links are 
value given some rules. The rules are based on your arrival time at that 
node.

So in your case given the the arrival time, your out-bound links might 
be modified by time dependent turn-restrictions and your average speed 
on the out-bound links might be effected by traffic feeds or historical 
average speed based on time of day, etc.

In Kishore's case, the valid out-bound links will be determined by modal 
schedules, and average link speeds will be determined by the mode of 
travel, like walk, bike, taxi, train etc. At nodes that are transfer 
points, then there may need to be rules about minimum transfer times, 
which equate to wait time between arrival and potential departures.

So if we think about these as abstractions, then at nodes we can have 
rules like:

1. restrictions
    - time dependent
    - vehicle class dependent restrictions
      o mopeds not allowed on divided highway
      o Bus only lanes, or HOV lanes
      o Emergency vehicle only lanes
      o pedestrian ways
      o bike lanes and paths
2. schedules
    - time dependent (this is very similar to restrictions)
    - vehicle class dependent
3. transfer costs
    - additional code of making a left hand turn in a right side country
    - cost to transfer modes in multi-modal network
    - toll cost


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

Yes, this is a good document. I believe it is missing an important case:

                   G
                   |
A---------<-------B-----------<---------C
                   |
F--------->-------E----------->---------D
                   |
                   H

So this depicts a street (G-B-E-H) crossing a divided roadway (A-B-C) 
west bound and (F-E-D) east bound. Now we don't need to worry about 
turning the wrong way on the oneway segments as that is handled.

If there is No U-turns at this intersection, then we need a restriction 
that says you may not turn on AB via BE from FE, about you are allowed 
to turn onto AB from via BE from EH or from the opposite direction ED is 
restricted from CB via BE, but EH is ok.

> 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.

Right. In Dijkstra, you typically have a pointer to your parent node, 
ie: the node you came from. And you have a list of node you can go to. 
In this case it is easy to add a reference to a restrictions on a given 
node. If the reference is null, then there are not restrictions. If you 
have a reference then restrictions could be stored in an array or list like:

has_time, time_from, time_to, node_to, ancestors[]

has_time, time_from, time_to - controls time dependancy or always valid

In my above example, we would have two restrictions for the No U-turns like:

at node B:
0, 0, 0, node_to=A, ancestors[E,F]

at node E:
0, 0, 0, node_to=D, ancestors=[B,C]

Maybe there is also a time dependent restriction on the divided road 
that restrictions traffic from turning onto the side road in the morning 
rush-hour, then we would add an additional restrictions to the above:

at node B:
1, 7AM, 9AM, node_to=G, ancestors=[C]
1, 7AM, 9AM, node_to=E, ancestors=[C]

at node E:
1, 7AM, 9AM, node_to=B, ancestors=[F]
1, 7AM, 9AM, node_to=H, ancestors=[F]

So if we translate that into a table design we have something like:

node, time_from, time_to, node_to, ancestors

which would be very easy to create and maintain.

OK, it is late here and I have flooded the list with a lot of mail 
tonight. I hope this all makes some sense and that the other threads 
might be useful.

Best regards,
   -Steve

> Thoughts?
>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev