A two stage heuristic algorithm for the integrated aircraft and crew schedule recovery problems

Airline disruptions incurred huge cost for airlines and serious inconvenience for travelers. In this paper, we study the integrated aircraft and crew schedule recovery problem. A two stage heuristic algorithm for the integrated recovery problem is proposed. In the first stage, the integrated aircraft recovery and flight-rescheduling model with partial crew consideration is built. This model is based on the traditional multi-commodity network model for the aircraft schedule recovery problem. The objective of this model also includes minimization of the original crew connection disruption. In the second stage, the integrated crew schedule recovery and flight re-scheduling model with partial aircraft consideration is built. We proposed a new multi-commodity model for the crew schedule recovery. The main advantage of such model is that it is much more efficient to integrate the flight-scheduling and aircraft consideration. New constraints are incorporated to guarantee that the aircraft connections generated in the stage 1 are still feasible. Two stages are run iteratively until no improvement can be achieved. Experimental results show that our method can provide better recovery solutions compared with the benchmark algorithms.     

航班恢复问题的迭代局部搜索算法

在恶劣天气和机械故障等原因造成航班不能按照原计划执行时，航空公司需要采取相应的措施对航班进行恢复。本文基于经典的资源指派模型，综合考虑了调整时间、换机、联程拉直、取消航班和调机5种恢复策略，提出一种以最小化加权成本为优化目标的航班恢复模型，并设计一种迭代局部搜索算法。首先用构造-修复启发式方法构造可行解，然后从该初始解出发，在飞机路线对的邻域中进行局部搜索。当陷入局部最优后，对解进行扰动，然后从扰动后的解重新出发进行局部搜索。为了提高搜索效率，同时降低陷入局部最优解的概率，局部搜索过程采用模拟退火算法。实例结果表明，本文提出的模型及算法能够在短时间内对受到影响的大规模航班计划进行恢复。     

An exact solution approach for multi-objective location–transportation problem for disaster response

This paper considers a three-objective location–transportation problem for disaster response. The location problem aims at determining the number, the position and the mission of required humanitarian aid distribution centers (HADC) within the disaster region. The transportation problem deals with the distribution of aid from HADCs to demand points. Three conflicting objectives are considered. The first objective minimizes the total transportation duration of needed products from the distribution centers to the demand points. The second objective minimizes the number of agents (first-aiders) needed to open and operate the selected distribution centers. The third objective minimizes the non-covered demand for all demand points within the affected area. We propose an epsilon-constraint method for this problem and prove that it generates the exact Pareto front. The proposed algorithm can be applied to any three-objective optimization problem provided that the problem involves at least two integer and conflicting objectives. The results obtained in our experimental study show that the computing time required by the proposed method may be large for some instances. A heuristic version of our algorithm yielded, however, good approximation of the Pareto front in relatively short computing times.     

分布式整数规划及其在航线扰动问题的应用

在航空公司的运作中时常会出现干扰它正常运作的现象。在这种情况下,航空公司必须马上制定航线修复计划使受到干扰的航线尽快复原,以防止更大面积的航班取消和航班延误。提出一种基于递增映射迭代方法的分布式整数规划算法来解决由于机场关闭引起的航线扰动问题。整个问题分成了两个子问题：可行航线的生成和飞机的重指派。第一个子问题的问题空间被初始点分割方法分割成了若干片段。然后在一个分布式的计算网络中使用递增映射迭代方法在分得的每个片段上同时求解第一个子问题。得到的可行航线用来求解第二个子问题。最后的算例结果可以发现提出的方法要好于CPLEX和多目标基因算法。     

A novel trajectory planning strategy for aircraft emergency landing using Gauss pseudospectral method

To improve the survivability during an emergency situation, an algorithm for aircraft forced landing trajectory planning is proposed. The method integrates damaged aircraft modelling and trajectory planning into an optimal control framework, in order to deal with the complex aircraft flight dynamics, a solving strategy based on Gauss pseudospetral method （GPM） is presented. A 3-DOF nonlinear mass-point model taking into account the wind is developed to approximate the aircraft flight dynamics after loss of thrust. The solution minimizes the forced landing duration, with respect to the constraints that translate the changed dynamics, flight envelope limitation and operational safety requirements. The GPM is used to convert the trajectory planning problem to a nonlinear programming problem （NLP）, which is solved by sequential quadratic programming algorithm. Simulation results show that the proposed algorithm can generate the minimum-time forced landing trajectory in event of engine-out with high efficiency and precision.     

基于多目标模糊线性规划求解方法的飞机排班问题研究

提出了一种基于多目标模糊线性规划法解决飞机排班问题的新算法。该算法将模糊理论与最优化概念相结合,根据最大隶属度原则,将以飞机飞行时间均衡优先、飞机起降次数均衡优先、飞机等待时间最少优先为目标函数的多目标模糊线性规划数学模型转化为一般的线性规划问题进行求解。实验数据表明,该算法可行、有效,步骤简捷,计算量小,能得到理想的结果。     

Minimizing makespan in three-machine flow shops with deteriorating jobs

In this paper, a three-machine permutation flow shop scheduling problem with time-dependent processing times is considered. By the time-dependent processing times we mean that the job's processing time is an increasing function of its starting time. The objective is to find a sequence that minimizes the makespan. This problem is well known to be NP-hard. Several dominance properties and a lower bound are derived to speed up the elimination process of a branch-and-bound algorithm. Moreover, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational experiments on randomly generated problems are conducted to evaluate the branch-and-bound algorithm and heuristic algorithm. Computational results show that the proposed heuristic algorithm M-NEH perform effectively and efficiently.     

Improved 3D Interpolation-Based Path Planning for a Fixed-Wing Unmanned Aircraft

Path planning for unmanned aircraft has attracted a remarkable amount of interest from the research community. However, planning in large environments such as the civil airspace has not been addressed extensively. In this paper we apply a heuristic incremental interpolation-based search algorithm with efficient replanning capabilities to the path planning problem for a fixed-wing aircraft operating in a natural environment to plan and re-plan long flight paths. We modified the algorithm to account for the minimum turning radius and the limited flight path angles of a fixed-wing aircraft. Additionally, we present a method to consider a desired minimum cruising altitude and a post-processing algorithm to improve the path and remove unnecessary path points. These properties specific to aircraft operation could not be addressed with the original algorithm. Simulation results show that the planner produces intuitive, short paths and is capable of exploiting previous planning efforts, when unknown obstacles are encountered.     

Two-machine flow shop scheduling with linear decreasing job deterioration

In this paper, we consider a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job, we mean that the processing time is a decreasing function of its execution start time. A proportional linear decreasing deterioration function is assumed. The objective is to find a sequence that minimizes total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational results for randomly generated problem instances are presented, which show that the heuristic algorithm effectively and efficiently in obtaining near-optimal solutions.     

国际航线网络中K条最短路径算法改进与仿真

K条最短路径(KSP)问题是国际航线网络实际路径优化问题。通过对航线网络特征与K条最短路径算法的分析,研究了解决KSP问题的典型Yen算法。针对Yen算法求解候选路径占用大量运算时间的问题,提出一种改进Yen算法。改进Yen算法通过借助A*算法的启发式策略,减少了产生候选航线路径的时间,从而提高了算法的搜索效率并减小了算法搜索的规模。通过对国际航线网络实例的仿真,实验结果表明改进Yen算法能够快速求解国际航线网络中的KSP问题;同时,与Yen算法相比,运算效率提升了75.19%以上,能够为航线路径优化提供决策支持。     

求解一类并行多机调度问题的混合启发式算法

该文研究了一类工件具有不同释放时间的并行多机调度问题，调度目标为使总流程时间最小。针对该类调度问题具有强NP—hard的特点，首先构造了的一种启发式算法，该算法能够在很短的时间内找到次优解。由于通常启发式算法会随着问题规模的扩大导致求解的质量有所下降，结合遗传算法的全局搜索能力，提出了一种混合启发式算法进一步改善解的质量。仿真结果表明该算法很好地结合了启发式算法和遗传算法的特点，能够在较短的时间内求解较大规模的调度问题，算法的计算量小，鲁棒性好。     

Heuristic algorithms for assigning and scheduling flight missions in a military aviation unit

We consider an operations planning problem in a military aviation unit that performs a number of flight missions with multiple identical aircrafts. The problem is to assign the flight missions to the aircrafts and to schedule these assigned missions on each aircraft. Sequence-dependent setup times are required between the missions, and multiple aircrafts may be needed for a mission, but the aircrafts assigned to the same mission should start the mission simultaneously. We develop heuristic algorithms for the problem with the objective of minimizing makespan, i.e., the time by which all the missions have been completed. For evaluation of the performance of the algorithms, a series of computational tests was performed on a number of problem instances, and results show that the proposed algorithms give good or near optimal solutions in a reasonable amount of time.     

A model for a reliable single allocation hub network design under massive disruption

Hub facilities may fail to operate in networks because of accidental failures such as natural disasters. In this paper, a quadratic model was presented for a reliable single allocation hub network under massive random failure of hub facilities which more than one hub may be disrupted in a route. It determines the location of the hub facilities and the primal allocation of non-hub nodes. It also determines the backup allocation in case of failure of the primal hub. First, a new lexicographic form of a bi-objective quadratic model is presented where the first objective maximizes served demands or equivalently, minimizes lost flows and the second objective minimizes total cost under a to massive disruption in the network. Then, by adding a structure-based constraint, the model is transformed to a single objective one. A linearization technique reported in the literature is applied on the quadratic model to convert it into classic linear zero–one mixed integer model while enhancing it by finding tighter bounds. The tight bounds’ technique is compared with other techniques in terms of computational time and its better performance was approved in some problem instances. Finally, due to the NP-hardness of the problem, an iterated local search algorithm was developed to solve large sized instances in a reasonable computational time and the computational results confirm the efficiency of the proposed heuristic, ILS can solve all CAB and IAD data set instances in less than 15 and 24 seconds, respectively. Moreover, the proposed model was compared with the classical hub network using a network performance measure, and the results show the increased efficiency of the model.     

Robust planning of airport platform buses

Most airports have two types of gates: gates with an air bridge to the terminal and remote stands. For flights at a remote stand, passengers are transported to and from the aircraft by platform buses. In this paper we investigate the problem of planning platform buses as it appears at Amsterdam Airport Schiphol. We focus on robust planning, i.e. we want to avoid that the bus planning is affected by flight delays and in this way invokes delays in other flights and ground-handling processes. We present a column generation algorithm for planning of platform buses that maximizes robustness. We also present a discrete-event simulation model to compare our algorithm to a first-come-first-served heuristic as is used in current practice. Our computational results with real-life data indicate that our algorithm significantly reduces the number of replanning steps and special recovery measures during the day of operation.     

Group scheduling problem: Key to flexible manufacturing systems

We present an efficient heuristic algorithm for determining the sequence which minimizes the makespan of a group scheduling problem at the first level. The problem, therefore, focuses on scheduling of parts (jobs) in a part family. In the generation of partial schedules at each iteration, a job with a high mean total processing time is given a higher priority than others. An example problem, chosen from a real world application, is used to implement, the algorithmic steps. For this example, it has also been shown that the makespan determine by the proposed heuristic is smaller than that determined previously by two documented algorithms.     

Flight operations recovery: New approaches considering passenger recovery

The sources of disruption to airline schedules are many, including crew absences, mechanical failures, and bad weather. When these unexpected events occur, airlines recover by replanning their operations. In this paper, we present airline schedule recovery models and algorithms that simultaneously develop recovery plans for aircraft, crews, and passengers by determining which flight leg departures to postpone and which to cancel. The objective is to minimize jointly airline operating costs and estimated passenger delay and disruption costs. This objective works to balance these costs, potentially increasing customer retention and loyalty, and improving airline profitability. Using an Airline Operations Control simulator that we have developed, we simulate several days of operations, using passenger and flight information from a major US airline. We demonstrate that our decision models can be applied in a real-time decision-making environment, and that decisions from our models can potentially reduce passenger arrival delays noticeably, without increasing operating costs.     

Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance

This research focuses on the problem of scheduling jobs on a single machine that requires periodic maintenance with the objective of minimizing the number of tardy jobs. We present a two-phase heuristic algorithm in which an initial solution is obtained first with a method modified from Moore's algorithm for the problem without maintenance and then the solution is improved in the second phase. Performance of the proposed heuristic algorithm is evaluated through computational experiments on randomly generated problem instances and results show that the heuristic gives solutions close to those obtained from a commercial integer programming solver in much shorter time and works better than an existing heuristic algorithm in terms of the solution quality.     

汽车维修车间作业排序的优化模型及调度算法*

针对汽车维修车间调度缺乏科学规划,导致较长的客户等待时间和较低的设备利用率的问题,在结合优化调度理论的基础上, 对这一实际调度问题的特性、模型和算法进行了研究。首先从最小化目标、机器环境、加工特征和约束几方面分析了问题的特征,建立了对应的数学模型;然后根据问题特性设计了分解法与约束引导的启发式算法相结合的调度算法;最后以实例分析验证了算法的可行性。仿真结果表明了所用算法在优化目标函数值上的优越性。     

A reactive mitigation approach for managing supply disruption in a three-tier supply chain

In this paper, we develop a quantitative reactive mitigation approach for managing supply disruption for a supply chain. We consider a three-tier supply chain system with multiple raw material suppliers, a single manufacturer and multiple retailers, where the system may face sudden disruption in its raw material supply. First, we develop a mathematical model that generates a recovery plan after the occurrence of a single disruption. Here, the objective is to minimize the total cost during the recovery time window while being subject to supply, capacity, demand, and delivery constraints. We develop an efficient heuristic to solve the model for a single disruption. Second, we also consider multiple disruptions, where a new disruption may or may not affect the recovery plans of earlier disruptions. We also develop a new dynamic mathematical and heuristic approach that is capable of dealing with multiple disruptions, after the occurrence of each disruption as a series, on a real-time basis. We compare the heuristic solutions with those obtained by a standard search algorithm for a set of randomly generated disruption test problems, which shows the consistent performance of our heuristic. Finally, a simulation model is developed to analyze the effect of randomly generated disruption events that are not known in advance. The numerical results and many random experiments are presented to explain the usefulness of the developed models and methodologies.     

An adaptive genetic algorithm for demand-driven and resource-constrained project scheduling in aircraft assembly

Scheduling of aircraft assembling activities is proven as a non-deterministic polynomial-time hard problem; which is also known as a typical resource-constrained project scheduling problem (RCPSP). Not saying the scheduling of the complex assemblies of an aircraft, even for a simple product requiring a limited number of assembling operations, it is difficult or even infeasible to obtain the best solution for its RCPSP. To obtain a high quality solution in a short time frame, resource constraints are treated as the objective function of an RCPSP, and an adaptive genetic algorithm (GA) is proposed to solve demand-driven scheduling problems of aircraft assembly. In contrast to other GA-based heuristic algorithms, the proposed algorithm is innovative in sense that: (1) it executes a procedure with two crossovers and three mutations; (2) its fitness function is demand-driven. In the formulation of RCPSP for aircraft assembly, the optimizing criteria are the utilizations of working time, space, and operators. To validate the effectiveness of the proposed algorithm, two encoding approaches have been tested with the real data of demand.