[pgrouting-dev] Re: Implementation of core Time Dependent
Dijkstra function
Jay Mahadeokar
jai.mahadeokar at gmail.com
Mon May 23 10:20:02 EDT 2011
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
> 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>> 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>>
>> Web: http://georepublic.de <http://georepublic.de/>
>>
>>
>>
>>
>> _______________________________________________
>> 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/20110523/31a144ab/attachment-0001.html
More information about the pgrouting-dev
mailing list