! The Full Truck Load(FTL) Routing problem.
We have a
set of loads available to be carried,
set of drivers/vehicles that can carry loads,
set of load-next_load deadhead combinations for
repositioning drivers, with associated cost,
for each driver & load combination, a profit contribution,
The problem is:
Which drivers should cover which loads, deadheading
between loads as need be, so as to
Maximize profit contribution minus cost of deadheads;
! Keywords: Routing, FTL routing, Vehicle routing,
Assignment, Load assignment, Trucking, Airlines;
SETS:
LOAD: NOTDONE;
DRIVER;
DXL( DRIVER, LOAD): PC, Y, W, Z;
DHEAD( LOAD, LOAD): COST;
DDHEAD(DRIVER, DHEAD): X;
ENDSETS DATA:
! Loads available;
LOAD = AB BC FG EF BG DE CD CE;
! Drivers/vehicles available;
DRIVER = TOM JON PAT;
! Possible driver-to-load assignments
and their profit;
DXL PC =
TOM AB 6.3
TOM BC 5.2
TOM FG 7.8
TOM EF 4.0
TOM BG 5.4
JON BC 7.8
JON DE 6.7
JON CD 8.9
JON CE 7.0
JON BG 6.3
PAT AB 9.1
PAT BC 8.5
;
! Which deadheads between loads are possible,
and their cost;
DHEAD COST =
AB BC 1.0
DE BC 3.9
CD BC 3.2
CD DE 1.0
CD FG 2.3
CD EF 2.1
FG BC 2.4
CE BC 4.5
CE DE 4.4
CE FG 4.6
CE EF 1.1
BG BC 2.8
BG EF 3.7
;
ENDDATA
SUBMODEL FTLMOD:
! Variables:
Y(d,j) = 1 if driver d does load j, else 0,
X(d,i,j) = 1 if driver d deadheads after doing load i
to next do load j,
W(d,j) = 1 if first load for driver d is load j,
Z(d,z) = 1 of last load for driver d is load j.
;
! Maximize profit contribution of loads carried
minus cost of deadheads;
MAX = OBJ;
OBJ = TOTREV - TOTCOST;
TOTREV = @SUM( DXL(d,j): PC(d,j)*Y(d,j));
TOTCOST = @SUM( DDHEAD( d, j1,j2): COST( j1, j2)*X(d,j1,j2));
! We can carry a load at most once;
@FOR( LOAD( j):
@SUM( DXL(d,j): Y(d,j)) + NOTDONE(j) = 1;
);
! For each driver d who does load j;
@FOR( DXL( d, j):
! he must come from someplace;
W(d,j) + @SUM( DDHEAD( d, j1, j): X(d, j1, j)) = Y(d,j);
! and go someplace;
Z(d,j) + @SUM( DDHEAD( d, j, j2): X(d, j, j2)) = Y(d,j);
! no fractional drivers allowed;
@BIN( Y(d,j));
);
! We only have one of each driver;
@FOR( DRIVER(d):
@SUM(DXL(d,j): W(d,j)) <= 1;
@SUM(DXL(d,j): W(d,j)) = @SUM(DXL(d,j): Z(d,j));
);
ENDSUBMODEL
CALC:
! Turn off default output before solving model;
@SET("TERSEO",2);
@SOLVE( FTLMOD);
! Write a little report;
@WRITE(' Driver/vehicle to Load Assignment Report.',@NEWLINE(1));
@WRITE(' Net Revenues from loads carried= ', TOTREV, @NEWLINE(1),
' Cost of deadheads= ', TOTCOST, @NEWLINE(1),
' Net profit = ', OBJ, @NEWLINE(1));
@WRITE(@NEWLINE(1),' Route Loads', @NEWLINE(1));
! Write a list of the loads to be carried by each driver;
@FOR( DRIVER(d):
@WRITE(' ', DRIVER(d),@NEWLINE(1));
! Find the first load;
@FOR( DXL(d,j) | W(d,j) #GT# .5:
CURLOAD = j;
);
! Write out current load for driver d...;
@WHILE( CURLOAD #GT# 0:
@WRITE(' ',LOAD(CURLOAD), @NEWLINE(1));
! Find next load;
NEXT = 0;
@FOR(DDHEAD(d,j, j2) | j #EQ# CURLOAD #AND# X(d,j,j2) #GT# .5:
NEXT = j2;
);
CURLOAD = NEXT;
);
@WRITE(@NEWLINE(1));
);
@WRITE(@NEWLINE(1),' Loads not carried.',@NEWLINE(1));
@FOR(LOAD(j) | NOTDONE(j) #GT# .5:
@WRITE(' ',LOAD(j),@NEWLINE(1));
);
ENDCALC
|