[pgrouting-dev] Time dependent data and input format
Jay Mahadeokar
jai.mahadeokar at gmail.com
Mon May 2 13:09:47 EDT 2011
On Sun, May 1, 2011 at 10:39 AM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:
> 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.
>
Thanks Steve, for the detailed explanation.
I agree. So, now can we assume we have following database tables, as per
things discussed till now:
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. TimeVaryingCosts (Any other suitable name?)
- gid
- start_time_and_date (May divide this into two columns: day_of_week and
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.
Thoughts?
> 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
>>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
--
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110502/3ccb518f/attachment.html
More information about the pgrouting-dev
mailing list