[pgrouting-dev] Re: Implementation of core Time Dependent Dijkstra
function
Stephen Woodbridge
woodbri at swoodbridge.com
Mon May 23 10:33:34 EDT 2011
I'm not a C++ programmer, but from what I have read on the boost list,
it seems that the path to writing generic templates is to write the code
first in regular C++ so it works and then refactor it to be more
generic. So step 1 is to do as you proposed.
Also since this project is to implement a "time dependent dijkstra
algorithm" in pgRouting, the generic templates seems to be out of scope.
It would be fine to do if you had the time and skill, but I think your
approach makes sense, use the tools that make your job easier and allow
you to achieve success.
Any contrary opinions to this?
-Steve
On 5/23/2011 10:20 AM, Jay Mahadeokar wrote:
> Hi,
>
> As initially discussed, I was trying to reuse the boost's dijkstra code
> to write the core time dependent dijkstra algorithm.
> Since Boost makes extensive use of generic programming, and I have no
> prior experience with such deep generic programming concepts, I was
> wondering if we really need all these features that boost provides.
>
> Another option would be to write the time-dependent dijkstra on our own.
>
> This will be a light-weight code without extensive use of generic
> programming like boost.
> So, i was thinking of using following:
>
> *1. *Boost::AdjecencyList - for storing graph.
> *2. *Std::Map - for storing distanceMap, predecessorMap.
>
> *3. *For weightMap:
>
> typedef struct weight_map_element
> {
> pair<int,double> edge;
> double travel_time;
> }
> weight_map_element_t;
>
> class weight_map
> {
>
> vector<weight_map_element_t> weight_map_set;
>
> public:
> void insert(weight_map_element_t element);
> double get_travel_time(int edge_id, double start_time);
>
> };
>
>
> *4. *std::priority_queue for the priority queue that will be used for
> dijkstra search.
>
>
> Will this be sufficient for our implementation? If yes, I will come up
> with the detailed internal function prototypes soon.
>
>
> On Wed, May 18, 2011 at 8:09 PM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>
> 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>
> <mailto: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>>
> <mailto: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>
> <mailto: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>
> <mailto: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 <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