GSoc 2014 Mukul Priya
- Name: Mukul Priya
- Country: India
- School and degree: International Institute Of Information Technology- Hyderabad, B.Tech(Hons) + Masters
- Email : [email protected] , [email protected] ,[email protected]
- Project Proposal
- Repository branch "gsoc-cvrptw"
- Users guide: pgr_vrpOneDepot
- Revised Goals And TimeLine
OSGeo Wiki notes: http://wiki.osgeo.org/wiki/Google_Summer_of_Code_2014_Ideas#What_to_expect_during_the_summer
- Report 1, 23-05-2014
- Report 2, 30-05-2014
- Report 3, 06-06-2014
- Report 4, 13-06-2014
- Report 5, 20-06-2014
- Report 6, 27-06-2014
- Report 7, 04-07-2014
- Report 8, 11-07-2014
- Report 9, 18-07-2014
- Report 10, 25-07-2014
- Report 11, 01-08-2014
- Report 12, 08-08-2014
- Report 13, 15-08-2014
-
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.
- 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 .
- 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 .
- No.
- 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 .
- 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.
- No
- 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.
- 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.
- No
- 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.
- 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.
- Not blocked on something but improving the optimizer is a very tricky task .
- 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.
- 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.
- No
- 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 .
- 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.
- No
- 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.
- 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.
- 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.
-
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.
- 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.
- 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.
- The optimizer will take some more time.
- 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 .
- 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.
- 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.
- 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.
- 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 .
- No
- 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.
- 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.
- No
- 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.
- 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.
- No
- 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.
- Go through the present VRP solver thoroughly .
- Discuss more about common features of different versions of VRP with my mentors .
- No
