! Single Fleet Full Truck Load Routing model in LINGO;
! Given:
a set of Locations,
a travel time matrix between pairs of locations,
a set of (from, to) deliveries to be made on
specific days,
find how to best move empty vehicles so the
deliveries can be done with a minimum number
of vehicles;
! Keywords: Routing, Full truck load routing, FTL, Vehicle routing;
SETS:
DAY;
LOCN: X0, NOTO, NOTD;
LXL( LOCN, LOCN): TD;
DXLXL( DAY, LOCN, LOCN): X;
LXLXD( LOCN, LOCN, DAY): LOADS;
ENDSETS ! Definitions:
Parameters:
TD(i,j) = days for a vehicle
to travel from i to j,
or if we depart from i on day t to
go to j, the vehicle will be able to
depart from j on day t+TD(i,j),
i.e, any load and unload times are incorporated
into TD(i,j),
LOADS(i,j,d) = loads that must be delivered from
i arriving at j on day d,
Variables:
X(d,i,j) = number vehicles leaving on day d
from locn i to locn j ;
DATA:
DAY = 1..35;
LOCN = KUWAIT ABUDBI ANTWRP HAMBRG CALAIS ;
TD = 1 1 11 14 10 ! KUWAIT;
1 1 10 13 9 ! ABUDBI;
11 10 1 3 5 ! ANTWRP;
13 12 3 1 999 ! HAMBRG;
12 10 5 999 1 ! CALAIS;
;
! Initial availability of vehicles at each location;
X0 = 999 999 0 0 0 ;
! Required deliveries;
LXLXD LOADS =
KUWAIT ANTWRP 13 1
KUWAIT ANTWRP 29 2
KUWAIT HAMBRG 21 2
KUWAIT HAMBRG 24 1
KUWAIT CALAIS 11 2
KUWAIT CALAIS 18 1
KUWAIT CALAIS 31 3
ABUDBI ANTWRP 18 1
ABUDBI ANTWRP 28 1
ABUDBI HAMBRG 16 1
ABUDBI CALAIS 23 1
ABUDBI CALAIS 31 1
;
ENDDATA
SUBMODEL ROUTEM:
MIN = OBJ;
! Minimize the number of vehicles inserted at day 1;
OBJ = @SUM( DXLXL( s,i,j) | s #EQ# 1: X(s,i,j));
! Conservation of vehicle flow:
For each day d and location k:
vehicles in = vehicles out;
@FOR( DAY(d) | d #GT# 1:
@FOR( LOCN(k):
[CF] @SUM( DXLXL( s, i, k) | s + TD(i,k) #EQ# d: X(s,i,k))
= @SUM( DXLXL( d, k, j) : X(d, k,j ))
);
);
! Must make certain deliveries from i to j on day d;
@FOR( LXLXD( i,j, d):
[MUST] @SUM( DXLXL(s,i,j) | s + TD(i,j) #EQ# d: X(s,i,j)) >= LOADS(i,j,d);
);
! Take into account initial location of tankers;
@FOR(LOCN(k):
@SUM( DXLXL( d, k, j) | d #EQ# 1 : X(d, k,j )) <= X0(k);
);
! Optionally, prohibit foolish alternative optima;
! Optionally, assuming triangle inequality holds on TD matrix,
can drop movements (i,j) for which i and j are
always destinations, never origins..;
@FOR( LOCN(i) | NOTO(i):
@FOR( DXLXL( d,i,j)| j #NE# i #AND# NOTO(j): X(d,i,j)= 0);
);
! Optionally, assuming triangle inequality holds on TD matrix,
can drop movements (i,j) for which i and j are
always origins, never destinations..;
@FOR( LOCN(i) | NOTD(i):
@FOR( DXLXL( d,i,j)| j #NE# i #AND# NOTD(j): X(d,i,j)= 0);
);
! Optionally, do not let vehicles set empty at j
if j is never an origin;
@FOR( LOCN(j) | NOTO(j):
[NOSIT] @SUM( DXLXL( d,i,j)| j #EQ# i: X(d,i,j))= 0;
);
ENDSUBMODEL
CALC:
! Set NOTO(i) = 1 if LOCN i is never an origin,
NOTD(i) = 1 if LOCN i is never a destination;
@FOR( LOCN(i):
NOTO(i) = 0; NOTD(i) = 0;
);
@FOR( LOCN(k)| @SUM( LXLXD(k,j,d): LOADS(k,j,d)) #EQ# 0:
NOTO(k) = 1;
);
@FOR( LOCN(k)| @SUM( LXLXD(i,k,d): LOADS(i,k,d)) #EQ# 0:
NOTD(k) = 1
);
@SET( 'TERSEO', 2); ! Set output level to super terse;
@SOLVE( ROUTEM);
! Write a simple report;
@WRITE(' Cost = ', Obj, @NEWLINE(1));
@WRITE( @NEWLINE(1),' Trip List',@NEWLINE(1),
' ODay DDay Origin Destination, #Vehicles ',@NEWLINE(1));
@FOR( DXLXL(d,i,j) | X(d,i,j) #GT# .5 #AND# i #NE# j:
@WRITE( ' ',@FORMAT(d,'3.0f'), ' ', @FORMAT(d+TD(i,j),'3.0f'),
' ', LOCN(i),' ',LOCN(j),' ',X(d,i,j),@NEWLINE(1));
);
@WRITE(@NEWLINE(1),' Idle Vehicle List',@NEWLINE(1),
' Day Location #Vehicles',@NEWLINE(1));
@FOR( DXLXL(d,i,j) | X(d,i,j) #GT# .5 #AND# i #EQ# j:
@WRITE( ' ',@FORMAT(d,'3.0f'), ' ', LOCN(i),' ',X(d,i,j),@NEWLINE(1));
);
ENDCALC
|