مقاله سال ۲۰۱۶

PLANNING, particularly scheduling of limited resources is one of the main tasks of Air Traffic Management (ATM). However, uncertainty, inaccuracy, and non-determinism almost always lead to deviations from the actual plan. Typical strategies to deal with these changes is to simply ignore them (plan freezing) or e slightly better e to regularly recompute or update the schedule t(j) (see Fig. 1). t(j) denotes the planned target time in the jth planning cycle. These adjustments are usually performed in hindsight, after the actual change in the data has occurred. This usually leads to schedules with reduced overall utilization and reduced throughput. The disadvantages of such an approach is obvious: A formerly optimum plan might not even be feasible any more after some disturbance has occurred. In this work, we follow a different route. First of all, we use mathematical optimization in order to design global optimum runway scheduling plans. Furthermore, in contrast to ignoring disturbances, we know there are disturbed scenarios that we integrate into the models a priori. Thus, the challenge is to incorporate uncertainty into the initial computation of the plans so that these plans are stable with respect to changes in the data. This leads to a better utilization of resources as well as to a more effi- cient support for ATM controllers and stakeholders.

Two different approaches currently exist to handle uncertainty in mathematical optimization: on the one hand stochastic optimization that can be used to compute good average solutions and on the other hand robust optimization to immunize against predefined worst-case scenarios. In normal life we intuitively act similarly. As a host of an invitation for 8 p.m. we know that there are some guests who often do not arrive before 8:30, but others will arrive in time. Depending on the invited guests, we start our preparation very early or we know that we still have time. In the stochastic case, our host tries to find a good compromise between his waiting time for the first guests and the waiting time of the guests for the host (still taking a shower and searching a pair of socks). In the robust case, however, the host tries to avoid the awkward situation that the first guest would arrive earlier than the host is prepared for.

In this paper we concentrate on robust optimization, i.e. the goal is to avoid improbable, but critical situations in order to obtain stable plans. Stochastic optimization and its combination with robustness is considered in the WP-E funded project RobustATM (Kapolke et al., 2016). However, an increase in stability naturally comes with the price that it might reduce the runway efficiency in general. In order to keep this price under control, we present different robust optimization concepts, a strict robust one and a light robust one. In the latter, the user specifies beforehand what reduction in efficiency is acceptable. Our methods then maximize the stability of the schedule while keeping the efficiency at the acceptable limit. Light robustness has been developed for railways (Fischetti and Monaci, 2009). We show here that it can be successfully applied for runway scheduling as well.