<div dir="ltr"><div>Hi Everyone ,<br><br></div><div>             I have been implementing Capacitated vehicle routing problem with time windows as my gsoc project under pgrouting . The most important task is the optimization part(<b>tabu search</b> here) for which by far i have implemented 3 different moves to avoid local minima but still the solution is not very close to the benchmark test results( <a href="http://web.cba.neu.edu/~msolomon/problems.htm">http://web.cba.neu.edu/~msolomon/problems.htm</a>  ).  <br>
<br></div><div>            For understanding purpose , i am explaining the structure of the solution a bit .Lets say the solution is called a collection of tours . Each tour is a collection of orders served by  a vehicle .<br>
</div><div><br></div><div>        The three different moves are :<br></div><div>1. Remove an order from one tour and insert into another tour<br></div><div>    What i do here is iterate over each of the tours, choose an order remove it from one of the tours and insert it into another , update the final solution if it is better than the previous best solution then we swap the best solution with this solution and mark the move as tabu move . <br>
<br></div><div>2. This move is a better version of the previous one , but here what i do is find the closest pair of orders in randomnly selected two tours and try to club them  together and then again carry on with the same process as above .<br>
<br></div><div>3. In this move , instead of removing what i do is swap orders between any two tours and then have a look at the solution.<br><br></div><div>         My optimizer keeps obtaining a local minima every now and then and i think the way the moves switch from one another is the trick here . so i am trying to figure out the best way in which the moves will switch among each other once the optimizer attains a local minima .<br>
           <br></div><div>         Currently i have not integrated my code with pgrouting and i have been testing only using the c++ code that i have . I am parsing the data for now and using it for my solver . I will intergrate it soon so that everyone can test it or use it . The code clean up is also required for now . Howver you can have a look at the code and solution of certain benchmark test cases here .<br>
<a href="https://github.com/pgRouting/pgrouting/tree/gsoc-cvrptw/src/cvrptw/tester">https://github.com/pgRouting/pgrouting/tree/gsoc-cvrptw/src/cvrptw/tester</a> <br><br></div><div>  Feel free to suggest anything .<br><br>
<br></div><div>Thanks and regards ,<br></div><div>Mukul <br></div><div><br>         <br></div></div>