A Proactive Crew Recovery Decision Support Tool for Commercial Airlines During Irregular Operations

In this paper, a decision support tool that automates crew recovery during irregular operations for large-scale commercial airlines is presented. The tool is designed for airlines that adopt the hub-spoke network stru cture. The advance of this tool over the existing ones is that it recovers projected crew problems that arise due to current system disruptions. In other words, it proactively recovers crew problems ahead of time before their occurrence. In addition, it gives a wide flexibility to react to different operation scenarios. Also, it solves for the most efficient crew recovery plan with the least deviation from the originally planned schedule. The tool adopts a rolling approach in which a sequence of optimization assignment problems is solved such that it recovers flights in chronological order of their departure times. In each assignment problem, the objective is to recover as many flights as possible while minimizing total system cost resulting from resource reassignments and flight delays. The output of this tool is in the form of new crew trippairs that cover flights in the considered horizon. A test case is presented to illustrate the model capabilities to solve a real-life problem for one of the major commercial airlines in the U.S.     

A multi-objective genetic algorithm for robust flight scheduling using simulation

Traditional methods of developing flight schedules generally do not take into consideration disruptions that may arise during actual operations. Potential irregularities in airline operations such as equipment failure are not adequately considered during the planning stage of a flight schedule. As such, flight schedules cannot be met as planned and their performance is compromised, which may eventually lead to huge losses in revenue for airlines. In this paper, we seek to improve the robustness of a flight schedule by re-timing its departure times. The problem is modeled as a multi-objective optimization problem, and a multi-objective genetic algorithm (MOGA) is developed to solve the problem. To evaluate flight schedules, SIMAIR 2.0, a simulation model which simulates airline operations under operational irregularities, has been employed. The simulation results indicate that we are able to develop schedules with better operation costs and on-time performance through the application of MOGA.     

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

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

A disruption recovery model for a single stage production-inventory system

This paper presents a newly developed disruption recovery model for a single stage production and inventory system, where the production is disrupted for a given period of time during the production up time. The model is categorized as a constrained non-linear optimization program which we have solved using an efficient heuristic developed in this paper. The model was also solved using an evolutionary algorithm and a comparison of the results from both methods was performed. The heuristic was able to accurately solve the model with significantly less time compared to the evolutionary algorithm. It can be shown that the optimal recovery schedule is dependent on the shortage cost parameters, as well as the extent of the disruption. The proposed model offers a potentially useful tool to help manufacturers decide on the optimal recovery plan in real time whenever the production system experiences a sudden disruption.     

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

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

An option-based revenue management procedure for strategic airline alliances

An airline has to decide whether to accept an incoming customer request for a seat in the airplane or to reject it in hope that another customer will request the seat later at a higher price. Capacity control, as one of the instruments of revenue management, gives a solution to this decision problem. In the presence of strategic alliances capacity control changes. For the case of two airlines in the alliance and a single flight leg we propose an option-based capacity control process. The determination of booking limits for capacity control is done with real options. A simulation model is introduced to evaluate the booking process of the partner airlines within the strategic alliance, considering the option-based procedure. In an iterative process the booking limits are improved with simulation-based optimization. The results of the option-based procedure will be compared with the results of the simulation-based optimization, the results of a first-come-first-served (FCFS) approach and ex post optimal solutions.     

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.     

Cost evaluation of airline maintenance investigation-triggering methods

A reliable investigation-triggering mechanism is critical for airlines in managing aircraft fleet reliability. This study developed a simulation model to evaluate the performance of various investigation-triggering mechanisms in various scenarios of aircraft fleet reliability. Factors that affect performance include flight delay costs, investigation costs, the costs of corrective actions, the accuracy of investigations, the effectiveness of corrective actions, and the monthly improvement rate. Nine investigation-triggering mechanisms were evaluated. The simulation results show that the monthly improvement rate significantly influences performance. The subject airline’s original investigation-triggering mechanism is not outstanding in most scenarios. This study recommends two of the nine investigation-triggering mechanisms for airlines when they select investigation-triggering mechanisms in various scenarios. Thus, useful guidance for adjusting airlines’ investigation-triggering mechanisms can be effectively provided.     

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

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

An airline scheduling model and solution algorithms under stochastic demands

When setting a good flight schedule airlines not only have to consider their fleet supply and related operations, as well as market share, but also stochastic variations caused by daily passenger demands in actual operations. Most of the past research on short-term flight scheduling has used the average passenger demand as input to produce the final timetable and schedule, which means that daily passenger variations that occur in actual operations are neglected. To consider such stochastic disturbances we developed a stochastic-demand scheduling model. We employed arc-based and route-based strategies to develop two heuristic algorithms that can be used to solve the model. The test results, based on a major Taiwan airline’s operation, show the good performance of the model and the solution algorithms.     

Logistics network design for product recovery in fuzzy environment

The design of product recovery network is one of the important and challenging problems in the field of reverse logistics. Some models have been formatted by researchers under deterministic environment. However, uncertainty is inherent during the process of the practical product recovery. In order to deal with uncertainty, this paper employs a fuzzy programming tool to design the product recovery network. Based on different criteria, three types of optimization models are proposed and some properties of them are investigated. To solve the proposed models, we design a hybrid intelligent algorithm which integrates fuzzy simulation and genetic algorithm. Finally, several numerical examples are presented to illustrate the effectiveness of the proposed models and algorithm.     

Simulation optimization for an emergency department healthcare unit in Kuwait

This paper integrates simulation with optimization to design a decision support tool for the operation of an emergency department unit at a governmental hospital in Kuwait. The hospital provides a set of services for different categories of patients. We present a methodology that uses system simulation combined with optimization to determine the optimal number of doctors, lab technicians and nurses required to maximize patient throughput and to reduce patient time in the system subject to budget restrictions. The major objective of this decision supporting tool is to evaluate the impact of various staffing levels on service efficiency. Experimental results show that by using current hospital resources, the optimization simulation model generates optimal staffing allocation that would allow 28% increase in patient throughput and an average of 40% reduction in patients’ waiting time.     

Modeling framework for optimal evacuation of large-scale crowded pedestrian facilities

The paper presents a simulation–optimization modeling framework for the evacuation of large-scale pedestrian facilities with multiple exit gates. The framework integrates a genetic algorithm (GA) and a microscopic pedestrian simulation–assignment model. The GA searches for the optimal evacuation plan, while the simulation model guides the search through evaluating the quality of the generated evacuation plans. Evacuees are assumed to receive evacuation instructions in terms of the optimal exit gates and evacuation start times. The framework is applied to develop an optimal evacuation plan for a hypothetical crowded exhibition hall. The obtained results show that the model converges to a superior optimal evacuation plan within an acceptable number of iterations. In addition, the obtained evacuation plan outperforms conventional plans that implement nearest-gate immediate evacuation strategies.     

集装箱码头泊位计划的鲁棒优化模型

针对集装箱码头作业中的不确定性因素,构建泊位计划的鲁棒优化模型与算法,目的是降低不确定性因素对集装箱码头作业系统的影响。首先,提出泊位计划鲁棒性度量指标,利用算例对各指标的效果进行分析。在此基础上,设计泊位计划鲁棒优化的两阶段优化算法。算法的第一阶段不考虑泊位计划的鲁棒性,以船舶总延误时间最小为目标;算法的第二阶段以所选择的鲁棒性指标最大为目标,以第一阶段获得的船舶总延误时间为约束条件,获得鲁棒调度方案。最后,研究作业资源(装卸桥数量)的变化对泊位计划鲁棒性的影响。算例分析表明,权重松弛量是有效的度量泊位计划鲁棒性的指标,两阶段算法可以有效解决泊位计划鲁棒优化问题。     

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.     

基于数字仿真的收益管理整合决策

对航空公司收益管理进行机票定价和座位存量分配的整合研究。应用计算机仿真算法动态构造民航收益管理系统中的需求预测模型,并根据航班收益最大化原则,确定价格与座位存量分配,根据需求变化实时调整价格和座位存量。仿真运算结果显示,该算法可以使航空公司不同航班收益比固定价格提高2%以上。     

IBM journey management library: an arena system for airport simulations

Airline passenger terminal congestion caused by increasing passenger traffic results in unsatisfactory levels of customer service. We discuss a simulation modelling tool to help airlines and airports to use advanced technology to improve service to passengers. The tool consists of custom designed, reusable modules that represent the most common airline and airport system data, logic and processes. A model of an actual airline operation based on this approach is described.     

多储备点多品种应急物资配送的多目标优化模型

应急救援的社会化、应急物资需求的多样性、应急物资需求和补给的时变性,对应急物流的配送调度提出了挑战.应急物流的紧急性要求最大程度保障受灾点的物资供应;在经济上则要求应急物流的成本最小化.通过将时间离散化为阶段序列,在应急物资需求和补给是可预测的情况下,建立一个多储备点、多物资品种、单受灾点的应急物资配送的多目标优化模型,来最小化应急物资短缺次数和运输成本.仿真实例表明,该模型可以通过优化引擎快速求解,能够发现导致短缺的应急物资品种和加强供应补给的时间区间.     

一种求解柔性资源约束前摄性项目调度问题的启发式算法

在不确定环境中,一个具有较高鲁棒性的进度计划可以保证项目的稳定实施。考虑到现实中资源可能具有多种技能,会对制定鲁棒性较高进度计划的过程产生影响,因此本文研究了柔性资源约束下前摄性项目调度优化问题。首先界定研究问题;然后从鲁棒性最大化的视角出发,构建了研究问题的优化模型,在对模型进行分析的基础上将其分解为经典鲁棒优化和资源技能分配两个子模型;随后设计了求解问题的基于削峰算法的启发式算法;最后用一个实际案例验证了算法有效性,并分析了关键参数对进度计划鲁棒性的影响,得到如下结论:项目进度计划鲁棒性随着项目工期的延长、资源可用量的增加或资源柔性的提高而增大。     

An integrated simulation-optimization framework for the operational planning of seaport container terminals

In this article the operational planning of seaport container terminals is considered by defining a suitable integrated framework in which simulation and optimization interact. The proposed tool is a simulation environment (implemented by using the Arena software) representing the dynamics of a container terminal. When the system faces some particular conditions (critical events), an optimization procedure integrated in the simulation tool is called. This means that the simulation is paused, an optimization problem is solved and the relative solution is an input for the simulation environment where some system parameters are modified (generally, the handling rates of some resources are changed). For this reason, in the present article we consider two modelling and planning levels about container terminals. The simulation framework, based on an appropriate discrete-event model, represents the dynamic behaviour of the terminal, thus it needs to be quite detailed and it is used as an operational planning tool. On the other hand, the optimization approach is devised in order to define some system parameters such as the resource handling rates; in this sense, it can be considered as a tool for tactical planning. The optimization procedure is based on an aggregate representation of the terminal where the dynamics is modelled by means of discrete-time equations.