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
|