[pgrouting-dev] Re: Implementation of core Time Dependent Dijkstra
function
Stephen Woodbridge
woodbri at swoodbridge.com
Tue May 24 23:17:32 EDT 2011
On 5/24/2011 7:06 PM, Jay Mahadeokar wrote:
>
>
> On Mon, May 23, 2011 at 8:03 PM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>
> 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.
>
>
> Well,
> The std::prority_queue does not support the decrease_key operation which
> will be needed for the dijkstra search. I dont think stl provides a heap
> data structure with decrease_key, delete_min and insert operations.
>
> The make_heap, and sort_heap would be too costly to maintain for dijkstra.
>
> Do you have any idea of open-source library that provides the heap
> datastructure with above functionality?
>
> I am thinking of implementing binary heap myself to support the required
> functionality.
> Thoughts?
Jay,
What about looking at the code in Booost Graph that does this. There is
probably some generic template code, but maybe you can just reuse the
algorithms and recode your own specific to this problem implementation.
Ashraf,
You implemented your own Dijkstra algorithm in OpenGraphRouter, can you
point Jay to your code there so that he can assess reusing some of that
fore this project. I think the following might do the trick
http://sourceforge.net/projects/opengraphrouter/
Look here at ShortestPathDikjstra.cpp, it looks like Ashraf is using a
Boost Mutable Queue:
http://opengraphrouter.svn.sourceforge.net/viewvc/opengraphrouter/tags/Newstructure/tags/gsoc2009/src/?pathrev=111
-Steve
> 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>
> <mailto: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>>
> <mailto: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
>
More information about the pgrouting-dev
mailing list