Lindo Systems

! 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