! Given a set of desired flights, figure out how to
route planes to cover these flights.
Repositioning flights are allowed at a cost.
This model illustrate two features:
1) Calendar routines for coordinating the times of
flights involving different locations and time zones,
2) The @INSERT( ) function for creating a derived set
according to fairly arbitrary rules;
! This version considers only flights with aircraft type or fleet
within specified range [ALO, AHI]. Thus, one can show the
economies of scale of combining fleets;
! Keywords:
Airline Routing, Fleet Routing, FTL routing,
Vehicle routing, Airline Scheduling, Fleet Scheduling;
SETS:
CITY: INITA, GMTOFF;
LEG;
CXC( CITY, CITY): TRVTIM;
LODPAIR( LEG, CITY, CITY): Year, Month, Day, Hour, Minute, AType,
DLTIME, Y, PLFLAG;
RLEG;
RPAIR( RLEG, CITY, CITY): DRTIME, U;
DOW /SUN..SAT/;
ENDSETS
DATA:
City, GMTOFF = ! Cities and their offset in hours from GMT;
Chicago -6 ! Chicago is 6 hours behind Greenwich Mean Time;
Salt_Lake_City -7
Los_Angeles -8
Phoenix -7
Las_Vegas -8
Tucson -7;
LEG = 1..7;
! Get data of each loaded candidate Origin-Destination (OD) pair;
LODPAIR, Year, Month, Day, Hour, Minute, AType =
! Origin Destination Departure time Aircraft
LEG City City Year Month Day Hour Minute Type;
1 Los_Angeles Salt_Lake_City 2012 10 20 11 0 3
2 Salt_Lake_City Phoenix 2012 10 24 16 20 2
3 Salt_Lake_City Los_Angeles 2012 10 25 16 0 1
4 Salt_Lake_City Las_Vegas 2012 10 26 16 0 5
5 Las_Vegas Salt_Lake_City 2012 10 28 12 0 5
6 Tucson Salt_Lake_City 2012 10 28 13 0 2
7 Chicago Las_Vegas 2012 10 22 10 30 1
;
! Get travel time matrix in minutes;
TRVTIM =
0 190 240 205 215 195 ! Chicago;
190 0 110 100 85 120 ! Salt_Lake_City;
240 110 0 120 120 120 ! Los_Angeles;
205 100 120 0 85 60 ! Phoenix;
215 85 120 85 0 95 ! Las_Vegas;
195 120 120 60 95 0 ;! Tucson;
RLEG = 1..1000; ! Possible number of repositioning legs;
VL = 1; ! Relative value of covering a loaded flight;
RP = .01; ! Relative cost of a repositioning flight;
RA = .95; ! Relative cost of an aircraft;
ALO = 1; ! Lower limit on aircraft type considered;
AHI = 5; ! Upper limit on aircraft type considered;
ENDDATA
! Variables:
Y(n,d,a) = 1 if load carrying flight n is flown from d to a,
U(n,d,a) = 1 if repositioning flight n is flown from d to a;
SUBMODEL ROUTEM:
! Maximize number of requested flights flown(covered)
- cost of repositioning flights
- cost of aircraft;
MAX = VL*@SUM( LODPAIR( n, d, a) |(ALO #LE# ATYPE(n,d,a)
#AND# ATYPE(n,d,a) #LE# AHI) : Y(n,d,a)) ! Loaded flights;
- RP*@SUM( RPAIR( n, d, a): U(n,d,a)) ! Repositions;
- RA*@SUM( CITY(i): INITA(i)); ! Initial AC at city i;
! You either fly it or you do not;
@FOR( LODPAIR( n, d, a): @BIN(Y(n,d,a)));
@FOR( RPAIR( n, d, a): @BIN(U(n,d,a)));
! For every departing loaded flight from d to a at time DLTIME,
the number of earlier arrivals - earlier departures must be >= Y(n,d,a);
@FOR( LODPAIR( n, d, a) |(ALO #LE# ATYPE(n,d,a) #AND# ATYPE(n,d,a) #LE# AHI) :
[LFLO] INITA(d)
+ @SUM( LODPAIR( n1, d1, d) | DLTIME(n1,d1,d) + TRVTIM(d1,d)/60 #LE# DLTIME(n,d,a)
#AND# (ALO #LE# ATYPE(n1,d1,d) #AND# ATYPE(n1,d1,d) #LE# AHI):
Y(n1,d1,d)) ! Loaded flights arriving earlier;
+ @SUM( RPAIR( n1, d1, d) | DRTIME(n1,d1,d) + TRVTIM(D1,d)/60 #LE# DLTIME(n,d,a):
U(n1,d1,d)) ! Repositioning flights arriving earlier;
- @SUM(LODPAIR(n1,d,a1) | DLTIME(n1,d,a1) #LT# DLTIME(n,d,a)
#AND# (ALO #LE# ATYPE(n1,d,a1) #AND# ATYPE(n1,d,a1) #LE# AHI):
Y(n1,d,a1)) ! Loaded flights departing earlier;
- @SUM( RPAIR(n1,d,a1) | DRTIME(n1,d,a1) #LE# DLTIME(n,d,a):
U(n1,d,a1)) ! Repositioning flights departing earlier;
>= Y(n,d,a); ! Loaded flight departing at time DLTIME(n,d,a);
);
! For every departing repositioning flight from d to a at time DRTIME,
the number of earlier arrivals - earlier departures must be >= U(n,d,a);
@FOR( RPAIR( n, d, a):
[RFLO] INITA(d)
+ @SUM( LODPAIR( n1, d1, d) | DLTIME(n1,d1,d) + TRVTIM(d1,d)/60 #LE# DRTIME(n,d,a)
#AND# (ALO #LE# ATYPE(n1,d1,d) #AND# ATYPE(n1,d1,d) #LE# AHI) :
Y(n1,d1,d)) ! Loaded flights arriving earlier;
+ @SUM( RPAIR( n1, d1, d) | DRTIME(n1,d1,d) + TRVTIM(d1,d)/60 #LE# DRTIME(n,d,a):
U(n1,d1,d)) ! Repositioning flights arriving earlier;
- @SUM(LODPAIR(n1,d,a1) | DLTIME(n1,d,a1) #LE# DRTIME(n,d,a)
#AND# (ALO #LE# ATYPE(n1,d,a1) #AND# ATYPE(n1,d,a1) #LE# AHI) :
Y(n1,d,a1)) ! Loaded flights departing earlier;
- @SUM( RPAIR(n1,d,a1) | a1 #NE# a #AND# (DRTIME(n1,d,a1) #LE# DRTIME(n,d,a)):
U(n1,d,a1)) ! Repositioning flights departing earlier;
>= U(n,d,a); ! Repositioning flight departing at time DRTIME(n,d,a);
);
ENDSUBMODEL
CALC:
! Convert Year, Month, Day, Hour, Minute, Second(n,d,a) to a scalar DLTIME(n,d,a)
in hours so we can do simple comparisons and arithmetic;
! Compute departure time in scalar GMT time for each loaded flight;
@FOR( LODPAIR( n, d, a):
DLTIME(n,d,a) = @YMD2STM( Year(n,d,a), Month(n,d,a), Day(n,d,a) , Hour(n,d,a), Minute(n,d,a), 0)
- GMTOFF(d); ! Take into account local time;
);
! Construct the set of candidate repositioning legs. For each departing
flight from city j, we add a candidate repositioning leg from every
other city j, j #NE# i, at TRVTIM(i,j) minutes earlier ;
k = 0;
@FOR( LODPAIR( n, j, a) |(ALO #LE# ATYPE(n,j,a) #AND# ATYPE(n,j,a) #LE# AHI) :
@FOR( CITY(i) | i #NE# j:
k = k+1;
@INSERT( RPAIR, k, i, j);
! Note, travel times are in minutes, scalar time in hours;
DRTIME(k,i,j) = DLTIME(n,j,a) - TRVTIM(i,j)/60;
);
);
! @GEN( ROUTEM); @SOLVE( ROUTEM);
@WRITE(' Value/flight covered= ',VL,@NEWLINE(1),
' Relative cost/repositioning= ',RP,@NEWLINE(1),' Relative cost/aircraft= ',RA,@NEWLINE(1));
@WRITE(@NEWLINE(1),' Number flights covered= ',
@SUM(LODPAIR(n,d,a)| Y(n,d,a) #GT# 0.5 #AND# (ALO #LE# ATYPE(n,d,a) #AND# ATYPE(n,d,a) #LE# AHI) :1),
' (of ',
@SUM(LODPAIR(n,d,a) |(ALO #LE# ATYPE(n,d,a) #AND# ATYPE(n,d,a) #LE# AHI) :1),')',@NEWLINE(1));
@WRITE(' Number aircraft used= ',@SUM(CITY(i):INITA(I)),@NEWLINE(1));
@WRITE(' Fleets used: ',ALO,' to ',AHI,@NEWLINE(1));
@WRITE(@NEWLINE(1),' Initial Aircraft Positions:',@NEWLINE(1),
' # Aircraft City', @NEWLINE(1));
@FOR( CITY(i)| INITA(i) #GT# 0.5:
@WRITE(' ', @FORMAT(INITA(i),'3.0f'), ' ', CITY(i),@NEWLINE(1));
);
@WRITE(@NEWLINE(1),' Load carrying flights: Depart at (local time)',@NEWLINE(1));
@WRITE(' Origin Destination yyyy mm dd hh mm dwk',@NEWLINE(1));
! A while loop to print the legs used, sorted by DLTIME;
@FOR( LODPAIR( n, d, a): PLFLAG(n,d,a) = 1); ! PLFLAG = 0 if already printed;
MORE = 1;
@WHILE(MORE:
MORE = 0;
CTIME = 9999999999;
@FOR( LODPAIR( n, d, a) | PLFLAG(n,d,a) #AND# (Y(n,d,a) #GT# 0.5)
#AND# (ALO #LE# ATYPE(n,d,a) #AND# ATYPE(n,d,a) #LE# AHI) :
CTEMP = DLTIME(n,d,a);
@IFC( CTEMP #LT# CTIME:
MORE = 1;
CTIME = CTEMP;
nsv=n; dsv=d; asv=a;
);
);
@IFC( MORE:
PLFLAG(nsv,dsv,asv) = 0;!
Begin code to ... Convert DLTIME(n,d,a) back to year, month, day, hour, minute;
CTIME = CTIME + GMTOFF(dsv); ! Take into account local time;
IYR = @STM2YR( CTIME); ! Get the year;
IMON = @STM2MON( CTIME); ! Get the month of the year;
IDAY = @STM2DAY( CTIME); ! Get day of month;
IHR = @STM2HR( CTIME); ! Get the hour of the day;
IMIN = @STM2MIN( CTIME); ! Get the minute of the hour;
IWKD = @STM2DWK( CTIME); ! Get the day of the week;
! End of code to convert to year, month,...;
@WRITE( @FORMAT(CITY(dsv),'18s'),' ',@FORMAT(CITY(asv),'18s'),' ',IYR,' ',
IMON,' ',@FORMAT(IDAY,'2.0F'),' ',@FORMAT(IHR,'2.0F'),' ',@FORMAT(IMIN,'2.0F'),' ',DOW(IWKD),@NEWLINE(1));
);
);
@WRITE(@NEWLINE(1),' Repositioning Flights:',@NEWLINE(1));
@FOR( RPAIR( n, d, a) | U(n,d,a) #GT# 0.5:
! Begin code to ... ;
! Convert DRTIME(n,d,a) back to year month, day, hour, minute;
CTIME = DRTIME(n,d,a)+ GMTOFF(d); ! Take into account local time;
IYR = @STM2YR( CTIME); ! Get the year;
IMON = @STM2MON( CTIME); ! Get the month of the year;
IDAY = @STM2DAY( CTIME); ! Get day of month;
IHR = @STM2HR( CTIME); ! Get the hour of the day;
IMIN = @STM2MIN( CTIME); ! Get the minute of the hour;
IWKD = @STM2DWK( CTIME); ! Get the day of the week;
! End of convert code;
@WRITE( @FORMAT(CITY(d),'18s'),' ',@FORMAT(CITY(a),'18s'),' ',IYR,' ',
IMON,' ',@FORMAT(IDAY,'2.0F'),' ',@FORMAT(IHR,'2.0F'),' ',@FORMAT(IMIN,'2.0F'),' ',DOW(IWKD),@NEWLINE(1));
);
ENDCALC
|
