Route generation for optimization in the Air Transport System : aircraft recovery problem and 4D trajectory planning

• Main Author: Qian, Xiongwen
• Other Authors: Chen Chun-Hsien
• Format: Theses and Dissertations
• Language: English
• Published: 2018
• Subjects: DRNTU::Engineering::Aeronautical engineering
• Online Access: http://hdl.handle.net/10356/73437
• Institution: Nanyang Technological University

The punctuality and efficiency of the Air Transport System (ATS) has a significant impact on the economy. In 2016, the US Passenger Carrier Delay Costs were estimated to be USD 62.55 per minute and the total US flight arrival delays amounted to over 59 million minutes. Furthermore, air traffic volume is growing rapidly. The International Civil Aviation Organization (ICAO) estimates that air traffic in the Asia Pacific region will triple by 2030. With the rapid growth of air traffic, the inefficiency of the ATS has become a salient problem. Flight delays, cancellations, and air traffic congestion cost customers and airlines a considerable amount of money. In this dissertation, we tackle the inefficiency of the ATS from two perspectives: airspace users (airlines) and Air Traffic Management (ATM) service providers (air traffic controllers). Correspondingly, two critical problems are studied on the operational level, the aircraft recovery problem (ARP) and 4D (three dimensions plus time) trajectory planning. Both problems are formulated as special routing problems, and because of the large computational scale of the two problems encountered in real life, they are solved by carefully designed route generation algorithms employing ad hoc decomposition techniques. In the first part of the dissertation, the aircraft recovery problem with airport capacity constraints and maintenance flexibility is investigated. The problem is to re-schedule flights and re-assign aircraft in real time with minimized recovery cost for airlines after disruptions occur. In most published studies, airport capacity and flexible maintenance are not considered simultaneously via an optimization approach. To bridge this gap, we propose a column generation framework to solve the problem. The framework consists of a master problem for selecting routes for aircraft and subproblems for generating routes. Airport capacity is explicitly considered in the master problem and swappable planned maintenances can be incorporated in the subproblem. Instead of the discrete delay models that are widely adopted in much of the existing literature, in this work flight delays are continuous and optimized accurately in the subproblems. The continuous-delay model improves the accuracy of the optimized recovery cost. In one test scenario, the accuracy is improved by up to 37.74%. The computational study based on real-world problems shows that the master problem gives a very tight linear relaxation with small, often zero, optimality gap. Large-scale problems can be solved within 5 minutes and the run time could be further shortened by parallelizing subproblems on more powerful hardware. In addition, from a managerial point of view, computational experiments reveal that swapping planned maintenances may bring a considerable reduction in recovery cost from an estimated 20% to 60%, depending on specific problem instances. Furthermore, the decreasing marginal value of airport slot quotas is found by computational experiments. In the second part of the dissertation, we consider a coordinated multi-aircraft 4D trajectory planning problem which is illustrated by planning 4D trajectories for aircraft traversing an Air Traffic Control (ATC) sector. The planned 4D trajectories need to specify each aircraft's position at any time, ensuring conflict-free trajectories and reducing fuel and delay costs, with possible aircraft maneuvers such as speed adjustments and flight level changes. In contrast to most existing literature, the impact of buffer safety distance is also under consideration, and freedom from conflict is guaranteed at any given time (not only at discrete time instances). The problem is formulated as a pure-strategy game with aircraft as players and all possible 4D trajectories as strategies. An efficient maximum improvement distributed algorithm decomposing multi-aircraft problems into single-aircraft problems is developed to find an equilibrium at which every aircraft cannot unilaterally improve further without the need to enumerate all possible 4D trajectories in advance. Proofs of the existence of the equilibrium and the convergence of the algorithm are given. A case study based on real air traffic data shows that the algorithm is able to solve 4D trajectories for online applications with an estimated 16.7% reduction in operating costs while allocating an abundant buffer safety distance at the minimum separation point. Computational experiments verify the scalability of the algorithm. Airlines and ATM service providers are the two vital stakeholders of the ATS; the methodologies and techniques developed in this dissertation make enlightening contributions to improving the operation of the ATS from an optimization point of view. Because decomposition methods are highly problem-dependent, the design of the algorithms requires both domain knowledge and mathematical intuition. However, in general, the proposed route generation algorithms in the dissertation also provide hints to many other real-life large-scale problems in logistics systems, such as railway transportation, maritime transportation, and unmanned aerial vehicle (UAV) transportation.