[pgrouting-dev] Re: Implementation of core Time Dependent
Dijkstra function
Jay Mahadeokar
jai.mahadeokar at gmail.com
Tue May 24 19:08:05 EDT 2011
On Wed, May 25, 2011 at 4:36 AM, Jay Mahadeokar <jai.mahadeokar at gmail.com>wrote:
>
>
> 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.
>
Forgot to mention that - make_heap() and sort_heap() are provided by stl
algorithms.But as mentioned, it would be very costly and inefficient to use
sort_heap() each time.
>
> 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
>
>
--
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110525/e81a3690/attachment-0001.html
More information about the pgrouting-dev
mailing list