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

[Stephen Woodbridge]

Hi Mukul,

Thank you for the update on your project and the explanation. It sounds 
like you are making good progress get the optimizer working.

Another variation on your move or swap pairs or triplets of orders. So 
if you can not find single order moves that proved a savings, start with 
adjacent pairs of orders and move the pair like you would a single 
order. The reason for this is that if two orders are in close proximity 
to one another then moving one or the other by itself is not a good move 
but moving both together is.

So for example here are two routes where orders b,c need to be swapped 
with orders u,v

R1:  a-\ /-b---c-\ /-d---e
         \         \
R2:  t-/ \-u---v-/ \-w---x

to get:

R1:  a---b---c---d---e

R2:  t---u---v---w---x

This can also be applied to moving a pair of triplet from one route to 
another.

Something to consider if you are not already doing this.

-Steve

On 7/31/2014 3:34 AM, Mukul priya wrote:
> 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
> <http://web.cba.neu.edu/%7Emsolomon/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
>
>