[Soc] TDSP implementation for pgRouting Weekly Report

Fri Jul 8 10:30:01 EDT 2011

Hi,

Weekly Report #6
Date - 8th July 2011

According to project plan
----------------------------------------------------------------------------------------------------------------------------------------
July 7th
Implement the basic tdsp query and test it using test data.

Current Progress:
----------------------------------------------------------------------------------------------------------------------------------------

I have coded the functions to retrieve data from time_dep_costs table and it
is presented to the core tdsp algorithm along with the data from ways table.
The query seems to be working nicely for now.

I have documented the design details [1] and written an example tutorial [2]
to try out the time_dependent_shortest_path algorithm. I guess this is
enough to show the functionality, although, the data and examples along with
the wrapper functions need to be worked on in next few weeks.

Any feedback/corrections are welcome.

[1] https://github.com/pgRouting/pgrouting/wiki/TDSP-Details
[2] https://github.com/pgRouting/pgrouting/wiki/TDSP-Tutorial-and-Example

On Fri, Jul 1, 2011 at 2:28 PM, Jay Mahadeokar <jai.mahadeokar at gmail.com>wrote:

> Hi,
>
> Weekly Report #5
> Date - 1st July 2011
>
> According to project plan [1]
>
> ----------------------------------------------------------------------------------------------------------------------------------
> July 5th
> Implement queries needed for edge data and time dependent data from
> database.
> Integrate the core algorithm and all components with CMAKE scripts.
>
> Current progress
>
> ----------------------------------------------------------------------------------------------------------------------------------
> The core time dependent function was ready, and the postgresql query with
> static time data was working last week,
>
> I wrote c functions that will extract the attributes of the time dependent
> cost table, and then accordingly extract the corresponding tuples into array
> of weightMap elements. These are then presented to the core tdsp function
> along with edges array. The tuples are correctly extracted as of now. But,
> there is some problem when the core function is called. I will try and
> resolve the issues next week.
>
> [1]
> https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan
>
> On Fri, Jun 24, 2011 at 6:47 AM, Jay Mahadeokar <jai.mahadeokar at gmail.com>wrote:
>
>> Hi,
>>
>> Weekly Report #5:
>> Date - 24th June 2011
>>
>>
>> According to project plan [2]
>>
>> -----------------------------------------------------------------------------------------------------------------------------------------
>>
>> June 25th
>> Implement modules needed for retrieving the time-dependent costs.
>> July 5th
>> Implement queries needed for edge data and time dependent data from
>> database.
>> Integrate the core algorithm and all components with CMAKE scripts.
>>
>> Current Progress
>>
>> -----------------------------------------------------------------------------------------------------------------------------------------
>> I have corrected the bug which was resulting in wrong results for
>> non-integer data in core tdsp algorithm. Apparently there was a problem in
>> the binary_heap implementation, but now it seems to be working fine.
>>
>>  I have juggled the ordering of the tasks a bit. I implemented the queries
>> for retrieving the edge data from database, and also wrote the postgres C
>> procedure that extracts the data from ways table, generates the boost graph
>> and presents it to the time dependent algorithm. The weight map is generated
>> such that cost is same for all times, which is the case for static data and
>> that is also fed to the core algorithm. The query returns set of path
>> results and the results are exactly matching with the pgRouting
>> shortest_path() query.  Please find the updated code in gsoc-tdsp branch of
>> pgRouting github repository [1].
>>
>> Next weeks goals:
>>
>> -----------------------------------------------------------------------------------------------------------------------------------------
>> The next step will now be to implement modules for retrieving the data
>> from time_dep_costs table and generate the time dependent weight map which
>> will be fed to the core algo instead of the static one.
>>
>> [1] https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp
>>
>> [2]
>> https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan
>>
>> On Sat, Jun 18, 2011 at 7:48 AM, Jay Mahadeokar <jai.mahadeokar at gmail.com
>> > wrote:
>>
>>> Hi,
>>>
>>> Weekly Report #4:
>>> Date - 18th June 2011
>>>
>>>
>>> According to project plan [2]
>>>
>>> -----------------------------------------------------------------------------------------------------------------------------------------
>>>  Finish the design of project, and the core-time dependent shortest path
>>> implementation and test the code with dummy data till 15 June.
>>> Implement modules needed for retrieving the time-dependent costs till
>>> June 25th.
>>>
>>
>>>
>>>
>>> ------------------------------------------------------------------------------------------------------------------------------------------
>>> Current Progress:
>>>
>>> Implementation of core-time dependent dijkstra has been done.
>>> I have run across a bug when dealing with non-integer time-dependent
>>> data, I am working on it.
>>> I discussed ways of generating the time-dependent data in pgrouting dev
>>> list [1].
>>> Accordingly  have written plpgsql function that generates test data [3].
>>> Many modifications and test instances can be generated as discussed in
>>> [1].
>>>
>>>
>>> ------------------------------------------------------------------------------------------------------------------------------------
>>> Next week goals:
>>> Fix the bug in dealing with non-integer data.
>>> Start working on writing function that will retrieve time-dependent data
>>> from database.
>>> Also start working main tdsp-plsql function(the actual query that will be
>>> exposed).
>>>
>>> [1] http://lists.osgeo.org/pipermail/pgrouting-dev/2011-June/000300.html
>>>
>>> [2]
>>> https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan
>>>  [3]
>>> https://github.com/pgRouting/pgrouting/blob/gsoc-tdsp/extra/tdsp/sql/data_generate_tdsp.sql
>>>
>>>
>>>
>>> On Fri, Jun 10, 2011 at 10:58 PM, Jay Mahadeokar <
>>> jai.mahadeokar at gmail.com> wrote:
>>>
>>>> Hi,
>>>>
>>>> Weekly Report #3:  (Also available at [1])
>>>> Date - 10th June 2011
>>>>
>>>> According to project plan [2]:
>>>>
>>>>
>>>> -----------------------------------------------------------------------------------------------------------------------------------------
>>>> Finish the design of project, and the core-time dependent shortest path
>>>> implementation and test the code with dummy data till 15 June.
>>>>
>>>>
>>>> Current Progress:
>>>>
>>>> ------------------------------------------------------------------------------------------------------------------------------------------
>>>>  I had coded and tested the core-tdsp algorithm such that it returns the
>>>> distance-map and predecessor-map for given source.
>>>> This week I wrote a wrapper function which does the following task:
>>>> - Takes edges, weight_map_elements, source and target vertices as
>>>> parameters.
>>>> - Generates boost adjacency graph, weight_map and passes it to the
>>>> tdsp_core function.
>>>> - tdsp_core returns the distance_map and predecessor_map corresponding
>>>> to source.
>>>> - The wrapper function now generates the path from source to
>>>> destination, and returns path_elements as result.
>>>>
>>>>
>>>> I tested this for different source-destination pairs and it seems to be
>>>> working for now. Bugs need to be discovered with more
>>>> rigorous testing and fixed in coming weeks.
>>>>
>>>>
>>>>
>>>> ------------------------------------------------------------------------------------------------------------------------------------
>>>> Next week goals:
>>>> Finalize the prototype for the postgreSQL query for tdsp.
>>>> How to formulate the query for retrieving data from the
>>>> timeDependentCost table (used to generate the weight_map) is still under
>>>> debate
>>>> on pgRouting mailing list. We are considering various options like
>>>> letting the user provide the query, or form the query ourselves
>>>> and the pros and cons of both approaches.
>>>>
>>>> We hope to find a viable solution for the same asap and start working
>>>> towards implementing the same.
>>>>
>>>> [1]
>>>> https://github.com/jay-mahadeokar/GSoc-2011-Project-Docs/blob/master/weekly-reports/10-Jun-2011
>>>> [2]
>>>> https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan
>>>>
>>>> Regards,
>>>>
>>>>
>>>> On Fri, Jun 3, 2011 at 10:40 PM, Jay Mahadeokar <
>>>> jai.mahadeokar at gmail.com> wrote:
>>>>
>>>>> Hi,
>>>>>
>>>>> Here is my weekly report #2. Also available at [1].
>>>>> Date - 3rd June 2011
>>>>>
>>>>> According to tentative project plan [3]:
>>>>>
>>>>> -----------------------------------------------------------------------------------------------------------------------------------------
>>>>> Finish the design of project, and the core-time dependent shortest path
>>>>> implementation and test the code with dummy data till 15 June.
>>>>>
>>>>>
>>>>> Current Progress:
>>>>>
>>>>> ------------------------------------------------------------------------------------------------------------------------------------------
>>>>> I had implemented initial draft of the core time-dependent algorithm in
>>>>> 1st week. I fixed a few bugs that were there in the initial draft.
>>>>>
>>>>> Organised the code into different header files - binary_heap.h,
>>>>> weight_map.h, edge_wrapper.h.
>>>>>
>>>>> Added a boost - dijkstra test function which calls
>>>>> boost::dijkstra_shortest_paths() so as to verify the result.
>>>>> Also, wrote a graph generator which can generate random graphs
>>>>> according to the parameters specified:
>>>>> - number of vertices
>>>>> - maximum outdegree of a vertex (I keep this 6 or 8 , since 6 is degree
>>>>> limit for planar graphs)
>>>>> - Number of time windows and the range of time windows.
>>>>>
>>>>> So, to see if the result returned by tdsp-dijkstra function is
>>>>> correct,  I generated random graphs with time window 1, which starts from 0,
>>>>> meaning that the same travel time will be there for any given start time.
>>>>> This is basically static dijkstra.
>>>>>
>>>>> I compared the results returned by tdsp-dijkstra and boost-dijkstra and
>>>>> I am getting same output. Tried for graphs with 20,100,500,1000 nodes with
>>>>> max outdegree 8. (generating graphs with nodes more than that was taking too
>>>>> much time and my CPU was getting overworked!)
>>>>>
>>>>> Only difference in boost-output and tdsp-output comes when there are
>>>>> more than one shortest paths of same length. The there might be difference
>>>>> of predecessors. I guess that is because of different implementations of
>>>>> priority queue (binary_heap in my case).
>>>>>
>>>>> I have updated the code in gsoc-tdsp branch: [2]. Please review, any
>>>>> comments are welcome.
>>>>>
>>>>> Also, the actual time-dependent functionality i.e multiple time windows
>>>>> needs to be tested for real world large graphs. To do this, we are planning
>>>>> to generate time dependent data ourselves corresponding to the static data
>>>>> available in pgRouting-workshop database, since such data is not freely
>>>>> available as far as our knowledge.
>>>>>
>>>>> Some of the options for this data generation (according to discussions
>>>>> in pgrouting-dev list)are:
>>>>>
>>>>> - Generate random data (That would take most extreme test cases into
>>>>> account)
>>>>> - If we think about "rush hour" around a major city, the highways
>>>>> (based on road class) flowing into the city in the morning would get reduced
>>>>> average speeds you could apply curve like average speed*percent based on 6am
>>>>> (90%), 7am(75%), 8am(45%), 9am(50%), 10am(85%) and do something similar in
>>>>> the evening rush. It might be too hard to figure on direction of flow in/out
>>>>> bound so apply the curve to all traffic. The assumption is that the highways
>>>>> are congested which will force traffic onto side streets. We can also reduce
>>>>> the lower class speeds by say a constant 80% during rush hour.
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> ------------------------------------------------------------------------------------------------------------------------------------
>>>>> Next week goals:
>>>>>
>>>>> * Generate the time-dependent data corresponding to the data in
>>>>> pgRouting-workshop as planned above.
>>>>> * Start working on writing postgreSQL C function that will call the
>>>>> core-time dependent function.
>>>>> * Keep testing the core function, find bugs if any, and fix them.
>>>>>
>>>>> [1]
>>>>> https://github.com/pgRouting/pgrouting/wiki/Time-dependent---Dynamic-Shortest-Path
>>>>> [2] https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp
>>>>> [3]
>>>>> https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan
>>>>> --
>>>>> Regards,
>>>>> -Jay Mahadeokar
>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> Regards,
>>>> -Jay Mahadeokar
>>>> II Year, MTech,
>>>> CSE, IIT Kanpur.
>>>>
>>>
>>>
>>>
>>> --
>>> Regards,
>>> -Jay Mahadeokar
>>>
>>>
>>
>>
>> --
>> Regards,
>> -Jay Mahadeokar
>>
>>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>

-- 
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/soc/attachments/20110708/72378e5e/attachment-0001.html