[pgrouting-dev] Re: Implementation of core Time Dependent
Dijkstra function
Jay Mahadeokar
jai.mahadeokar at gmail.com
Tue May 24 23:58:56 EDT 2011
On Wed, May 25, 2011 at 8:47 AM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:
> 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
>
>
>
Thanks Steve for the suggestion. I actually implemented a BinaryHeap class
for exact requirements, and it seems to be solving the purpose.
The basic functions in class are:
class binary_heap
{
vector<Vertex> heap;
void heapify(int index);
public:
void insert(Vertex v); //inserts v into heap and rebalances it so that
heap property is maintained.
double decrease_key(int index, double delta); // Decreases key of vertex
with id = index, by delta.
Vertex delete_min(); //deletes the min key vertex and rebalances heap.
};
Note that in binary heap all above operations need O(log n) time.
I will complete the initial draft of the algorithm soon and update it on
github in next few days.
We can see what else is needed then.
-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
>>
>> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
--
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110525/bfa5f93a/attachment-0001.html
More information about the pgrouting-dev
mailing list