! Air Traffic Flow Model with Ground Delays.
Determine when each of a set of flights should take off.
Each flight is described by
a desired/scheduled take off time, and
the time intervals at which it will use
various resources (take off runway,
flight control sectors, landing runway).
Each resource (runway or flight control sector) is
described by how many aircraft can simultaneously
use it.
The objective is to minimize the total ground delay
suffered by all flights, subject to no resource
being overutilized at any point in time.
Time is discretized into buckets.
The parameter tmbkt specifies the length of each bucket;
! Keywords: Air traffic control, Ground delays, Sequencing;
SETS:
! Declare the various sets and the attributes associate
with each member of the set;
sector: scap;
flight: tmbgn;
time;
sxt( sector, time): overload;
fxt( flight, time): z;
fxs( flight, sector): TMENT, TMOUT;
ENDSETS
DATA:
! Assume all times are in minutes;
tmbkt = 5; ! Minutes in a discrete time period/time bucket.
the larger the bucket, the smaller the model and
faster it solves. A smaller bucket provides
a more accurate model;
time = 1..80; ! Number discrete time periods in plan horizon;
delaymx = 45; ! Maximum delay tolerated for any flight;
delaywgt = 1; ! Weight in objective on total delay;
congestwgt = 100; ! Wgt in objective on total overcongestion;
! The possible bottlenecks in the system.
the runways, and the various air control sectors;
sector = ORDRNWY DCARNWY DFWRNWY DENRNWY BOSRNWY ABQRNWY
SECTORN SECTORNE SECTORE SECTORS SECTORSW SECTORW SECTORC;
! Number planes/tasks that each resource can simultaneously handle.
Each runway can handle only 1 plane at a time,
Each sector can handle two simultaneously;
scap = 1 1 1 1 1 1
2 2 2 2 2 2 2;
! The flights to be scheduled, O'Hare to Dallas,
WashingtonDC to Denver, Boston to Albuquerque;
flight = ORDDAL1 DCADEN1 BOSABQ1;
! Their scheduled start times;
tmbgn = 10 0 25;
! Description of flight, resource, start, end of usage...;
fxs, tment, tmout =
! of flight from Chicago to Dallas;
ORDDAL1 ORDRNWY 0 5
ORDDAL1 SECTORN 5 20
ORDDAL1 SECTORC 20 110
ORDDAL1 SECTORS 110 135
ORDDAL1 DFWRNWY 135 140
! of flight from Washington National to Denver;
DCADEN1 DCARNWY 0 5
DCADEN1 SECTORE 5 60
DCADEN1 SECTORC 60 140
DCADEN1 SECTORW 140 245
DCADEN1 DENRNWY 245 250
! of flight from Boston to Albuquerque;
BOSABQ1 BOSRNWY 0 5
BOSABQ1 SECTORNE 5 60
BOSABQ1 SECTORC 60 140
BOSABQ1 SECTORSW 140 355
BOSABQ1 ABQRNWY 355 360 ;
! For this data set, if:
ORDDAL1 departs on time it is in SECTORC from 30 to 120,
DCADEN1 departs on time it is in SECTORC from 60 to 140,
BOSABQ1 departs on time it is in SECTORC from 85 to 165,
so there would be 3 planes in SECTORC from 85 to 120,
exceeding the capacity of 2, so one must be delayed;
ENDDATA
SUBMODEL groundlay:
! Parameters:
scap(s) = number planes allowed in sector s simultaneously,
tmbgn( f) = scheduled begin time of flight f,
tment( f, s) = time flight f enters sector s minus depart time,
tmout( f, s) = time flight f exits sector s minus depart time,
;
! Variables:
z(f,b) = 1 if flight f takes off at time bucket b ;
! Bucket b begins at tmbkt*(b-1) and ends at tmbkt*b;
! An activity starting at p and ending at q overlaps bucket b if
p < b*tmbkt, and q > tmbkt*(b-1),
We say a flight f is delayed if it does not start in its
its earliest possible bucket, i.e., bucket b so (b-1)*tmbkt >= tmbgn(f);
! Objective:
Minimize the cost of ground delay + congestion;
Min = delaywgt * delaytot + congestwgt * overloadtot;
overloadtot = @SUM( sxt(s,b): overload(s,b));
delaytot = @SUM( fxt(f,b): tmbkt*(b-1 - @FLOOR(tmbgn(f)/tmbkt))*z(f,b));
! Each flight f must depart in some time bucket b;
@FOR( flight(f):
[MUSTDO] @SUM( time(b): z(f,b)) = 1;
);
! Number aircraft in sector s in time period t
<= capacity + tolerated_congestion;
@FOR( sector( s):
@FOR( time(b):
! Sum over departure times t1 that would put plane in
this sector at time bucket b;
[SCTCAP] @SUM( fxs(f,s):
@SUM( time(b1) | (b1 + tment(f,s)/tmbkt #le# b)
#and# (b1 + tmout(f,s)/tmbkt #gt# b):
z(f,b1))) <= scap(s) + overload(s,b);
);
);
! The z(f,b) must be binary/(0 or 1);
@FOR( fxt(f,b): @BIN( z(f,b)));
! Set to zero infeasible departure times;
@FOR( fxt( f,b) | (b-1)*tmbkt #lt# tmbgn(f)
#or# (b-1)*tmbkt #gt# tmbgn(f) + delaymx:
z(f,b) = 0;
);
! Possible extensions:
Flight connections:
Flight f2 cannot depart any earlier than x minutes after arrival of flight f1,
Alternate flight paths:
There are two or more alternate paths for a flight,
exactly one must be taken.;
ENDSUBMODEL
CALC:
@SET( 'TERSEO',2); ! Output level (0:verb, 1:terse, 2:only errors, 3:none);
@SET( 'OROUTE',1); ! Route output immediately to the window line by line;
@SET( 'IPTOLR', .02); ! Set ending relative optimality tolerance;
@SET( 'TIM2RL', 5); ! Time in seconds to apply optimality tolerance;
@solve( groundlay); ! Solve the model;
! Write a little report;
@WRITE(' Scheduling of Ground Delays for a Set of Flights', @NEWLINE(1));
@WRITE(' Flight Sched_depart Actual', @NEWLINE(1));
@FOR( flight(f):
dtime = @SUM( fxt(f,b): tmbkt*(b-1)*z(f,b));
@WRITE( ' ',@FORMAT( flight(f),'10s'),' ',
@FORMAT( tmbgn(f),'7.0f'),' ', @FORMAT( dtime,'7.0f'), @NEWLINE(1))
);
@WRITE(' Total delay= ', delaytot, @NEWLINE(1));
ENDCALC
|
