Mixed-Integer Reformulations of Resource-Constrained Two-Stage Assignment Problems - Hupp, Lena; Kapolke, Manu; Liers, Frauke; Martin, Alexander; Weismantel, Robert (2020)
The running time for solving a mixed-integer linear optimization problem (MIP) strongly depends on the number of its integral variables. Bader et al. [Math. Progr. 169 (2018) 565–584] equivalently reformulate an integer program into an MIP that contains a reduced number of integrality constraints, when compared to the original model. Generalizing the concept of totally unimodular (TU) matrices, the reformulation is determined via a so-called affine TU decomposition of the underlying constraint matrix. In this work, we develop affine TU decompositions for two-stage resource-constrained b-matching problems that have challenging applications in runway utilization of aircraft. Mathematically, the task consists in determining an optimum two-stage bipartite b-matching in a graph. The two stages are linked by resource restrictions modeled by specific knapsack constraints. Determining an affine TU decomposition for this problem is reduced to the question of how the incidence matrix of a bipartite graph can be enlarged by appending a submatrix such that the resulting matrix again is TU. Sufficient conditions are derived for the structure of such a submatrix. We apply our findings to two-stage b-matching problem with one resource constraint. For several resource constraints, the TU requirements are not met in general. Nevertheless, in case b = 1, we reformulate the problem with one resource constraint per node such that the underlying polytope is integral. This again leads to a reduced number of integrality constraints, when compared to the original formulation. The computational study focuses on the aircraft application. Using state-of-the-art MIP solvers, it is shown that, especially for the case with few resource constraints, the reformulated models usually lead to considerably shorter running times, when compared to solving the original formulation.
Keywords: mixed-integer programming reformulation; affine TU decomposition; total unimodularity; runway utilization

Pre-tactical optimization of runway utilization under uncertainty - Kapolke, Manu; Fürstenau, Norbert; Heidt, Andreas; Liers, Frauke; Mittendorf, Monika; Weiß, Christian (Journal of Air Transport Management, 2016)
Efficient planning of runway utilization is one of the main challenges in Air Traffic Management (ATM). It is important because runway is the combining element between airside and groundside. Furthermore, it is a bottleneck in many cases. In this paper, we develop a specific optimization approach for the pre-tactical planning phase that reduces complexity by omitting unnecessary information. Instead of determining arrival/departure times to the minute in this phase yet, we assign several aircraft to the same time window of a given size. The exact orders within those time windows can be decided later in tactical planning. Mathematically, we solve a generalized assignment problem on a bipartite graph. To know how many aircraft can be assigned to one time window, we consider separation requirements for consecutive aircraft types. In reality, however, uncertainty and inaccuracy almost always lead to deviations from the actual plan or schedule. Thus, we present approaches to incorporate uncertainty directly in our model in order to achieve a stabilization with respect to changes in the data. Namely, we use techniques from robust optimization and stochastic optimization. Further, we analyze real-world data from a large German airport to obtain realistic delay distributions, which turn out to be two-parametric Γ-distributions. Finally, we describe a simulation environment to test our new solution methods.
Keywords: Pre-tactical planning; Runway; Optimization; Uncertainty; Robustness; Data analysis

Pre-Tactical Planning of Runway Utilization Under Uncertainty: Optimization and Validation - Fürstenau, Norbert; Heidt, Andreas; Kapolke, Manu; Liers, Frauke; Mittendorf, Monika; Weiß, Christian (Proceedings of the SESAR Innovations Days 2015, 2015)
Efficient planning of runway utilization is one of the main challenges in Air Traffic Management (ATM). In a previous paper, we developed a specific optimization approach for the pre-tactical planning phase that reduces complexity by omitting unnecessary information. Further, we investigated the impact of disturbances on our solutions, since in reality uncertainty and inaccuracy almost always lead to deviations from actual plans. In this paper, we now present approaches to incorporate uncertainty directly in our model in order to achieve a stabilization with respect to changes in the data. Namely, we use techniques from robust optimization and stochastic optimization. Further, we analyze real-world data from a large German airport to obtain realistic delay distributions, which turn out to be two-parametric Γ-distributions. We describe a simulation environment and test our new solution methods against standard algorithms (e.g., First-Come-First-Serve). The encouraging results show that our approaches significantly reduce the number of necessary replan nings.
Keywords: runway utilization; planning; pre-tactical; optimization; uncertainties; stochastic; robust; algorithms; models; validation; Monte Carlo simulation

Pre-tactical time window assignment: Runway utilization and the impact of uncertainties - Heidt, Andreas; Kapolke, Manu; Liers-Bergmann, Frauke; Fürstenau, Norbert; Helmke, Hartmut (SIDs 2014 - Proceedings of the SESAR Innovation Days, 2014)
Efficient planning of runway utilization is one of the main challenges in Air Traffic Management (ATM). It is important because runway is the combining element between airside and groundside. Furthermore, it is a bottleneck in many cases. In this paper, we develop a specific optimization approach for the pre-tactical planning phase that reduces complexity by omitting unnecessary information. Instead of determining arrival/departure times to the minute in this phase yet, we assign several aircraft to the same time window of a given size. The exact orders within those time windows can be decided later in tactical planning. Mathematically, we solve a generalized assignment problem on a bipartite graph. To know how many aircraft can be assigned to one time window, we consider distance requirements for consecutive aircraft types. We develop an optimization model, which can be solved fast in practice but may provide unnecessary large time buffers, and extend it to a model that solves the problem to global optimality. In reality, uncertainty and inaccuracy almost always lead to deviations from the actual plan or schedule. We present computational results concerning the abovementioned optimization approaches and investigate the impact of disturbances on our deterministic solutions. As a next step, we will incorporate uncertainties directly in our model. Therefore, we analyze real-world data from a large German airport in order to obtain realistic delay distributions and describe a simulation environment to test current and future solution methods.
CRIS-Team Scopus Importer:2023-03-07

Pre-tactical Time Window assignment: Runway Utilization and the Impact of Uncertainties - Heidt, Andreas; Kapolke, Manu; Liers, Frauke; Fürstenau, Norbert; Helmke, Hartmut (Proceedings of the SESAR Innovation Days 2014, 2014)
Efficient planning of runway utilisation is one of the main challenges in Air Traffic Management (ATM). It is important because runway is the combining element between airside and groundside. Furthermore, it is a bottleneck in many cases. However, uncertainty and inaccuracy almost always lead to deviations from the actual plan or schedule. In this paper, we develop an optimization approach for the pre-tactical planning phase that provides some flexibility in the face of small disturbances in the input data, so that we need to change our plans less frequently. Instead of determining arrival/departure times to the minute in this phase yet, we assign several aircraft to the same time slot of a given size. The exact orders within those time windows can be decided later in tactical planning. Mathematically, this leads to a generalised assignment problem on a bipartite graph. We develop an integer program (IP), which can be solved very fast but may provide unnecessary large time buffers, and extend it to a mixed integer program (MIP) that solves the problem to global optimality. We present computational results concerning the abovementioned optimization approach and investigate the impact of disturbances on our deterministic solutions. As a next step, we will incorporate uncertainties directly in our model. Therefore, we analyse real-world data from a large German airport in order to obtain realistic delay distributions and describe a simulation environment to test current and future solution methods.
Keywords: arrival / departure scheduling; stochastic optimization; robustness; delay statistics; modeling

Robust runway scheduling under uncertain conditions - Heidt, Andreas; Helmke, Hartmut; Kapolke, Manu; Liers, Frauke; Martin, Alexander (Journal of Air Transport Management, 2016)
The runway is the main element that combines airside and groundside of the ATM System. Thus, it is crucial to develop efficient models and planning algorithms for its effective usage. The best planning algorithm, however, is useless if the resulting plans cannot be implemented in the real world. This often happens because the input data of the planning algorithms face disturbances or changes over time, respectively. For example, an estimated time of arrival/departure of an aircraft may be changed. It is usually not certain for the next ten hours. In this work, we study the runway scheduling problem under uncertain conditions. First, we present mathematical optimization models that ignore uncertainties. In the most effective approach, we compute for every discretized point in time whether an aircraft is scheduled and if so, which one is. Then, in each planning step we take uncertainties into account. We then apply different robust optimization methods in order to devise solution approaches that lead to stable plans. These optimization approaches are integrated into a simulation tool and evaluated in different traffic scenarios. The Monte-Carlo simulations for a mixed-mode runway system show that our robust approaches result in fewer sequence changes and target time updates, when compared to the usual approach in which the plan is simply updated in case of infeasibility. Thus, we show that protection against uncertainties by using robust optimization indeed leads to considerably more stable plans.
Keywords: Scheduling; Uncertainty; Time-indexed model; MIP; Mixed-integer programming; Dynamic time-indexed model; Strict robustness; Light robustness