不正常航班恢复模型和算法研究

主要根据2017年中国研究生数学建模竞赛中的航班恢复问题,探讨航班遇到突发情况时,如:机场在某时间段关闭,如何按照不同要求重新规划航班,使得旅客总延误时间或航班总延误时间尽可能短.航班恢复是一个NP-Hard问题,根据竞赛所涉航班恢复的4个子问题,分别根据其特有的约束条件和飞机间调整所需额外成本的计算办法,建立了相应的混合整数规划模型.通过先检测不正常航班的相关信息如延误扩散情况,再选择航班恢复计划使延误尽可能小,给出了启发式算法求解上述规划模型.进一步,对航班恢复问题所涉及的前3个子问题,分析了其延误时间下界,并与算法所得的延误时间进行比较,发现算法所得延误时间等于或者非常接近估计下界,这说明算法所得新航班计划是最优的或者非常接近最优航班恢复计划.     

多机型航班恢复问题研究

主要研究了基于航班延误时间最短的航班行程规划问题,分别建立了最基本的多机型航班恢复问题模型、考虑旅客行程重新规划的航班恢复问题模型.在约束条件下,先在单机型航班恢复的基础上考虑多机型航班恢复,最后考虑基于飞机载客量的多机型航班恢复.构建时空网络模型,结合改进的分支定界法和启发式算法,确定筛选范围,调整不同的影响范围,达到较优的结果.对于多机型航班恢复问题,得到航班总延误时间为12850分钟.接着分析考虑飞机载客量的多机型航班恢复问题,分析建立的模型得到航班总延误时间为约1886650分钟.建立的模型有较好的鲁棒性,且具有较好的实用性.     

基于路径置换的航班恢复问题研究

探讨了第十四届中国研究生数学建模竞赛提出的OVS机场因某一段时间关闭而产生的航班恢复方案制定问题.建立Time-space Network模型,通过遍历法解决单机型的航班恢复问题,得出航班延误的最小时间.其次,针对多机型的航班置换与恢复问题,运用匈牙利算法处理约束条件,以航班延时成本最小值为目标函数,得到较好的航班时刻表.最后在考虑旅客流情况下,增加约束条件得出了旅客的整体延误时间.     

航班恢复规划的数学建模

针对第十四届全研究生数学建模竞赛C题的航班恢复规划问题展开研究,将多机场问题简化为双机场航班重排问题,研究了中枢机场应急关闭之后航班的规划.首先,建立了单一机型的航班恢复模型,通过飞机置换使该机型航班航班延误总时间最小.然后,引入多机型及不同机型交换成本,建立多机型,双机场的类时空网络模型,并引入航班串的概念,进一步减小航班重排后的整体延误时间.最后,增加旅客总体延误时间的考虑.进一步考虑航班之间不同机型交换带来的影响,将计划起飞时间位于18:00到22:30的航班,在21:00到22:30时间段中进行重新排列.通过Lingo计算包括航班延误,航班取消和飞机置换的方法所有航班的最小化延误.     

基于大系统分解协调的CDM下不正常航班恢复优化

针对不正常航班恢复以及民航调度系统中空管、机场和航空公司之间复杂的协同调度问题,设计了一个基于大系统分解协调的不正常航班调度系统分解方法.首先简述了基于CDM的航班调度系统结构及原理,然后针对不正常航班恢复所涉及的各参与主体利益需求,建立分解级协调级多级递阶结构的不正常航班恢复优化调度模型,对分解后的各子系统模型采用遗传算法优化求解.最后通过东北空域内各主要机场航班调度的算例验证分析,结果表明采用方法能够减少航班延误时间,提高航空管理和服务质量,为具体工程应用提供决策支持.     

基于优先级的进离港航班排序优化问题研究

研究机场终端区进离港航班排序优化问题,对于提高跑道利用率以及降低航班延误损失具有重要意义。本文首先考虑航班运行方式(降落和起飞)、飞机类型以及航班的重要程度(航程是否连续)的不同所造成延误损失的不同,设计三维优先级表反映调度优先等级,并将其转化为延误成本系数。其次,为实现调度的公平性和减轻管制人员的工作负荷,设置允许延误的航班架次约束、邻边约束以及最大限制位置约束。再次,以最小化航班总延误成本为目标建立模型,提出相应的改进蚁群算法(GJAC)进行求解。最后通过数值实验验证所提算法在考虑调度优先等级及上述约束条件的同时能有效减少进离港航班队列的总延误成本。     

机场放行能力约束条件下的航班延误波及分析

航班延误影响机场和航空公司的正常运行,同时给旅客出行带来不便,因此,对航班延误的预测分析具有重要的现实意义.在机场放行能力约束条件下,分析航班延误波及情况,对延误时长进行定量预测.以航班历史数据为学习样本,计算在前序航班延误的影响下,后续航班在不同延误等级的初始条件概率,并按照航班优先级以及预测时段机场的放行能力约束,对初始条件概率进行修正,从而对航班延误时长进行短期预测.最后通过实例分析,结果表明考虑机场放行能力约束,提升了航班延误预测的准确度,验证了方法的有效性.     

基于并行GRASP的不正常航班调度算法

将并行计算与GRASP结合,设计了一种新的基于并行GRASP的不正常航班调度算法,给出了详细的算法流程与步骤;同时考虑了使用备用飞机、延误航班与取消航班等不正常航班调度策略,通过并行GRASP算法优化了构造的飞机路线和取消路线组成的初始解,给出了每架飞机新的航班路线和航班取消路线。国内一家中等规模航空公司实际算例的结果证明了算法能有效降低以往算法的时间复杂度,明显提升运算效率,可用于较大规模的不正常航班调度运算。     

空中交通流量管理中的改航策略研究

针对在恶劣天气下出现的大规模航班延误情况,根据机场和航路段的动态容量约束,建立了改航策略模型,并提出求解该模型的有效算法.选择全国航班时刻表进行仿真,仿真结果表明:该模型提供了在恶劣天气下更安全、更经济的航班改航策略,可为战术级流量管理提供辅助决策.     

基于序贯决策的航班恢复方法

针对枢纽机场临时关闭后的航班恢复问题,提出了一种新的调度方法,为实时航班恢复提供了新思路.通过重新定义恢复操作,将多变量复杂约束的航班规划问题转化为约束条件简单的序贯决策问题.新方法以原始航班计划为基础,按时间顺序对各时刻的机场起降航班流量约束进行冲突消解.在每一决策时刻,推理计算各航班推迟成本,优先安排成本高的航班起降.测试用例表明,新方法能够为繁忙枢纽机场临时关闭后的多机型航班恢复问题快速地给出最优调整方案.将模型拓展应用于飞机旅客一体化恢复问题,也能够迅速获得调整方案.     

航班登机口分配问题的数学建模

登机口作为机场的重要组成部分,其资源利用率直接影响航班服务的效率.针对不同的优先级建立多目标规划模型对航班进行优化分配,采用贪心算法和禁忌搜索算法,结合登机口类型、航班时间的约束,逐次对最大化分配航班问题、最小化中转旅客最短流程时间问题、最小化旅客总体紧张度问题进行建模求解.结果表明该算法不仅提升了求解速度,并且在航班登机口分配问题中展现了较好的综合寻优能力.这对民航机场实现经济效益、提高旅客满意度有一定的参考价值.     

基于粒子群算法的航班舱位控制研究

首先介绍了收益管理提出的背景思想,在对航班收益管理基本概念作简要阐述的情况下,给出了期望边际座位收入理论.提出了在北京到上海的单航程航段下,航空公司会提供出发时间不同但航程相同的连续两个航班.旅客在没能购买到期望的航班舱位时,会以一定的概率选择购买下一航班的机票或者取消订票,改乘其他交通运输工具.旅客对于某一航班的座位需求主要由固有需求和上一航班需求的转移两部分构成.基于这样的角度建立了两航班机票预售模型,不考虑动态订座,no-show和超售等情况,并利用算法对模型进行了求解和分析.最后得出结论当航班票价等级数量较少时,为高票价等级安排较多数量座位可提高航班收入.而当航班票价等级数量比较多时,为低票价等级多安排一些座位可为航班提高收入.     

基于梯度提升决策树的航班延误分类预测

考虑航空交通网络状态特征对航班延误的影响,将上游的航班延误状态特征加入到预测因素中,并使用梯度提升决策树(Gradient Boost Decision Tree,GBDT)的方法构建了航班延误预测模型.与以往的决策树算法、SVM分类算法、RF算法相比,GBDT算法在航班延误分类预测上具有更高的准确度,可有效提高机场运行管理效率.     

基于动态环境的机场航班实时调度优化研究

在对天气、空中管制等动态环境引起航班延误所造成的各主体利益损失分析及目标追求的基础上,建立单一机场航班动态实时调度微调两阶段优化模型,其中目标函数为追求航空公司、乘客利益和机场保障的经济损失加权和最小化,采用遗传算法优化求解.从最大效率利用终端区空域的角度,评估航班调度方案.具体的算例表明采用本方法能依据动态环境不断优化微调需更新的航班时刻表,达到兼顾各方利益提高机场综合服务水平的目的,证明了方法的可行性.     

基于替代航路的进场航班排序优化方法

针对机场终端区航班延误日益严重的现状,为减轻空中交通管制员工作负荷,缓解航班延误,研究了进场航班排序优化问题.通过引入替代进近航路和时间偏差成本的概念,建立了进场航班排序模型;基于调度窗口和冻结范围概念,提出了动态优化方法;结合进场航班排序模型与动态优化方法,以国内某机场的运行数据进行了仿真验证.仿真结果表明:与实际运行相比,基于替代航路的进场航班排序优化方法优化效果显著,减少了约25%的进场航班延误,提高了机场终端区航空器的运行效率.优化方法可以即时获得最优方案,辅助空中交通管制员做出决策.     

基于最小延误时间和经济成本的空中高速路匝口排序研究

空中高速路是解决空域资源紧缺问题的一种新途径.在建立延误时间成本最小的空中高速路匝口航班排序模型的基础上,分析并得出了航班延误经济成本函数,建立了基于最小延误时间和经济成本的空中高速路匝口航班排序模型,并利用NSGAII算法进行求解.最后利用不同时段的航班数据进行算例仿真,计算航空器进入空中高速路的时刻及其延误成本.结果表明,与先到先服务策略相比,提出的优化模型对于单个航班的延误时间成本、经济成本和累积经济成本分别降低47.2%,51.3%和54.4%,模型与解法可行.     

基于多目标规划的飞机路径恢复最优化算法研究

本文针对同一机场中同机型的多架飞机受到干扰后, 飞机路径恢复的多目标最优化问题进行研究。首先根据航空公司实际航班调整的常用原则和航班干扰管理的基本思想, 基于连接网络建立多目标规划模型, 其中两个目标按照优先级排列:第一个目标为最小化航班的最大延误时间, 第二个目标为最小化参与交换的飞机数量。然后根据该问题的航班波结构特点, 结合求解多目标规划的分层序列法, 分析优化问题的若干最优性质, 并基于快速排序算法和最小费用路算法设计出多项式算法。最后用算例验证了算法的有效性。该研究结果可以为航空公司减少航班延误提供理论和技术支持。     

单架飞机受干扰后飞机路径恢复多项式算法研究

飞机路径恢复是航班调整中保证航班能够运行的必要条件之一,而传统目标下的飞机路径优化问题是NP-hard的。本文针对单架飞机受到干扰后,基于最小最大目标的同机型飞机路径最优化问题,给出了一个新的多项式时间算法。首先基于航空公司调整航班的常用原则,提出把最大航班延误时间最小化作为问题的目标。然后根据问题的一些特点和目标形式,设计出解构造算法,得到飞机路径恢复问题的最优解,并分析出算法的复杂度为O(n²)。相对于一般的最小最大二分图匹配算法(复杂度为O(n³log(n))),该算法具有较小的时间复杂度。最后用实例验证了解构造算法的有效性。该研究结果将为航空公司减少航班延误提供理论和方法支持。     

考虑航站楼扩增对中转旅客影响的登机口优化调度模型

机场新增卫星厅,在优化分配登机口的同时需要考虑最小化旅客行走时间该方面学术研究有限,充分考虑航站楼扩增对中转旅客的影响,建立综合的登机口优化调度的模型.设计无向图着色模型,提出基于禁色影响度的贪婪着色算法,设计内层深度模拟退火与外层浅层模拟退火相结合的双重退火优化算法,引入乘客换乘因素,考虑失败惩罚,提出基于社群联盟冲突消解原则的图着色优化算法,实现对模型的优化,得到最佳调度方案.     

基于多目标优化的改航策略研究

随着我国航空运输的快速发展,由恶劣天气等原因导致的航班延误日益增多.传统的改航策略选取总延误损失最小为单一目标,不仅难以满足流量管理不同对象、不同阶段的需求,而且易造成空域利用率偏低.首先将改航策略与地面等待和空中等待相结合,然后综合考虑航空公司的利益,建立多目标优化模型,并采用稳定性和健壮性较强的多目标进化算法求解.最后选取全国典型繁忙日的实际飞行计划,进行了仿真验证.仿真结果表明,策略不仅可为航班动态地选择航路以避开容量限制区域,还可供流量管理部门参考不同目标来确定改航方案.