```! 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!Case01; TMAX = 99999!Case01; VCAP = 18!Case01; DISTMAX = 5000!Case01; MXTRK = 9999!Case01; TOLOPT = 0.0000001 ! 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= ! 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!Case01; 996 0 1167 1019 596 1059 1227 1055 904 792 1238 1010!Case01; 2162 1167 0 1747 1723 214 168 250 2070 598 745 268!Case01; 1067 1019 1747 0 710 1538 1904 1528 948 1149 2205 1484!Case01; 499 596 1723 710 0 1589 1827 1579 354 1214 1809 1535!Case01; 2054 1059 214 1538 1589 0 371 36 1943 389 959 54!Case01; 2134 1227 168 1904 1827 371 0 407 2043 755 628 425!Case01; 2050 1055 250 1528 1579 36 407 0 1933 379 995 45!Case01; 151 904 2070 948 354 1943 2043 1933 0 1568 2022 1889!Case01; 1713 792 598 1149 1214 389 755 379 1568 0 1266 1266!Case01; 2083 1238 745 2205 1809 959 628 995 2022 1266 0 1001!Case01; 2005 1010 268 1484 1535 54 425 45 1889 335 1001 0 ! Case 2; !Case02 TMPM = 0.02; !Case02 TMAX = 9; !Case02 VCAP = 9999; !Case02 DISTMAX = 5000; !Case02 MXTRK = 9; !Case02 TOLOPT = 0.2; !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 ; !Case02 TML = 99999; ! 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; !Case03 TMAX = 9; !Case03 VCAP = 9999; !Case03 DISTMAX = 5000; !Case03 MXTRK = 9; !Case03 TOLOPT = 0.6; !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; !Case03 TME = 0 ; !Case03 TML = 99999; ! 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 ```