Robust aircraft conflict resolution under trajectory prediction uncertainty

In air traffic control, aircraft velocity may be perturbed due to weather effects or measurements errors and affect trajectory prediction. We address the aircraft conflict resolution problem in the presence of such perturbations. We consider polyhedral uncertainty sets on aircraft velocity, develop a budgeted robust optimization approach and show that it is amenable to mixed-integer optimization. Numerical experiments reveal that perturbations of the order of 5% on aircraft velocities can be accounted for without significantly impacting performance.     

Solving air traffic conflict problems via local continuous optimization

This paper first introduces an original trajectory model using B-splines and a new semi-infinite programming formulation of the separation constraint involved in air traffic conflict problems. A new continuous optimization formulation of the tactical conflict-resolution problem is then proposed. It involves very few optimization variables in that one needs only one optimization variable to determine each aircraft trajectory. Encouraging numerical experiments show that this approach is viable on realistic test problems. Not only does one not need to rely on the traditional, discretized, combinatorial optimization approaches to this problem, but, moreover, local continuous optimization methods, which require relatively fewer iterations and thereby fewer costly function evaluations, are shown to improve the performance of the overall global optimization of this non-convex problem.     

Using graph concepts to assess the feasibility of a sequenced air traffic flow with low conflict rate

In this paper, we propose to study feasibility issues of a new air traffic paradigm. In this paradigm, aircraft are following immaterial moving points in such a way that no conflict (or at most few) occurs between aircraft. We provide lower and upper bounds on the maximum density of a solution. In particular, we characterize the density of the solution according to the colorability of an auxiliary graph, modelling the potential conflicts between moving points.     

Configuration of airspace sectors for balancing air traffic controller workload

In this paper, we consider the problem of reconfiguring a section of the national airspace into appropriate sectors from the viewpoint of balancing the predicted air traffic controller workload. The given section of the airspace is specified as a convex polygon in two-dimensions (or a union of such structures), and contains a discretized set of weighted grid points representing localized sub-regions, where the weights reflect the associated air traffic controller monitoring and conflict resolution workloads. We describe four variants of a mixed-integer programming-based algorithmic approach to recursively partition the specified airspace region so as to balance the total weight distribution within each resulting sector. In addition, we augment the proposed model to further accommodate inter-sector coordination workload within this partitioning process, which accounts for the number of flight hand-offs between adjacent sectors. Some illustrative examples are presented to assess the proposed methodology and to investigate the relative computational efficiency and the quality of solutions produced by each algorithmic variant. One competitive procedure is then used to configure a region of airspace over the U.S. using realistic flight data. The main purpose of this work is to provide some modeling concepts and insights to complement the rich body of existing literature on this topic.     

Aircraft proximity termination conditions in the planar turn centric modes

Closed-form analytic solutions for proximity management strategies are of great importance as a design benchmark when validating both automated systems and procedures associated with the design of air traffic rules. Merz (1973) first presented a solution for a set of optimal strategies for resolving co-planar co-operative encounters between two aircraft (or ships) with identical linear and rotational speeds. This paper extends the solution domain for turning aircraft beyond that of identical aircraft by presenting a rigorous analysis of the problem through a generalised optimisation approach. This analysis provides a dependable method for determining the location of the point of closest approach. This is achieved by using a vector form of Fermat’s equation for stationary points. A characteristic of this solution is the identification of a fixed reference point lying on the vector between the aircraft turn centres or on one of its extensions. This point is then used to determine where the location of the minima in the relative range between the aircraft will occur. Bounds for the domain of the solution are constructed in terms of the rotational angles of the aircraft on their turn circles. Four distinct topologies are required to characterise the types of minima that can occur. The methodology has applications in an operational context permitting a more detailed and precise specification of proximity management functions when developing algorithms for aircraft avionics and air traffic management systems.     

A fixed-point iteration approach for multibody dynamics with contact and small friction

Acceleration–force setups for multi-rigid-body dynamics are known to be inconsistent for some configurations and sufficiently large friction coefficients (a Painleve paradox). This difficulty is circumvented by time-stepping methods using impulse-velocity approaches, which solve complementarity problems with possibly nonconvex solution sets. We show that very simple configurations involving two bodies may have a nonconvex solution set for any nonzero value of the friction coefficient. We construct two fixed-point iteration algorithms that solve convex subproblems and that are guaranteed, for sufficiently small friction coefficients, to retrieve, at a linear convergence rate, the unique velocity solution of the nonconvex linear complementarity problem whenever the frictionless configuration can be disassembled. In addition, we show that one step of one of the iterative algorithms provides an excellent approximation to the velocity solution of the original, possibly nonconvex, problem if for all contacts we have that either the friction coefficient is small or the slip velocity is small.Subject Index. 70E55, 75M10, 75M15, 90C33A partial version of this work has appeared in the proceedings of the NATO Advanced Studies Institute on Virtual Nonlinear Multibody Systems, Prague, 2002.     

Improving short-term conflict alert via tabu search

In this paper we describe some work carried out by National Air Traffic Services in the UK into developing optimisation tools to help improve the effectiveness of one of their air traffic control safety systems—short-term conflict alert. In short-term conflict alert a computer system continually monitors radar data and alerts air traffic controllers if it detects a situation where two aircraft are in danger of approaching too close to one other. Within the computer program that makes up the short-term conflict alert system is a large number of parameters. Choosing appropriate values for these parameters is a task that is currently done via extensive human intervention. In this paper we describe how a modern heuristic technique, tabu search, can be used to make parameter choices.     

Ein nichtlineares Glättungsverfahren zur rekonstruktion von flugbahnen aus radardaten

Data processing is an important tool in airspace surveillance and air traffic control today. In this paper the problem is treated how to reconstruct a flown trajectory from its correlated radar plots subject to a certain knowledge of the aircraft manoeuverability and the radar measurement statistics. A variational approach leads to a generalized smoothing spline method. Simulation results are presented.     

Models for single-sector stochastic air traffic flow management under reduced airspace capacity

Air traffic efficiency is heavily influenced by unanticipated factors that result in capacity reduction. Of these factors, weather is the most significant cause of delays in airport and airspace operations. Considering weather-related uncertainty, air traffic flow management involves controlling air traffic through allocation of available airspace capacity to flights. The corresponding decision process results in a stochastic dynamic problem where aircraft on the ground and in the air are controlled based on the evolution of weather uncertainty. We focus on the single-sector version of the problem that is applicable to a majority of cases where a volume of airspace has reduced capacity due to convective weather. We model the decision process through stochastic integer programming formulations and computationally analyse it for tractability. We then demonstrate through actual flight schedule data that a simplistic but practically implementable approximation procedure is a generally effective solution approach for these models.     

基于优先级的进离港航班排序优化问题研究

研究机场终端区进离港航班排序优化问题,对于提高跑道利用率以及降低航班延误损失具有重要意义。本文首先考虑航班运行方式(降落和起飞)、飞机类型以及航班的重要程度(航程是否连续)的不同所造成延误损失的不同,设计三维优先级表反映调度优先等级,并将其转化为延误成本系数。其次,为实现调度的公平性和减轻管制人员的工作负荷,设置允许延误的航班架次约束、邻边约束以及最大限制位置约束。再次,以最小化航班总延误成本为目标建立模型,提出相应的改进蚁群算法(GJAC)进行求解。最后通过数值实验验证所提算法在考虑调度优先等级及上述约束条件的同时能有效减少进离港航班队列的总延误成本。     

A set packing model for the ground holding problem in congested networks

Air traffic flow management (ATFM) consists of several activities performed by control authorities in order to reduce delays due to traffic congestion. Ground holding decisions restrict certain flights from tacking off at the scheduled departure time if congestion is expected at the destination airport. They are motivated by the fact that it is safer to hold an aircraft on the ground than in the air. Several integer linear programming models have been proposed to efficiently solve the ground holding problem (GHP). In this paper we investigate a set packing formulation of the GHP and design a branch-and-cut algorithm to solve the problem in high congestion scenarios, i.e., when lack of capacity induces flights cancellation. The constraint generation is carried out by heuristically solving the separation problem associated with a large class of rank inequalities. This procedure exploits the special structure of the GHP's intersection graphs. The computational results indicate that the proposed algorithm outperforms other algorithms in which flight cancellation has been allowed.     

Approximation of the steepest descent direction for the O-D matrix adjustment problem

In this paper, a method to approximate the directions of Clarke's generalized gradient of the upper level function for the demand adjustment problem on traffic networks is presented. Its consistency is analyzed in detail. The theoretical background on which this method relies is the known property of proximal subgradients of approximating subgradients of proximal bounded and lower semicountinuous functions using the Moreau envelopes. A double penalty approach is employed to approximate the proximal subgradients provided by these envelopes. An algorithm based on partial linearization is used to solve the resulting nonconvex problem that approximates the Moreau envelopes, and a method to verify the accuracy of the approximation to the steepest descent direction at points of differentiability is developed, so it may be used as a suitable stopping criterion. Finally, a set of experiments with test problems are presented, illustrating the approximation of the solutions to a steepest descent direction evaluated numerically. Research supported under Spanish CICYT project TRA99-1156-C02-02.     

Canonical Duality Theory and Solutions to Constrained Nonconvex Quadratic Programming

This paper presents a perfect duality theory and a complete set of solutions to nonconvex quadratic programming problems subjected to inequality constraints. By use of the canonical dual transformation developed recently, a canonical dual problem is formulated, which is perfectly dual to the primal problem in the sense that they have the same set of KKT points. It is proved that the KKT points depend on the index of the Hessian matrix of the total cost function. The global and local extrema of the nonconvex quadratic function can be identified by the triality theory [11]. Results show that if the global extrema of the nonconvex quadratic function are located on the boundary of the primal feasible space, the dual solutions should be interior points of the dual feasible set, which can be solved by deterministic methods. Certain nonconvex quadratic programming problems in {\open {R}}^{n} can be converted into a dual problem with only one variable. It turns out that a complete set of solutions for quadratic programming over a sphere is obtained as a by-product. Several examples are illustrated.     

Scheduling aircraft landings at London Heathrow using a population heuristic

With increasing levels of air traffic, making effective use of limited airport capacity is obviously important. This paper reports on an investigation undertaken by National Air Traffic Services in the UK into improving runway utilisation at London Heathrow. This investigation centred on developing an algorithm for improving the scheduling of aircraft waiting to land. The heuristic algorithm developed (a population heuristic) is discussed and results presented using actual operational data relating to aircraft landings at London Heathrow. This data indicates that our algorithm could have improved on air traffic control decisions in such cases by between 2–5?% in terms of reducing the timespan required to land all of the aircraft considered.     

A light-propagation model for aircraft trajectory planning

Predicted air traffic growth is expected to double the number of flights over the next 20 years. If current means of air traffic control are maintained, airspace capacity will reach its limits. The need for increasing airspace capacity motivates improved aircraft trajectory planning in 4D (space+time). In order to generate sets of conflict-free 4D trajectories, we introduce a new nature-inspired algorithm: the light propagation algorithm (LPA). This algorithm is a wavefront propagation method that yields approximate geodesic solutions (minimal-in-time solutions) for the path planning problem, in the particular case of air-traffic congestion. In simulations, LPA yields encouraging results on real-world traffic over France while satisfying the specific constraints in air-traffic management.     

一类Nevanlinna-Pick问题的Toeplitz向量方法

首次应用改进的Ｔｏｅｐｌｉｔｚ向量方法刻划Ｃａｒａｔｈｅｏｄｏｒｙ函数类中含多重零插值点的Ｎｅｖａｎ ｌｉｎｎａ Ｐｉｃｋ问题与截断的三角矩量问题之间的内在联系，从而给出这类Ｎｅｖａｎｌｉｎｎａ Ｐｉｃｋ问题的可解性准则和通解的参数化表示．     

Conditional Gradient Method for Double-Convex Fractional Programming Matrix Problems

We consider the problem of optimizing the ratio of two convex functions over a closed and convex set in the space of matrices. This problem appears in several applications and can be classified as a double-convex fractional programming problem. In general, the objective function is nonconvex but, nevertheless, the problem has some special features. Taking advantage of these features, a conditional gradient method is proposed and analyzed, which is suitable for matrix problems. The proposed scheme is applied to two different specific problems, including the well-known trace ratio optimization problem which arises in many engineering and data processing applications. Preliminary numerical experiments are presented to illustrate the properties of the proposed scheme.     

Optimal Cooperative Collision Avoidance Strategy for Coplanar Encounter: Merz’s Solution Revisited

Analytic solutions for optimal collision avoidance strategies are of great importance when setting and validating air traffic rules and as a benchmark when validating automated proximity management and collision avoidance systems. Such a solution for optimal air collision avoidance strategies for a coplanar cooperative encounter between two identical aircraft (or ships) was first presented by Merz (Proc. Joint Automatic Control Conf., Pap. 15-3:449–454, 1973; Navigation 20(2):144–152, 1973). Unfortunately, Merz provided only a very brief indicative justification for his solution. This paper presents a rigorous analysis of the problem. New results include a characterization of a complete set of extremals, justification for optimal strategies and an analysis of the properties of the regions of different optimal strategies. A simple, practical and sufficiently accurate closed form approximation for dispersal curves that partition the plane of initial positions into the regions of different optimal strategies is also presented. We thank the anonymous referees and our colleagues Drs. R.S. Anderssen and R. Jarrett for helpful comments and suggestions.     

A mathematical model and algorithms for the aircraft hangar maintenance scheduling problem

An aircraft hangar maintenance scheduling problem is studied, motivated by the aircraft heavy maintenance conducted in a hangar operated by an independent maintenance service company. The aircraft hangar maintenance scheduling problem in such context consists of determining a maintenance schedule with minimum penalty costs in fulfilling maintenance requests, and a series of hangar parking plans aligned with the maintenance schedule through the planning period. A mixed-integer linear programming (MILP) mathematical model, integrating the interrelations between the maintenance schedule and aircraft parking layout plans, is presented at first. In the model, the variation of parking capacity of the maintenance hangar and the blocking of the aircraft rolling in and out path are considered. Secondly, the model is enhanced by narrowing down the domain of the time-related decision variables to the possible rolling in and out operations time of each maintenance request. Thirdly, to obtain good quality feasible solutions for large scale instances, a rolling horizon approach incorporating the enhanced mathematical model is presented. The results of computational experiments are reported, showing: (i) the effectiveness of the event-based discrete time MILP model and (ii) the scalability of the rolling horizon approach that is able to provide good feasible solutions for large size instances covering a long planning period.