10
$\begingroup$

I'm really interested in knowing the methods used by the Air-Traffic-Flow-Management (ATFM) providers to increase the throughput of the airspace by balancing safety, efficiency and cost. I've been reading different research papers and most of them conclude on using algorithms based on linear programming to manage the arrival and departure slots.

For instance, there are many articles explaining a possible resolution of the Ground Holding Problem, that allocates departure slots so that no sector is violated, by using linear programming and mathematical optimization techniques. Airport capacity as well can be improved by the use of linear programming.

I know that linear programming is based on minimizing/maximizing a certain objective function, subject to a set of constraints.

I see that these techniques can be a good idea to have a big picture of an optimal configuration of slots, for instance. But are these linear programming algorithms actually used?

Is linear programming so much effective to carry out air traffic management according to this method? What other methods are powerful and used nowadays to manage air traffic?

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't know what NMOC actually uses, but I think it is not linear programming. The algorithm must be an online one, that is it must assign time slots to flights as the flight plans are filed, without much room for moving the already scheduled ones. Linear programming is not suitable for that. I'd rather expect some variation on online scheduling (all the optimization algoritms are rather closely related though). $\endgroup$
    – Jan Hudec
    May 11, 2015 at 9:33
  • $\begingroup$ That's what I thought. But I found plenty of research papers talking about linear programming techniques applied to air traffic management. $\endgroup$
    – Airman01
    May 11, 2015 at 12:22
  • $\begingroup$ Honestly this question is probably a bit to specific/technical, unless if you could get people who actually designed the software that's used, it'd be hard to give details, since most people that use the software just use it or press the buttons to get the result they need. In the US when flow times are issued, they're all done via computer(In the US, EDCTs are off Proposed departure time, APREQ programs are call the TMU when they're close to ready to go, and figure out a release time that works) $\endgroup$
    – slookabill
    May 11, 2015 at 22:10

2 Answers 2

Reset to default
8
$\begingroup$

Linear programming (LP) is an optimization method that finds the highest (or lowest) possible value of a set of linear equations given a number of linear constraints.

There are a number of objectives in Air Traffic Management that may be described by linear equations. Runway throughput for example: twice as many aircraft can be seen as "twice as good". Or delay: one minute of delay of a passenger aircraft with 400 passengers is as bad as 2 minutes of delay for a passenger aircraft with 200 passengers (both have 400 passenger-minutes-of-delay). Mathematical models based on these linear relationship can help to make decisions for air traffic controllers/planners.

There are obvious limitations to linear programming. Not everything can be modeled as a linear relationship. Often the relations are more complex and linear models will be a poor fit because the relationship is not linear at all. In ATFM modelling, usually binary integer variables are used that can only take values of zero or one, thus a Binary Integer Linear Program is solved (BIP). And is 40 minutes of delay of a 10 passenger aircraft as bad as 1 minute of delay of a 400 passenger aircraft? These kind of relationships tend to prevent the small aircraft from ever taking off: it always pays off to let a bigger aircraft jump the queue. Perhaps a quadratic component in the 'cost-function' would bring a solution here.

Therefore more advanced models are needed. Methods like Integer Linear Programming (ILP), Mixed Integer Linear Programming, Mixed Integer Quadratic Programming and more advance optimization algorithms are used as well.

Another problem is that while these optimization methods may be able to find a best possible strategy, they are not necessarily easy to understand. Air traffic controllers don't like to be just told what to do, they need to understand why a strategy is proposed so they can think ahead and create what-if scenarios. It is impossible to program every what-if scenario in the optimization model, so at times the controller will need to deviate from the proposed solution. Without understanding what the algorithm had planned, it is difficult for a controller to predict the knock-on effects of his deviation from the proposed plan.

Early arrival management software worked reasonably well when the weather was nicely playing along, but gave hopelessly wrong suggestions when a couple of thunderstorms would render the normal approach routes unusable. Flexibility and two way communication between the system and the controller is essential to make a good product, there is much more to it than choosing the right optimization algorithm.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Even the linearity assumption that delay minutes per person is a good metric is something of a simplification. It's probably better overall to delay a large plane than a small one because the large plane is likely to be flying a longer route (more opportunity to make up the lost time) and also be flying fewer legs in the day (less susceptible to accumulating delays). So the whole thing is pretty non-linear. $\endgroup$
    – David Richerby
    May 12, 2015 at 15:10
  • $\begingroup$ @DeltaLima Excellent answer. That's what I was expecting about linear relationships. Thank you so much it helped a lot. $\endgroup$
    – Airman01
    May 12, 2015 at 16:13
4
$\begingroup$

In Europe, the Network Management uses the Computer-Assisted-Slot-Allocation (CASA) algorithm in the Enhanced Tactical Flow Management System to allocate the departure slots. The CASA algorithm is a heuristic that follows the 'first-planned-first-served' principle and shifts departure timeslots of flights that would otherwise violate sector capacities. Eurocontrol describes the CASA Algorithm in the Air Traffic Flow and Capacity Management Users Manual:

In accordance with the principle of ‘First Planned - First Served’ the system extracts all the flights entering the specified airspace and sequences them in the order they would have arrived at the airspace in the absence of any restriction.

...

In addition to this fundamental process, a number of other mechanisms will act to compensate for factors such as late received flight plans and modifications.

This is not the same as Linear Optimization.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .