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

pgRouting pgrouting-dev
1

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 .

  1. 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 .

  2. 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

2

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/~msolomon/problems.htm&gt; ).

             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