Periodic airline fleet assignment with time windows,spacing constraints,and time dependent revenues

Given the sets of flights and aircraft of an airline carrier, the fleet assignment problem consists of assigning the most profitable aircraft type to each flight. In this paper we propose a model for the periodic fleet assignment problem with time windows in which departure times are also determined. Anticipated profits depend on the schedule and the selection of aircraft types. In addition, short spacings between consecutive flights which serve the same origin–destination pair of airports are penalized. We propose a non-linear integer multi-commodity network flow formulation. We develop new branch-and-bound strategies which are embedded in our branch-and-price solution strategy. Finally, we present computational results for periodic daily schedules on three real-world data sets.     

Multifleet routing and multistop flight scheduling for schedule perturbation

Efficient and effective incidental scheduling techniques for schedule perturbation are essential to an airline carrier's operations. This research aims at developing a framework to assist carriers in fleet routing and flight scheduling for schedule perturbations in the operations of multifleet and multistop flights. The framework is based on a basic multifleet schedule perturbation model constructed as a timespace network from which strategic models are developed to research incidental scheduling. These network models are formulated as multiple commodity network flow problems. Lagrangian relaxation with subgradient methods accompanied by the network simplex method, a Lagrangian heuristic and a modified subgradient method are developed to solve the problems. A case study regarding the international operations of a major Taiwan airline carrier is presented.     

航空公司中的飞行员配置研究

随着新航线的开辟和新飞机的投入使用,航空公司的任务量急剧增长,飞行员需求的估计和机组的合理配置变得日益重要。本文基于实际工作需求,提出一类用于评估飞行员数量,并进行机组均衡配置的整数规划模型,为航空公司进行飞行员的数量评估和任务分配提供决策支持。本文在以下两个方面做出改进:1)加入国际长途航线,研究国内短途航线和国际长途航线混合搭配情况下飞行员的配置问题;2)鉴于大型整数规划求解的复杂性,通过评估航空公司所需要的飞行员数量的下界,为决策人员制定中长期规划提供依据。本文通过启发式算法进行飞行员的配置,计算结果接近理论问题的下界,证明了算法的有效性。     

Operational aircraft maintenance routing problem with remaining time consideration

The aircraft maintenance routing problem is one of the most studied problems in the airline industry. Most of the studies focus on finding a unique rotation that will be repeated by each aircraft in the fleet with a certain lag. In practice, using a single rotation for the entire fleet is not applicable due to stochasticity and operational considerations in the airline industry. In this study, our aim is to develop a fast responsive methodology which provides maintenance feasible routes for each aircraft in the fleet over a weekly planning horizon with the objective of maximizing utilization of the total remaining flying time of fleet. For this purpose, we formulate an integer linear programming (ILP) model by modifying the connection network representation. The proposed model is solved by using branch-and-bound under different priority settings for variables to branch on. A heuristic method based on compressed annealing is applied to the same problem and a comparison of exact and heuristic methods are provided. The model and the heuristic method are extended to incorporate maintenance capacity constraints. Additionally, a rolling horizon based procedure is proposed to update the existing routes when some of the maintenance decisions are already fixed.     

基于BP神经网络的航空公司机队可靠性评价模型

机队作为航空公司运输能力的关键,其安全性与可靠性直接影响到航空公司的经济效益.根据航空公司机队可靠性统计和数据采集方式以及实际应用情况,建立了航空公司机队可靠性评价指标体系.鉴于机队可靠性受多种复杂因素影响及各指标体系非线性等特点,结合人工神经网络基本原理和特性,提出了BP神经网络机队可靠性评价模型.最后应用该模型对航空公司机队可靠性进行了实例分析,得出了评价等级.结果表明,基于BP神经网络机队可靠性评价模型是可行的,该方法能够实现动态的评价,对提高航空公司机队可靠性评价技术水平具有现实的意义.     

A model for designing the meteorologically most reliable airline schedule

Due to meteorological conditions certain airports in some regions have to be frequently closed during winter months. An immediate consequence is an increase in the number of cancelled flights, which is a disruption of airline schedules on the overall transportation network. In this paper a research concerning the reliability of airline scheduling as related to meteorological conditions is conducted and an indicator for quantifying the adaptability of airline schedules to meteorological conditions is proposed. A heuristic algorithm for minimizing the number of needed aircraft for given traffic volume is also presented. In case where more than one solution with the same number of engaged aircraft is possible the solution chosen is the one with the minimum number of passengers whose flights are expected to be cancelled on account of meteorological conditions. The proposed algorithm is illustrated by an appropriate numerical example.     

Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem

Airline crew scheduling problem is a complex and difficult problem faced by all airline companies.To tackle this problem, it was often decomposed into two subproblems solved successively. First, the airline crew-pairing problem, which consists on finding a set of trips – called pairings – i.e. sequences of flights, starting and ending at a crew base, that cover all the flights planned for a given period of time. Secondly, the airline crew rostering problem, which consists on assigning the pairings found by solving the first subproblem, to the named airline crew members. For both problems, several rules and regulations must be respected and costs minimized.It is sure that this decomposition provides a convenient tool to handle the numerous and complex restrictions, but it lacks, however, of a global treatment of the problem. For this purpose, in this study we took the challenge of proposing a new way to solve both subproblems simultaneously. The proposed approach is based on a hybrid genetic algorithm. In fact, three heuristics are developed here to tackle the restriction rules within the GA’s process.     

Solving a manpower scheduling problem for airline catering using metaheuristics

We study a manpower scheduling problem with job time windows and job-skills compatibility constraints. This problem is motivated by airline catering operations, whereby airline meals and other supplies are delivered to aircrafts on the tarmac just before the flights take-off. Jobs (flights) must be serviced within a given time-window by a team consisting of a driver and loader. Each driver/loader has the skills to service some, but not all, of the airline/aircraft/configuration of the jobs. Given the jobs to be serviced and the roster of workers for each shift, the problem is to form teams and assign teams and start-times for the jobs, so as to service as many flights as possible. Only teams with the appropriate skills can be assigned to a flight. Workload balance among the teams is also a consideration. We present model formulations and investigate a tabu search heuristic and a simulated annealing heuristic approach to solve the problem. Computational experiments show that the tabu search approach outperforms the simulated annealing approach, and is capable of finding good solutions.     

A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture

The airline’s ability to offer flight schedules that provide service to passengers at desired times in competitive markets, while matching demand with an aircraft fleet of suitable size and composition, can significantly impact its profits. In this spirit, optional flight legs can be considered to construct a profitable schedule by optimally selecting among such alternatives in concert with assigning the available aircraft fleet to all the scheduled legs. Examining itinerary-based demands as well as multiple fare-classes can effectively capture network effects and realistic demand patterns. In addition, allowing flexibility on the departure times of scheduled flight legs can increase connection opportunities for passengers, hence yielding robust schedules while saving fleet assignment costs within the framework of an integrated model. Airlines can also capture an adequate market share by balancing flight schedules throughout the day, and recapture considerations can contribute to more realistic accepted demand realizations. We therefore propose in this paper a model that integrates the schedule design and fleet assignment processes while considering flexible flight times, schedule balance, and recapture issues, along with optional legs, path/itinerary-based demands, and multiple fare-classes. A polyhedral analysis is conducted to generate several classes of valid inequalities, which are used along with suitable separation routines to tighten the model representation. Solution approaches are designed by applying Benders decomposition method to the resulting tightened model, and computational results are presented using real data obtained from United Airlines to demonstrate the efficacy of the proposed procedures.     

Fleet assignment and routing with schedule synchronization constraints

This paper introduces a new type of constraints, related to schedule synchronization, in the problem formulation of aircraft fleet assignment and routing problems and it proposes an optimal solution approach. This approach is based on Dantzig–Wolfe decomposition/column generation. The resulting master problem consists of flight covering constraints, as in usual applications, and of schedule synchronization constraints. The corresponding subproblem is a shortest path problem with time windows and linear costs on the time variables and it is solved by an optimal dynamic programming algorithm. This column generation procedure is embedded into a branch and bound scheme to obtain integer solutions. A dedicated branching scheme was devised in this paper where the branching decisions are imposed on the time variables. Computational experiments were conducted using weekly fleet routing and scheduling problem data coming from an European airline. The test problems are solved to optimality. A detailed result analysis highlights the advantages of this approach: an extremely short subproblem solution time and, after several improvements, a very efficient master problem solution time.     

基于多目标规划的飞机路径恢复最优化算法研究

本文针对同一机场中同机型的多架飞机受到干扰后, 飞机路径恢复的多目标最优化问题进行研究。首先根据航空公司实际航班调整的常用原则和航班干扰管理的基本思想, 基于连接网络建立多目标规划模型, 其中两个目标按照优先级排列:第一个目标为最小化航班的最大延误时间, 第二个目标为最小化参与交换的飞机数量。然后根据该问题的航班波结构特点, 结合求解多目标规划的分层序列法, 分析优化问题的若干最优性质, 并基于快速排序算法和最小费用路算法设计出多项式算法。最后用算例验证了算法的有效性。该研究结果可以为航空公司减少航班延误提供理论和技术支持。     

A hybrid scatter search heuristic for personalized crew rostering in the airline industry

The crew scheduling problem in the airline industry is extensively investigated in the operations research literature since efficient crew employment can drastically reduce operational costs of airline companies. Given the flight schedule of an airline company, crew scheduling is the process of assigning all necessary crew members in such a way that the airline is able to operate all its flights and constructing a roster line for each employee minimizing the corresponding overall cost for personnel. In this paper, we present a scatter search algorithm for the airline crew rostering problem. The objective is to assign a personalized roster to each crew member minimizing the overall operational costs while ensuring the social quality of the schedule. We combine different complementary meta-heuristic crew scheduling combination and improvement principles. Detailed computational experiments in a real-life problem environment are presented investigating all characteristics of the procedure. Moreover, we compare the proposed scatter search algorithm with optimal solutions obtained by an exact branch-and-price procedure and a steepest descent variable neighbourhood search.     

Maximizing revenue in the airline industry under one-way pricing

The paper describes a methodology that has been implemented in a major British airline to find the optimal price to charge for airline tickets under one-way pricing. An analytical model has been developed to describe the buying behaviour of customers for flights over the selling period. Using this model and a standard analytical method for constrained optimization, we can find an expression for the optimal price structure for a flight. The expected number of bookings made on each day of the selling period and in each fare class given these prices can then be easily calculated. A simulation model is used to find the confidence ranges on the numbers of bookings and these ranges can be used to regulate the sale of tickets. A procedure to update the price structure based on the remaining capacity has also been developed.     

Solving Large Airline Crew Scheduling Problems: Random Pairing Generation and Strong Branching

The airline crew scheduling problem is the problem of assigning crew itineraries to flights. We develop a new approach for solving the problem that is based on enumerating hundreds of millions random pairings. The linear programming relaxation is solved first and then millions of columns with best reduced cost are selected for the integer program. The number of columns is further reduced by a linear programming based heuristic. Finally an integer solution is obtained with a commercial integer programming solver. The branching rule of the solver is enhanced with a combination of strong branching and a specialized branching rule. The algorithm produces solutions that are significantly better than ones found by current practice.     

基于乘客惰性行为的平行航班动态定价

在同一条航线上,航空公司提供起飞时间不同的多个航班,这样的航班称为平行航班。本文以同一航线上的多个平行航班为研究对象,在考虑乘客的惰性深度和惰性广度的基础上,利用动态规划方法,研究了乘客的惰性行为对各航班最优价格的影响。数值实验表明:乘客的惰性对各航班的最优价格起负面影响,即各航班的最优价格随乘客惰性深度的增加而减小,随乘客惰性广度的增加而减小。     

A branch-and-price approach for operational aircraft maintenance routing

In recent years, considerable effort in the field of operations research has been paid to optimizing airline operations, including the logistics of an airline’s fleet of aircraft. We focus on the problem of aircraft routing, which involves generating and selecting a particular route for each aircraft of a sub-fleet that is already assigned to a set of feasible sequences of flight legs. Similar studies typically focus on long-term route planning. However, stochastic events such as severe weather changes, equipment failures, variable maintenance times, or even new regulations mandated by the Federal Aviation Administration (FAA) play havoc on these long-term plans. In addition, these long-term plans ignore detailed maintenance requirements by considering only one or two of the primary maintenance checks that must be performed on a regular, long-term basis. As a result, these plans are often ignored by personnel in airline operations who are forced on a daily basis to develop quick, ad hoc methods to address these maintenance requirements and other irregular events. To address this problem, we develop an operational aircraft maintenance routing problem formulation that includes maintenance resource availability constraints. We propose a branch-and-price algorithm for solving this problem, which, due to the resource constraints, entails a modification of the branch-on, follow-on branching rule typically used for solving similar problems. Through computational testing, we explore the efficiency of this solution approach under a combination of heuristic choices for column (route) generation and selection.     

A heuristic approach based on shortest path problems for integrated flight,aircraft, and passenger rescheduling under disruptions

In this paper, we present a heuristic method to solve an airline disruption management problem arising from the ROADEF 2009 challenge. Disruptions perturb an initial flight plan such that some passengers cannot start or conclude their planned trip. The developed algorithm considers passengers and aircraft with the same priority by reassigning passengers and by creating a limited number of flights. The aim is to minimize the cost induced for the airline by the recovery from the disruptions. The algorithm is tested on real-life-based data, as well as on large-scale instances and ranks among the best methods proposed to the challenge in terms of quality, while being efficient in terms of computation time.     

An overview of the issues in the airline industry and the role of optimization models and algorithms

Optimization application has revolutionized the airline industry in all phases of the planning process. One of the current issues facing the airline industry is planning under uncertainty, especially in the context of schedule disruptions. We discuss the robust models and solution algorithms that have been proposed and developed to handle the uncertain parameters. We show that stochastic programming (SP) provides an ideal paradigm for capturing the uncertainties and making robust decisions. We develop and investigate a prototype fleet assignment model formulated as a two-stage SP with recourse.     

How Airlines and Airports Recover from Schedule Perturbations: A Survey

The explosive growth in air traffic as well as the widespread adoption of Operations Research techniques in airline scheduling has given rise to tight flight schedules at major airports. An undesirable consequence of this is that a minor incident such as a delay in the arrival of a small number of flights can result in a chain reaction of events involving several flights and airports, causing disruption throughout the system. This paper reviews recent literature in the area of recovery from schedule disruptions. First we review how disturbances at a given airport could be handled, including the effects of runways and fixes. Then we study the papers on recovery from airline schedule perturbations, which involve adjustments in flight schedules, aircraft, and crew. The mathematical programming techniques used in ground holding are covered in some detail. We conclude the review with suggestions on how singular perturbation theory could play a role in analyzing disruptions to such highly sensitive schedules as those in the civil aviation industry.     

Airline Crew Scheduling: State-of-the-Art

The airline industry is faced with some of the largest scheduling problems of any industry. The crew scheduling problem involves the optimal allocation of crews to flights. Over the last two decades the magnitude and complexity of crew scheduling problems have grown enormously and airlines are relying more on automated mathematical procedures as a practical necessity. In this paper we survey different approaches studied and discuss the state-of-the-art in solution methodology for the airline crew scheduling problem. We conclude with a discussion about promising areas for further work to make it possible to get very good solutions for the crew scheduling problem.