! 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