[pgrouting-dev] Re: Implementation of core Time Dependent
Dijkstra function
Jay Mahadeokar
jai.mahadeokar at gmail.com
Wed May 18 08:08:57 EDT 2011
Hi,
I think what we need is a function on following lines:
Given a query_start_time, it should query the TimeDepCosts table, and return
the set of entries which have their start_time within query_start_time +
delta. This delta might be x hours, depending on the upper bound of the
expected journey time.
We need following things handled in our model:
If query_start_time is 11PM Sunday and delta is 10 hours, we will need to
query entries with start time between 11PM Sunday and 9AM Monday. So,
basically the function needs to be periodic in terms of time_of_day and
day_of_week.
As Steve suggested, we can maintain conventions for day_of_week like:
-3 - holidays
-2 - weekend days
-1 - week days
0 - all days
1-7 Mon - Sun.
If we just assume entries for -3,-2,-1,0 and ignore each entry for Sun -
Sat, that would reduce the space required assuming that the entries for
weekdays is same. If times for different weekdays is different then we would
have separate entries for each day.
So, the query should properly examine the query_day_of_week and select the
proper entries. Ex: For above query, if it is sunday, then after 12AM, next
entries will be queried with time_of_day as -1, but if it was Saturday, next
entries will be queried with time_of_day as -2.
We can have a boolean parameter like *isHoliday* in query itself, which will
tell if a given day (may be weekday) is holiday or not.Then again the query
will have to be modified accordingly (query for -3). This will take care of
query for local holiday etc and we do not have to worry about calenders. The
user will have to worry about that.. :-)
There can be time_from and time_to entries as well. But, if we just have
entries like:
day_of_week: -1, time_of_day: 00:01, 55mph
day_of_week: -1, time_of_day: 07:00, 30mph
day_of_week: -1, time_of_day: 10:01, 55mph
day_of_week: -1, time_of_day: 16:31, 30mph
we can assume that the entry with time_of_day 00:01 is valid upto 07:00.
And if query_start_time is 02:00 and delta is 10 hours, we can query entries
which have time_of_day < query_start_time + delta (taking care of change of
day).
Is this assumption reasonable?
*weightMap Abstraction*
I think the design would be more modular if we keep the weightMap
independent of the underlying time conventions. Since as Daniel pointed out,
this algorithm can also be used for non-road networks.
So, whatever the underlying time conventions, we can assume that in the end
the query should return pairs like:
< <edgeId, offset_time> , travel_time/speed >
We will assume that query_start_time is 0, i.e we offset every thing by
query_start_time.
The offset_time will be as follows:
As in above example,
If start_tme is 02:00 and day_of_week is -1, and delta as 10 hours.
Then, edge entries for edgeId 1 will be:
< <1, 05:00 > , 30 mph>
< <1, 08:01 > , 55 mph>
< <1, 14:31 > , 30 mph>
Basically, the offset_time will abstract out any internal details of
weekdays, change of days etc and it will just contain the offset from
start_time.
This will greatly simplify the core time dependent dijkstra implementation.
Thoughts?
On Wed, May 18, 2011 at 10:46 AM, Stephen Woodbridge <
woodbri at swoodbridge.com> wrote:
> Hi Daniel,
>
> These are good points.
>
> I agree that turn restrictions should be thought about but only implemented
> if there is time. I think we should take the discussion of turn restriction
> into a separate thread. I'm interested in what you think is a limitation
> that can't be modeled in Dijkstra or A*.
>
> Regarding the time modeling, my point was just that we needed more thought
> there and a richer model developed. The crontab model is a good idea. I'm
> not opposed to modeling monthly or yearly events, but they rarely exist
> other than holidays which I tried to capture. I suppose you could model
> something like the Boston Marathon and model all the road closures and
> restrictions, but it seems to be a lot of work for a one day event, but I
> can see city government's deploying the resources to model something like
> this.
>
> Regarding timezones: Times need to be entered with zones for models that
> cross zones but all the data should be converted to UTC internally so it
> runs in a consistent time model. Timezones are for input and output, but the
> solver should be ignorant of them, in my opinion.
>
> I have carried my GPS from the Eastern to central time zone, and it knew
> the local time when I powered it up. So my guess is that it would auto
> correct when crossing the time zone.
>
> -Steve
>
>
> On 5/17/2011 10:42 PM, Daniel Kastl wrote:
>
>> Hi Jay and Steve,
>>
>> This looks really nice, but let me give some comments regarding how to
>> model time, because this is really tricky in my opinion. Especially when
>> thinking about an abstract network that isn't a road network.
>>
>>
>>
>> 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.
>>
>>
>> Currently in pgRouting Dijkstra and A* don't support turn restrictions
>> modelling. What I actually like on Shooting Star is, that it routes from
>> edge to edge instead of node to node. So it allows to model relations
>> between edges rather than nodes, which I think is more close to how
>> humans would think of this.
>> Dijkstra can only visit one node one times (as Shooting star only visits
>> an edge once). Well, there can be turn restriction cases where a node is
>> passed twice and which can't be done correctly with Dijkstra as far as I
>> know.
>>
>> In the beginning I wouldn't think about the turn restrictions too much.
>> Let's take it as an extra when we see we still have enough time.
>> Of course if you have a good idea to implement it all at once with only
>> little extra work, then that's fine.
>>
>>
>> For time definitions in your tables I think you need to probably
>> define some common structure for handling a time entry.
>>
>>
>> Another problem might be time zones. Plain day field + time field might
>> not be able to allow driving from one time zone to another (or just
>> think about a flight network). I never went from one timezone to another
>> by car or train, but Steve and Anton, you might have this experience.
>> How does car navigation software handle this when you cross the timezone
>> border? ;-)
>>
>> So taking "timestamp with timezone" for those fields might be a good
>> idea to be able to support such a functionality.
>>
>>
>> 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
>>
>>
>> I think the problem here is how to model recurring time dependent costs,
>> right?
>> If you think about weekdays, then you can't for example model monthly or
>> yearly events.
>>
>> I'm not really sure this is useful information here, but I once saw
>> about how the "iCal" format models recurring calendar events:
>> http://ext.ensible.com/deploy/dev/examples/calendar/recurrence-widget.html
>>
>> Maybe we can learn something from there. The example needed to be
>> extended with some duration probably. But looking about calendar formats
>> might be a good idea to model holidays etc.
>>
>> Or another (stupid) example would be cron job syntax. Something I always
>> need to google for as I can't remember it ;-)
>>
>> All this time dependent stuff, events and schedules is also an issue in
>> Darp solver.
>> And it probably is important also for the multi-modal routing, so if we
>> can find some clever way how to model this and can share it between
>> algorihtms, that would be great.
>>
>> Daniel
>>
>>
>> --
>> Georepublic UG & Georepublic Japan
>> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de>
>> Web: http://georepublic.de <http://georepublic.de/>
>>
>>
>>
>>
>> _______________________________________________
>> 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/20110518/82ab8b7e/attachment-0001.html
More information about the pgrouting-dev
mailing list