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.     

Dynamic preventive maintenance scheduling of the modules of fighter aircraft based on random effects regression model

Proper maintenance of fighter aircraft is an important issue to control theairpower. Typical maintenance policy applied is based on the constant schedulefor a given module. This kind of maintenance does not take into account varyingcharacteristics of the module over time. In this paper, we utilize the randomeffects Weibull regression model for non-constant MTBF (mean time betweenfailure) and MTTR (mean time to repair) in order to provide a dynamic preventivemaintenance schedule reflecting the module's varying characteristics in atimely manner. Our study is expected to contribute to ROKA (Republic of KoreaAirforce) in terms of improving the level of combat readiness of fighteraircraft.     

基于成本优先级的部件维修策略分析

现实中,系统由于任务、环境等因素,无法实时对故障部件进行维修。因此需要在任务间隔期间或对故障部件进行维修的同时对系统各部件进行预防性机会维修。本文考虑系统期望维修成本,提出了基于部件维修优先级的预防性维修策略。首先把系统期望维修成本分为失效部件维修成本、失效部件导致系统故障的成本和预防性维修其他部件的成本,提出了基于成本的二态和多态系统部件维修优先级度量方法,并在两种场景下分析了如何选择预防性维修部件。其次针对多态系统,研究了基于成本重要度的部件最佳维修水平,并讨论了成本约束下的部件预防性维修策略。最后以某型预警机系统为例进行验证,结果表明,基于成本的预防性维修策略不仅与故障部件位置和相关成本有关,而且还与可用于预防性维修的其他部件重要性有关。     

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.     

航空机务维修的优化管理

在航空机务维修工作中,科学的管理、人力资源的合理配置对及时完成维修任务,保障训练作战计划至关重要.从装备完好率和完成任务的及时性出发,分别建立了数学优化配置模型,并给出了这两种情况下效益(成本)矩阵的构造方法,进而将优化模型转化为最优线性指派问题来处理,从而为航空机务维修工作中人力资源的优化配置提供了一种科学、合理的决策方法.     

The Aircraft Maintenance Base Location Problem

Aviation authorities such as the Federal Aviation Administration (FAA) provide stringent guidelines for aircraft maintenance, with violations leading to significant penalties for airlines. Moreover, poorly maintained aircraft can lead to mass cancellation of flights, causing tremendous inconvenience to passengers and resulting in a significant erosion in brand image for the airline in question. Aircraft maintenance operations of a complex and extended nature can only be performed at designated maintenance bases. Aircraft maintenance planning literature has focused on developing good tail-number routing plans, while assuming that the locations of the maintenance bases themselves are fixed. This paper considers an inverse optimization problem, viz., locating a minimal number of maintenance bases on an Euler tour, while ensuring that all required aircraft maintenance activities can be performed with a stipulated periodicity. The Aircraft Maintenance Base Location Problem (AMBLP) is shown to be NP-complete and a new lower bound is developed for the problem. The performance of four simple “quick and dirty” heuristics for obtaining feasible solutions to AMBLP is analyzed.     

Heuristics for flight and maintenance planning of mission aircraft

Flight and Maintenance Planning (FMP) of mission aircraft addresses the question of which available aircraft to fly and for how long, and which grounded aircraft to perform maintenance operations on, in a group of aircraft that comprise a unit. The objective is to achieve maximum fleet availability of the unit over a given planning horizon, while also satisfying certain flight and maintenance requirements. The application of exact methodologies for the solution of the problem is quite limited, as a result of their excessive computational requirements. In this work, we prove several important properties of the FMP problem, and we use them to develop two heuristic procedures for solving large-scale FMP instances. The first heuristic is based on a graphical procedure which is currently used for generating flight and maintenance plans of mission aircraft by many Air Force organizations worldwide. The second heuristic is based on the idea of splitting the original problem into smaller sub-problems and solving each sub-problem separately. Both heuristics have been roughly sketched in earlier works that have appeared in the related literature. The present paper develops the theoretical background on which these heuristics are based, provides in detail the algorithmic steps required for their implementation, analyzes their worst-case computational complexity, presents computational results illustrating their computational performance on random problem instances, and evaluates the quality of the solutions that they produce. The size and parameter values of some of the randomly tested problem instances are quite realistic, making it possible to infer the performance of the heuristics on real world problem instances. Our computational results demonstrate that, under careful consideration, even large FMP instances can be handled quite effectively. The theoretical results and insights that we develop establish a fundamental background that can be very useful for future theoretical and practical developments related to the FMP problem.     

Risk aversion in maintenance: overmaintenance and the principal-agent problem

^** Email: r.d.baker{at}salford.ac.uk The concept of a risk-averse maintenance policy is introduced,and two approaches to modelling it are discussed, the firstbeing via utility functions, and the second via inflation ofthe costs of unscheduled failures. After introducing a generalmethodology, several examples of its application are given.Principal-agent theory is then applied to the case of a maintenanceengineer (the agent) who overmaintains equipment due to excessiverisk aversion. Incentives based on the total cost of maintenanceand failures can reduce overmaintenance, and it may be optimalfor management to pay such an incentive. The problem is illustratedwith an example of block maintenance. Suggestions for furtherwork in this field are made.     

Network flow-based approaches for integrated aircraft fleeting and routing

Given a schedule of flights to be flown, the aircraft fleeting and routing problem (AFRP) consists of determining a minimum-cost route assignment for each aircraft so as to cover each flight by exactly one aircraft while satisfying maintenance requirements and other activity constraints. We investigate network flow-based heuristic approaches for this problem. Computational experiments conducted on real-data given by TunisAir show that the proposed heuristic consistently yields very near-optimal solutions while requiring modest CPU effort.     

A mathematical model and algorithms for the aircraft hangar maintenance scheduling problem

An aircraft hangar maintenance scheduling problem is studied, motivated by the aircraft heavy maintenance conducted in a hangar operated by an independent maintenance service company. The aircraft hangar maintenance scheduling problem in such context consists of determining a maintenance schedule with minimum penalty costs in fulfilling maintenance requests, and a series of hangar parking plans aligned with the maintenance schedule through the planning period. A mixed-integer linear programming (MILP) mathematical model, integrating the interrelations between the maintenance schedule and aircraft parking layout plans, is presented at first. In the model, the variation of parking capacity of the maintenance hangar and the blocking of the aircraft rolling in and out path are considered. Secondly, the model is enhanced by narrowing down the domain of the time-related decision variables to the possible rolling in and out operations time of each maintenance request. Thirdly, to obtain good quality feasible solutions for large scale instances, a rolling horizon approach incorporating the enhanced mathematical model is presented. The results of computational experiments are reported, showing: (i) the effectiveness of the event-based discrete time MILP model and (ii) the scalability of the rolling horizon approach that is able to provide good feasible solutions for large size instances covering a long planning period.     

MULTIPLE JEEPS PROBLEM WITH CONTAINER RESTRICTION

Jeep problem is a kind of model of logistics in extreme situation, which has application in exploration and aircraft problems. The optimal distance and driving strategy of multiple jeeps problem are known. We consider multiple jeeps problem with container restriction, which is more complicated in the proof of feasibility and optimality of a driving strategy. We investigate when it can achieve the same optimal distance as without restriction.Based on the non-restricted optimal distance, a new driving strategy is proposed. We provide the necessary and sufficient condition to ensure the feasibility of the strategy, and obtain the maximal feasible distance.     

Robust optimization for relief logistics planning under uncertainties in demand and transportation time

Emergency logistics is an essential component of post-disaster relief campaigns. However, there are always various uncertainties when making decisions related to planning and implementing post-disaster relief logistics. Considering the particular environmental conditions during post-disaster relief after a catastrophic earthquake in a mountainous area, this paper proposes a stochastic model for post-disaster relief logistics to guide the tactical design for mobilizing relief supply levels, planning initial helicopter deployments, and creating transportation plans within the disaster region, given the uncertainties in demand and transportation time. We then introduce a robust optimization approach to cope with these uncertainties and deduce the robust counterpart of the proposed stochastic model. A numerical example based on disaster logistics during the Great Sichuan Earthquake demonstrates that the model can help post-disaster managers to determine the initial deployments of emergency resources. Sensitivity analyses explore the trade-off between optimization and robustness by varying the robust optimization parameter values.     

基于演化博弈的低碳物流政府监管策略研究

政府制定适合的政策是实现低碳物流的必要手段.构建了物流企业、政府和消费者三方演化博弈模型,分析了稳定策略及满足条件,运用MATLAB进行仿真分析,并在此基础上构建混合回归模型进行仿真和实证分析.研究表明:1)物流企业策略的选择与政府研发力度、建设力度和惩罚力度均有关系.2)政府的研发和惩罚力度主要影响物流企业是否低碳;...     

A heuristic approach for an integrated fleet-assignment,aircraft-routing and crew-pairing problem

This paper deals with the fleet-assignment, aircraft-routing and crew-pairing problems of an airline flying between Canary Islands. There are two major airports (bases). The company is subdivided in three operators. There are no flight during the night. A crew route leaves from and returns to the same base. An aircraft route starts from one base and arrive to the other base due to maintenance requirements. Therefore some crews must change aircrafts, which is an undesired operation. This paper presents a mathematical formulation based on a binary variable for each potential crew and aircraft route, and describes a column-generation algorithm for obtaining heuristic solutions. Computational results on real-world instances are given and compared to manual solutions by the airline.     

模糊决策在航空维修工程中的应用

本文以模糊数学和规划论为工具，对航空维修工程中一类决策问题的决策方法进行了探讨，给出了具有普遍意义的建模思想，通过实例分析，证明了这种方法的可行性和先进性。     

Unbiased ensemble square root filters

Ensemble square root filters are a method of data assimilation, where model forecasts are combined with observations to produce an improved state estimate, or analysis. There are a number of different algorithms in the literature and it is not clear which of these is the best for any given application. This work shows that in some implementations there can be a systematic bias in the analysis ensemble mean and consequently an accompanying shortfall in the spread of the analysis ensemble as expressed by the ensemble covariance matrix. We have established a set of necessary and sufficient conditions for the scheme to be unbiased. While these conditions are not a cure-all and cannot deal with independent sources of bias such as model and observation errors, they should be useful to designers of ensemble square root filters in the future. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Simple Stochastic Model of Air–Naval Combat

Consideration is given to a scenario where a fleet of ships, each armed with the same anti-aircraft weapon, is attacked by identical aircraft in line-ahead formation. It is assumed that each aircraft uses its weapon against one ship, but all ships use their weapons against each aircraft as it attacks in turn. A difference equation for the bivariate probability distribution of ship and aircraft casualties is obtained, and some analytic results are derived by decomposition of the problem. Using data from the sinking of the HMS Prince of Wales and HMS Repulse in World War II to estimate parameter values, a numerical solution of the difference equation is provided. A separate method for computing the ultimate or terminal form of the distribution is given.     

Canadian forces global reach support hubs: facility location and aircraft routing models

The Canadian Forces (CF) is seeking to establish permanent and temporary operational support hubs at strategic locations around the globe to improve its logistics support effectiveness and responsiveness for deployed operations. This paper addresses two logistics problems associated with the hub-based support concept, namely, hub location optimization and aircraft routing problems. A discrete facility location model was developed to analyse the hub-based support effectiveness and to determine the optimal hub locations. An aircraft routing model was also developed to determine optimal aircraft routes for the movement of cargo and supplies from various support hubs to a theatre of operation. Both models were formulated using mixed integer nonlinear programming. Historical CF deployment and sustainment data were used to conduct the analysis and to illustrate the methodology. The study indicates that the hub-based support approach would offer potential cost avoidance on sustainment lift and could be an effective strategy for improvement of the CF's support capability. It also indicates that potential lift costs could be avoided through optimal routing of sustainment flights.     

Maintenance of an unreliable M/G/1 queue-like job shop

This paper considers the maintenance of an unreliable M/G/1 queue-like job shop, integrating the maintenance process and the resulting queue operating characteristics. The system may breakdown, leading to unscheduled maintenance. Otherwise, preventive maintenance is done whenn jobs have been processed — whichever comes first. Using arguments from renewal theory, basic results regarding the queue-maintenance policy are established. Both an analytical and numerical example are studied in detail.     

Strategic planning in fractional aircraft ownership programs

In the fractional ownership model, the partial owner of an aircraft is entitled to certain flight hours per year, and the management company is responsible for all the operational considerations of the aircraft and for making an aircraft available to the owner at the requested time and place. In the recent years although the industry as a whole has experienced significant growth, most of the major fractional jet management companies have been unprofitable. To increase profitability a management company must minimize its operating costs and increase its crew and aircraft utilization. In this paper, we present a methodology for efficiently scheduling the available resources of a fractional jet management company that takes into consideration the details in real world situations. We then discuss several strategic planning issues, including aircraft maintenance, crew swapping, demand increase and differentiation, and analyze their effects on the resource utilization and profitability.