! 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 pickedup and brought to the ramp,
3 TEN) an empty container brought to the customer,
4 TNE) an empty container pickedup from customer,
5 TFN) a full container delivered from the ramp to the customer, no empty to pickup,
6 TNF) a full container pickedup from the customer and brought to the ramp, no empty needed,
7 TFF) a full container delivered to the customer and a full container
pickedup from same customer and brought to the ramp.
A trucktractor 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 "outandback" 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
outandback 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 pickup 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 k1 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(k1)) #AND# (FXT(k) #GE# FXT(k1))) <= Y(k1);
);
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),
' Twostop 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
