MODEL:
SETS:  ! Fleet routing and assignment with deadheading (fleetdhd) in LINGO;
 ! We are given 
    1) a set of loads to be carried, each load having
       an origin city, a destination city, and a departure time,
    2) travel times between cities.
   How should load carrying vehicles be routed so as to minimize
   some measure of vehicle cost?;
! Key words: fleet routing, fleet assignment, dead heading,
             tanker scheduling, aircraft scheduling;
! Reference: Dantzig, G. and D. Fulkerson(1954), "Minimizing the
      Number of Tankers to Meet a Fixed Schedule", Naval Research
      Logistics Quarterly, vol. 1, pp. 217-222;

 CITY :;  ! The cities involved;
 VTYPE:   ! Vehicle types;
  FCOST,  ! Fixed cost of using a vehicle for > 0 loads;
  FSIZE;  ! Max fleet size of this type;
 LOAD:;   ! The loads to be delivered;
 LXCXC( LOAD, CITY, CITY) :
  DEPAT;   ! Load departure time(ready for loading);
 VXC( VTYPE, CITY): 
  AVAILIN; ! Number vehicles initially available at each city;
  VXCXC( VTYPE, CITY, CITY):
    ATIME, ! time from city to city for loaded vehicle;
    BTIME, ! time from city to city for deadheading vehicle;
   CDHEAD; ! Cost of a deadhead;
 VXLXCXC( VTYPE, LXCXC): 
  X,      ! Number vehicles used(0 or 1) by type, on this load;
  PC;     ! Profit contribution by type, Load;
ENDSETS
DATA: ! A variation of the Dantzig-Fulkerson example; CITY = S1 S2 D1 D2 D3; ! Cities involved; VTYPE, FCOST, FSIZE = ! Vehicle type, fixed cost, fleet size; STND 1 99 FAST 1.5 1; AVAILIN= 99 99 99 99 99, ! Number initially available; 99 99 99 99 99; ! of each vehicle type by locn; LOAD = 1..20; LXCXC, DEPAT = ! Loads to be carried; ! LOAD Origin Dest. Depart; 1 S1 D1 1 2 S1 D1 4 3 S1 D1 7 4 S1 D1 10 5 S1 D1 13 6 S1 D2 9 7 S1 D2 15 8 S1 D3 6 9 S1 D3 12 10 S2 D1 3 11 S2 D1 6 12 S2 D1 9 13 S2 D1 12 14 S2 D2 7 15 S2 D2 10 16 S2 D2 13 17 S2 D2 15 18 S2 D3 5 19 S2 D3 10 20 S2 D3 15; ATIME = ! Time to move a loaded vehicle; !S1 S2 D1 D2 D3; 0 99 2 3 2 ! S1, STND vehicle; 99 0 1 2 1 ! S2; 2 1 0 99 99 ! D1; 3 2 99 0 99 ! D2; 2 1 99 99 0 ! D3; 0 99 1.5 2.1 1.5 ! S1, FAST vehicle; 99 0 1 1.5 1 ! S2; 1.5 1 0 99 99 ! D1; 2.1 1.5 99 0 99 ! D2; 1.5 1 99 99 0; ! D3; BTIME = ! Time to move an empty vehicle; !S1 S2 D1 D2 D3; 0 99 2 3 2 ! S1, STND vehicle; 99 0 1 2 1 ! S2; 2 1 0 99 99 ! D1; 3 2 99 0 99 ! D2; 2 1 99 99 0 ! D3; 0 99 1.5 2.1 1.5 ! S1, FAST vehicle; 99 0 1 1.5 1 ! S2; 1.5 1 0 99 99 ! D1; 2.1 1.5 99 0 99 ! D2; 1.5 1 99 99 0; ! D3; PC = 0; ! Profit contribution of each vehicle*Load combo; ENDDATA SETS: ! Create set of interesting deadhead moves; ! After finishing load &2 from &3 to &4, a deadhead from &4 to &6 is useful in carrying load &5 if it gets there in time; VLCCLCC( VTYPE, LXCXC, LXCXC)| DEPAT(&2,&3,&4)+ATIME(&1,&3,&4)+BTIME(&1,&4,&6)#LE# DEPAT(&5,&6,&7): XDH; ! Number vehicles deadheading empty, after doing load L1 to next do load L2; ! Create set of initial deadhead moves. Assume time starts at 0; VCLCC( VTYPE, CITY, LXCXC)| BTIME(&1,&2,&4) #LE# DEPAT(&3,&4,&5): XI; ! Number vehicles of type &1 initially at &2 that deadhead to carry load &3 from &4 to &5; ENDSETS
! Variables: X( V, L, I, J) = 1 if a vehicle of type V carries load L from city I to city J, XDH(V,L1,I1,J1,L2,I2,J2) = 1 if the vehicle of type V that carried load L1 from city I1 to city J1, then deheads from city J1 to city I2 to carry load L2 from I2 to J2, XI(V, J1, L2, I2, J2) = 1 if a vehicle of type V initially at city J1, deadheads to I2 to carry load L2 from I2 to J2; !-------------------------------------------------------------------; ! Maximize profit contribution from LOADs minus overhead cost of vehicles in fleet; MAX = @SUM(VXLXCXC( V, L, I, J): PC(V,L,I,J) * X(V,L,I,J)) - @SUM(VCLCC(V1,J1,L1,I2,J2): FCOST(V1) * XI( V1,J1,L1,I2,J2)); ! Each load must be carried by some vehicle; @FOR( LXCXC( L, I, J): [MUST] @SUM(VXLXCXC( V, L, I, J): X(V,L,I,J)) = 1; ); ! If vehicle type V carries the load, we must get it from an initial reposition move, or a deadhead after some other load; @FOR(VXLXCXC( V, L, I, J): [FLIN] @SUM(VCLCC(V,J1,L,I,J): XI( V,J1,L,I,J)) + @SUM(VLCCLCC(V,L1,I1,J1,L,I,J): XDH(V,L1,I1,J1,L,I,J)) = X(V,L,I,J); ); ! We cannot use more vehicles at the end of a load than delivered the load; @FOR(VXLXCXC( V, L, I, J): [FOUT] X(V,L,I,J) >= @SUM(VLCCLCC(V,L,I,J,L2,I2,J2): XDH(V,L,I,J,L2,I2,J2)) ); ! Cannot start with more vehicles than available; @FOR( VXC( V, I): [INIT] @SUM( VCLCC( V, I, L, I2, J2): XI(V,I,L,I2,J2)) <= AVAILIN(V,I); ); ! Total fleet size constraint for each vehicle type; @FOR( VTYPE(V): @SUM( VCLCC( V, I, L, I2, J2): XI(V,I,L,I2,J2)) <= FSIZE(V) ); ! Fractional vehicles are not allowed; @FOR(VXLXCXC( V, L, I, J): @GIN( X(V,L,I,J))); @FOR(VCLCC(V,J,L,I,J): @GIN(XI( V,J,L,I,J))); END