A math-heuristic algorithm for the integrated air service recovery

A sophisticated flight schedule might be easily disrupted due to adverse weather, aircraft mechanical failures, crew absences, etc. Airlines incur huge costs stemming from such flight schedule disruptions in addition to the serious inconveniences experienced by passengers. Therefore, an efficient recovery solution that simultaneously decreases an airline's recovery cost while simultaneously mitigating passenger dissatisfaction is of great importance to the airline industry. In this paper, we study the integrated airline service recovery problem in which the aircraft and passenger schedule recovery problems are simultaneously addressed, with the objective of minimizing aircraft recovery and operating costs, passenger itinerary delay cost, and passenger itinerary cancellation cost.Recognizing the inherent difficulty in modeling the integrated airline service recovery problem within a single formulation (due to its huge solution space and quick response requirement), we propose a three-stage sequential math-heuristic framework to efficiently solve this problem, wherein the flight schedules and aircraft rotations are recovered in the first stage, Then, a flight rescheduling problem and passenger schedule recovery problems are iteratively solved in the next two stages. Time-space network flow representations, along with mixed-integer programming formulations, and algorithms that take advantages of the underlying problem structures, are proposed for each of three stages. This algorithm was tested on realistic data provided by the ROADEF 2009 challenge and the computational results reveal that our algorithm generated the best solution in nearly 72% of the test instances, and a near-optimal solution was achieved in the remaining instances within an acceptable timeframe. Furthermore, we also ran additional computational runs to explore the underlying characteristics of the proposed algorithm, and the recorded insights can serve as a useful guide during practical implementations of this algorithm.     

A model and optimization-based heuristic for the operational aircraft maintenance routing problem

This paper investigates the Operational Aircraft Maintenance Routing Problem (OAMRP). Given a set of flights for a specific homogeneous fleet type, this short-term planning problem requires building feasible aircraft routes that cover each flight exactly once and that satisfy maintenance requirements. Basically, these requirements enforce an aircraft to undergo a planned maintenance at a specified station before accumulating a maximum number of flying hours. This stage is significant to airline companies as it directly impacts the fleet availability, safety, and profitability. The contribution of this paper is twofold. First, we elucidate the complexity status of the OAMRP and we propose an exact mixed-integer programming model that includes a polynomial number of variables and constraints. Furthermore, we propose a graph reduction procedure and valid inequalities that aim at improving the model solvability. Second, we propose a very large-scale neighborhood search algorithm along with a procedure for computing tight lower bounds. We present the results of extensive computational experiments that were carried out on real-world flight networks and attest to the efficacy of the proposed exact and heuristic approaches. In particular, we provide evidence that the exact model delivers optimal solutions for instances with up to 354 flights and 8 aircraft, and that the heuristic approach consistently delivers high-quality solutions while requiring short CPU times.     

Heuristic approach to the airline schedule disturbances problem

Abstract

When disturbances make it impossible to realise the planned flight schedule, the dispatcher at the airline operational centre defines a new flight schedule based on airline policy, in order to reduce the negative effects of these perturbations. Depending on airline policy, when designing the new flight schedule, the dispatcher delays or cancels some flights and reassigns some flights to available aircraft. In this paper, a decision support system (DSS) for solving the airline schedule disturbances problem is developed aiming to assist decision makers in handling disturbances in real-time. The system is based on a heuristic algorithm, which generates a list of different feasible schedules ordered according to the value of an objective function. The dispatcher can thus select and implement one of them. In this paper, the possibilities of DSS are illustrated by real numerical examples that concern JAT Airways' flight schedule disturbances.     

Flight schedule punctuality control and management: a stochastic approach

The insufficiency of infrastructure capacity in an air transport system is usually blamed for poor punctuality performance when implementing flight schedules. However, investigations have revealed that ground operations of airlines have become the second major cause of flight delay at airports. A stochastic approach is used in this paper to model the operation of aircraft turnaround and the departure punctuality of a turnaround aircraft at an airport. The aircraft turnaround model is then used to investigate the punctuality problem of turnaround aircraft. Model results reveal that the departure punctuality of a turnaround aircraft is influenced by the length of scheduled turnaround time, the arrival punctuality of inbound aircraft as well as the operational efficiency of aircraft ground services. The aircraft turnaround model proposed is then employed to evaluate the endogenous schedule punctuality of two turnaround aircraft. Model results, when compared with observation data, show that the operational efficiency of aircraft ground services varies among turnarounds. Hence, it is recommended that the improvement of departure punctuality of turnaround aircraft may be achieved from two approaches: airline scheduling control and the management of operational efficiency of aircraft ground services.     

Evaluation and implications of environmental charges on commercial flights

Environmental charges are one of the economic instruments for controlling externalities. Their application to commercial flights has become a preferred method of encouraging the sustainable development of the air transport industry. Two kinds of externalities, aircraft noise and engine emissions, both generating profound impacts on human beings and on the environment, are considered here. The hedonic price method is applied to calculate the social cost of aircraft noise during the landing and take-off stages of the flight. The marginal impact of each flight with specific aircraft/engine combinations is derived for the allocation of aggregate noise social costs. In contrast, the dose - response method is applied to estimate the social cost of each engine exhaust pollutant during different flight modes. The combination of aircraft noise and engine emissions social costs is then evaluated on the basis of several environmental charge mechanism scenarios, using Amsterdam Airport Schiphol as a case study. It is shown that the current noise or engine emissions related charges at airports are lower than the actual social costs of their respective externalities. The implications of charge mechanism scenarios are subsequently discussed and evaluated in terms of their impacts on airline costs, airfares and passenger demand.     

An optimization model for a real-time flight scheduling problem

Although airlines plan aircraft routes and crew schedules in advance, perturbations occur everyday. As a result, flight schedules may become infeasible and would need to be updated. This Day of Operations Scheduling problem impacts the entire system of an airline as the decisions enforced are final. When perturbations are relatively small, the airline may be able to at least preserve the planned aircraft and crew itineraries. We propose a model that determines new flight schedules based on planned crew transfers, rest periods, passenger connections, and maintenance. Its dual is shown to be a network model, hence solvable in a real-time environment. In addition, it can be used in more sophisticated operational and planning systems.     

The airline perturbation problem: considering disrupted passengers

Abstract

When airlines are faced with some unforeseen short-term events, they have to reconstruct their flight schedules. Although aircraft recovery decisions affect passengers, these disrupted passengers and recovering them have not been explicitly considered in most previous aircraft recovery models. This paper presents an assignment model for airline schedule recovery which recovers both aircraft and disrupted passengers simultaneously, using a rolling horizon time framework. Our model examines possible flight retiming, aircraft swapping, over-flying, ferrying, utilization of reserve aircraft, cancellation and passenger reassignment to generate an efficient schedule recovery plan. The model ensures that the schedule returns to normal within a certain time and the objective is to minimize operational recovery aircraft cost, cancellation and delay cost as well as disrupted passenger cost. The model is tested using a data-set with two disruption scenarios. The computational results show that it is capable of handling the integrated aircraft and passenger recovery problem successfully.     

A multiobjective model for maximizing fleet availability under the presence of flight and maintenance requirements

Every aircraft, military or civilian, must be grounded for maintenance after it has completed a certain number of flight hours since its last maintenance check. In this paper, we address the problem of deciding which available aircraft should fly and for how long, and which grounded aircraft should perform maintenance operations, in a group of aircraft that comprise a combat unit. The objective is to achieve maximum availability of the unit over the planning horizon. We develop a multiobjective optimization model for this problem, and we illustrate its application and solution on a real life instance drawn from the Hellenic Air Force. We also propose two heuristic approaches for solving large scale instances of the problem. We conclude with a discussion that gives insight into the behavior of the model and of the heuristics, based on the analysis of the results obtained.     

The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery

Once limited to the military domain, unmanned aerial vehicles are now poised to gain widespread adoption in the commercial sector. One such application is to deploy these aircraft, also known as drones, for last-mile delivery in logistics operations. While significant research efforts are underway to improve the technology required to enable delivery by drone, less attention has been focused on the operational challenges associated with leveraging this technology. This paper provides two mathematical programming models aimed at optimal routing and scheduling of unmanned aircraft, and delivery trucks, in this new paradigm of parcel delivery. In particular, a unique variant of the classical vehicle routing problem is introduced, motivated by a scenario in which an unmanned aerial vehicle works in collaboration with a traditional delivery truck to distribute parcels. We present mixed integer linear programming formulations for two delivery-by-drone problems, along with two simple, yet effective, heuristic solution approaches to solve problems of practical size. Solutions to these problems will facilitate the adoption of unmanned aircraft for last-mile delivery. Such a delivery system is expected to provide faster receipt of customer orders at less cost to the distributor and with reduced environmental impacts. A numerical analysis demonstrates the effectiveness of the heuristics and investigates the tradeoffs between using drones with faster flight speeds versus longer endurance.     

A heuristic model for frequency planning and aircraft routing in small size airlines

The flight schedule of an airline is the primary factor in finding the most effective and efficient deployment of the airline's resources. The flight schedule process aims at finding a set of routes with associated aircraft type, frequency of service and times of departures and arrivals in order to satisfy a specific objective such as profit maximization. In this paper, we develop a two‐phase heuristic model for airline frequency planning and aircraft routing for small size airlines. The first phase develops a frequency plan using an economic equilibrium model between passenger demand for flying a particular route and aircraft operating characteristics. The second phase uses a time‐of‐day model to develop an assignment algorithm for aircraft routing.     

A hybrid optimization-simulation approach for robust weekly aircraft routing and retiming

We address the robust weekly aircraft routing and retiming problem, which requires determining weekly schedules for a heterogeneous fleet that maximizes the aircraft on-time performance, minimizes the total delay, and minimizes the number of delayed passengers. The fleet is required to serve a set of flights having known departure time windows while satisfying maintenance constraints. All flights are subject to random delays that may propagate through the network. We propose to solve this problem using a hybrid optimization-simulation approach based on a novel mixed-integer nonlinear programming model for the robust weekly aircraft maintenance routing problem. For this model, we provide an equivalent mixed-integer linear programming formulation that can be solved using a commercial solver. Furthermore, we describe a Monte-Carlo-based procedure for sequentially adjusting the flight departure times. We perform an extensive computational study using instances obtained from a major international airline, having up to 3387 flights and 164 aircraft, which demonstrates the efficacy of the proposed approach. Using the simulation software SimAir to assess the robustness of the solutions produced by our approach in comparison with that for the original solutions implemented by the airline, we found that on-time performance was improved by 9.8–16.0%, cumulative delay was reduced by 25.4–33.1%, and the number of delayed passengers was reduced by 8.2–51.6%.     

Effective aircraft maintenance schedule adjustment following incidents

In the real world, planned aircraft maintenance schedules are often affected by incidents. Airlines may thus need to adjust their aircraft maintenance schedules following the incidents that occur during routine operations. In tradition, such aircraft maintenance schedule adjustment has been performed manually, a process which is neither effective nor efficient, especially when the problem scale is large. In this study, an aircraft maintenance schedule adjustment model is developed, with the objective of minimizing the total system cost, subject to the related operating constraints. The model is formulated as a zero-one integer program and is solved using a mathematical programing solver. The effectiveness of the model is evaluated by application to a case study using data from an aircraft maintenance center in Taiwan. The test results show the proposed model, as well as the scheduling rules abstracted from the results are useful for the decision maker to adjust good maintenance schedules.     

Assessment of carbon emission costs for air cargo transportation

This study presents a set of models that calculate carbon emissions in individual phases of flight during air cargo transportation, investigates resultant carbon footprints by aircraft type and flight route, and estimates increases in transportation costs for airlines due to carbon taxes imposed by the EU ETS. The estimated results provide useful references for airlines in aircraft assignment on different routes and in aircraft selection for new purchases. Validation of the model is conducted by simulating the potential impact of the implementation of the EU ETS on costs of air cargo transportation for six routes and six types of aircraft. Results show that the impact may be subject to various factors including unit carbon emissions per aircraft, aviation emission allowances per airline, and carbon trading prices; and that increases in costs of air cargo transportation range from 0% to 5.27% per aircraft per route. Therefore, the implementation of the EU ETS may encourage airlines to cut down their operating costs by reducing their carbon emissions, thereby ameliorating greenhouse gas pollution caused by air cargo transportation.     

航班快速恢复建模与仿真研究

随着民用航空的发展与竞争,航班延误不仅影响航空飞行的安全与正常,更与航空公司的运营效率、运营成本及乘客利益息息相关。针对某一恶劣天气影响,对某公司受影响航班进行重新调配,考虑到航班的备降、盘旋等待、延误、取消等多种状态,以总成本最小为目标函数,建立航班快速恢复模型,通过MATLAB运用遗传算法设计航班恢复算法进行求解,得出最经济的航班恢复方案。     

Future electricity demand from battery‐powered vehicles

An important decision faced by airline schedulers is how to adapt the flight schedule and aircraft assignment to unforeseen perturbations in an established schedule. In the face of unforeseen aircraft delays, schedulers have to decide which flights to delay, and when delays become excessive, which to cancel. Current scheduling models deal with simple decision problems of delay or cancellation, but not with both simultaneously. But in practice the optimal decision may involve results from the integration of both flight cancellations and delays. In Part I of this paper, a quadratic programming model for the integration decision problem is given. The model can formulate the integration of flight cancellations and delays as well as some special cases, such as the ferrying of surplus aircraft and the possibility of swapping different types of aircraft. In this paper, based on the special structure of the model, an effective algorithm is presented, sufficient computational experiments are conducted and some results are reported. These show that we can expect to obtain a sufficiently good solution in terms of reasonable CPU time.     

Coordinated scheduling models for allied airlines

Recently, as a means of forming global networks and improving operation efficiency, major air carriers have increasingly entered into alliances with other carriers. Fleet routing and flight scheduling are not only important in individual airline operations, but also affect the alliances. The setting of a good flight schedule can not only enhance allied airline operating performance, but can also be a useful reference for alliance decision-making. In this research, we develop several coordinated scheduling models, which will help the allied airlines solve for the most satisfactory fleet routes and timetables under the alliance. We employ network flow techniques to construct the models. The models are formulated as multiple commodity network flow problems which can be solved using a mathematical programming solver. Finally, to evaluate the models, we perform a case study based on real operating data from two Taiwan airlines. The preliminary results are good, showing that the models could be useful for airline alliances.     

Integrated airline planning: Robust update of scheduling and fleet balancing under demand uncertainty

The airline schedule planning problem is defined as the sequence of decisions that need to be made to obtain a fully operational flight schedule. Historically, the airline scheduling problem has been sequentially solved. However, there have already been many attempts in order to obtain airline schedules in an integrated way. But due to tractability issues it is nowadays impossible to determine a fully operative and optimal schedule with an integrated model which accounts for all the key airline related aspects such as competitive effects, stochastic demand figures and uncertain operating conditions. Airlines usually develop base schedules, which are obtained much time in advance to the day of operations and not accounting for all the related uncertainty. This paper proposes a mathematical model in order to update base schedules in terms of timetable and fleet assignments while considering stochastic demand figures and uncertain operating conditions, and where robust itineraries are introduced in order to ameliorate miss-connected passengers. The proposed model leads to a large-scale problem which is difficult to be solved. Therefore, a novel improved and accelerated Benders decomposition approach is proposed. The analytical work is supported with case studies involving the Spanish legacy airline, IBERIA. The presented approach shows that the number of miss-connected passengers may be reduced when robust planning is applied.     

Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem

In this paper, we study two closely related airline planning problems: the robust weekly aircraft maintenance routing problem (RWAMRP) and the tail assignment problem (TAP). In real life operations, the RWAMRP solution is used in tactical planning whereas the TAP solution is implemented in operational planning. The main objective of these two problems is to minimize the total expected propagated delay (EPD) of the aircraft routes. To formulate the RWAMRP, we propose a novel weekly line-of-flights (LOF) network model that can handle complex and nonlinear cost functions of EPD. Because the number of LOFs grows exponentially with the number of flights to be scheduled, we propose a two-stage column generation approach to efficiently solve large-scale real-life RWAMRPs. Because the EPD of an LOF is highly nonlinear and can be very time-consuming to accurately compute, we propose three lower bounds on the EPD to solve the pricing subproblem of the column generation. Our approach is tested on eight real-life test instances. The computational results show that the proposed approach provides very tight LP relaxation (within 0.6% of optimal solutions) and solves the test case with more than 6000 flights per week in less than three hours. We also investigate the solutions obtained by our approach over 500 simulated realizations. The simulation results demonstrate that, in all eight test instances, our solutions result in less EPDs than those obtained from traditional methods. We then extend our model and solution approach to solve realistically simulated TAP instances.     

The impact of strategic management and fleet planning on airline efficiency - A random effects Tobit model based on DEA efficiency scores

As a result of the liberalisation of airline markets; the strong growth of low cost carriers; the high volatility in fuel prices; and the recent global financial crisis, the cost pressure that airlines face is very substantial. In order to survive in these very competitive environments, information on what factors impact on costs and efficiency of airlines is crucial in guiding strategic change. To evaluate key determinants of 58 passenger airlines’ efficiency, this paper applies a two-stage Data Envelopment Analysis (DEA) approach, with partially bootstrapped random effects Tobit regressions in the second stage. Our results suggest that the effects of route optimisation, in the sense of average stage length of the fleet, are limited to airline technical efficiency. We show that airline size and key fleet mix characteristics, such as aircraft size and number of different aircraft families in the fleet, are more relevant to successful cost management of airlines since they have significant impacts on all three types of airline efficiency: technical, allocative and, ultimately, cost efficiency. Our results also show that despite the fuel saving benefits of younger aircraft, the age of an airline’s fleet has no significant impact on its technical efficiency, but does have a positive impact on its allocative and cost efficiency.     

Disruption Management of an Inequality-Based Multi-Fleet Airline Schedule by a Multi-Objective Genetic Algorithm

Abstract

This paper presents a novel application of a Method of Inequality-based Multi-objective Genetic Algorithm (MMGA) to generate an efficient time-effective multi-fleet aircraft routing algorithm in response to the schedule disruption of short-haul flights. It attempts to optimize objective functions involving ground turn-around times, flight connections, flight swaps, total flight delay time and a 30-minute maximum delay time of original schedules. The MMGA approach, which combines a traditional Genetic Algorithm (GA) with a multi-objective optimization method, can address multiple objectives at the same time, then explore the optimal solution. The airline schedule disruption management problem is traditionally solved by Operations Research (OR) techniques that always require a precise mathematical model. However, airline operations involve too many factors that must be considered dynamically, making a precise mathematical model difficult to define. Experimental results based on a real airline flight schedule demonstrate that the proposed method, Multi-objective Optimization Airline Disruption Management by GA, can recover the perturbation efficiently within a very short time. Our results further demonstrate that the application can yield high quality solutions quickly and, consequently, has potential to be employed as a real-time decision support tool for practical complex airline operations.