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.     

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.     

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.     

Assigning arriving flights at an airport to the available gates

Unexpected changes in the flight schedules may disrupt the initial aircraft-gate assignments, and result in congestions and delays in getting aircraft onto gates. A mathematical model is developed to assign the flights with the minimum range of unutilised time periods of gates, subject to the level of service offered to passengers and other physical and managerial considerations. (The assignments are expected to be flexible enough to absorb the minor modifications in the flight schedules.) Interactive optimum and heuristic procedures, both utilising lower bounds on the ranges of future solutions, are proposed to cope with the major changes in disrupting the initial gate-assignments. Over randomly generated schedules, 74 flights can be optimally assigned to seven gates within 17 seconds when the gates are re-utilised within 30 minutes after each departure. The heuristic reaches the optimal solution after evaluating at most 20 partial solutions at one level. Over data obtained from Riyadh’s International Airport, the heuristic outperforms the existing practice: On average, 72.03% and 54.28% improvements are obtained on the number of remote served aircraft and towed aircraft, respectively.     

Static target search path planning optimization with heterogeneous agents

Disruptions in airline operations can result in infeasibilities in aircraft and passenger schedules. Airlines typically recover aircraft schedules and disruptions in passenger itineraries sequentially. However, passengers are severely affected by disruptions and recovery decisions. In this paper, we present a mathematical formulation for the integrated aircraft and passenger recovery problem that considers aircraft and passenger related costs simultaneously. Using the superimposition of aircraft and passenger itinerary networks, passengers are explicitly modeled in order to use realistic passenger related costs. In addition to the common routing recovery actions, we integrate several passenger recovery actions and cruise speed control in our solution approach. Cruise speed control is a very beneficial action for mitigating delays. On the other hand, it adds complexity to the problem due to the nonlinearity in fuel cost function. The problem is formulated as a mixed integer nonlinear programming (MINLP) model. We show that the problem can be reformulated as conic quadratic mixed integer programming (CQMIP) problem which can be solved with commercial optimization software such as IBM ILOG CPLEX. Our computational experiments have shown that we could handle several simultaneous disruptions optimally on a four-hub network of a major U.S. airline within less than a minute on the average. We conclude that proposed approach is able to find optimal tradeoff between operating and passenger-related costs in real time.     

Modeling and Solving an Airline Schedule Generation Problem

Since opening a new flight connection or closing an existing flight has a great impact on the revenues of an airline, the generation of the flight schedule is one of the fundamental problems in airline planning processes.In this paper we concentrate on a special case of the problem which arises at charter companies. In contrast to airlines operating on regular schedules, the market for charter airlines is well-known and the schedule is allowed to change completely from period to period. Thus, precise adjustments to the demands of the market have a great potential for minimizing operating costs.We present a capacitated network design model and propose a combined branch-and-cut approach to solve this airline schedule generation problem. To tighten the linear relaxation bound, we add cutting planes which adjust the number of aircraft and the spill of passengers to the demand on each itinerary.For real-world problems from a large European charter airline we obtain solutions within a very few percent of optimality with running times in the order of minutes on a customary personal computer for most of the data sets.     

Optimal dispatching strategy on an airline network after a schedule perturbation

It often happens that one or more aeroplanes from an airline fleet are taken out of operation for technical reasons and the airline has to operate on the existing network with a reduced number of planes. This paper presents the results of an effort to define a new ad hoc schedule for this situation, so that the total passenger delay on an airline network is minimized. A network is formed, in which nodes represent flights on a given airline network, and arcs are the total time losses on individual flights. The problem of determining a new routing and scheduling plan for the airline fleet is solved by branch and-bound methods. A numerical example illustrates the efficiency of the model.     

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

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

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.     

单架飞机受干扰后飞机路径恢复多项式算法研究

飞机路径恢复是航班调整中保证航班能够运行的必要条件之一,而传统目标下的飞机路径优化问题是NP-hard的。本文针对单架飞机受到干扰后,基于最小最大目标的同机型飞机路径最优化问题,给出了一个新的多项式时间算法。首先基于航空公司调整航班的常用原则,提出把最大航班延误时间最小化作为问题的目标。然后根据问题的一些特点和目标形式,设计出解构造算法,得到飞机路径恢复问题的最优解,并分析出算法的复杂度为O(n²)。相对于一般的最小最大二分图匹配算法(复杂度为O(n³log(n))),该算法具有较小的时间复杂度。最后用实例验证了解构造算法的有效性。该研究结果将为航空公司减少航班延误提供理论和方法支持。     

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.     

Scheduling charter aircraft

We present a system that is used for scheduling charter aircraft. At the core of the system is an elastic set partitioning model that is embedded in a decision support system. The model assigns a set of flights that have to be performed to the available fleets of aircraft at minimal cost while satisfying all operational requirements. Flights that cannot be accommodated by the available fleets are sold off to other operators. The minimised costs include the cost of flying the aircraft, the cost of selling off flights, and penalties on violations of soft constraints. The system has been in daily operation for almost a year, and it provides high quality schedules and saves numerous hours to the schedulers.     

面向靠桥率及道口冲突率的航班-机位指派问题优化模型及其启发式算法研究

在给定航班时刻表条件下,对于进出港航班的机位分配,除了必须满足航班、飞机和机位之间的技术性要求之外,还要考虑尽量提高整个机场的机位利用率,且方便旅客出入港及时、安全和便捷.文章以飞机机型、所属航空公司、客运/货运航班、国内/国际航班等匹配条件为约束条件,以航班-机位分配完成率、靠桥率、道口非冲突率为目标,建立了一个航班...     

A genetic local search algorithm with a threshold accepting mechanism for solving the runway dependent aircraft landing problem

As the demand for air transportation continues to grow, some flights cannot land at their preferred landing times because the airport is near its runway capacity. Extra fuel consumption and air pollution are then caused by the landing delays. Moreover, such delays may possibly yield extra costs for both passengers and airline companies that result from rescheduling transfer passengers and crew members. Consequently, how to increase the handling efficiency of congested airports is a crucial management issue. Building new runways at existing airports is often not feasible due to environmental, financial and geographical constraints. Therefore, devising a method for tackling the aircraft landing problem (ALP) in order to optimize the usage of existing runways at airports is the focus of this paper. This paper aims to develop a solution procedure based on a genetic local search (GLS) algorithm for solving the ALP with runway dependent attributes. A set of numerical experiments were conducted to test the validity of the proposed algorithm based on five test instances created and investigated by previous studies. The numerical results showed that the proposed GLS algorithm can effectively and efficiently determine the runway allocation, sequence and landing time for arriving aircraft for the five test cases by minimizing total delays under the separation constraints in comparison with the outcomes yielded by previous studies.     

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.     

Solving a large-scale crew pairing problem

Airline companies seek to solve the problem of determining an assignment of crews to a pre-determined flight schedule with minimum total cost, called the Crew Pairing Problem (CPP). Most of the existing studies focus on the CPP of North American airlines, which widely differs from that of most European airline companies in terms of the objective function, the flight structure, and the planning horizon. In this study, we develop an optimization-driven heuristic algorithm that can efficiently handle large-scale instances of the CPP that must be solved on a monthly basis. We perform computational experiments using flight schedules of an European airline company to test the performance of the solution method. Our computational results demonstrate that our algorithm is able to provide high-quality solutions to monthly instances with up to 27?000 flight legs.     

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

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

机场任务指派问题的优化方案研究

本文研究了机场任务指派问题,该问题是指将具有特殊属性的任务指派给有限数量的班次。由于机场任务和班次属性的多样性,机场任务指派问题是一个复杂的组合优化问题,属于NP-完全问题。本文以任务完成产生的效益总和最大化为目标建立数学优化模型,提出有效不等式,应用CPLEX软件对实际数据进行求解,结果表明,CPLEX可以在较短时间内对一定规模的算例求得最优解。同时对影响目标函数的四个因素:任务数量、班次数量、班次工作时长和任务属性分别进行分析,通过实际算例测试对比,得出具有指导意义的结论,即根据机场特征分别调整四个因素不仅能够提高机场资源的有效利用率,而且能够提高机场的运行效率和服务水平。     

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.     

The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints

The tail assignment problem is a critical part of the airline planning process that assigns specific aircraft to sequences of flights, called lines-of-flight, to satisfy operational constraints. The aim of this paper is to develop an operationally flexible method, based upon the one-day routes business model, to compute tail assignments that satisfy short-range—within the next three days—aircraft maintenance requirements. While maintenance plans commonly span multiple days, the methods used to compute tail assignments for the given plans can be overly complex and provide little recourse in the event of schedule perturbations. The presented approach addresses operational uncertainty by using solutions from the one-day routes aircraft maintenance routing approach as input. The daily tail assignment problem is solved with an objective to satisfy maintenance requirements explicitly for the current day and implicitly for the subsequent two days. A computational study will be performed to assess the performance of exact and heuristic solution algorithms that modify the input lines-of-flight to reduce maintenance misalignments. The daily tail assignment problem and the developed algorithms are demonstrated to compute solutions that effectively satisfy maintenance requirements when evaluated using input data collected from three different airlines.