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

[Daniel Kastl]

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
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110518/104762b0/attachment.html