Lindo Systems
! 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;
! Keywords:
Airline Routing, Fleet Routing,
Airline Scheduling, Fleet Scheduling;
SETS:
CITY: INITA, GMTOFF;
LEG;
CXC( CITY, CITY): TRVTIM;
LODPAIR( LEG, CITY, CITY): Year, Month, Day, Hour, Minute,
DLTIME, Y, PLFLAG;
RLEG;
RPAIR( RLEG, CITY, CITY): DRTIME, U;
DOW /MON..SUN/;
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 on each loaded candidate OD pair;
LODPAIR, Year, Month, Day, Hour, Minute =
! Origin Destination Departure time
LEG City City Year Month Day Hour Minute ;
1 Los_Angeles Salt_Lake_City 2012 10 20 11 0
2 Salt_Lake_City Phoenix 2012 10 24 16 20
3 Salt_Lake_City Los_Angeles 2012 10 25 16 0
4 Salt_Lake_City Las_Vegas 2012 10 26 16 0
5 Las_Vegas Salt_Lake_City 2012 10 28 12 0
6 Tucson Salt_Lake_City 2012 10 28 13 0
7 Chicago Las_Vegas 2012 10 22 10 30
;
! 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;
ENDDATA
SUBMODEL ROUTEM:
! Maximize number of requested flights flown
- cost of repositioning flights
- cost of aircraft;
MAX = VL*@SUM( LODPAIR( n, d, a): 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):
[LFLO] INITA(d)
+ @SUM( LODPAIR( n1, d1, d) | DLTIME(n1,d1,d) + TRVTIM(d1,d)/60 #LE# DLTIME(n,d,a):
Y(n1,d1,d))
+ @SUM( RPAIR( n1, d1, d) | DRTIME(n1,d1,d) + TRVTIM(D1,d)/60 #LE# DLTIME(n,d,a):
U(n1,d1,d))
- @SUM(LODPAIR(n1,d,a1) | DLTIME(n1,d,a1) #LT# DLTIME(n,d,a):
Y(n1,d,a1))
- @SUM( RPAIR(n1,d,a1) | DRTIME(n1,d,a1) #LE# DLTIME(n,d,a):
U(n1,d,a1))
>= Y(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):
Y(n1,d1,d))
+ @SUM( RPAIR( n1, d1, d) | DRTIME(n1,d1,d) + TRVTIM(d1,d)/60 #LE# DRTIME(n,d,a):
U(n1,d1,d))
- @SUM(LODPAIR(n1,d,a1) | DLTIME(n1,d,a1) #LE# DRTIME(n,d,a):
Y(n1,d,a1))
- @SUM( RPAIR(n1,d,a1) | a1 #NE# a #AND# (DRTIME(n1,d,a1) #LE# DRTIME(n,d,a)):
U(n1,d,a1))
>= U(n,d,a);
);
ENDSUBMODEL
CALC:
! Begin code to ..
! Convert Year, Month, Day, Hour, Minute(n,d,a) to a scalar DLTIME(n,d,a)
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;
);
! End of code to convert to scalar 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):
@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); ! If you want to see the explicit scalar model;
@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 :1),
' (of ',@SUM(LODPAIR(n,d,a) :1),')',@NEWLINE(1));
@WRITE(' Number aircraft used= ',@SUM(CITY(i):INITA(I)),@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),' Trips flown: 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):
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));
@WRITE(' Origin Destination yyyy mm dd hh mm dwk',@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