[pgrouting-dev] Re: Implementation of core Time Dependent
Dijkstra function
Jay Mahadeokar
jai.mahadeokar at gmail.com
Tue May 24 19:06:05 EDT 2011
On Mon, May 23, 2011 at 8:03 PM, Stephen Woodbridge <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?
>
>> 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
>>
>
> _______________________________________________
> 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/87312f2e/attachment-0001.html
More information about the pgrouting-dev
mailing list