Lindo Systems

MODEL:   !(peapod1);
! Keywords: Vehicle routing, Routing, LTL delivery;
! The Vehicle Routing Problem (VRP) occurs in many service 
systems such as delivery, customer pick-up, repair and 
maintenance. A fleet of vehicles, each with fixed 
capacity, makes a trip starting at a common depot and
returning to the depot after visiting locations where
service is demanded. The amount of demand assigned to a 
trip cannot exceed vehicle capacity.

  To apply this LINGO model to a specific situation, you only
need understand and change the data in the DATA section.
  To solve, click on the red bullseye.
  To see the solution, click on the X= icon.
  The links used in the trips are specified by the
nonzero X(i,j)'s in the solution.

  This is a small, simple formulation. Problems with more
than a dozen cities can take lots of time. There are
alternative, bigger, faster formulations.  
For a copy of LINGO, see http://www.lindo.com;

SETS:
CITY: Q, XCOOR, YCOOR, U;
! Q(I) = amount required at city I(given),
     must be delivered by just 1 vehicle.
  U(I) = accumulated deliveries at city I ;
CXC( CITY, CITY): DIST, X;
! DIST(I,J) = distance from city I to city J
  X(I,J) is 0-1 variable, 
      = 1 if some vehicle travels from city I to J,
else 0 ;
ENDSETS

DATA:
! Webvan case;
CITY=  W  C1 ! C2; C3  C4 ! C5  C6 ; C7 ! C8  C9 C10 C11; C12 C13;
XCOOR= 0   0 ! 6 ;  7   9 ! 15  20 ; 17 !  7   1  15  20;   7   2;
YCOOR= 0  12 ! 5 ; 15  12 !  3   0 ; -2 ! -4  -6  -6  -7;  -9 -15;
! Amount to be delivered to each customer;
    Q= 0  48 ! 36; 43  92 !  57  16; 56 ! 30  57  47  91;  55  38;
! VCAP is the capacity of a vehicle ;
VCAP = 200;
ENDDATA

!----------------------------------------------------------;
!Compute the (Euclidean) distance matrix;
 @FOR( CXC(I,J):
   DIST(I,J) = ((XCOOR(I)-XCOOR(J))^2 + (YCOOR(I)-YCOOR(J))^2)^.5;
     );
!----------------------------------------------------------;
! The objective is to minimize total distance traveled;
MIN = @SUM( CXC(I,J): DIST(I,J) * X(I,J));

! for each city K, except depot....;
@FOR( CITY( K)| K #GT# 1:
! a vehicle must enter city K from some city I,... ;
  @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 city K after service ;
  @SUM( CITY( J)| J #NE# K #AND# ( J #EQ# 1 #OR#
        Q( J) + Q( K) #LE# VCAP): X( K, J)) = 1;
! city K cannot travel back to itself,...;
   X( K, K) = 0;

! U( K) = amount delivered on trip up to city K
    >= amount needed at K but <= vehicle capacity;
    @BND( Q( K), U( K), VCAP);
! If K follows I, then U( K) >= U(I) + Q(K)..;
   @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);
        );

! Optional cuts:
  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( I, J): @BIN( X( I, J)) ;);
! Must send enough vehicles out of depot;
  @SUM( CITY( J)| J #GT# 1: X( 1, J)) >= 
      @FLOOR((@SUM( CITY( I)| I #GT# 1: Q( I))/ VCAP) + .999);
END