考虑运力外调的航班优化调度方法

董兵; 王子悦; 姚浩然; 杨睿超

doi:10.12404/j.issn.1671-1815.2501995

科学技术与工程 ›› 2026, Vol. 26 ›› Issue (3) :1293-1298 DOI: 10.12404/j.issn.1671-1815.2501995

论文：航空、航天

考虑运力外调的航班优化调度方法

作者信息 +

Optimal Flight Scheduling Method Considering Outward Dispatch

Author information +

文章历史 +

摘要

随着近年来极端天气和突发公共事件的频发,航空应急运输需求增长。为解决如何在运力外调的同时尽可能保障航班正常运营的问题,通过分层求解的思路研究了航空公司参与应急运输,运力外调后导致运力减少下的航班恢复问题。首先,基于航班延误时间最小、运营成本最小为恢复目标,建立了多目标的航班优化调度整数规划模型。其次,采用分层求解的思路,用二进制搜索算法对最小允许延误时间进行计算,基于上述结果为限制条件筛选符合的弧构建航班网络模型,结合Dijkstra算法实现飞机交换次数最小,再通过Gurobi求解器计算出最小运营成本的恢复方案。最后,以航空公司的飞行计划为例验证模型及算法的可行性。结果表明:与传统运力外调下的处理方案相比,本文中提出的模型及算法提高了10.3%的航班执行率,减少了航班的取消,为航班优化调度提供了一种可行的方法。

Abstract

In light of the escalating frequency of extreme meteorological phenomena and emergent public incidents in recent years, the demand for emergency airlift capabilities has witnessed a marked surge. In order to ensure normal flight operations during the outward dispatch of airline aircraft, a hierarchical solution approach was used to investigate the flight recovery problem faced by airlines participating in emergency transportation due to reduced capacity. It begined with the formulation of a multi-objective integer programming model prioritizes concurrent minimization of cumulative flight delay duration and operational expenditures in disrupted scheduling scenarios, followed by implementation of a bisection search algorithm to determine the minimal permissible delay threshold through constraint stratification. Subsequent development of a flight network topology via arc selection mechanisms incorporated Dijkstra’s algorithm to minimize aircraft substitution frequency, culminating in computational optimization using the Gurobi solver to derive cost-minimal recovery strategies. Finally, the feasibility of the proposed model and algorithm was validated using an airline’s actual flight plan as a case study. The results show that, compared with traditional outward dispatch solutions, the proposed approach improves the flight execution rate by 10.3%, reduces flight cancellations, and offers an effective method for flight schedule optimization.

Graphical abstract

关键词

运力外调 / 航班执行率 / 飞机交换 / 二进制搜索算法 / Dijkstra算法

Key words

outward dispatch / flight completion rate / aircraft swapping / binary search algorithm / Dijkstra’s algorithm

引用本文

引用格式 ▾

董兵, 王子悦, 姚浩然, 杨睿超. 考虑运力外调的航班优化调度方法[J]. 科学技术与工程, 2026, 26(3): 1293-1298 DOI:10.12404/j.issn.1671-1815.2501995

DONG Bing, WANG Zi-yue, YAO Hao-ran, YANG Rui-chao. Optimal Flight Scheduling Method Considering Outward Dispatch[J]. Science Technology and Engineering, 2026, 26(3): 1293-1298 DOI:10.12404/j.issn.1671-1815.2501995

登录浏览全文

4963

注册一个新账户忘记密码

民航具有快速响应的特点,是国防运输和经济安全的重要保障力量,也是参与突发事件应急保障的重要组成部分。航空公司接收运力外调任务,会导致公司运力减少。如果不进行调整,会导致航班大量取消,对后续运行造成困难,影响旅客的出行^[1]。

运力外调后,因对飞机调用的突然性及时长不确定性,运控人员采取的办法为:将被调度飞机涉及的航班全部取消,待被调度飞机相应任务执行完毕后,继续执行航班计划^[2]。这样的调整可以在短时间内做出响应,直接取消航班的方式虽简单,但对旅客出行是不利的,如何减少航班取消是本文研究的核心问题。

针对该问题,学者们提出了多种优化方法。Kammoun等^[3-4]使用遗传算法优化时间Petri网通过优化调度实现运力不足下的航班恢复,使系统中的所有飞机都可以在每个时刻进行建模。Vink等^[5]构建并行时空网络,使用混合整数规划模型(mixed-integer programming, MIP)结合基于规则的选择启发式算法,在中断发生时可以迅速求解优化调度后的航班时刻表。杨新湦等^[6]构建了基于广度优先搜索的航班网络生成算法,并在此基础上考虑巡航速度控制策略,通过优化调度对航班进行一体化恢复。Lin等^[7]在航班时刻容量限制下,利用巡航速度控制,建立圆锥二次混合整数规划模型(conic quadratic mixed-integer programming,CQMIP)进行航班的优化调度。Yan 等^[8]构建了一种带边约束的网络流模型,结合MIP模型和启发式算法对运力不足下航班优化调度问题进行研究。Liu等^[9]提出一种时间带网络模型,结合MIP模型利用高铁实现飞机的回收以进行航班优化调度。Huang等 ^[10]针对货运航空公司中断的飞机及货运时间表进行优化调度,提出了一种基于机器学习的列生成方法,该方法能消除不良的航班延误决策及降低扰动带来的成本。Erkan等^[11]构建了一个单机队固定时隙下运力不足的优化调度模型,便于利益攸关方对模型进行扩展以拟合其需要的恢复目标。

以单一目标进行优化调度不足以满足航空公司多个优化目标的需求,Kammoun等^[12]构建了两个优化目标的数学模型结合遗传算法对航班优化调度问题进行求解,更加符合实际情况下的客观约束。Lahooti等^[13]建立双目标模型对恢复过程中所有单个飞行段的飞机进行调度,并使用改进的禁忌搜索算法进行求解,能在短时间内获得大规模问题的最优处理结果。李雅聪等^[14]通过贝叶斯网络得到不确定因素对航班恢复过程中过站时间的影响,构建以最小化总延误时间和航空公司公平性的多目标航班优化调度模型,运用多目标遗传算法(non-dominated sorting genetic algorithm II,NSGA-Ⅱ)进行求解。Ding 等^[15]利用深度强化学习结合可变邻域搜索算法,建立航班优化调度模型框架。

综上,当前研究大多数针对机场关闭或管制、气象原因导致的运力不足下不正常航班优化调度^[16],而针对运力外调情况下研究较少。为此,现以航空公司运力外调且不改变原航班串的情况下,通过合理调整航班计划,执飞更多航班的问题进行研究。以期为航班运力外调时优化调度提供可行方法。

1 运力外调下航班优化调度建模

1.1 问题描述

为了减少因运力外调而取消航班导致航班执行率下降,采用飞机交换和航班延误的方式,通过调度优化,在减少航班的取消下,尽可能减少航空公司的损失。基于以上目标,本文构建的模型遵循如下假设。

(1)假定机场关闭时间为凌晨02∶00,开放时间为早上06∶00。

(2)仅考虑运力外调当日的航班恢复。

(3)本文中只考虑飞机的恢复。

(4)不考虑飞机的维修问题。

运力外调下,航空公司的航班运行如图1所示。节点代表机场,弧代表飞机的飞行活动。

在调度节点处,航空公司接到上级部门的应急运力外调指令,指定部分飞机从调度弧出发,前往任务节点参与应急保障任务。剩余飞机沿执行弧继续执行原定期飞行计划。必经节点表示原定期飞行计划中涉及的机场。由于部分飞机被外调参与应急任务,导致可用运力减少,无法完全按照原定期飞行计划执行航班任务,从而出现运力不足的情况。为提高航班执行率,必须对原定期飞行计划进行重新调整和优化。回归弧表示响应运力外调的飞机在完成应急保障任务后,返回原飞行计划继续执行航班任务或回归出发机场。结束节点则标志着航班恢复过程的终结,系统恢复至稳定状态。这一过程不仅涉及航班调度的动态调整,还需综合考虑飞机资源的最优配置与任务执行的效率,在应急保障任务和原定期飞行计划之间实现平衡。

1.2 符号说明

本文中符号说明如表1所示。

1.3 模型构建

将原飞行计划中有关被调度飞机航班串的执行时间延误至该飞机最早可用时间的恢复方案可能是同时满足航空公司损失最小、所有航班总延误时间最小的恢复方案。但是有关调度飞机的航班延误时间将随飞机的最早可用时间无限延长。延误时间过长会导致旅客的满意度大幅度下降,甚至导致航班串无法完整执行。

通过飞机交换减少最大允许延误时间,最大允许延误时间即确保航班计划的可行性和服务质量的前提下延误时间的上限。通过减少最大允许延误时间,在获得延误时间最短的恢复方案的同时将延误时间进行平滑,避免出现某航班延误较长时间,如图2所示。

交换前由于飞机A和飞机B的最早可用时间均晚于对应航班串的首个航班的起飞时间,导致航班串A、B均出现延误,其中航班串B的延误时间较长。进行飞机交换后,虽然两个航班串依旧延误,但是延误时间被平滑的分配至两个航班串,有效解决了交换前航班串B延误时间过长的问题。同时根据建模生成最小化航空公司恢复成本,生成符合恢复目标的恢复方案。

根据优化调度目标建立混合整数线性规划模型(mixed-integer linear programming, MILP)求解。以最大允许延误时间最小、航班执行及延误的成本最小作为目标函数建模,即

(1)mind_max=max

∑ k i ∈ K ∑ r i ∈ R d k i r i

(2)minC=${\sum }_{{k}_{i}\in K}^{}{\sum }_{{r}_{i}\in R}^{}{C}_{{r}_{i}}^{{k}_{i}}{x}_{{r}_{i}}^{{k}_{i}}$+C_d${d}_{{k}_{i}{r}_{i}}$

(3)${C}_{{r}_{i}}^{{k}_{i}}$=${t}_{{r}_{i}}{C}_{o}^{{k}_{i}}$+C_l

(4)${d}_{{k}_{i}{r}_{i}}$=max(0,${t}_{{k}_{i}}$-${d}_{h{r}_{i}}$)

式(1)为最小化新生成航班计划相对于原航班计划中对应航班串的允许延误时间;式(2)为最小化航空公司执行航班的成本及新航班计划相对于原航班计划对应航班串的延误导致的延误成本;式(3) 为航班串运营成本的计算公式。飞机k_i执行航班串r_i的延误时间用飞机k_i的最早可用时间${t}_{{k}_{i}}$减去原飞行计划对应航班串r_i内第一个航班f₁的原定出发时间${t}_{h{r}_{i}}$进行计算。由于有些飞机并不需要响应调度,这些飞机全天可用,为免出现负值的计算错误,采用式(4)的方式进行处理。

该目标函数满足以下约束条件:

(5)s.t.

∑ r i ∈ R x r i k i

≤1,k_i∈K,r_i∈R

(6)

∑ k i ∈ K ∑ r i ∈ R x r i k i

=1, ∀ r_i∈R

(7)${x}_{{r}_{i}}^{{k}_{i}}$=0,1, k_i∈K,r_i∈R

式(5)表示每架飞机仅可执行一个航班串;式(6)表示每个原定期航班计划内的航班串均要被执行。为了描述飞机和航班串之间的执行关系,引入式(7)决策变量x,表示k_i飞机执行航班串r_i时,${x}_{{r}_{i}}^{{k}_{i}}$=1,否则${x}_{{r}_{i}}^{{k}_{i}}$=0。

2 模型求解算法

在以往多目标规划模型的求解中,往往根据需求对不同的目标函数定义相应的权重用以在实际计算中确定目标函数的优先级及影响因子大小。而本文中两个目标函数难以定义合理的权重,采用分层求解的思想,结合二进制搜索算法和Dijkstra算法对该多目标模型进行求解。优化调度流程如图3所示。

为了对模型进行求解,在Python环境下构建网络流模型,设置源节点、执行节点、结束节点。其中源节点至执行节点的弧为飞机弧,代表飞机从调度节点出发执行飞行任务或应急保障任务,每个弧赋值1的流量。执行节点至结束节点的每条弧对应为某飞机k_i执行某航班串r_i的执行弧,给每条弧定义弧权重,每条弧附有3个标签:d_kr、a_kr、b_kr。d_kr为当飞机k_i执行航班串r_i时,航班串r_i相对于原定期飞行计划中r_i的延误时间[计算规则见式(4)]。a_kr为判定航班串r_i是否由原定期飞行计划内对应飞机k_i执行。如果重新制定飞行计划后飞机k_i依旧执行相同的航班串r_i,则记a_kr=0,否则记a_kr=1。b_kr为弧的容量,令b_kr=1,代表每条弧仅能容纳1个单位的容量,表示一个航班串仅能被一架飞机执行一次。

基于分层求解的思路,首先引用二进制搜索算法对最小化最大允许延误时间进行计算,随后以上一步得出的最小化最大允许延误时间为限制,筛选符合条件的执行弧构建带权有向图,结合Dijkstra算法实现飞机交换次数最小,最后结合Gurobi求解器计算出最小成本的恢复方案。二进制搜索是一种在有序数组或者列表中查找特定元素的搜索算法,其时间复杂度为O(lgN)^[17]。延误时间可以表示为一组根据升降顺序排序的数组。本文处理最小化最大允许延误时间、最小化飞机交换次数的主要算法流程如下:

Step1 构建网络流模型,包括源节点、执行节点、结束节点、飞机弧、执行弧。

Step2 所有飞机弧流量设置为1。计算所有执行弧相对于原定期飞行计划的延误对应赋值在标签d_kr中。设置执行弧流量为b_kr=1。对每条执行弧按规则设置a_kr标签。

Step3 引入初始d_max、d_min。根据求解问题初始化d_max为当前网络所有执行弧延误时间的最大值,令d_min=0。

Step4 初始化网络流量l(f)=0。

Step5 去除原始网络中执行弧标签不满足d_min≤d_kr≤d_max的执行弧,其他网络属性、内容不变,在此基础上构建子网络模型。

Step6 去除上一步生成的网络中执行弧标签不满足d_kr≤(d_max+d_min)/2的执行弧,其他网络属性、内容不变,在此基础上构建子网络模型。

Step7 以执行弧的标签a_kr为弧的费用,Dijkstra算法计算该子网络的最小成本路径。

Step8 判断网络流量l(f)是否达到该网络的最大流量l(f)_max=n。若满足转Step10,否则转Step9。

Step9 更新d_min=(d_max+d_min)/2。转Step6。

Step10 导出当前d_max为mind_max,导出符合条件的执行弧集合。

Step11 结束。

以上算法在最小化允许延误时间的同时,构建带权有向图,以判定是否发生飞机交换的弧标签a_kr为路径费用,用Dijkstra算法计算最小成本路径,尽可能减少了恢复期间飞机的交换。实现本文恢复目标的同时,从根源上减少航空公司由于飞机交换产生的时间、运营成本。随后引入商业求解器Gurobi对本文模型进行求解,获得满足恢复目标:尽可能减少航空公司的损失、尽可能缩短延误时间、尽可能减少不必要的飞机交换的最优解。

3 算例分析

为了验证以上建模及算法对运力外调下航空公司飞机恢复问题的处理效果,采用昆明航空公司的飞行计划进行验证。实验在Python2024.1.4环境下对算法编程实现,并调用大规模数学优化求解器Gurobi11.0.3对模型进行求解, 程序在搭载AMD R9 7845HX处理器,16 G内存的电脑上运行。

3.1 参数设置及数据描述

该算例涉及22架飞机,22个航班串,77个航班,30个机场。涉及优化调度的部分飞行计划及对应飞机可用时间如表2所示。算例中所有航班串内任意两个航班之间的过站时间均大于45 min,所有航班运行时间均在早上06∶00时至第二天凌晨02∶00之间。从表2中可以看出,该航空公司接到应急运力外调,要求调度飞机号为10和16的飞机参与应急保障。应急保障任务完成后k₁₀和k₁₆的回归时间为当天下午14∶35分和16∶00时。

算例中的执飞飞机机型均为B737,涉及模型中成本计算的各项参数的取值如表3所示。由于机场、航班串不同,部分参数有差异,为便于计算,其中数值均采用平均值。

3.2 实验结果分析

为了评估本文的多目标优化调度模型及算法对运力外调下航空公司航班的优化调度能力,采用3个方案进行比对。设方案一为此前航空公司接收运力外调的传统处理方案:将被调度飞机涉及的航班全部取消,待被调度飞机回归后,继续执行航班计划;方案二:将被调度的飞机对应航班串直接顺延至被调度飞机可用;方案三:根据本文模型和算法进行优化后的恢复方案。

按照延误的传播性,每个航班之间留足至少45 min的过站时间需求,根据机场6时开放第二天凌晨2时关闭的机场开放时间,对算例进行求解。方案三求解结果为:将k₁₀、k₁₆与k₂₁、k₂₀进行飞机交换执行对应航班串。方案三通过二进制搜索减少系统最大允许延误时间的迭代过程如图4所示。图4展示了d_max、d_min在迭代过程中的变化情况,其中d_mid=(d_max+d_min)/2。初期(前5次迭代),d_min迅速上升,d_max迅速下降,d_mid波动较大;随后3条曲线逐渐趋于稳定,表明算法逐步收敛,延误时间范围缩小,最终逼近最优解。这反映了二进制搜索算法在优化过程中的高效性和稳定性。

各方案求解结果如表4所示。实验结果表明,方案二、方案三的航班取消数量均小于方案一,各方案航班取消率分别为8%、2%、无航班取消。方案二较方案一航班取消率降低7.8%,方案三对比不进行飞机交换的方案二,方案三无航班取消的情况。方案一有关运力外调飞机的航班均取消,航班无限延误,方案二总延误时间为2 090 min,通过算法减少最大允许延误时间后,方案三总延误时间为1 055 min,方案三相对于方案二总延误时间降低49.5%。方案二、方案三延误航班的延误时间如图5所示,方案二最大允许延误时间为370 min,方案三最大允许延误时间为225 min,并且方案三的每段航班的延误时间更平滑,没有出现某段航班延误时间过长的情况。

4 结论

以航空公司运力外调导致运力减少背景下的航班优化调度问题进行研究。以运营成本最小、延误时间最小为优化调度目标。由于本文的恢复目标之间难以有效定量权重,利用分层求解的思路进行多目标规划模型进行求解。较以往通过对不同目标定义不同权重以计算多目标问题的方式增加了一定的科学性。同时使用分层求解的思路可以更有效的在规划过程中突出目标函数的主要、次要程度。算法针对优化对象延误时间是有序数组的特性,选择了对有序数组较其他算法在空间、时间上更具有优势的二进制搜索算法,提升了计算速度的同时降低算法的整体复杂度。最后建立带权有向图利用Dijkstra算法计算该有向图的最小成本路径,以实现最小化交换飞机次数。以算例为例,通过本文方法生成的方案相对于传统处理办法,降低了10.3%的航班取消率。证明本文构建的模型在进行航空公司运力外调下航班恢复时,可以有效提升航班执行率。

为了减少算法的复杂程度,未对机组人员的工作时长是否超时进行考虑。在后续研究中,可考虑通过飞机交换、航班延误和航班取消来实现运力外调下的飞机、机组一体化的优化调度。

参考文献

原文顺序 | 出版日期 | 本文引用

[1]	Lee J, Lee K, Moon I. A reinforcement learning approach for multi-fleet aircraft recovery under airline disruption[J]. Applied Soft Computing, 2022, 129: 109556.

[2]	方杰. 突发情况下应急运力调度理论与方法研究[D]. 南京: 南京航空航天大学, 2015.

[3]	Fang Jie. Research on the theory and methods of emergency capacity scheduling in sudden situations[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2015.

[4]	Kammoun M A, Rezg N. An efficient hybrid approach for resolving the aircraft routing and rescheduling problem[J]. Journal of Air Transport Management, 2018, 71: 73-87.

[5]	Kammoun M A, Rezg N. Novel approach for the continuous flight rescheduling problem resolution[J]. International Journal of Computational Science and Engineering, 2019, 8(1): 107-112.

[6]	Vink J, Santos B F, Verhagen W J C, et al. Dynamic aircraft recovery problem an operational decision support framework[J]. Computers & Operations Research, 2020: 117, 104892.

[7]	杨新湦, 屈琮博, 王梓旭. 巡航速度控制下航空公司受扰航班一体化恢复[J]. 科学技术与工程, 2021, 21(9): 3848-3854.

[8]	Yang Xinyan, Qu Congbo, Wang Zixu. Integrated recovery of airline disrupted flights under cruise speed control[J]. Science Technology and Engineering, 2021, 21(9): 3848-3854.

[9]	Lin J, Jiang J, Tang Y. Integrated aircraft and crew recovery with cruise speed control under slot capacity restriction: a benders decomposition method[J]. Journal of Industrial and Management Optimization, 2025, 21(1): 825-852.

[10]	Yan S, Chen Y C. Flight rescheduleng, fleet rerouting and passenger reassignment for typhoon disruption events[J]. Transportation Letters, 2022, 14(8): 818-837.

[11]	Liu H, Sun F, Zhang Y. An air-rail intermodal strategy for aircraft recovery[J]. Chinese Journal of Aeronautics, 2022, 35(6): 240-249.

[12]	Huang L, Xiao F, Zhou J, et al. A machine learning based column-and-row generation approach for integrated air cargo recovery problem[J]. Transportation Research Part B: Methodological, 2023, 178: 102846.

[13]	Erkan H, Erkip N K, Özge s. Collaborative decision making for air traffic management: a generic mathematical program for the rescheduling problem[J]. Computers & Industrial Engineering, 2019, 137: 106016.

[14]	Kammoun M A, Turki S, Rezg N. Optimization of flight rescheduling problem under carbon tax[J]. Sustainability, 2020, 12(14), 5576.

[15]	Lahooti E M, Rashidi K A, Baradaran V. A bi-objective model for aircraft and crew recovery considering individual flight legs and maintenance requirements[J]. Engineering Optimization, 2024, 56(11): 1799-1825.

[16]	李雅聪, 邵荃, 唐小卫. 考虑离场航班公平性的航班恢复优化模型[J]. 科学技术与工程, 2023, 23(7): 3084-3090.

[17]	Li Yacong, Shao Quan, Tang Xiaowei. Flight recovery optimization model considering the fairness of departure flights[J]. Science Technology and Engineering, 2023, 23(7): 3084-3090.

[18]	Ding Y, Wandelt S, Wu G, et al. Towards efficient airline disruption recovery with reinforcement learning[J]. Transportation Research Part E: Logistics and Transportation Review, 2023, 179: 103295.

[19]	Santana M, Vega J D L, Morabito R, et al. The aircraft recovery problem: a systematic literature review[J]. EURO Journal on Transportation and Logistics, 2023, 12: 100117.