GSoc 2014 Mukul Priya - pgRouting/pgrouting GitHub Wiki

Biography

GSoC project

My Status Reports

OSGeo Wiki notes: http://wiki.osgeo.org/wiki/Google_Summer_of_Code_2014_Ideas#What_to_expect_during_the_summer

Revised goals

Goals and New Timeline

  • week 7: Try and reduce the number of vehicles form the initial solution and then capitalize on the outcome and feed it into the optimizer .

  • week 8: Implement the 2-opt* (exchange/removal-insertion of orders between two routes ) , observe the initial results and see how it can be further improved . I have already implemented most of the portion of this method .

  • week 9-10: More improvement(after modification )if possible and Integrate it with the code and test it for CVRPTW (build test suites if required).

  • week 11-12: Tweak the optimizer for CVRP (without time windows)

  • week 13-14: Documentation and integration with pgRouting .

  • Regarding community discussions , as discussed with my mentors all the technical discussion involving the project will now be done on the developers mailing list.This will be helpful in eventually informing the community about the problems that i may face and in case of that they will also be able to give some suggestions.

Report 13

What did i do this week ?

  • The initial version of my project is ready for use. I already integrated it last week .The how to use guide is also up which is the same one developed by Razequl for VRP last year with few minor changes. Code coomenting and cleaning is also going on .

What will I be working on next ?

  • I have been working on the optimizer as there will be always some scope of improvement in that . Other things will come up as users begin to use it .

Did I meet with any stumbling blocks?

  • No.

Report 12

What did i do this week ?

  • Tried to improve my optimizer , wasn't able to do so to much extent . Tried to implement two swaps instead of one , there is still some work to do . Meanwhile i have integrated it to pgrouting , the build was successful but the sql querry is yet to be tested .

What will I be working on next week?

  • Test the integration so that it is works perfectly . have the use me guide and other documentation ready. and in between keep on testing and improving the optimizer.

Did I meet with any stumbling blocks?

  • No

Report 11

What did i do this week ?

  • I tested the optimizer for some benchmark test cases http://web.cba.neu.edu/~msolomon/problems.htm.This was mentioned in the previous to do list so i tried out some of the test cases and compared my tabu search results with the available benchmark results for the same test cases.

What will I be working on next week?

  • As discussed with my mentors , we agreed on testing and improving the optimizer further so for this week, i will try swapping (or removing-inserting) two or three orders at a time. The focus will be on closing the gap between my solution and the benchmark solution.

Did I meet with any stumbling blocks?

  • No

Report 10

What did i do this week ?

  • I improved the optimizer further more (added one more move to it), however the optimizer currently gets stuck after obtaining a local minima so it will be interesting to observe how the moves switch between themselves and have a order for the moves so that local minima is avoided.

What will I be working on next week?

  • I will test the optimizer for some benchmark test cases http://web.cba.neu.edu/~msolomon/problems.htm.This was mentioned in the previous to do list so i will try it out this weekend.
  • Will work towards further improvising the optimizer and also have a look at modifying the current implementation to solve CVRP without time windows.

Did I meet with any stumbling blocks?

  • Not blocked on something but improving the optimizer is a very tricky task .

Report 9

What did i do this week ?

  • I spent most of my time this week in modifying the optimizer and testing it . I also implemented one of the moves (swapping orders between two randomly selected routes) as per the plan mentioned in last week's report.

What will I be working on next week?

  • I will continue testing the optimizer for new data sets after adding some more neighbourhood moves or by modifying the current implementation .
  • I will also test my implementation for some benchmark test cases http://web.cba.neu.edu/~msolomon/problems.htm.

Did I meet with any stumbling blocks?

  • No

Report 8

What did i do this week ?

  • As mentioned in the time line , I implemented a basic Tabu search this week with one of the moves (2-opt*) for generating neigbourhood. I tested the implementation for a basic data set with 100 orders and was able to optimize the initial solution by some extent .

What will I be working on next week?

  • I will continue testing the optimizer for new data sets after adding one more neighbourhood move inside the tabu search.
  • Depending on the data set , it is difficult to estimate which neigbourhood move might give better results/ optimal solution. I will try and test with more data sets which have their corresponding best solution so far and then compare it with the results of my implementation.

Did I meet with any stumbling blocks?

  • No

Report 7

What did i do this week ?

  • As mentioned in the new proposed time line , i worked on reducing the number of vehicles of the generated initial solution before feeding this solution into the optimizer.However This procedure should work better after the optimizer has done its work.

What will I be working on next week?

  • I will be working on the optimizer this week as mentioned in the plan. I will be implementing the 2-opt* method for generating neighbourhood inside Tabu Search.

Did I meet with any stumbling blocks?

  • The method adopted by me to reduce the vehicles was easy to implement , however the results were not what i expected , i think after we have an optimal solution It should work .However I will give some more time to it during this weekend and see if i can improve it.

Goals and New Timeline

  • week 7: Try and reduce the number of vehicles form the initial solution and then capitalize on the outcome and feed it into the optimizer .

  • week 8: Implement the 2-opt* (exchange/removal-insertion of orders between two routes ) , observe the initial results and see how it can be further improved . I have already implemented most of the portion of this method .

  • week 9-10: More improvement(after modification )if possible and Integrate it with the code and test it for CVRPTW (build test suites if required).

  • week 11-12: Tweak the optimizer for CVRP (without time windows)

  • week 13-14: Documentation and integration with pgRouting .

  • Regarding community discussions , as discussed with my mentors all the technical discussion involving the project will now be done on the developers mailing list.This will be helpful in eventually informing the community about the problems that i may face and in case of that they will also be able to give some suggestions.

Report 6

What did i do this week ?

  • Too many things happened this week and I am glad that the project is still on.I am really thankful to my mentors and Anne for keeping the project alive. As I mentioned in my last weekly report, I spent this week implementing the optimizer for CVRPTW ( Tabu search with 2-opt and 2-opt*) . I am still working on the same thing.

What will I be working on next week?

  • As Asked by Anne ,i will first work on having a new goal list and a detailed time schedule for the same after having a discussion with my mentors according to which the project will be evaluated in future.
  • The first priority will always be of having a working CVRPTW and I will be spending most of my time implementing the optimizer this week also.

Did I meet with any stumbling blocks?

  • The optimizer will take some more time.

Report 5

What did i do this week ?

  • After not able to debug the original VRP_Basic code (The Tabu search segment) I started implementing my own VRP after having a discussion with my mentors . I have borrowed the class architecture and the data structure form VRP basic code but the methods and implementation will be different. I have already coded the initial solution segment using Steve's note on the same topic ( sequential construction and hill climbing). There are few bugs in the code right now and i am fixing the same .

What will I be working on next week?

  • After discussion with my mentors , i will start implementing the Tabu search , it is a tricky thing to do so it might require a few more days and a lot of discussion. Once it is done , the next step will be to focus on other goals of the project.

Did I meet with any stumbling blocks?

  • The tabu search is kind of difficult to implement , i got stuck on VRP basic code and spent a lot more time then expected on that . However after discussion with my mentors , i felt implementing the whole thing again would be the best job to do here.

Report 4

What did i do this week ?

  • I am still working on the optimizer(tabu search).Modifying and trying to compile the Vrp_basic code so that i can make it work for the TSP problem at least and after that modify it for VRP. This paper (section 2.3) Gives a very simple and algorithmic example of Tabu search and has been very helpful.

What will I be working on next week?

  • I think i will get the optimizer working this weekend , if not then the first priority will be to get it in working condition and after that tweak it and see results for VRP and its variants.
  • The focus will be on discussion with my mentors and implementation of my initial plan .

Did I meet with any stumbling blocks?

  • No

Report 3

What did i do this week ?

  • As per the initial plan for this week , the goal was to either get the optimizer of VRP_basic working or implement a new one . I went through the code initially but dropped the idea and started implementing a new one.we have got the initial feasible solution ready and the next step is to implement the optimizer.

What will I be working on next week?

  • Get the optimizer working ,at least a basic one such that we can solve the basic VRP and TSP.
  • Once the above goal is achieved which will then give me a better understanding of the problem in terms of implementation , i will then be able to get a better view on the architectural aspect of the general solver which is the ultimate goal.

Did I meet with any stumbling blocks?

  • No

Report 2

What did i do this week ?

  • Read more about the different category of VRP problems and different optimization techniques that can be used to obtain an optimal result.
  • Went through the VRP_Basic code and had a discussion with my mentors on the same.

What will I be working on next week?

  • Study the optimizer used in VRP_Basic and try to make it work , if not then start implementing a new optimizer.
  • Initially we have planned to focus on solving basic VRP and TSP and that is the goal for the coming weeks.

Did I meet with any stumbling blocks?

  • No

Report 1

What did i do this week ?

  • As per the plan i read the paper provided by Steve and also researched a bit more about various versions of VRP.
  • Had a look at Optaplanner as well to get some more idea about implementation. * Had a quick look at the present VRP solver code (not very thoroughly though).
  • The other things like repository branch has already been set up. I am already familiar with the code base and other stuff.

What will I be working on next week?

  • Go through the present VRP solver thoroughly .
  • Discuss more about common features of different versions of VRP with my mentors .

Did I meet with any stumbling blocks?

  • No