GSoC 2014 Manikanta Kondeti - pgRouting/pgrouting GitHub Wiki

Report List

Biography:

GSoC Project:

Status Reports:

Report 13

My initial plan:

  • Try to finish up the remaining tasks

What did i do this week?

  • Integration into pgRouting and wrote a bit of documentation

What will I be working on next week?

  • Working on optimization the solution.

Did I meet with any stumbling blocks?

  • No

Report 12

My initial plan:

  • Complete that integration and jump into improvising the solution and documentation.
  • And also code review

What did i do this week?

  • Integration into pgRouting and wrote a bit of documentation

What will I be working on next week?

  • Try to finish up the remaining tasks

Did I meet with any stumbling blocks?

  • No

Report 11

My initial plan:

  • To integrate it into pgRouting

What did i do this week?

  • Trying to integrate it into pgRouting.
  • Sorted out all the errors and understanding that spi code which is helpful to take data from postgresql db.

What will I be working on next week?

  • Complete that integration and jump into improvising the solution and documentation.
  • And also code review

Did I meet with any stumbling blocks?

  • No

Report 10

My initial plan:

  • Implementing a few things with OOP and try to write the optimizer.

What did i do this week?

  • As per the plan I've reimplemented and designed a few things. Now most of them in objects for a better understanding.
  • Wrote an optimizer which is partially working.
  • Tested it with all the input files and its working for every test case.

What will I be working on next week?

  • I will be working on Integration into pgRouting which will be my final task for the project.

Did I meet with any stumbling blocks?

  • A few postgresql and postgis errors. Sorted it out

Report 9

My initial plan:

  • To start writing TABU and optimizing the solution.

What did i do this week?

  • Rewriting the data structures. Need to think more on object oriented. So I started reading a bit about OOP concepts.
  • Getting a clear picture on Neighborhoods and the Reactive-TABU part.
  • Got struck with the logic, and how to store the moves. I'm working on it. Will update it by next week.

What will I be working on next week?

  • Implementing a few things with OOP and try to write the optimizer.

Did I meet with any stumbling blocks?

  • No.

Report 8

My initial plan:

*To read about TABU and start coding it.

What did i do this week?

  • Working on TABU search. Read some good references provided by steve.
  • Trying to apply neighborhood moves and storing them in TABU list (doing it locally). I will push it within 1 or 2 days.

What will I be working on next week?

  • I will be working on TABU and have to discuss with my mentors, optimization will be heart of my project. I will try my best to get it done.

Did I meet with any stumbling blocks?

  • No.

Report 7

My initial plan:

*To read about TABU and start coding it.

What did i do this week?

  • I was trying to resolve the bugs.
  • I also read the paper (Reactive TABU search). I will discuss with my mentors and start coding.

What will I be working on next week?

  • I will be working on TABU and have to discuss with my mentors, optimization will be heart of my project. I will try my best to get it done.

Did I meet with any stumbling blocks?

  • There are few bugs on the initial solution. I got struck there and I'm trying hard to resolve them. You can find that code in tester folder in brach gsoc-vrppdtw. Below is the link.

Report 6

My initial plan:

  • To implement a TABU optimization on the initial solution. This will be the important task in my project. Will spend a few more days on reading the resources and discuss with my mentors & will start coding.

What did i do this week?

  • This week I did'nt concentrate on coding. I started with few resources and read them.
  • Due to some unfortunate situations I was busy with some other work.
  • I will try to recover this tasks in the next week schedule.

What will I be working on next week?

  • Need few more days to read about TABU and code it.
  • From now you can follow everything up to date. I started to write a wiki for live updates.

Did I meet with any stumbling blocks?

  • At the moment I’m not blocked.

Report 5

My initial plan:

  • To complete the basic solution in a few days.

What did i do this week?

  • Coded the initial solution and Eventually the first step is done. I have to remove some unnecessary things.
  • Cleared most of the bugs and trying to implement it with vectors instead of arrays.

What will I be working on next week?

  • My next step will be to implement a TABU optimization on the initial solution. This will be the important task in my project. Will spend a few more days on reading the resources and discuss with my mentors & will start coding.
  • From now you can follow everything up to date. I started to write a wiki for live updates.

Did I meet with any stumbling blocks?

  • At the moment I’m not blocked.

Report 4

My initial plan:

  • To decide which algorithm to implement and start coding. Had some discussions with my mentors, which helped me a lot.
  • Design the data structures and collect all the test data into separate folder.

What did i do this week?

  • As per the plan I decided to start coding the solution. i.e.. to get the initial feasible solution.
  • Read the paper and My mentors helped me a lot in understanding each step clearly.

What will I be working on next week?

  • I will try to complete the basic solution in a few days.
  • From now you can follow everything up to date. I started to write a wiki for live updates.

Did I meet with any stumbling blocks?

  • At the moment I’m not blocked.

Report 3

My initial plan:

  • I will spend few more days on understanding simulated annealing code.
  • After that will start designing data structures and proceed according to the plan mentioned in proposal.

What did i do this week?

  • Collected a few more resources which are useful for VRP & read them all. Watched some videos related to VRP. Resource-1 Resource-2
  • After reading these resources got to know some more heuristics. Read Clarke and Wright algorithm and Implemented it. Tested it with some data and it worked fine. Ofcourse there are some bugs in it. Will try to solve it.
    Source code - Clarke and Wright Algorithm
  • Discussing with my mentors about heuristics and also regarding test data.

What will I be working on next week?

  • By now initial plan is set i.e.. we need to apply some heuristic to get a basic feasible solution. Next step is to discuss with my mentors and see what optimization technique is appropriate and easy to implement.
  • Design the data structures and collect all the test data into separate folder.

Did I meet with any stumbling blocks?

  • At the moment I’m not blocked.

Report 2

My initial plan:

  • To understand the different optimization techniques.
  • Understand Simulated Annealing code.

What did i do this week?

  • Completed reading the paper provided by Steve sir. Paper on PDPTW
  • Reading more about local search methods(Hill Climbing, Simulated Annealing, Genetic Algorithm).
  • Started understanding Simulated Annealing code and put it in Github.
  • Refined project plan and will update it on my page (Notes link).

What will I be working on next week?

  • I will spend few more days on understanding simulated annealing code.
  • After that will start designing data structures and proceed according to the plan mentioned in proposal.

Did I meet with any stumbling blocks?

  • At the moment I’m not blocked.

Report 1

My initial plan:

  • To install everything perfectly.
  • To Study the problem carefully.
  • Understanding the pgRouting architecture.

What did i do this week?

  • Research on different optimization techniques.
  • Initially I started with TABU search and want to get more clarity. So I decided to understand these algorithms as well. 1. Genetic Algorithm 2. Simulated Annealing
  • Reading the paper provided by Steve sir. Paper on PDPTW

What will I be working on next week?

  • I will spend a week more on these algorithms and discuss with my mentors and start designing as per plan in the report.
  • By next week my main goal is to clearly understand all of these & choose the appropriate optimization for solving VRP-Pickup and Delivery Problem and also to set some basic goals for my project.

Did I meet with any stumbling blocks?

  • I had some doubts regarding git errors and compiling pgRouting. My mentors helped me to solve those.
  • At the moment I’m not blocked.