[Soc] TDSP implementation for pgRouting Weekly Report

Fri Jun 17 22:18:43 EDT 2011

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/soc/attachments/20110618/da42ce77/attachment.html