基于多目标优化的机场行李运输车辆调度问题研究

行李装卸是指将旅客的托运行李装上飞机或从飞机上卸载下来的一种机场地面保障服务,行李运输车是民航使用的在机场地面运输旅客托运行李的特种车辆。目前机场普遍采用的单车服务单航班的车辆调度方式,车辆的使用成本高、效率较低,且无法保证任务量的均衡。在建立的机场行李运输车辆调度模型的基础上,首先利用最邻近算法构建由一个出港航班和一个到港航班组成的车辆行驶总路程最短的子路径集合;然后依据子路径间的时间衔接关系对子路经进行优化组合,将所有子路径任务合理分配给行李运输车,实现所需车辆数最少和车辆任务量均衡的目标;最后,应用机场实际算例进行仿真试验,通过对试验结果的分析,验证了所建模型及求解算法的合理性和有效性。     

飞机除冰服务资源的并行机调度方法

以冬季机场除冰资源优化安排问题作为研究对象,以提高飞机除冰资源利用效率为目标,通过对机场飞机除冰过程调度问题的理论和方法进行研究分析,提出了采用混合调度算法来解决机场除冰调度问题的研究方案.在此基础上构建数学模型来实现除冰资源的最大化利用,并对模型进行了算法仿真和对比分析.结果表明,采用该算法对飞机除冰调度问题进行求解,可以实现除冰资源的更有效利用,能够更好地提升现有人工调度方法的资源利用效率.     

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

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

基于多目标动态规划的多跑道进港排序

随着航空运输的高速增长,航班延误日益严重,而对飞机进行进港排序和跑道调度能有效提高机场吞吐量、减少飞机燃油花费,从而减轻航班延误,提升经济效益.由于大量飞机的多跑道进港优化调度问题是一个非确定型多项式完全(NP-C)问题,该问题一直没有得到有效解决.本文针对已有的基于位置交换束缚的单跑道动态规划算法运算量大、运算效率低的不足,采用优化解空间的措施并运用贪心策略,同时将其推广到双跑道调度,从而解决大量飞机的双跑道、多目标进港排序优化问题.大量仿真实验表明,该算法复杂度与飞机数量呈近似线性关系,能在较短时间内对吞吐量和降落花费同时实现优化.     

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

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

精确求解进港飞机调度双目标优化问题的epsilon约束算法

随着机场客流的持续增长,航班延误日益严重。同时,对于机场最重要的跑道资源而言,积雪结冰等会造成 飞机 打滑,从而出现事故。对于机场管理者,周期性地维护跑道至关重要,以防雨雪天气出现飞机打滑事故。该研究主要针对跑道上的 航班调度问题,考虑恶劣天气环境下跑道的周期性维护(如周期性喷洒除雪盐等)。为了在保证航班的服务质量的同时提高机场跑道的使用效率,文中以最小化航班总延误和跑道使用时间为优化的双目标。首先,提出该双目标优化问题混合整数规划模型;其次,为了精确求解出Pareto前沿,开发出epsilon约束算法;最后,给出算例来说明模型和算法的可行性。通过数学规划理论建模并开发精确求解算法,为机场资源优化研究提供参考。     

基于A~*算法的机场滑行路径优化研究

研究机场场面航班的滑行路径分配和滑行冲突问题。针对目前滑行效率制约机场调度。滑行冲突影响飞行安全的状态,提出将安全间隔、滑行规则和冲突避免限制规则作为约束条件建立了滑行路径优化模型。采用了A*算法给出了问题的优化,在保证滑行道调度零冲突的前提下,缩小航班的总滑行时间,提高了滑行效率。以重庆江北国际机场为例,与管制员依据机场细则得到的路径相比,结果表明提出的滑行道调度模型和优化方法是可行的,在实现较优的滑行路径的基础上能智能的发现冲突、解决冲突,可为繁忙机场的机场调度提供了决策支持。     

实现多目标优化的机场特种车辆调度算法

为保证航班正常运行,机场特种车辆必须高效完成地面保障服务任务。目前机场特种车辆的调度方式是单车单航班服务的人工调度方式,成本较高,且效率较低。针对该问题提出一种基于节约算法的解决方案。该方案分为两个阶段:第一阶段,利用节约算法求出满足行驶总路程最短的子路径集合;第二阶段,通过构建的新方法将每个子路径任务合理分配给所有车辆,实现车辆数目最少和任务量差异最小的目标。以国内某机场实际航班数据做算例进行实验,与单车单航班服务相比,总路程节省49.28%;与不加任务量约束相比,任务均衡度由43.55%提高到95.16%。实验结果表明,利用该算法调度特种车辆可大幅降低服务成本,且能实现任务均衡。     

基于背压路由算法的离港飞机滑行路径优化

针对现有优化算法仅从最短路径或最小滑行时间的角度出发,忽略了航空公司满意度和滑行道负载率对滑行道调度影响的问题,提出了基于背压路由的离港滑行路径优化算法．算法首先将离港滑行路径优化问题等价转化为网络拓扑结构中的路由搜索问题,然后利用背压路由算法求解具有最大航空满意度和最小滑行道负载率的滑行路径．对国内某枢纽机场实际运行数据的仿真结果表明,运用该算法获得的滑行路径在保证跑道及滑行道效用的同时,能够有效减少飞机滑行时间,改善机场拥塞问题,缓解机场容量与需求的矛盾,提高机场运行效率,为离港航班滑行路径优化提供了新的研究思路．     

运用VB对机场空域飞行冲突的模拟

本文介绍运用VB对机场起飞飞机与航路飞机的飞行冲突进行模拟的方法,利用VB事件驱动的编程机制控制可能产生的飞行冲突。     

融合回溯算法在离场航班排序问题中的应用

在离场航班优化排序问题的研究中,针对特定的情况,塔台管制员需要提高机场容量或者减少航班延误时间,要求管制员给出一个理想的离场航班排序方式。鉴于以上两种情况,首先根据ICAO规定的的起飞飞机间雷达间隔要求(尾流间隔和非尾流间隔),建立了飞机离场排序问题的数学模型。然后融合位置约束交换算法,并考虑航路流控的影响,设计融合回溯算法。采用以重庆江北机场为例进行仿真验证,结果显示,在不存在航路流控和存在航路流控两种情况下,都可以得到大大减少航班延误时间的排列和提高机场容量的排列,证明运用回溯算法可解决离场排序问题的高效性。     

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

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

求解机场终端区飞机着陆调度问题的遗传算法

空中管制员需为到达的飞机安排跑道并计算着陆时间,以飞机空中延误最小为出发点研究了多跑道的飞机着陆调度问题,约束条件为每架飞机的着陆时间应落在规定的时间窗内及相邻两架飞机应满足最小时间间隔。针对该问题设计了一种遗传算法对问题进行求解,其中染色体由飞机排序链表和跑道链表组成,相应的交叉和变异算子也做了改进设计。仿真实验用数据库OR-Library中的实例验证了该算法的有效性。     

An adaptive large neighborhood search heuristic for solving a robust gate assignment problem

With the rapid growth of air traffic demand, airport capacity becomes a major bottleneck within the air traffic control systems. Minor disturbances may have a large impact on the airport surface operations due to the overly tight schedules, which results in frequent gate conflict occurrences during airport’s daily operations. A robust gate schedule that is resilient to disturbances is essential for an airport to maintain a good performance. Unfortunately, there is no efficient expert system available for the airport managers to simultaneously consider the traditional cost (the aircraft tow cost, transfer passenger cost) and the robustness. To fill this gap, in this paper, we extend the traditional gate assignment problem and consider a wider scope, in which the traditional costs and the robustness are simultaneously considered. A mathematical model is first built, which leads to a complex non-linear model. To efficiently solve this model, an adaptive large neighborhood search (ALNS) algorithm is then designed. We novelly propose multiple local search operators by exploring the characteristics of the gate assignment problem. The comparison with the benchmark algorithm shows the competitiveness of proposed algorithm in solving the considered problem. Moreover, the proposed methodology also has great potential from the practical perspective since it can be easily integrated into current expert systems to help airport managers make satisfactory decisions.     

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.     

飞机维修计划优化模型与算法研究

分析了航空维修生产调度中的维修计划编制问题,仔细研究了飞机维修计划编制流程和约束条件,建立了飞机维修计划编制优化模型,不仅考虑了飞机维修资源的约束,同时还考虑了维修日期对效益的影响,能够快速确定每架飞机开始检修日期。为了求解模型,建立了离散粒子群优化算法,采用适合模型的粒子取值和速度变化方式。应用生产数据进行实际排产的实验结果表明,建立的模型和算法切实可行,可应用于生产实际,可大大提高生产调度自动化水平。     

Multiple objective solution approaches for aircraft rerouting under the disruption of multi-aircraft

This paper considers a multi-objective aircraft recovery problem for airline disruption. An integer programming formulation is first established based on connection network with three conflicting objectives, where the first objective minimizes the total deviation from original flight schedules, the second objective minimizes the maximal flight delay time, and the third objective minimizes the number of aircraft actually attended in swapping. Optimal analysis is provided for a small scale aircraft recovery problem with the last two objectives and then one polynomial time algorithm for aircraft recovery problem after the disruption to multi-aircraft in a fleet at an airport. One heuristic combined ε-constraints method and neighborhood search algorithm is designed for large scale disruption recovery problem. The results obtained from computational experiment illustrate effectiveness and efficiency of the heuristic. The outcome of this research could provide theoretical and practical supports for airlines to reduce flight delays.     

The evaluation of air transportation network based on multiple criteria

The problem is partitioned into two components: to propose the air transportation network based on “hub and spoke” pattern as alternative network in Sumatera island (one of the islands in Indonesia), and to propose the algorithm for the aircraft selection of the suitable type of aircraft in the operation on airport pairs. The algorithm presented in this paper is obtained from heuristic, and then comparing of our proposal with the existing one is done, based on the multiple criteria.