! The truckload delivery and\or pickup or drayage problem in LINGO (DrayageX).
Customers need empty or full containers picked up or delivered
from a central facility\depot\yard\ramp.
We have the following customer types who need only and no more:
1 TFE) a full container from the ramp\depot\yard
delivered to the customer and an empty container picked up,
2 TEF) an empty container brought to the customer and a full
container picked-up and brought to the ramp,
3 TEN) an empty container brought to the customer,
4 TNE) an empty container picked-up from customer,
5 TFN) a full container delivered from the ramp to the customer, no empty to pickup,
6 TNF) a full container picked-up from the customer and brought to the ramp, no empty needed,
7 TFF) a full container delivered to the customer and a full container
picked-up from same customer and brought to the ramp.
A truck-tractor can move only one container at a time.
The ramp has enough empty containers to satisfy any customer needs.
The ramp has sufficient storage for any empty containers that customers wish to get rid of.
A simple "out-and-back" way of satisfying each customer is to simply
send one truck independently to each customer to
do whatever delivery or pickup is required.
A notable feature is that empty containers are generic. A customer does
not care where an empty container goes or where it came from.
This provides an opportunity to do better than the simple one truck
out-and-back to each customer.
Thus, we can see that the following pairings are possible for one trip
from the ramp and back:
TFE->TEF
TFE->TEN
TEN->TNE
TEN->TNF
TFN->TNE
TFN->TNF
We do not consider:
1) the more general pick-up and delivery problem in which
a truck may visit more than two customers, picking up an empty container at one,
delivering it to the next customer, proceeding with no container to a third
customer and picking up an empty and taking it to a fourth customer, etc.
2) different container types, e.g., different sizes, or
some customers might need regular, others an empty "reefer" trailer,
;
! Keywords: Drayage, Pickup and Delivery, Routing, FTL, Container routing;
SETS:
CUST: TYPE, PS, TS; ! Folks needing a visit by our tractor;
PAIR( CUST, CUST): TB; ! Paired visits possible;
TRUCK: L, T, TP, Y, FXT;
TXC( TRUCK, CUST): XS;
TXP(TRUCK, PAIR): XB;
ENDSETS
DATA:
! Customer, Type, and travel time To or From;
CUST TYPE TS =
C1 1 1.71
C2 1 0.45
C3 1 1.34
C4 1 1.51
C5 2 1.32
C6 2 0.31
C7 2 0.87
C8 2 1.42
C9 2 0.76
C10 2 0.79
C11 3 0.39
C12 4 0.57
C13 5 1.48
C14 5 1.49
C15 6 1.95
C16 6 1.17
C17 7 1.58
;
! Customer pairs and travel time between them;
PAIR TB =
C1 C5 2.78
C1 C6 3.17
C1 C7 3.57
C1 C8 4.12
C1 C9 3.32
C1 C10 4.04
C1 C11 3.14
C2 C5 1.32
C2 C6 0.86
C2 C7 1.60
C2 C8 1.77
C2 C9 0.94
C2 C10 1.44
C2 C11 0.52
C3 C5 1.57
C3 C6 2.67
C3 C7 3.39
C3 C8 2.55
C3 C9 2.02
C3 C10 2.85
C3 C11 2.31
C4 C5 3.66
C4 C6 2.76
C4 C7 2.35
C4 C8 4.40
C4 C9 3.59
C4 C10 3.80
C4 C11 3.13
C11 C12 1.03
C11 C15 2.03
C11 C16 1.22
C12 C13 2.16
C12 C14 2.21
C13 C15 4.82
C13 C16 4.09
C14 C15 2.25
C14 C16 1.91
;
TRUCK L FXT =
TFE 11 1 ! Truck, time limit, Fixed charge;
TEF 10 1
TEN 10 1.5
TNE 10 1.5
TFN 9 1.6;
ENDDATA
! Parameters:
TS(i) = outbound time for a visit to i alone,
return time is assumed equal,
TB(i,j) = travel time between i and j,
L(k) = max work we can assign to truck k,
;
! Variables:
XS(k,i) = 1 if truck k makes an out and back trip to i alone,
XB(k,i,j) = 1 if truck k visits i and j on a single round trip,
T(k) = total time assigned to truck k
;
SUBMODEL DRAY:
MIN = OBJ;
OBJ = @SUM ( TRUCK(k): T(k) + FXT(k)*Y(k));
! Every customer must be visited as much as required;
@FOR( CUST(i):
@SUM( TRUCK(k): XS(k,i)) ! Either singly...;
+ @SUM( TXP(k,r,s) | r #EQ# i #OR# s #EQ# i: XB(k,r,s)) = 1;
);
! Work done by truck k;
@FOR( TRUCK(k):
T(k) = @SUM( CUST(i): 2*TS(i)*XS(k,i))
+ @SUM( PAIR(i,j): (TS(i)+TB(i,j)+TS(j))*XB(k,i,j));
);
! Truck k can work at most L(k);
@FOR( TRUCK( k):
T(k) <= L(k)*Y(k);
);
! Assignment variables must be 0 or 1;
@FOR( TXC(k,i): @BIN( XS(k,i)));
@FOR( TXP(k,i,j): @BIN( XB(k,i,j)));
@FOR( TRUCK(k): @BIN( Y(k)));
! Prohibit any incompatible pairings;
@SUM( TXP(k,i,j) | #NOT# (
( TYPE(i) #EQ# 1 #AND# TYPE(j) #EQ# 2) #OR# ( TYPE(j) #EQ# 1 #AND# TYPE(j) #EQ# 2) #OR#
( TYPE(i) #EQ# 1 #AND# TYPE(j) #EQ# 3) #OR# ( TYPE(j) #EQ# 1 #AND# TYPE(j) #EQ# 3) #OR#
( TYPE(i) #EQ# 3 #AND# TYPE(j) #EQ# 4) #OR# ( TYPE(j) #EQ# 3 #AND# TYPE(j) #EQ# 4) #OR#
( TYPE(i) #EQ# 3 #AND# TYPE(j) #EQ# 6) #OR# ( TYPE(j) #EQ# 3 #AND# TYPE(j) #EQ# 6) #OR#
( TYPE(i) #EQ# 4 #AND# TYPE(j) #EQ# 5) #OR# ( TYPE(j) #EQ# 4 #AND# TYPE(j) #EQ# 5) #OR#
( TYPE(i) #EQ# 5 #AND# TYPE(j) #EQ# 6) #OR# ( TYPE(j) #EQ# 5 #AND# TYPE(j) #EQ# 6) ):
XB(k,i,j)) = 0;
! Kill some symmetry. Use truck k-1 before k if it has
just as much capacity and is just as cheap;
@FOR( TRUCK(k) | k #GT# 1:
Y(k)*((L(k) #LE# L(k-1)) #AND# (FXT(k) #GE# FXT(k-1))) <= Y(k-1);
);
ENDSUBMODEL
CALC:
@SET( 'TERSEO', 2); ! Turn off default output;
@SOLVE(DRAY); ! Solve the subproblem;
@WRITE(' Trip report:', @NEWLINE(1));
@WRITE(' Single stop trips:', @NEWLINE(1),' Truck Customer',@NEWLINE(1));
@FOR( TXC(k,i) | XS(k,i) #GT# .5 :
@WRITE( ' ', TRUCK(k),' ', CUST(i), @NEWLINE(1));
);
@WRITE(@NEWLINE(1),
' Two-stop trips:', @NEWLINE(1),' Truck Customers',@NEWLINE(1));
@FOR( TXP(k,i,j) | XB(k,i,j) #GT# .5 :
@WRITE( ' ', TRUCK(k),' ', CUST(i),' ', CUST(j), @NEWLINE(1));
);
@WRITE( @NEWLINE(1), ' Truck report:', @NEWLINE(1),
' Truck Total Time', @NEWLINE(1));
@FOR( TRUCK(k) | Y(k) #GT# .5:
@WRITE(' ', TRUCK(k),' ', @FORMAT(T(k),"8.2F"), @NEWLINE(1))
);
@WRITE(@NEWLINE(1),' Total cost = ', OBJ, @NEWLINE(1));
ENDCALC
|
