[pgrouting-dev] Capacitated Vehicle routing problem with time windows

[Mukul priya]

Hi Everyone ,

             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(*tabu search* 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(
http://web.cba.neu.edu/~msolomon/problems.htm  ).

            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 .

        The three different moves are :
1. Remove an order from one tour and insert into another tour
    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 .

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 .

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.

         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 .

         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 .
https://github.com/pgRouting/pgrouting/tree/gsoc-cvrptw/src/cvrptw/tester

  Feel free to suggest anything .


Thanks and regards ,
Mukul
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20140731/1343fcc1/attachment.html>