Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - A dynamic programming approach for the airport capacity allocation problem
AU - Dell'Olmo, Paolo
AU - Lulli, Guglielmo
PY - 2003/7
Y1 - 2003/7
N2 - In most of the optimization models developed to manage airports operations, arrivals and departures capacities are treated as independent variables: that is the number of flights allowed to take off does not affect the number of landings in any unit of time, and vice versa. This assumption is seldom verified in most of the congested airports, where many interactions between arrivals and departures take place. In this paper, we face the problem of finding the optimal trade‐off between the number of arrivals and departures in order to reduce a delay function of all the flights, using a more realistic representation of the airport capacity, i.e. the capacity envelope. Under the assumption of piecewise linear convex capacity envelopes and of the exact interpolation of all the Pareto‐optimal operational points, we show that the problem can be formulated as a linear programming model. For general airport capacity envelopes, we propose a dynamic programming formulation with a corresponding backward solution algorithm, which is robust, easy to implement and has a linear computational complexity. The algorithm performances are evaluated on different realistic scenarios, and the optimal solutions are compared with those computed by a greedy algorithm, which can be seen as an approximation of the current decision procedures. The percentage deviation of the cost of these two solutions ranges from 3.98 to 35.64%
AB - In most of the optimization models developed to manage airports operations, arrivals and departures capacities are treated as independent variables: that is the number of flights allowed to take off does not affect the number of landings in any unit of time, and vice versa. This assumption is seldom verified in most of the congested airports, where many interactions between arrivals and departures take place. In this paper, we face the problem of finding the optimal trade‐off between the number of arrivals and departures in order to reduce a delay function of all the flights, using a more realistic representation of the airport capacity, i.e. the capacity envelope. Under the assumption of piecewise linear convex capacity envelopes and of the exact interpolation of all the Pareto‐optimal operational points, we show that the problem can be formulated as a linear programming model. For general airport capacity envelopes, we propose a dynamic programming formulation with a corresponding backward solution algorithm, which is robust, easy to implement and has a linear computational complexity. The algorithm performances are evaluated on different realistic scenarios, and the optimal solutions are compared with those computed by a greedy algorithm, which can be seen as an approximation of the current decision procedures. The percentage deviation of the cost of these two solutions ranges from 3.98 to 35.64%
KW - air traffic management
KW - airport operations
KW - dynamic programming
U2 - 10.1093/imaman/14.3.235
DO - 10.1093/imaman/14.3.235
M3 - Journal article
VL - 14
SP - 235
EP - 249
JO - IMA Journal of Management Mathematics
JF - IMA Journal of Management Mathematics
SN - 1471-678X
IS - 3
ER -