The vehicle routing problem occurs in many service systems such as delivery, customer pick-up, repair and maintenance. A fleet of vehicles, each with fixed capacity, starts at a common depot and returns to the depot after visiting locations where service is demanded. The objective is to minimize the total distance of all the routes.

In general, it takes much longer to find the best routes as the number of locations grow. Large versions of this model may have to be tackled using some form of heuristics.

In this particular example, we are delivering one product to seven cities with the depot at city 1.

MODEL:

 

! The Vehicle Routing Problem (VRP);

 

SETS:

 ! Q(I) is the amount required at city I,

   U(I) is the accumulated delivers at city I ;

  CITY/1..8/: Q, U;

 

 ! DIST(I,J) is the distance from city I to city J

   X(I,J) is 0-1 variable: It is 1 if some vehicle

   travels from city I to J, 0 if none;

  CXC( CITY, CITY): DIST, X;

ENDSETS

 

DATA:

 ! city 1 represent the common depo;

  Q  =  0    6    3    7    7   18    4    5;

 

 ! distance from city I to city J is same from city

   J to city I distance from city I to the depot is

   0, since the vehicle has to return to the depot;

 

  DIST =  ! To City;

 ! Chi  Den Frsn Hous   KC   LA Oakl Anah   From;

     0  996 2162 1067  499 2054 2134 2050!Chicago;

     0    0 1167 1019  596 1059 1227 1055!Denver;

     0 1167    0 1747 1723  214  168  250!Fresno;

     0 1019 1747    0  710 1538 1904 1528!Houston;

     0  596 1723  710    0 1589 1827 1579!K. City;

     0 1059  214 1538 1589    0  371   36!L. A.;

     0 1227  168 1904 1827  371    0  407!Oakland;

     0 1055  250 1528 1579   36  407    0;!Anaheim;

 

 ! VCAP is the capacity of a vehicle ;

  VCAP = 18;

ENDDATA

 

 ! Minimize total travel distance;

  MIN = @SUM( CXC: DIST * X);

 

 ! For each city, except depot....;

  @FOR( CITY( K)| K #GT# 1:

 

 ! a vehicle does not traval inside itself,...;

    X( K, K) = 0;

 

 ! a vehicle must enter it,... ;

    @SUM( CITY( I)| I #NE# K #AND# ( I #EQ# 1 #OR#

     Q( I) + Q( K) #LE# VCAP): X( I, K)) = 1;

 

 ! a vehicle must leave it after service ;

    @SUM( CITY( J)| J #NE# K #AND# ( J #EQ# 1 #OR#

     Q( J) + Q( K) #LE# VCAP): X( K, J)) = 1;

 

 ! U( K) is at least amount needed at K but can't

   exceed capacity;

    @BND( Q( K), U( K), VCAP);

 

 ! If K follows I, then can bound U( K) - U( I);

    @FOR( CITY( I)| I #NE# K #AND# I #NE# 1:

     U( K) >= U( I) + Q( K) - VCAP + VCAP *

      ( X( K, I) + X( I, K)) - ( Q( K) + Q( I))

       * X( K, I);

    );

 

 ! If K is 1st stop, then U( K) = Q( K);

    U( K) <= VCAP - ( VCAP - Q( K)) * X( 1, K);

 

 ! If K is not 1st stop...;

    U( K)>= Q( K)+ @SUM( CITY( I)|

     I #GT# 1: Q( I) * X( I, K));

  );

 

 ! Make the X's binary;

  @FOR( CXC: @BIN( X));

 

 ! Minimum no. vehicles required, fractional

   and rounded;

  VEHCLF = @SUM( CITY( I)| I #GT# 1: Q( I))/ VCAP;

  VEHCLR = VEHCLF + 1.999 -

   @WRAP( VEHCLF - .001, 1);

 

 ! Must send enough vehicles out of depot;

  @SUM( CITY( J)| J #GT# 1: X( 1, J)) >= VEHCLR;

END

Model: VROUTE