基于蚁群协同算法的图权值停机位分配模型

停机位分配关系到整个机场系统的运行,是机场地面作业的核心部分。根据不同航班占用停机位的时间冲突约束,将航班之间的冲突关系表示成图的权值0-1,基于停机位、航班类型的匹配约束和得到的图的权值,运用蚁群协调算法,在保证不存在停机位分配冲突约束的前提下,以最少数量航班被分配到远停机位和旅客到停机位总行走时间最小为目标函数,对航班进行停机位分配。对枢纽机场进行停机位分配,并与遗传算法在停机位分配上的应用做比较,表明蚁群协调算法在停机位分配上的应用从运行时间和实验结果都明显好于遗传算法,验证了算法的合理性,这一算法可作为机场停机位分配的参考。     

航班滑行路径规划和停机位分配联合优化

针对机场的航班滑行路径规划和停机位分配的联合优化调度问题,构建基于冲突回避的滑行道与停机位联合调度模型,并提出改进的自适应差分进化算法求解问题。以最小化航班的滑行时间和旅客转机的行走时间为优化目标,建立非线性混合整数规划联合调度模型。设计考虑了滑行冲突的路径规划算法,完成航班的滑行路径分配,并通过自适应动态调整差分进化算法参数,引入个体位置边界的扰动策略,进一步改善了算法的搜索性能。对国内某枢纽机场的仿真结果表明,所提出的算法可以有效避免滑行冲突,缩短滑行时间,是能够兼顾旅客服务质量和航班场面滑行效率的有效方法。     

基于松弛算法的停机位分配优化方法

针对机场近机位资源紧缺及实际航班到离港时间偏离计划时间对停机位分配所造成的扰动，提出了在同机位相邻航班间加入缓冲时间的停机位分配调度方法。首先，建立了以机位空闲时间、远机位占用时间最小为目标的鲁棒性停机位分配模型；然后，设计了一种基于双目标的拉格朗日松弛优化算法，并使用次梯度算法求解拉格朗日松弛算法中的对偶问题。基于国内某枢纽机场运行数据的仿真结果表明，所提方法的优化方案和原始机位分配方案相比，机位使用量和机位空闲时间分别降低了15.79%、7.56%，机位占用率提高了18.72%，并且冲突率降低到3.57%，达到了有效提高停机位利用率与鲁棒性的目的。     

基于多目标优化禁忌搜索算法的停机位分配方法研究

针对机位资源分配不均给机场运行多方带来的公平性问题，提出多目标优化的停机位分配方法。建立以旅客通行距离、飞机滑行距离和远机位使用次数最小为多目标优化分配模型。分析航班属性设置分配优先级表。设计一种基于pareto最优的多目标优化禁忌搜索算法，使用pareto最优策略对解集进行筛选。在机场实际分配方案的基础上进行仿真实验,旅客通行距离和飞机滑行距离分别缩短18%和5%，机位资源的使用数量减少20%，航班靠桥率提高到93%，多目标优化禁忌搜索算法比遗传算法更优。     

基于免疫遗传算法的停机位动态再分配优化

针对兼顾旅客转机行走距离、航班场面滑行距离和停机位使用效率的多目标停机位分配的问题,以最小化航班停机位分配的扰动性为优化目标,建立停机位动态再分配混合整数规划模型.提出基于航班序列的自然数编码方案,设计改进的免疫遗传求解算法,保证个体在遗传操作中的可行性.将免疫算法中个体密度的概念引入对个体适应度值的评价过程,以保持种群的多样性,避免算法过早收敛.实例仿真结果表明,所提出的优化方法能够有效降低延误航班对停机位预分配计划造成的影响.     

面向场面滑行的机场关键资源蚁群调度模型*

每一架飞机场面滑行时间的长短和飞机总体滑行时间的均衡性反应了机场调度的合理性。跑道和停机位的分配直接决定了飞机的滑行时间。根据不同航班占用停机位的时间不同,将航班的停机位分配约束关系表示成图的权值0-1。充分考虑跑道容量等约束条件,对航班进行跑道初始化分配。基于停机位类型、航班类型、经计算得出的图的权值和跑道分配结果,运用蚁群算法,以最少数量的航班分配到远停机位和飞机总体滑行时间的均衡性为目标函数,对航班进行停机位分配。然后根据停机位分配结果,对跑道分配进行调整,反复迭代求出最优结果,并对枢纽机场进行调度仿真,验证了算法的合理性,可作为机场调度的参考。     

成本约束下多机场群航班频率优化模型仿真北大核心

采用目前方法对多机场群航班频率进行优化时,没有考虑旅客的出行成本,对航班频率优化后存在延误时间长、延误航班数量多、出行成本高和日利用率低的问题。提出考虑出行成本的多机场群航班频率优化模型构建方法,在构建航班频率优化模型之前,对旅客的出行方式进行博弈分析,在Stackelberg博弈模型的基础上构建双层博弈模型,上层模型实现社会效益最大化,下层模型实现旅客出行费用最小化,完成多机场群航班频率优化模型的构建,并采用遗传算法对多机场群航班频率优化模型求解,完成航班频率的优化。仿真结果表明,所提方法的延误时间短、延误航班数量少、出行成本低、日利用率低。     

基于遗传算法的动态飞机停机位分配模型研究

机场停机位作为机场保障服务工作中的重要设施,随着中国民航业逐步拓宽的规模,航班数量的不断增长给其分配带来巨大压力;迅速合理的机位分配方案可以最大化促进航班运行效率以及其它机场地面服务工作的开展;为了缓解机场停机位资源的紧张现象,同时解决飞机停机位到跑道出口或者入口的滑行时间最短,对到场飞机所使用的停机位最优化分配问题进行了研究,对飞机从跑道出口到停机位的最短路径进行了分析计算,采用了目前计算速度更快的遗传算法的关键技术,引入改进策略求解,对停机位最优分配进行迭代计算,不断计算出最合理的机位分配资源,根据机位分配问题的约束条件和主要优化目标分析,建立以机位空闲时间均匀化为目标的模型,经模型优化后,远机位使用空闲时间的平方差由156.89降低为75.69,近机位使用效率提高了12%～22%,实验验证满足了机场机位资源最优分配等工程应用。     

航班延误分布式检测与仿真

关于航班延误问题,已成为是困扰民航部门和广大旅客的热点,涉及多个环节和多种影响因素的航班延误状态检测是难点.针对某天某时刻航班实际运行发生的情况,将生物免疫系统机制与机场航班运行机制联系起来,为提高检测准确率,提出了一种分布式人工免疫模型的机场航班延误实时检测方法,采用分布式检测模型的特点,用各周次训练出来的检测器联合实时对下一时刻的机场离港航班延误状态进行检测,仿真结果表明方法不仅能够实时准确地检测机场离港航班状态,而且能够准确预测下一时间段累计延误航班数量,为航班延误预警提供决策支持.     

基于改进蚁群协同算法的枢纽机场场面滑行道优化调度模型

滑行道连接停机位和跑道,是机场场面调度的重要关键环节。基于飞机滑行时的冲突约束和跑道资源的动态分配,采用改进蚁群协同算法与滑动窗口控制相结合的方法,对滑行道进行优化调度。在保证滑行道零冲突、兼顾单个航班滑行时间的前提下,缩小机场进出港航班总滑行时间。对国内某枢纽机场的滑行道调度仿真实验表明,所提出的方法和模型具有明显的优势,可为枢纽机场的场面滑行调度提供决策支持。     

Study on an improved adaptive PSO algorithm for solving multi-objective gate assignment

Gate is a key resource in the airport, which can realize rapid and safe docking, ensure the effective connection between flights and improve the capacity and service efficiency of airport. The minimum walking distances of passengers, the minimum idle time variance of each gate, the minimum number of flights at parking apron and the most reasonable utilization of large gates are selected as the optimization objectives, then an efficient multi-objective optimization model of gate assignment problem is proposed in this paper. Then an improved adaptive particle swarm optimization(DOADAPO) algorithm based on making full use of the advantages of Alpha-stable distribution and dynamic fractional calculus is deeply studied. The dynamic fractional calculus with memory characteristic is used to reflect the trajectory information of particle updating in order to improve the convergence speed. The Alpha-stable distribution theory is used to replace the uniform distribution in order to escape from the local minima in a certain probability and improve the global search ability. Next, the DOADAPO algorithm is used to solve the constructed multi-objective optimization model of gate assignment in order to fast and effectively assign the gates to different flights in different time. Finally, the actual flight data in one domestic airport is used to verify the effectiveness of the proposed method. The experiment results show that the DOADAPO algorithm can improve the convergence speed and enhance the local search ability and global search ability, and the multi-objective optimization model of gate assignment can improve the comprehensive service of gate assignment. It can effectively provide a valuable reference for assigning the gates in hub airport.     

A knowledge-based airport gate assignment system integrated with mathematical programming

Airport gate assignment is the process of selecting and allocating aircraft to gates to create an assignment schedule, and it is one of the major functions of airport operations. With the increase of passenger traffic volumes and the number of flights, the complexity of this task and the factors to be considered have increased significantly, and efficient gate utilization has received considerable attention. This paper proposes a knowledge-based airport gate assignment system integrated with mathematical programming techniques to provide a solution that satisfies both static and dynamic situations within a reasonable computing time. A partial parallel assignment is introduced, which considers a group of aircraft and looks at all the available gates and then does the gate assignments by optimizing a multi-objective function. For the validation of the proposed approach, an example is used as a case study, and a prototype system with various functions has been developed in a microcomputer environment.     

Multi-commodity flow network model of the flight gate assignment problem

The flight gate assignment problem is encountered by gate managers at an airport on a periodic basis. This assignment should be made so as to balance carrier efficiency and passenger comfort, while providing buffers for unexpected events that cause assignment disruptions. In this paper, a binary integer multi-commodity gate flow network model is presented with the objective of minimizing the fuel burn cost of aircraft taxi by type and expected passenger discomfort for “tight” connections as a function of inter-gate distance and connection time. This approach is shown to be computationally efficient within a decomposition approach for large problem instances. A numerical application of this approach is given for the gating of Continental Airlines at George W. Bush Intercontinental Airport in Houston (IAH).     

Multi-commodity flow network model of the flight gate assignment problem

The flight gate assignment problem is encountered by gate managers at an airport on a periodic basis. This assignment should be made so as to balance carrier efficiency and passenger comfort, while providing buffers for unexpected events that cause assignment disruptions. In this paper, a binary integer multi-commodity gate flow network model is presented with the objective of minimizing the fuel burn cost of aircraft taxi by type and expected passenger discomfort for “tight” connections as a function of inter-gate distance and connection time. This approach is shown to be computationally efficient within a decomposition approach for large problem instances. A numerical application of this approach is given for the gating of Continental Airlines at George W. Bush Intercontinental Airport in Houston (IAH).     

The use of meta-heuristics for airport gate assignment

Improper assignment of gates may result in flight delays, inefficient use of the resource, customer’s dissatisfaction. A typical metropolitan airport handles hundreds of flights a day. Solving the gate assignment problem (GAP) to optimality is often impractical. Meta-heuristics have recently been proposed to generate good solutions within a reasonable timeframe. In this work, we attempt to assess the performance of three meta-heuristics, namely, genetic algorithm (GA), tabu search (TS), simulated annealing (SA) and a hybrid approach based on SA and TS. Flight data from Incheon International Airport are collected to carry out the computational comparison. Although the literature has documented these algorithms, this work may be a first attempt to evaluate their performance using a set of realistic flight data.     

复合类别航站楼分配问题的改进和声搜索算法

随着航空运输业的蓬勃发展,如何在硬件条件受限的情况下尽量提高机场的运行效率来满足日益增长的航班起降需求,日益受到关注.为了对机场航站楼登机门分配问题进一步优化,提出一种考虑登机门复合类别的航站楼分配问题,并建立数学模型,描述在航线类别、班机型号以及最短停靠间隔对于登机门选取的约束下,带有临时停机坪辅助的登机门分配优化问题.在模型经过精确算法验证的基础上,为适应登机门问题特性并求解中大规模问题,首次引进和声搜索算法,增加复杂约束条件,对编码解码、初始解产生以及寻优过程进行改进,提出一种更高效的改进和声搜索算法对模型进行求解.通过使用Lingo软件和Matlab软件对中小规模算例分别进行精确求解和智能算法求解,对比表明所提出智能算法的有效性、全局搜索能力以及求解效率.再通过对大规模问题的求解,表明所提出算法在现有条件下能够减小转机旅客的总转机路程,取得了较好的效果.     

Airport Gate Scheduling with Time Windows

In contrast to the existing airport gate assignment studies where flight have fixed schedules, we consider the more realistic situation where flight arrival and departure times can change. Although we minimize walking distances (or travel time) in our objective function, the model is easily adapted for other material handling costs including baggage and cargo costs. Our objectives are achieved through gate assignments, where time slots alloted to aircraft at gates deviate from scheduled slots minimally. Further, the model can be applied to cross-docking optimization in areas other than airports, such as freight terminals where material arrival times (via trucks, ships) can fluctuate. The solution approach uses insert and interval exchange moves together with a time shift algorithm. We then use these neighborhood moves in Tabu Search and Memetic Algorithms. Computational results are provided and verify that our heuristics work well in small cases and much better in large cases when compared with CPLEX solver.     

A conceptual solution to the aircraft gate assignment problem using 0, 1 linear programming

The U.S. commercial airline movement to “hub” operations has increased rapidly over the past several years. This trend will grow with the introduction of the Wayport concept. These giant “people exchange” facilities will feature multiple runways and massive concourses. While the Wayport developers may automate the ground movement of passengers, the sheer size of the facilities and the anticipated close scheduling of flights will confront the passenger with a problem of new dimension in getting from arrival gate to departure gate. One thing that could help alleviate the situation would be “sensible” assignment of flights to gates - sensible in that the assignment would take into account the communion of interest of the passengers. Other things being equal, the positioning of incoming flights should take into account the distribution of passengers among connecting flights. The larger the number of passengers arriving on flight X for destination A, the closer flight X should be positioned to the flight departing for A. This inquiry looks conceptually at this problem, reducing the distance passengers must walk from gate to gate. The criterion selected is minimization of the total passenger-distance travel for a given arrival-departure cycle. The problem can be conveniently cast as a 0,1 Linear Programming (LP) problem. The author discusses derivation of problem parameters and then solves several representative problems. A unique feature of the LP approach is the availability with the optimal solution of cost factors and assignments for suboptimal solutions. Minor changes in the input data do not require reworking the problem. Although the solution is characterized as conceptual, some ideas are given for practical use of the solution methodology in a dynamic airport environment.     

Reducing airport gate blockage in passenger aviation: Models and analysis

Commercial flights are typically assigned to an arrival gate at their destination station (airport) prior to their departure from their origin station. Although the gate is scheduled to be available when the flight arrives, this is not always the case in practice. Due to variability in departure and flight times, the arriving flight might arrive early, the previous flight departing from the gate might depart late, or both. When a flight arrives at its scheduled gate but has to wait because the preceding aircraft is still occupying that gate, we refer to this as gate blockage. Gate blockage can have many negative impacts, including passenger delays, missed connections, and increased fuel burn. Our research is focused on incorporating the inherent stochasticity of the system into the planning process to reduce the prevalence and impact of gate blockage. Specifically, we formulate an optimization problem to assign flights to gates so as to minimize the expected impact of gate blockage. We use historical data to predict delay distributions and conduct experiments to assess both the computational tractability of our approach and its potential for improvement in solution quality over existing approaches.