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 XCOOR= 0 0 ! 6 ; 7 9 YCOOR= 0 12 ! 5 ; 15 12 ! Amount to be delivered to each customer; Q= 0 48 ! 36; 43 92 ! 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