Lindo Systems
! The Vehicle Routing Problem (VRP), with time windows (VRouteWindow);
! Keywords: Vehicle Routing, Routing, LTL Delivery, Time Windows;
SETS:
! Definitions:
Parameters:
Q(i) is the amount required at city i,
DIST(i,j) is the distance from city i to city j,
Variables:
Z(i,j) = 1 if some vehicle travels from city i to city j, else 0,
LOADCUM(i) is the accumulated deliveries at city i ;
! Time related definitions:
Parameters:
TMPM = time per mile,
TME(k) = earliest allowed arrival time at stop k,
TML(k) = latest allowed arrival time at k,
TMV(k) = stop or visit time at k,
TMAX = maximum time for any trip, e.g., 11 hrs in US,
MXTRK = maximum number of trucks\vehicles.
Variables:
TMA(k) = arrival time at k;
CITY: Q, LOADCUM, DISTCUM, TME, TML, TMV, TMA;
CXC( CITY, CITY): DIST, Z;
ENDSETS
DATA:
! Case 1;
!Case01; TMPM = 1.2; ! Time per mile;
!Case01; TMAX = 99999; ! Upper limit on time for a trip;
!Case01; VCAP = 18; ! Capacity of a vehicle ;
!Case01; DISTMAX = 5000; ! Max distance allowed on a trip;
!Case01; MXTRK = 9999; ! Max vehicles allowed;
!Case01; TOLOPT = 0.0000001; ! Optimality tolerance;
! city 1 represents the common depot;
! 1 2 3 4 5 6 7 8 9 10 11 12;
!Case01; CITY = Chi Den Frsn Hous KC LA Oakl Anah Peor Phnx Prtl Rvrs;
! Amount to be delivered to each customer (must be 0 for depot);
!Case01; Q= 0 6 3 7 7 18 4 5 2 6 7 2;
! Earliest time;
!Case01; TME= 0 1000 2800 2000 1800 3600 3500 2400 100 1500 1800 1900;
! Latest time;
!Case01; TML=99999 2500 2900 3000 3900 3900 3900 3800 800 2400 2800 3800;
! Visit time at each city;
!Case01; TMV = 0 10 12 10 10 14 10 10 10 10 11 12;
! city 1 represents the common depot, i.e. Q( 1) = 0;
! city 1 represents the common depot, i.e. Q( 1) = 0;
! Distance from city I to city J is same(but need not be) from J to I,
distance from city I to the depot maybe 0(but need not be),
if vehicle need not return to the depot ;
!Case01; DIST= ! To City;
! Chi Den Frsn Hous KC LA Oakl Anah Peor Phnx Prtl Rvrs;
!Case01; 0 996 2162 1067 499 2054 2134 2050 151 1713 2083 2005! Chicago;
!Case01; 996 0 1167 1019 596 1059 1227 1055 904 792 1238 1010! Denver;
!Case01; 2162 1167 0 1747 1723 214 168 250 2070 598 745 268! Fresno;
!Case01; 1067 1019 1747 0 710 1538 1904 1528 948 1149 2205 1484! Houston;
!Case01; 499 596 1723 710 0 1589 1827 1579 354 1214 1809 1535! K. City;
!Case01; 2054 1059 214 1538 1589 0 371 36 1943 389 959 54! L. A.;
!Case01; 2134 1227 168 1904 1827 371 0 407 2043 755 628 425! Oakland;
!Case01; 2050 1055 250 1528 1579 36 407 0 1933 379 995 45! Anaheim;
!Case01; 151 904 2070 948 354 1943 2043 1933 0 1568 2022 1889! Peoria;
!Case01; 1713 792 598 1149 1214 389 755 379 1568 0 1266 1266! Phoenix;
!Case01; 2083 1238 745 2205 1809 959 628 995 2022 1266 0 1001! Portland;
!Case01; 2005 1010 268 1484 1535 54 425 45 1889 335 1001 0;! Rverside;
! Case 2;
!Case02 TMPM = 0.02; ! Time per mile;
!Case02 TMAX = 9; ! Upper limit on time for a trip;
!Case02 VCAP = 9999; ! Capacity of a vehicle ;
!Case02 DISTMAX = 5000; ! Max distance allowed on a trip;
!Case02 MXTRK = 9; ! Max vehicles allowed
!Case02 TOLOPT = 0.2; ! Optimality tolerance;
!Case02 CITY =
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17;
! Amount to be delivered to each customer (must be 0 for depot);
!Case02 Q =
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1;
!Case02 TME = 0 ; ! Earliest time at each stop;
!Case02 TML = 99999; ! Latest time;
! Time required at CUST i;
!Case02 TMV =
0 2 2 2 2 2 2 2 2 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5;
! DIST(i,j) = Distance from i (row) to j (col);
!Case02 DIST=
0 33 4 21 110 45 7 33 15 74 64 15 64 80 109 30 10
33 0 37 21 96 41 26 29 46 55 74 46 54 69 104 51 42
4 37 0 25 114 49 11 37 12 78 65 12 67 83 111 27 6
21 21 25 0 91 27 17 13 36 53 55 36 45 61 92 49 31
110 96 114 91 0 65 107 78 125 41 70 125 46 31 33 139 119
45 41 49 27 65 0 43 14 60 33 35 60 19 35 65 75 54
7 26 11 17 107 43 0 30 20 70 66 20 61 78 108 32 16
33 29 37 13 78 14 30 0 48 41 45 48 31 48 79 62 42
15 46 12 36 125 60 20 48 0 89 75 0 79 95 122 18 6
74 55 78 53 41 33 70 41 89 0 57 89 18 21 56 101 83
64 74 65 55 70 35 66 45 75 57 0 75 39 44 53 92 69
15 46 12 36 125 60 20 48 0 89 75 0 79 95 122 18 6
64 54 67 45 46 19 61 31 79 18 39 79 0 16 51 93 73
80 69 83 61 31 35 78 48 95 21 44 95 16 0 36 109 89
109 104 111 92 33 65 108 79 122 56 53 122 51 36 0 139 116
30 51 27 49 139 75 32 62 18 101 92 18 93 109 139 0 23
10 42 6 31 119 54 16 42 6 83 69 6 73 89 116 23 0 ;
! Case 3;
!Case03 TMPM = 0.02; ! Time per mile;
!Case03 TMAX = 9; ! Upper limit on time for a trip;
!Case03 VCAP = 9999; ! Capacity of a vehicle ;
!Case03 DISTMAX = 5000; ! Max distance allowed on a trip;
!Case03 MXTRK = 9; ! Max vehicles allowed ! CUST = ;
!Case03 TOLOPT = 0.6; ! Optimality tolerance;
!Case03 CITY =
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25;
!Case03 Q = 1; ! A simple, you must visit problem;
!Case03 TME = 0 ; ! Earliest time at each stop;
!Case03 TML = 99999; ! Latest time;
! Time required at CUST i;
!Case03 TMV =
0 2 2 2 2 2 2 2 2 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1 1 1 1 1 1;
! DIST( i, j) = Distance from i (row) to j (col);
!Case03 DIST=
0 33 4 21 110 45 7 33 15 74 64 15 64 80 109 30 10 32 15 54 71 9 20 21 140
33 0 37 21 96 41 26 29 46 55 74 46 54 69 104 51 42 58 32 78 77 36 19 49 130
4 37 0 25 114 49 11 37 12 78 65 12 67 83 111 27 6 28 15 50 73 11 24 17 143
21 21 25 0 91 27 17 13 36 53 55 36 45 61 92 49 31 52 30 74 60 18 3 41 122
110 96 114 91 0 65 107 78 125 41 70 125 46 31 33 139 119 142 120 164 61 104 92 131 36
45 41 49 27 65 0 43 14 60 33 35 60 19 35 65 75 54 77 57 99 36 38 30 66 95
7 26 11 17 107 43 0 30 20 70 66 20 61 78 108 32 16 35 13 57 73 13 16 25 138
33 29 37 13 78 14 30 0 48 41 45 48 31 48 79 62 42 65 43 86 48 27 16 54 108
15 46 12 36 125 60 20 48 0 89 75 0 79 95 122 18 6 17 16 38 83 22 35 6 154
74 55 78 53 41 33 70 41 89 0 57 89 18 21 56 101 83 105 82 127 52 69 54 94 76
64 74 65 55 70 35 66 45 75 57 0 75 39 44 53 92 69 91 78 111 11 55 57 81 87
15 46 12 36 125 60 20 48 0 89 75 0 79 95 122 18 6 17 16 38 83 22 35 6 154
64 54 67 45 46 19 61 31 79 18 39 79 0 16 51 93 73 96 74 117 35 57 46 85 77
80 69 83 61 31 35 78 48 95 21 44 95 16 0 36 109 89 111 90 133 36 73 63 101 61
109 104 111 92 33 65 108 79 122 56 53 122 51 36 0 139 116 139 121 160 43 101 95 129 35
30 51 27 49 139 75 32 62 18 101 92 18 93 109 139 0 23 10 20 27 101 38 47 12 169
10 42 6 31 119 54 16 42 6 83 69 6 73 89 116 23 0 23 15 45 78 16 30 12 148
32 58 28 52 142 77 35 65 17 105 91 17 96 111 139 10 23 0 26 22 100 39 51 11 171
15 32 15 30 120 57 13 43 16 82 78 16 74 90 121 20 15 26 0 46 86 24 28 17 151
54 78 50 74 164 99 57 86 38 127 111 38 117 133 160 27 45 22 46 0 120 60 73 33 192
71 77 73 60 61 36 73 48 83 52 11 83 35 36 43 101 78 100 86 120 0 63 62 90 77
9 36 11 18 104 38 13 27 22 69 55 22 57 73 101 38 16 39 24 60 63 0 18 28 132
20 19 24 3 92 30 16 16 35 54 57 35 46 63 95 47 30 51 28 73 62 18 0 40 124
21 49 17 41 131 66 25 54 6 94 81 6 85 101 129 12 12 11 17 33 90 28 40 0 160
140 130 143 122 36 95 138 108 154 76 87 154 77 61 35 169 148 171 151 192 77 132 124 160 0;
ENDDATA
! Warning: This simple formulation will probably perform poorly
for >> 12 cities. Larger problems require more sophisticated formulations;
SUBMODEL VROUTE:
! Variables:
Z( i, j) = 1 if some vehicle travels from city i to city j, else 0,
LOADCUM( i) is the accumulated deliveries at city i,
TMA( i) = time of arrival at CITY i ;
! Minimize total travel distance + a slight wgt to arriving early;
MIN = DISTOT + 0.0001 * @SUM( CITY( i) | i #NE# DEPOTI: TMA( i));
DISTOT = @SUM( CXC( i, j): DIST( i, j) * Z( i, j));
@FOR( CITY( k):
! a vehicle does not travel inside itself,...;
Z( k, k) = 0;
);
! For each city, except depot....;
@FOR( CITY( k)| k #NE# DEPOTI:
! a vehicle must enter city K from some city I, together
their demands cannot exceed vehicle capacity, and
cannot make too long a trip (assumes triangle inequality... ;
[NTR] @SUM( CITY( i)| i #NE# k #AND# ( i #EQ# DEPOTI #OR#
(( Q( i) + Q( k) #LE# VCAP) #AND# ( DIST( DEPOTI, i) + DIST( i, k) + DIST( k, DEPOTI) #LE# DISTMAX))):
Z( i, k)) = 1;
! a vehicle must leave K after service to some city J;
[XIT] @SUM( CITY( j)| j #NE# k #AND# ( j #EQ# DEPOTI #OR#
(( Q( j) + Q( k) #LE# VCAP) #AND# ( DIST( DEPOTI, k) + DIST( k, j) + DIST( j, DEPOTI) #LE# DISTMAX))):
Z( k, j)) = 1;
! LOADCUM( k) is at least amount needed at K, but can't
exceed vehicle capacity;
@BND( Q( k), LOADCUM( k), VCAP);
! If K follows I, then can bound LOADCUM( k) - LOADCUM( i);
@FOR( CITY( i)| i #NE# k #AND# i #NE# DEPOTI:
[LCUM] LOADCUM( k) >= LOADCUM( I)
+ Q( k)* Z( i, k) ! Case: i precedes k;
- Q( i)* Z( k, i) ! Case: k precedes i;
+( Q( k) - VCAP)*(1- Z( i, k)- Z( k, i)) ; ! Case: neither above;
);
! If K is 1st stop, then LOADCUM( k) = Q( k);
LOADCUM( k) <= VCAP - ( VCAP - Q( k)) * Z( DEPOTI, k);
! If K is not 1st stop...;
LOADCUM( k) >= Q( k) + @SUM( CITY( i)| I #NE# DEPOTI: Q( i) * Z( i, k));
);
! Compute the total distance traveled by the vehicle through k;
@FOR( CITY( k):
[R_TD_1] DISTCUM( k) >= DIST( DEPOTI, k)* Z( DEPOTI, k);
@FOR( CITY( i)| i #NE# DEPOTI:
[R_TD] DISTCUM( k) >= DISTCUM( i)
+ DIST( i, k)* Z( i, k) ! Case: i precedes k;
- DISTMAX * ( 1 - Z(i, k))
);
);
! Longest trip cannot exceed max trip length;
DISTCUM( DEPOTI) <= DISTMAX;
! Make the X's binary;
@FOR( CXC( i, j): @BIN( Z( i, j)));
! Parameters:
! TMPM = time per mile,
TME( k) = earliest allowed arrival time at stop K,
TML( k) = latest allowed arrival time at K,
TMV( k) = stop or visit time at K,
TMAX = maximum time for any trip, e.g., 11 hrs in US,;
! Time window related constraints;
@FOR( CITY( k)| k #NE# DEPOTI:
@FOR( CITY( i) | i #NE# k:
! Time of arrival at K if preceding stop was I;
[RTM] TMA( k) >= TMA(i)
+ ( TMV( i) + TMPM* DIST( i, k))* Z( i, k)
- TML( i)*(1- Z( i, k));
! Must arrive within the [TME, TML] window. We are allowed to wait
in order to arrive no earlier than TME(k);
@BND( TME( k), TMA( k), TML( k));
);
! Max trip time constraint, assumes distance matrix
satisfies triangle inequality;
[XT] TMA( k) + TMV( k) + TMPM* DIST( k, DEPOTI)* Z( k, DEPOTI) <= TMAX;
);
! Max vehicles\trucks constraint;
@SUM( CITY( j) | j #NE# DEPOTI: Z( DEPOTI, j)) <= MXTRK;
! Some optional cuts;
! Minimum no. vehicles required,
fractional, and rounded up;
VEHCLF = @SUM( CITY( I)| I #NE# DEPOTI: Q( I))/ VCAP;
VEHCLR = @FLOOR( VEHCLF +.9999);
! Must send enough vehicles out of depot;
@SUM( CITY( j) | j #NE# DEPOTI: Z( DEPOTI, j)) >= VEHCLR;
! Subtour size 2 cuts, cannot go i to j and j to i,
( Case Q(i) + Q(j) #GT# VCAP already taken care of);
@FOR( CITY( i) | i #NE# DEPOTI:
@FOR( CITY( j) | j #GT# i #AND# Q( i) + Q( j) #LE# VCAP:
Z( i, j) + Z( j, i) <= 1;
);
);
! Subtours of size 3 cuts,( Case Q(i) + Q(j) #GT# VCAP already taken care of);
@FOR( CITY( i) | i #NE# DEPOTI:
@FOR( CITY(j) | j #NE# DEPOTI #AND# i #LT# j :
@FOR( CITY(k) | k #NE# DEPOTI #and# j #LT# k:
[TRIPL] Z(i,j) + Z(j,i) + Z(i,k) + Z(k,i) + Z(j,k) + Z(k,j) <= 2;
);
);
);
! Cut: Cannot go from i to j if trip would be too long(Assume triangle inequality);
@FOR( CITY( i) | i #NE# DEPOTI:
@FOR( CITY( j) | i #NE# DEPOTI #AND# j #NE# i #AND#
( TMV( i) + TMV( j) + TMPM*( DIST( DEPOTI, i) + DIST( i, j) + DIST( j, DEPOTI)) #GT# TMAX):
Z( i, j) = 0;
);
);
! Cut: (i, j, k) cannot be on same trip if too long;
@FOR( CITY( i) | i #NE# DEPOTI:
@FOR( CITY( j) | j #NE# DEPOTI #AND# i #LT# j:
@FOR( CITY( k) | k #NE# DEPOTI #AND# j #LT# k #AND#
( TMV( i) + TMV( j) + TMV( j) + TMPM* @SMIN(
DIST( DEPOTI, i) + DIST( i, j) + DIST( j, k) + DIST( k, DEPOTI),
DIST( DEPOTI, i) + DIST( i, k) + DIST( k, j) + DIST( j, DEPOTI),
DIST( DEPOTI, j) + DIST( j, i) + DIST( i, k) + DIST( k, DEPOTI),
DIST( DEPOTI, j) + DIST( j, k) + DIST( k, i) + DIST( i, DEPOTI),
DIST( DEPOTI, k) + DIST( k, i) + DIST( i, j) + DIST( j, DEPOTI),
DIST( DEPOTI, k) + DIST( k, j) + DIST( j, i) + DIST( i, DEPOTI))
#GT# TMAX):
Z( i, j) + Z( i, k) + z( j, i) + z( j, k) + z( k, i) + z( k, j) <= 1;
);
);
);
ENDSUBMODEL
CALC:
@SET( 'TERSEO', 1); ! Make output somewhat terse;
@SET( 'IPTOLR', TOLOPT); ! Relative optimality tolerance;
@SET( 'TIM2RL', 30); ! Time to turn on IPTOLR in seconds;
DEPOTI = 1; ! Set the index of the depot;
@SOLVE( VROUTE);
ISTAT = @STATUS();
@IFC( ISTAT #EQ# 0 #OR# ISTAT #EQ# 4: ! Do report only if optimal or feasible;
FW = 12;
NROUTES = 0;
@WRITE( @NEWLINE(2),' Vehicle Routing Trip Report',@NEWLINE(1),
' Total distance= ', DISTOT);
! Write a listing of the routes;
@FOR( CITY( j):
@IFC( Z( DEPOTI, j) #GT# .5: ! City j first on trip? ;
NROUTES = NROUTES + 1;
@WRITE( @NEWLINE( 2), 'ROUTE ', NROUTES, ':', @NEWLINE( 1));
@WRITE(' FROM TO ARR TIME', @NEWLINE( 1));
@WRITE('-------------------------------------', @NEWLINE( 1));
@WRITE( ' ', CITY( DEPOTI), (FW-@STRLEN( CITY( DEPOTI)))*' ',
CITY( j), (FW-@STRLEN( CITY( j)))*' ',
@FORMAT( TMA( j), '10.1f'), @NEWLINE( 1)
);
IPOS = J;
@WHILE( IPOS #NE# DEPOTI:
NLOOPS = NLOOPS + 1;
@FOR( CITY( J2): ! Which city J2 follows city IPOS? ;
@IFC( Z( IPOS, J2) #GT# .5:
@IFC( J2 #NE# DEPOTI: ! Have we returned to depot? ;
@WRITE( ' ', CITY( IPOS), (FW-@STRLEN( CITY( IPOS)))*' ',
CITY( J2), (FW-@STRLEN( CITY( J2)))*' ',
@FORMAT( TMA( J2), '10.1f'), @NEWLINE( 1)
);
@ELSE
@WRITE( ' ', CITY( IPOS), (FW-@STRLEN( CITY( IPOS)))*' ',
CITY( DEPOTI), (FW-@STRLEN( CITY( DEPOTI)))*' ',
@FORMAT( TMA( IPOS) + TMV( IPOS) + TMPM * DIST( IPOS, DEPOTI), '10.1f'), @NEWLINE( 1)
);
);
IPOS = J2;
@BREAK;
);
);
);
);
);
);
ENDCALC