[pgrouting-dev] Re: Implementation of core Time Dependent Dijkstra function

[Stephen Woodbridge]

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