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

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

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.     

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

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

改进非支配排序精英遗传算法的篦冷机参数优化

为优化篦冷机控制参数,提高换热效率,将传热和粘性耗散引起的修正熵产数分别作为目标函数,利用遗传算法对篦冷机参数进行多目标优化.为增加多目标遗传算法的种群多样性,提高算法的局部搜索能力,对传统的非支配排序精英遗传算法(NSGA-Ⅱ)进行部分功能改进.构建多种群、多交叉算子的操作模式,根据子种群对最优解集的贡献量自适应调节子种群规模,利用局部搜索算法提高算法的局部搜索能力.通过标准多目标优化问题验证所提出算法的有效性,并根据优化得到的篦冷机熵产数的最优解集,给出冷却风机功率最小的最优控制方案,通过与生产线的实际数据进行对比验证其优化效果.     

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

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

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.     

The over-constrained airport gate assignment problem

In this paper, we study the over-constrained airport gate assignment problem where the objectives are to minimize the number of ungated flights and total walking distances or connection times. We first use a greedy algorithm to minimize ungated flights. Exchange moves are employed to facilitate the use of heuristics. Simulated annealing and a hybrid of simulated annealing and tabu search are used. Experimental results are good and exceed those previously obtained.     

基于改进模拟退火算法的登机口分配问题

为研究新建卫星厅对中转旅客的航班衔接的影响,分析中转旅客的换乘紧张程度,提高机场资源利用效率,本文对登机口分配问题进行研究.在最小化登机口使用个数的前提下,考虑了中转旅客的换乘紧张度,建立了飞机-登机口分配0-1整数规划模型.为改善传统启发式算法的搜索能力,本文结合变邻域搜索的邻域构造思想,综合利用集束搜索和模拟退火算法的优势,提出了基于集束搜索的改进型模拟退火算法,并借助Java语言进行编程求解.结果表明:与禁忌搜索算法、变邻域搜索算法和经典蚁群算法相比,本文所提出算法的优化效果较好.     

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

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

复杂多约束条件下航班除冰延误机理及资源优化配置

针对机场除冰运行存在的除冰航班延误频发、除冰资源使用粗放的问题,提出了考虑航班延误机理的除冰资源优化配置方法.研究了多参数综合影响的除冰效率及航班动态随机环境下的除冰排队延误机理.分析了除冰运行过程的复杂多约束条件,构建了以最小化除冰液消耗、除冰车需求和除冰延误架次为目标的飞机除冰资源多目标优化配置模型.利用自适应网格多目标粒子群算法求解模型并提出了基于多属性决策优化的除冰资源优化配置方法.除冰资源优化配置后除冰液消耗量、除冰车需求量、除冰延误架次相较于优化前分别降低了13.9%,12.8%, 19.3%.该方法为机场除冰运行资源优化提供了新思路.     

和声搜索-分布估计混合算法求解多目标优化问题

针对和声搜索算法不能很好地求解多目标优化问题的缺陷,提出一种多目标和声搜索—分布估计混合算法(MHS-EDA)。该算法一方面利用分布估计的采样操作对和声记忆库内进行搜索,拓宽了和声记忆库内空间;另一方面对和声记忆库外进行外部档案搜索,实现群体间信息交换,从而提高了多目标和声算法的全局搜索能力。数值实验选取六个常用测试函数,并与多目标遗传算法、多目标分布估计算法、多目标和声搜索算法进行比较,测试结果表明提出的混合算法能够有效地解决多目标优化问题。     

一种新型的多目标优化混合量子进化算法

针对复杂多目标优化问题,提出一种混合量子进化算法,并利用它求解多目标函数优化问题。该算法根据多目标优化的特点,创建外部集合保存历代搜索到的非支配解,利用其中的精英个体设计了一种旋转角自适应调整的量子门更新策略,并对量子比特表示的概率幅设置最大和最小阈值,以防止量子群体早熟收敛。借鉴量子门引入了专门针对量子个体的旋转交叉算子,同时小概率地对量子比特进行取反变异操作。对所提算法的计算复杂度进行了理论分析。与另一种已有的多目标量子进化算法的比较结果表明,所提算法具有更好的收敛性能、分布特性及求解效率。     

民用机场停机位优化配置计算机仿真

停机位配置指为到港或离港航班指定适宜的登机口,确保航班正点。航班停机位的高效、合理安排是机场地面作业中的一项核心任务。在系统分析国内繁忙机场停机位配置情况的基础上进行计算机仿真,模拟给出停机位优化配置。同时考虑旅客登转机时间(旅客满意度)、机型与停机位类型匹配(机场效益)等优化目标。系统运行稳定,效率高。     

多Agent的航空器滑行策略优化

快速发展的民航事业导致很多机场容量不足。为缓解大型机场交通拥堵的现状,研究了航空器滑行策略优化问题。滑行路径优化是指在特定的时间段内,根据机场资源信息和地面运行管理系统对进离场航空器在跑道和停机位之间的距离进行优化管理。通过深入剖析机场地面的网络结构,综合考虑滑行冲突、地面运行规则等因素,提出了多Agent滑行策略优化方法,该方法提升了机场资源利用率;基于地面网络链路结构的概念,建立了航空器滑行策略优化模型;结合多Agent的基本理论,设计了跑道出口选择概率函数和多Agent系统滑行路径优化结构,以寻求航空器的最优滑行路径。以国内某大型机场的实际情况为研究背景进行了航空器滑行策略实验,结果表明,与以往的算法相比,多Agent滑行策略优化方法的效果更为显著。设置跑道口的速度和同一交叉口航空器的最小间隔距离,通过对跑道出口的选择和Agent间的交互协商,航空器能够对原滑行路径进行有效调整,并缩短其在机场场面上的滑行时间。与最短路径算法相比,多Agent滑行策略方法在航空器的总滑行距离、航空器在滑行道上的密度以及平均等待时间方面的优化效果更好,且其对滑行道资源的分配更合理。其中,航空器在节点处的平均等待时间减少了8.26%。所提策略可有效缓解机场交通拥堵的现状,提高场面运行效率,对减少航空器延误和保障机场的运营安全具有重要意义。     

A multi-objective differential evolutionary algorithm for constrained multi-objective optimization problems with low feasible ratio

Most current evolutionary multi-objective optimization (EMO) algorithms perform well on multi-objective optimization problems without constraints, but they encounter difficulties in their ability for constrained multi-objective optimization problems (CMOPs) with low feasible ratio. To tackle this problem, this paper proposes a multi-objective differential evolutionary algorithm named MODE-SaE based on an improved epsilon constraint-handling method. Firstly, MODE-SaE self-adaptively adjusts the epsilon level in line with the maximum and minimum constraint violation values of infeasible individuals. It can prevent epsilon level setting from being unreasonable. Then, the feasible solutions are saved to the external archive and take part in the population evolution by a co-evolution strategy. Finally, MODE-SaE switches the global search and local search by self-switching parameters of search engine to balance the convergence and distribution. With the aim of evaluating the performance of MODE-SaE, a real-world problem with low feasible ratio in decision space and fourteen bench-mark test problems, are used to test MODE-SaE and five other state-of-the-art constrained multi-objective evolution algorithms. The experimental results fully demonstrate the superiority of MODE-SaE on all mentioned test problems, which indicates the effectiveness of the proposed algorithm for CMOPs which have low feasible ratio in search space.     

基于动态拥挤距离的混合多目标免疫优化算法

多目标免疫优化算法的研究目标是种群均匀分布于优化问题的非劣最优域并使算法快速收敛。为进一步提高多目标优化问题非支配解集合的分布均匀性和收敛性,提出了一种基于动态拥挤距离的混合多目标免疫优化算法。该算法基于动态拥挤距离来对个体进行比较和更新操作,从而保持最终解集的均匀分布,同时借鉴经典差分进化算法中的变异引导算子来加强免疫优化算法的局部搜索能力并提高搜索精度。基于5个经典测试函数的仿真结果表明, 与其他几种有效的多目标优化算法相比,所提算法不仅在求得Pareto最优解集的逼近性、均匀性和宽广性上有明显优势,而且收敛速度也有较大的改进和提高。     

自适应种群更新策略的多目标粒子群算法

针对粒子种群较差的局部搜索能力,提出了一种自适应种群更新策略的多目标粒子群算法。该算法在每次种群进行迭代时,根据种群的多样性测度以及每个粒子的适应度值,自适应地改变速度权重,以此来提高种群粒子在局部搜索时的活性,使算法具有较强的局部搜索能力同时又保留了足够的全局搜索能力。最后利用多组经典测试样例进行仿真,并与传统的粒子群算法以及速度线性衰减算法做比较,在单目标优化中,自适应粒子群算法能够更快地寻找最优位置;在多目标优化中,自适应粒子群算法能够更快速地收敛于帕累托最优边界。     

一种求解多目标组合优化的遗传局部搜索算法

为改善遗传算法求解多目标组合优化问题的搜索效率,提出一种新的遗传局部搜索算法.算法采取非劣解并行局部搜索策略以及基于分散度的精英选择策略,并采用基于NSGA-Ⅱ的适应度赋值方式和二元赌轮选择操作,以提高算法收敛性,保持群体多样性.实验结果表明,新算法能够产生数量较多分布较广的近似Pareto最优解.     

基于人类社交行为的动态多目标优化

为了提高多目标微粒群优化算法处理多目标优化问题的性能,降低计算复杂度,改善算法的收敛性,提出了一种基于人类社交行为的多目标动态微粒群优化算法。考虑到粒子寻优过程受到环境中精英粒子与平庸粒子的影响,分别对自身产生推力与阻力作用,并引入局部跳出策略,使算法具有很强的全局搜索能力和较好的鲁棒性能。通过典型的多目标优化函数对算法进行了测试验证,结果表明提出的多目标算法具有较快的收敛速度和较强的跳出局部最优能力,性能优越,可供许多领域优化问题求解借鉴。     

基于多目标分阶段的跑道调度计划算法*

针对多条跑道环境下离港飞机调度问题,提出了一种基于多目标、两阶段算法。算法第一阶段以飞机重量类型为主要分解参数,生成离港飞机序列。该参数在跑道调度计划问题上比其他参数更具影响力和稳定性。算法第二阶段从离港飞机队列池中选取可用序列,将特殊航班指配到目标类型序列中,生成优化的飞行航班时刻表。实验表明,采用两阶段跑道调度计划算法进行多跑道离港飞机调度比采用先来先服务算法调度在跑道总吞吐量上有明显改善,能有效降低机场航班延误,提高跑道运营效率。