Disruption management in the airline industry—Concepts,models and methods

This paper provides a thorough review of the current state-of-the-art within airline disruption management of resources, including aircraft, crew, passenger and integrated recovery. An overview of model formulations of the aircraft and crew scheduling problems is presented in order to emphasize similarities between solution approaches applied to the planning and recovery problems. A brief overview of research within schedule robustness in airline scheduling is included in the review, since this proactive measure is a natural complement to disruption management.     

Flight operations recovery: New approaches considering passenger recovery

The sources of disruption to airline schedules are many, including crew absences, mechanical failures, and bad weather. When these unexpected events occur, airlines recover by replanning their operations. In this paper, we present airline schedule recovery models and algorithms that simultaneously develop recovery plans for aircraft, crews, and passengers by determining which flight leg departures to postpone and which to cancel. The objective is to minimize jointly airline operating costs and estimated passenger delay and disruption costs. This objective works to balance these costs, potentially increasing customer retention and loyalty, and improving airline profitability. Using an Airline Operations Control simulator that we have developed, we simulate several days of operations, using passenger and flight information from a major US airline. We demonstrate that our decision models can be applied in a real-time decision-making environment, and that decisions from our models can potentially reduce passenger arrival delays noticeably, without increasing operating costs.     

An integrated scenario-based approach for robust aircraft routing,crew pairing and re-timing

For reasons of tractability, the airline scheduling problem has traditionally been sequentially decomposed into various stages (e.g. schedule generation, fleet assignment, aircraft routing, and crew pairing), with the decisions from one stage imposed upon the decision-making process in subsequent stages. Whilst this approach greatly simplifies the solution process, it unfortunately fails to capture many dependencies between the various stages, most notably between those of aircraft routing and crew pairing, and how these dependencies affect the propagation of delays through the flight network. In Dunbar et al. (2012) [9] we introduced a new algorithm to accurately calculate and minimize the cost of propagated delay, in a framework that integrates aircraft routing and crew pairing. In this paper we extend the approach of Dunbar et al. (2012) [9] by proposing two new algorithms that achieve further improvements in delay propagation reduction via the incorporation of stochastic delay information. We additionally propose a heuristic, used in conjunction with these two approaches, capable of re-timing an incumbent aircraft and crew schedule to further minimize the cost of delay propagation. These algorithms provide promising results when applied to a real-world airline network and motivate our final integrated aircraft routing, crew pairing and re-timing approach which provides a substantially significant reduction in delay propagation.     

Integrated aircraft-path assignment and robust schedule design with cruise speed control

Assignment of aircraft types, each having different seat capacity, operational expenses and availabilities, critically affects airlines’ overall cost. In this paper, we assign fleet types to paths by considering not only flight timing and passenger demand, as commonly done in the literature, but also operational expenses, such as fuel burn and carbon emission costs associated with adjusting the cruise speed to ensure the passenger connections. In response to flight time uncertainty due to the airport congestions, we allow minor adjustments on the flight departure times in addition to cruise speed control, thereby satisfying the passenger connections at a desired service level. We model the uncertainty in flight duration via a random variable arising in chance constraints to ensure the passenger connections. Nonlinear fuel and carbon emission cost functions, chance constraints and binary aircraft assignment decisions make the problem significantly more difficult. To handle them, we use mixed-integer second order cone programming. We compare the performance of a schedule generated by the proposed model to the published schedule for a major U.S. airline. On the average, there exists a 20% overall operational cost saving compared to the published schedule. To solve the large scale problems in a reasonable time, we also develop a two-stage algorithm, which decomposes the problem into planning stages such as aircraft-path assignment and robust schedule generation, and then solves them sequentially.     

An iterative approach to robust and integrated aircraft routing and crew scheduling

In airline scheduling a variety of planning and operational decision problems have to be solved. We consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights in a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved later. Also, when minimal cost solutions are used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day. We generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We solve the two original problems iteratively. Starting from a minimal cost solution, we produce a series of solutions which are increasingly robust. Using data from domestic airline schedules we evaluate the benefits of the approach as well as the trade-off between cost and robustness. We extend our approach considering the aircraft routing problem together with two crew pairing problems, one for technical crew and one for flight attendants.     

A two stage heuristic algorithm for the integrated aircraft and crew schedule recovery problems

Airline disruptions incurred huge cost for airlines and serious inconvenience for travelers. In this paper, we study the integrated aircraft and crew schedule recovery problem. A two stage heuristic algorithm for the integrated recovery problem is proposed. In the first stage, the integrated aircraft recovery and flight-rescheduling model with partial crew consideration is built. This model is based on the traditional multi-commodity network model for the aircraft schedule recovery problem. The objective of this model also includes minimization of the original crew connection disruption. In the second stage, the integrated crew schedule recovery and flight re-scheduling model with partial aircraft consideration is built. We proposed a new multi-commodity model for the crew schedule recovery. The main advantage of such model is that it is much more efficient to integrate the flight-scheduling and aircraft consideration. New constraints are incorporated to guarantee that the aircraft connections generated in the stage 1 are still feasible. Two stages are run iteratively until no improvement can be achieved. Experimental results show that our method can provide better recovery solutions compared with the benchmark algorithms.     

Aircraft maintenance,routing, and crew scheduling planning for airlines with a single fleet and a single maintenance and crew base

This work proposes an approach for solving the aircraft maintenance routing problem (AMRP) and the crew scheduling problem (CSP) in sequential and integrated fashions for airlines having a single fleet with a single maintenance and crew base, as is the case for most Latin American and many low-cost airlines. The problems were initially solved in the traditional sequential fashion. The AMRP was formulated to maximize revenue while satisfying fleet size. It was solved such that the final flight schedule was also determined. The CSP was solved by including a heuristic to obtain an efficient first feasible solution, and adapting a labeling algorithm to solve the pricing problems that arise in the column-generation technique. Finally, an integrated model was formulated and solved. Both approaches were tested on the real flight schedules of three important Latin American airlines. The solutions were coherent, independent of computational parameters, and obtained in short computational times in a standard PC (e.g. <1 h for up to 522 flights). Continuous relaxations gave very tight bounds (e.g. gaps < 0.8%). The integrated solutions offered small improvements over the sequential solutions (e.g. up to 0.6% or US$45,000 savings/year). However, these savings should increase drastically with fleet size and with the complexity of the flight schedule offered by the airline.     

An integrated aircraft routing,crew scheduling and flight retiming model

In the integrated aircraft routing, crew scheduling and flight retiming problem, a minimum-cost set of aircraft routes and crew pairings must be constructed while choosing a departure time for each flight leg within a given time window. Linking constraints ensure that the same schedule is chosen for both the aircraft routes and the crew pairings, and impose minimum connection times for crews that depend on aircraft connections and departure times. We propose a compact formulation of the problem and a Benders decomposition method with a dynamic constraint generation procedure to solve it. Computational experiments performed on test instances provided by two major airlines show that allowing some flexibility on the departure times within an integrated model yields significant cost savings while ensuring the feasibility of the resulting aircraft routes and crew pairings.     

A passenger demand model for airline flight scheduling and fleet routing

Fleet routing and flight scheduling are essential to a carrier's profitability, its level of service and its competitive capability in the market. This research develops a model and a solution algorithm to help carriers simultaneously solve for better fleet routes and appropriate timetables. The model is formulated as an integer multiple commodity network flow problem. An algorithm based on Lagrangian relaxation, a sub-gradient method, the network simplex method, the least cost flow augmenting algorithm and the flow decomposition algorithm is developed to efficiently solve the problem. The results of a case study, regarding a major Taiwan airline's operations, show the model's good performance.Scope and purposeFleet routing and flight scheduling issues have been widely studied to enhance airline's operation efficiency. Normally, network flow techniques are adopted for modeling and solving such complex mathematical problems. However, traditional approaches, which employ draft timetable as an essential medium, not only involve too much subjective judgement and decision making in the process but also reveal an incapability of directly and systematically managing the interrelation between supply and demand. The purpose of this paper is to develop a network model together with a solution algorithm, that can directly manage the interrelationships between passenger trip demands and flight supplies, in order to effectively assist carriers’ scheduling.     

飞机指派问题优化模型及算法研究

为了提高航空企业飞机排班计划的自动化水平,分析了航空企业飞机排班计划编制流程,将这个复杂组合优化问题分解为3个组合优化问题,重点研究了其中的飞机指派优化问题,归纳了要考虑的主要约束条件,以优化理论为基础,针对飞机排班计划优化问题中的关键问题—飞机指派问题建立了飞机指派优化模型,模型考虑了飞机与航班之间在机型、飞行区域、客流量等条件上的匹配要求,并给出了模型约束条件的编码方法,同时根据大量实际生产数据给出相应的惩罚系数表。为求解模型,构造了一种自适应单亲遗传算法,算法选用了适合模型的遗传算子,采用动态调整遗传算子操作概率的方式加快优化速度。采用航空公司的实际航班数据进行仿真实例研究结果表明,该模型和算法切实可行。     

Robust crew pairing for managing extra flights

This paper discusses a modeling approach to robust crew pairing when a set of extra flights is likely to be added to the regular flight schedule. The set of these possible extra flights is known at the planning stage. We demonstrate that these extra flights may be incorporated into the schedule if necessary by modifying the planned crew pairings appropriately and without delaying or canceling existing flights. To this end, we either identify a pair of crews whose schedules may be (partially) swapped while adding an extra flight into the schedule or show that an extra flight may be inserted into the schedule of a crew without affecting others. We note that deadheading may be necessary in either case. For these two types of solutions, we define the appropriate feasibility rules with respect to the common airline regulations. We then propose two robust mathematical programming models that consider incorporating such solutions into the set of selected pairings while keeping the increase in the crew cost at an acceptable level. The baseline solution for comparison is found by a conventional crew pairing model in the literature which ignores robustness at the planning stage and relies on recovery procedures at the time of operation. We also propose the variations of the two models, where the double counting of the possible solutions across extra flights is prevented. Finally, we conduct computational experiments on a set of data generated from the actual data of an airline company. We solve the crew pairing problem both with the proposed robust models and the conventional model. Our results demonstrate the benefits of the proposed modeling approach and indicate that the proposed robust models provide natural options to recovery without disrupting the existing flights at a relatively small incremental cost, which is visible at the planning stage.     

Agent-based airline scheduling

The development of an airline schedule can be defined as the art of developing system-wide flight patterns that deliver optimum service to the public in terms of quantity as well as quality. The development of the schedule is market driven with maintenance and crew requirements as constraints. This paper deals with an integrated agent-based approach for the airline scheduling problem. A bidding protocol is used to generate a market based schedule. FIFO and genetic algorithms are used to develop a crew schedule. An expert system combined with the Q-learning algorithm assist operational schedulers in resolving operational conflicts such as delays.     

Airline planning benchmark problems—Part I:: Characterising networks and demand using limited data

This paper is the first of two papers entitled “Airline Planning Benchmark Problems”, aimed at developing benchmark data that can be used to stimulate innovation in airline planning, in particular, in flight schedule design and fleet assignment. While optimisation has made an enormous contribution to airline planning in general, the area suffers from a lack of standardised data and benchmark problems. Current research typically tackles problems unique to a given carrier, with associated specification and data unavailable to the broader research community. This limits direct comparison of alternative approaches, and creates barriers of entry for the research community. Furthermore, flight schedule design has, to date, been under-represented in the optimisation literature, due in part to the difficulty of obtaining data that adequately reflects passenger choice, and hence schedule revenue. This is Part I of two papers taking first steps to address these issues. It does so by providing a framework and methodology for generating realistic airline demand data, controlled by scalable parameters. First, a characterisation of flight network topologies and network capacity distributions is deduced, based on the analysis of airline data. Then a multi-objective optimisation model is proposed to solve the inverse problem of inferring OD-pair demands from passenger loads on arcs. These two elements are combined to yield a methodology for generating realistic flight network topologies and OD-pair demand data, according to specified parameters. This methodology is used to produce 33 benchmark instances exhibiting a range of characteristics. Part II extends this work by partitioning the demand in each market (OD pair) into market segments, each with its own utility function and set of preferences for alternative airline products. The resulting demand data will better reflect recent empirical research on passenger preference, and is expected to facilitate passenger choice modelling in flight schedule optimisation.     

A novel column generation strategy for large scale airline crew pairing problems

A crew pairing is a sequence of flight legs beginning and ending at the same crew domicile. Crew pairing planning is the primary cost-determining phase in airline crew scheduling. Optimizing crew pairings of an airline timetable is an extremely important process which helps to minimize operational crew costs and to maximize crew utilization.There are various restrictions imposed by regulations or company policies that must be considered and satisfied in crew pairing generation process. Keeping these restrictions and regulations in mind, the main goal of the optimization is the generation of low cost sets of valid crew pairings which cover all flights in airline's timetable.For this research study, already existing works related to crew pairing optimization are examined and a new column generation strategy, a pricing network design and a pairing elimination heuristic are developed as a contribution to the previous studies. In the proposed strategy, the main problem is modeled and solved as a set-covering problem and the pricing sub problem is modeled as a shortest-path problem which is efficiently solved over a duty-flight overnight connection graph by the combined usage of heuristic and exact algorithms. The proposed strategy has been tested with real world data obtained from Turkish Airlines and it is seen that it is capable of generating very competitive solutions compared to current practices in Turkish Airlines. It is also observed that there are various advantages of proposed solution approach such as sensitivity to penalty coefficients, generating less deadheads, very close solution times with a single threaded software and light weight hardware.     

Solving shortest path problems with a weight constraint and replenishment arcs

This paper tackles a generalization of the weight constrained shortest path problem (WCSPP) in a directed network with replenishment arcs that reset the accumulated weight along the path to zero. Such situations arise, for example, in airline crew pairing applications, where the weight represents duty hours, and replenishment arcs represent crew overnight rests; and also in aircraft routing, where the weight represents time elapsed, or flight time, and replenishment arcs represent maintenance events. In this paper, we review the weight constrained shortest path problem with replenishment (WCSPP-R), develop preprocessing methods, extend existing WCSPP algorithms, and present new algorithms that exploit the inter-replenishment path structure. We present the results of computational experiments investigating the benefits of preprocessing and comparing several variants of each algorithm, on both randomly generated data, and data derived from airline crew scheduling applications.     

航班延误树的构造与波及分析

由于一架飞机在一天中要执行多个航班,各航班之间存在前后衔接关系,因此,一个航班的延误会波及到下游许多其它航班。重点研究飞机和机组资源对于航班延误与波及的影响,给出延误树的生成过程,通过初始航班延误的触发,动态建立以该航班为根结点的航班延误树,并根据统计结果给出相关量值。实例分析了初始航班延误发生的时刻、持续时间与波及的程度,以期辅助优化飞机与机组排班,减少航班延误。     

Intelligent planning and the design of a new risk-based,intelligent flight plan

A safe flight starts with effective performance of the pre-flight flight planning and briefing task. However, several problems related to the execution of this task can be identified. Potentially, the introduction of an improved flight plan provides an opportunity to improve the quality and availability of information provided to Flight Crew, thereby enhancing the quality of crew briefings. The proposed risk-based, intelligent flight plan is designed from the perspective of the current operational concept (e.g. fixed routes and ATC managerial role for separation), and associated airline Flight Planning and Dispatch functions. In this case, the focus is sharing information across specific airline stakeholders (e.g. Flight Operations Management and Safety functions) and Maintenance, to support a safe and efficient flight operation. Overall, the introduction of this new flight plan will result in the definition of new operational and organisational processes, along with a new way of performing the pre-flight, planning and briefing task. It is anticipated that this will impact positively on the operational and safety outcome of the flight.     

民用飞机多级健康状态评估技术研究

保障飞机安全高效地运行,不断提高飞机派遣可靠度是每一家航空公司需担负的责任和不懈追求的目标;民用飞机多级健康状态评估技术将充分利用各类工程数据、技术数据和可靠性分析数据,建立飞机技术派遣量化评估方法,甄选影响飞机技术派遣的主要参数,并通过对各参数进行权重分配,建立综合量化分析模型,针对专机、VIP及其他特殊航线运行要求,精准高效地为飞机的技术派遣提供决策依据,保证特殊运行航班的安全性以及签派可靠度;在航空公司机队的实际应用中表明,基于飞机多级健康状态的评估系统能够有效地提高机队的派遣可靠度和日利用率,具有重要的工程应用价值。     

An integer programming approach to support the US Air Force's air mobility network

The United States Air Force's air mobility command is responsible for creating a schedule and executing that schedule for a large-scale air mobility network that encompasses aircraft with prioritized missions. Aerial ports (airports) can process or park a maximum number of aircraft, called the maximum on ground (MOG). As the schedule changes due to disruptions, such as equipment failure or weather, the MOG constraint can cause the new schedule to be infeasible. Traditionally, re-planning the channel route schedule to adhere to MOG constraints has been a manual process that usually stops after the first feasible set of changes is found, due to the challenges of large amounts of data and urgency for a re-plan. We extend Bertsimas and Stock's integer program formulation for the commercial airline Multi-Airport Ground-Holding Problem to the air mobility network. Our integer programming formulation recommends delays to certain aircraft on the ground to minimize the effects of system-wide disruptions while taking account mission priorities of the aircraft.