[Soc] TDSP implementation for pgRouting Weekly Report

Thu Jun 23 21:17:17 EDT 2011

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