[pgrouting-dev] Re: Implementation of core Time Dependent Dijkstra
function
Stephen Woodbridge
woodbri at swoodbridge.com
Wed May 18 10:39:25 EDT 2011
On 5/18/2011 8:08 AM, Jay Mahadeokar wrote:
> 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.. :-)
This (isHoliday) might work for a single day, but will not work if the
query crosses into the next day(s). Holidays are an input convenience to
describe recurring events. So say we have a convenient way to input that
data and store it into tables as we have described, then the query for
costs would need to decide is a given day is a holiday or not and then
select the correct entries to return based on that. For ease of
implementation, we could just start with a stub function the returns
false and later implement a table lookup based on the date or day of
year that determines if isHoliday=t/f for any given start_time+offset.
Then when querying schedules, for example, we would select holiday
schedules if they exist and its a holiday otherwise search the regular
tables.
> 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?
This sounds reasonable if the response is in units of time (offset) from
query_start_time. Assuming we use a resolution of seconds, then the
response would be in seconds from start time.
> *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.
I suggested seconds above, but if someone is modeling events in say
glacier flow, geological times or the big bang, they might need other
units of time. I would say that because we are talking about time based
schedules and need to deal with days, hours minutes we should probably
not worry about these other timeframes as the solver will be offset
based it will work with any units and then only the wrappers for
extracting the costs from the schedules would need to change to deal
with other timeframes. So lets not get hung up on this, I think this is
a sound plan.
-Steve
> 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 <mailto: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>
> <mailto: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 <mailto:pgrouting-dev at lists.osgeo.org>
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
More information about the pgrouting-dev
mailing list