一种修复多机型飞机运行计划的分布式整数规划方法

在航空公司各条航线的日常运行中时常会受到飞机故障或极端天气等各种干扰从而引起航班延误或取消等现象。为减少干扰给航空公司带来的损失,一种分布式整数规划方法被用来修复受干扰的飞机运行计划,从而使延误航班或取消航班的数量降到最低。首先建立一个基于TSP模型的可行性问题用来生成可行航线。之后在MPI搭建的一个多机分布式计算网络上使用递增映射迭代方法对此问题进行求解。最后将求解得到的可行航线指派给飞机从而得到飞机运行修复计划。通过算例结果比较可以看出此分布式整数规划方法要好于一些文献中同类型方法。     

基于分布式优化的协同干扰任务分配研究

为保证目标区域干扰覆盖和最小能量消耗的优化目标,建立协同干扰任务分配模型。在分布式协同优化框架下,将集中式任务分配问题,转换为各个虚任务区内小规模的分布式优化问题,采用分解-协调优化模式和启发式遗传算法相结合的方法,实现对各个子区域优化问题的二次迭代求解。仿真结果表明,分布式协同优化方法能够有效降低协同干扰任务分配问题的求解规模,避免“维数灾”,具有可行性。     

基于非归一化直方图的GrabCut图像分割算法改进

针对GrabCut算法在图像分割中存在迭代求解耗时长、分割结果欠分割的问题,提出了一种基于非归一化直方图改进的GrabCut算法。在保留GrabCut第一次分割结果的基础上,通过非归一化直方图计算像素点属于前景或背景的方法来代替高斯混合模型迭代学习的过程;在构图过程中引入一类新的节点Bin进行构图以提高分割精度。选取MSRA1000数据集中部分图片进行实验验证,结果表明该算法在分割效果和效率上都有明显的提升,在进行背景复杂图像的分割时改进算法优势更加明显。     

分布式奇异值分解最小平方估计算法

对奇异值（SVD）分解求解最小平方估计的问题进行了研究。提出迭代式分割与合并的算法（IDMSVD）,目的是改善奇异值分解在估计参数时非常耗费时间以及内存空间的问题。基于IDMSVD提出了分布式迭代式分割与合并算法（MRDSVD）,使用Hadoop平台的MapReduce来实现,实验结果显示,IDMSVD可以有效改善SVD求最小平方解耗费运行时间与内存空间的问题,MRDSVD算法可进一步改善IDMSVD的运行时间。     

半分布式forward-reflected-Douglas-Rachford分裂算法求解广义纳什平衡点

针对多个体参与的广义纳什平衡点的求解问题, 已有算法通常都是基于两算子分裂算法forward--backward splitting. 本文基于三算子分裂算法forward--reflected--Douglas--Rachford(FRDR) splitting, 提出一种半分布式的FRDR算法. 半分布式旨在强调对偶变量的信息交换总是按照分布式的方式进行. 该算法有如下特性: 可以实现邻点映射和投影映射分别计算; 不需要假设伪梯度映射是协强制的或者强单调的; 通过存储上一轮交换的信息, 可以做到所需信息在每一轮迭代中只进行一次交换. 同时, 论文给出了有关迭代残差的收敛速率, 并通过数值仿真验证了所提算法的有效性.     

求解CARP-RP-ML问题的改进算法

传统方法无法有效求解交通道路维护运作中的有补给点及多装载的容量约束弧路径(CARP-RP-ML)问题。为此,提出改进的启发式算法和遗传算法。启发式算法将不同的分割算法用于由所有需求弧随机排序得到的个体上,构造问题的可行解;遗传算法利用分割算法计算其个体适应值,确定对应的可行车辆路径及补给位置,并用局部搜索作为变异算子,进一步扩大搜索空间。数值实验结果表明,与启发式算法相比,遗传算法能更有效地求解CARP-RP-ML问题。     

航班计划优化模型及其应用研究

以利润最大化为目标函数，构造了航空公司航班计划优化模型。采用禁忌搜索算法对其进行求解，通过对航班数据的预处理和技巧，加快了算法的处理效率，对航空公司编制航班计划具有实际意义。以某航空公司特定机型的航班计划数据进行实证，验证了该模型和算法的可行性。     

基于可变优先级的航班时隙排序

空中交通拥塞日益严重．这不仅带来大量的经济损失．同时给飞行安全带来隐患。地面等待策略作为短期措施中缓解交通拥塞的有效方法．其核心是如何解决时隙分配问题。传统的时隙分配算法（RBS和Compression算法）采用的是“先排班先服务”的原则,且没有考虑到航空公司的公平性。针对RBS和Compression算法的局限性．采用一种新的优先级设定方法,在同时考虑航空公司公平性、不同类型航班延误损失的不同、同类型航班载客量不同以及同一航班等待时间不同的基础上对航班进行优先级设定。采用分支定界法求解最优解。使用该算法对北京首都机场某个时间段内航班进行仿真排序结果显示：该改进算法在一定程度上提高时隙分配的合理性。减少航空公司的总延误损失．同时尽可能公平的保证航空公司所服务对象的利益。     

使用新的码字分割方法的快速LBG算法

针对LBG算法中初始码书生成存在盲目性的问题,提出了一种基于训练向量集合分量之间的相关性进行码向量分割的方法。在迭代过程,记录每一个码向量所映射的训练向量子集;生成新的初始码书时,首先计算被分割码向量所映射的训练子集的第一个分量与其他各分量之间的协方差;根据协方差来分割相应的码向量。实验表明,应用新的码向量分割机制后,LBG算法中的迭代次数和运行时间减少了约10%左右。     

求解正则化最小二乘问题的一个非精确交替方向乘子法

正则化最小二乘问题广泛出现在图像处理、统计学等领域中,交替方向乘子法(ADMM)是求解这个问题的一种有效方法.ADMM在每一步迭代过程中,都需要求解两个子问题,子问题能否有效地求解对整个算法的有效性有重要影响.在有些情形,精确求解子问题是不可能的,或者是需要花费很大代价的.由于这个原因,非精确地求解子问题的一类算法得到了发展.而已有的非精确类ADMM算法,在迭代过程中需要不断提高子问题解的精度,从而子问题迭代步数也越来越多,这就影响了整个算法的效率.这篇文章提出了一个不精确ADMM算法,该算法的特点是在迭代过程中,子问题的迭代步数是确定的,这克服了之前算法的不足.文章中的数值例子也说明了提出的算法是有效的.     

An iterative approach to robust and integrated aircraft routing and crew scheduling

In airline scheduling a variety of planning and operational decision problems have to be solved. We consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights in a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved later. Also, when minimal cost solutions are used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day. We generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We solve the two original problems iteratively. Starting from a minimal cost solution, we produce a series of solutions which are increasingly robust. Using data from domestic airline schedules we evaluate the benefits of the approach as well as the trade-off between cost and robustness. We extend our approach considering the aircraft routing problem together with two crew pairing problems, one for technical crew and one for flight attendants.     

Airline planning benchmark problems—Part I:: Characterising networks and demand using limited data

This paper is the first of two papers entitled “Airline Planning Benchmark Problems”, aimed at developing benchmark data that can be used to stimulate innovation in airline planning, in particular, in flight schedule design and fleet assignment. While optimisation has made an enormous contribution to airline planning in general, the area suffers from a lack of standardised data and benchmark problems. Current research typically tackles problems unique to a given carrier, with associated specification and data unavailable to the broader research community. This limits direct comparison of alternative approaches, and creates barriers of entry for the research community. Furthermore, flight schedule design has, to date, been under-represented in the optimisation literature, due in part to the difficulty of obtaining data that adequately reflects passenger choice, and hence schedule revenue. This is Part I of two papers taking first steps to address these issues. It does so by providing a framework and methodology for generating realistic airline demand data, controlled by scalable parameters. First, a characterisation of flight network topologies and network capacity distributions is deduced, based on the analysis of airline data. Then a multi-objective optimisation model is proposed to solve the inverse problem of inferring OD-pair demands from passenger loads on arcs. These two elements are combined to yield a methodology for generating realistic flight network topologies and OD-pair demand data, according to specified parameters. This methodology is used to produce 33 benchmark instances exhibiting a range of characteristics. Part II extends this work by partitioning the demand in each market (OD pair) into market segments, each with its own utility function and set of preferences for alternative airline products. The resulting demand data will better reflect recent empirical research on passenger preference, and is expected to facilitate passenger choice modelling in flight schedule optimisation.     

Solving a robust airline crew pairing problem with column generation

In this study, we solve a robust version of the airline crew pairing problem. Our concept of robustness was partially shaped during our discussions with small local airlines in Turkey which may have to add a set of extra flights into their schedule at short notice during operation. Thus, robustness in this case is related to the ability of accommodating these extra flights at the time of operation by disrupting the original plans as minimally as possible. We focus on the crew pairing aspect of robustness and prescribe that the planned crew pairings incorporate a number of predefined recovery solutions for each potential extra flight. These solutions are implemented only if necessary for recovery purposes and involve either inserting an extra flight into an existing pairing or partially swapping the flights in two existing pairings in order to cover an extra flight. The resulting mathematical programming model follows the conventional set covering formulation of the airline crew pairing problem typically solved by column generation with an additional complication. The model includes constraints that depend on the columns due to the robustness consideration and grows not only column-wise but also row-wise as new columns are generated. To solve this difficult model, we propose a row and column generation approach. This approach requires a set of modifications to the multi-label shortest path problem for pricing out new columns (pairings) and various mechanisms to handle the simultaneous increase in the number of rows and columns in the restricted master problem during column generation. We conduct computational experiments on a set of real instances compiled from local airlines in Turkey.     

Aircraft maintenance,routing, and crew scheduling planning for airlines with a single fleet and a single maintenance and crew base

This work proposes an approach for solving the aircraft maintenance routing problem (AMRP) and the crew scheduling problem (CSP) in sequential and integrated fashions for airlines having a single fleet with a single maintenance and crew base, as is the case for most Latin American and many low-cost airlines. The problems were initially solved in the traditional sequential fashion. The AMRP was formulated to maximize revenue while satisfying fleet size. It was solved such that the final flight schedule was also determined. The CSP was solved by including a heuristic to obtain an efficient first feasible solution, and adapting a labeling algorithm to solve the pricing problems that arise in the column-generation technique. Finally, an integrated model was formulated and solved. Both approaches were tested on the real flight schedules of three important Latin American airlines. The solutions were coherent, independent of computational parameters, and obtained in short computational times in a standard PC (e.g. <1 h for up to 522 flights). Continuous relaxations gave very tight bounds (e.g. gaps < 0.8%). The integrated solutions offered small improvements over the sequential solutions (e.g. up to 0.6% or US$45,000 savings/year). However, these savings should increase drastically with fleet size and with the complexity of the flight schedule offered by the airline.     

Recoverable robust single day aircraft maintenance routing problem

Aircraft maintenance planning is of critical importance to the safe and efficient operations of an airline. It is common to solve the aircraft routing and maintenance planning problems many months in advance, with the solution spanning multiple days. An unfortunate consequence of this approach is the possible infeasibility of the maintenance plan due to frequent perturbations occurring in operations. There is an emerging concept that focuses on the generation of aircraft routes for a single day to ensure maintenance coverage that night, alleviating the effects of schedule perturbations from preceding days. In this paper, we present a novel approach to ensure that a sufficient number of aircraft routes are provided each day so maintenance critical aircraft receive maintenance that night. By penalising the under supply of routes terminating at maintenance stations from each overnight airport, we construct a single day routing to provide the best possible maintenance plan. This single day aircraft maintenance routing problem (SDAMRP) is further protected from disruptions by applying the recoverable robustness framework. To efficiently solve the recoverable robust SDAMRP acceleration techniques, such as identifying Pareto-optimal cuts and a trust region approach, have been applied. The SDAMRP is evaluated against a set of flight schedules and the results demonstrate a significantly improved aircraft maintenance plan. Further, the results demonstrate the magnitude of recoverability improvement that is achieved by employing recoverable robustness to the SDAMRP.     

双层规划模型在航空收益管理中的应用研究

论文目的是解决如何合理地安排机型分配及确定不同折扣舱位数量使得航空公司获得最大收益的问题,利用双层规划方法建立航空收益的双层规划模型,通过算例得到了较好的结果,验证了模型的正确性,得到了双层规划模型能够解决航空收益管理优化问题的结论。     

Agent-based airline scheduling

The development of an airline schedule can be defined as the art of developing system-wide flight patterns that deliver optimum service to the public in terms of quantity as well as quality. The development of the schedule is market driven with maintenance and crew requirements as constraints. This paper deals with an integrated agent-based approach for the airline scheduling problem. A bidding protocol is used to generate a market based schedule. FIFO and genetic algorithms are used to develop a crew schedule. An expert system combined with the Q-learning algorithm assist operational schedulers in resolving operational conflicts such as delays.     

Integrated aircraft-path assignment and robust schedule design with cruise speed control

Assignment of aircraft types, each having different seat capacity, operational expenses and availabilities, critically affects airlines’ overall cost. In this paper, we assign fleet types to paths by considering not only flight timing and passenger demand, as commonly done in the literature, but also operational expenses, such as fuel burn and carbon emission costs associated with adjusting the cruise speed to ensure the passenger connections. In response to flight time uncertainty due to the airport congestions, we allow minor adjustments on the flight departure times in addition to cruise speed control, thereby satisfying the passenger connections at a desired service level. We model the uncertainty in flight duration via a random variable arising in chance constraints to ensure the passenger connections. Nonlinear fuel and carbon emission cost functions, chance constraints and binary aircraft assignment decisions make the problem significantly more difficult. To handle them, we use mixed-integer second order cone programming. We compare the performance of a schedule generated by the proposed model to the published schedule for a major U.S. airline. On the average, there exists a 20% overall operational cost saving compared to the published schedule. To solve the large scale problems in a reasonable time, we also develop a two-stage algorithm, which decomposes the problem into planning stages such as aircraft-path assignment and robust schedule generation, and then solves them sequentially.     

An integrated aircraft routing,crew scheduling and flight retiming model

In the integrated aircraft routing, crew scheduling and flight retiming problem, a minimum-cost set of aircraft routes and crew pairings must be constructed while choosing a departure time for each flight leg within a given time window. Linking constraints ensure that the same schedule is chosen for both the aircraft routes and the crew pairings, and impose minimum connection times for crews that depend on aircraft connections and departure times. We propose a compact formulation of the problem and a Benders decomposition method with a dynamic constraint generation procedure to solve it. Computational experiments performed on test instances provided by two major airlines show that allowing some flexibility on the departure times within an integrated model yields significant cost savings while ensuring the feasibility of the resulting aircraft routes and crew pairings.     

Duty-period-based network model for crew rescheduling in European airlines

Airline rescheduling is a relatively new field in airline Operations Research but increasing amounts of traffic will make disturbances to the original schedule more frequent and more severe. Thus, the need to address the various problems arising from this situation with systematic, cost-efficient approaches is becoming more urgent. One such problem is crew rescheduling where after a disturbance in the crew schedule the aim is to determine new crew assignments that minimize the `impact’ on the original schedule. In this work we present a new duty-period-based formulation for the airline crew rescheduling problem that is tailored to the needs of European airlines. It uses a new type of resource constraints to efficiently cover the various labor regulations. A solution method based on branch-and-price is tested on various rescheduling scenarios, each with several distinct cases. Results show that the solution method is capable of providing solutions within the short period of time available to a rescheduler after a disturbance occurs.