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
|