基于减少旅客延误的航班中转行程优化

2022-02-25马丽娜孙梦圆

科技和产业 2022年1期

郭梁，马丽娜，王倩，孙梦圆

(南京航空航天大学民航学院，南京 210000)

随着经济的快速发展，人们对出行尤其是远距离出行的需求与日俱增，具备明显速度优势的航空运输逐渐成为人们首选的出行方式。然而目前航空运输单位的运营、管理和协调能力同日益增长的旅客运输量之间还存在着巨大的矛盾，产生了大量的航班和旅客延误现象，导致旅客满意度降低，有损航空公司形象，降低民航行业竞争力。

航空公司和旅客的损失很大一部分是由旅客错过中转造成的，旅客错过航班中转产生的旅客延误极大影响到旅客对航空运输承运人的满意度和忠诚度，如何通过优化行程来减少旅客延误是学者需要研究的重点。Farley等[1]提出了一种基于运筹学的延误时间最小化算法，通过对航班计划进行调整来最小化旅客延误；Farley和Brodsky等[2]提出了一种航班优化算法，减少因航班错过或取消产生的旅客延误；Brunner[3]提出了一种根据地面等待计划调整航班时刻的方法，尽可能降低航班延误及取消时产生的各种成本；Barnhar和Fearing等[4]建立了旅客历史行程的延误模型，使用改进的贪婪算法来计算旅客延误；Maher和Stephen[5]在考虑客流的同时，考虑了航班时刻表、飞机和机组人员的恢复问题；Montlaur和Delgado[6]采用了多种成本函数比较了使航班延误和旅客延误的不同优化策略的差异；Voltes-Dorta等[7]评估了大型机场在关闭时的脆弱性，并将受到干扰的旅客转移到产生延误最少的航班；Mccarty和Cohn[8]通过对延误航班进行预测提前将旅客分配到新的行程，并且进一步调整仍然错过中转的旅客行程；Montlaur和Delgado[9]从航空公司和乘客角度建立公平性指标，在保证公平的情况下减少航班延误和旅客延误。

国内对于旅客延误的研究主要是从航班计划调整和不正常航班恢复角度出发。王飞等[10]以航班正点率、旅客延误时间、延误成本、基尼系数等指标的不同组合为优化目标,建立了多目标优化模型；张静等[11]以旅客整体为对象建立了旅客总体延误时间最小的航班恢复模型；齐莉[12]针对枢纽机场最大化航班衔接水平的特点，构建了航班时刻优化模型对航班时刻表进行优化；杨新湦[13]结合航空公司和旅客的利益建立了航班网络和航班时刻双层优化模型，以航空公司收益；姜思露等[14]针对航班频率的优化问题建立了基于旅客计划延误的航班频率优化模型，使旅客计划延误成本和航班运行成本之和最小；张舜尧等[15]将软备份运力分配在飞行时间和过站时间中建立航班计划优化模型，提高了航班正常率。

通过对国内外研究现状的分析，国内外研究仍存在以下不足：目前国内研究主要是对航班计划进行调整及行程的恢复，并没有考虑错过中转的旅客以及被调整航班上的旅客。为减少中转行程中产生的旅客延误，针对旅客延误较严重的中转行程，建立行程优化模型，在同时考虑后序航班与当前航班旅客延误的情况下对后序航班的离场时间进行调整优化，为中转旅客提供更多预留时间来减少旅客中转中断的情况，最终达到降低旅客延误的目的，并且比较了不同最短旅客衔接时间和选用不同遗传算法时的优化结果，证明了模型和算法的稳定性。

1 中转行程优化模型

1.1 模型优化思路

旅客错过中转的原因往往是由于前序航班发生延误，导致旅客的中转时间不足。本文的优化思路主要是对后序航班的离场时间进行调整，在不增加后序航班旅客延误的条件下使得中转旅客的中转时间能够大于旅客最短衔接时间，进而可以正常中转，以达到降低旅客延误的目标。图1为后序航班时间调整示意图，图中f1与f2为同一中转行程中的前序、后序航班，当前序航班f1发生延误，后序航班f2按照计划离场时间起飞，航班f2离场时间与航班f1到达时间的差值小于旅客最短衔接时间时，航班f1转乘到航班f2的中转旅客将错过中转。此时对后序航班的离场时刻进行调整，为后序航班f2以特定时间为间隔建立z个副本f2,1、f2,2、f2,3、…、f2,z，分别表示航班f2的z个可供选择的离场时间，通过建立的优化模型，在符合航班运行限制的条件下选择一个合适的航班f2的副本，使得后序航班f2的离场时刻与前序航班f1的到达时刻之间的差值大于旅客最短衔接时间，即中转旅客可以完成中转。

图1 后序航班时间调整示意图

在本文的研究中，模型的建立基于以下假设条件：

1)所需要的前序、后序航班的运行计划、中转旅客数量等基本信息完备且已知。

2)所有涉及离场航班调整的航班均为发生航班取消的情况。

3)后序航班可按照特定时间间隔进行调整。

4)航班班次以及航线方案保持不变。

1.2 目标函数

以错过中转旅客与后序航班上旅客的总延误最小为目标建立目标函数，即

(1)

(2)

(3)

1.3 约束条件

为使得调整后的航班能够合理有效地运行，根据航班实际运行限制提出以下约束条件：

1)航班限制约束。后序航班j只能有一个副本作为前序航班i的中转航班，表示为

(4)

2)旅客人数约束。前序航班i上的错过中转至航班j的副本z的旅客人数应小于需要从前序航班i中转至后序航班j的旅客人数，表示为

(5)

3)容量约束。每个时间窗内离场航班总数受到最大离场容量的限制，表示为

(6)

4)航班连续性约束。同一架飞机在按照航班时刻表进行飞行时，如果其中一个航班被调整，那么后续其他航班也会受到影响，所以在调整的时候应该对航班的时间间隔进行限制，连续性航班应满足航班最大最小中转时间的约束，表示为

(7)

(8)

(9)

5)旅客延误约束。考虑到后序航班上的旅客，调整后后序航班上增加的旅客延误应小于不进行调整时旅客错过中转产生的延误，表示为

(10)

(11)

(12)

2 算法设计

遗传算法(genetic algorithm，GA)是一种模拟自然界生物优胜劣汰、适者生存的经典进化算法，具有搜索范围大、收敛速度快等优点，而种马遗传算法(Stud GA)[14]与经典的遗传算法相比具有更快的收敛速度，因此本文采用种马遗传算法对模型进行求解。算法流程图如图2所示。具体算法步骤如下：

图2 种马遗传算法流程

步骤1染色体编码。对于本文提出的中转行程优化问题，每个后序中转航班的副本构成解的集合，所以选择二进制编码，基因片段数由航班副本数决定，每个片段采用0～1编码，编码后染色体一一对应每个航班副本。

步骤2初始化种群。种群的初始化将从后序中转航班j的所有副本z中随机选择组成初始个体，所得到的种群就是一个可行解的集合，在可行解集合中初始化将有利于种群的快速进化。

步骤3适应度函数。根据中转旅客的延误时间构建适应度函数，本文为最小化问题，因此设置其为目标函数的倒数，表示为

(13)

式中：f(x)为目标函数。

步骤4算子设计。采用锦标赛选择策略从当前种群中独立的选择1个父体，然后在剩余种群中独立的选择一个母体，检查父体与母体间的汉明距离，若汉明距离超过设定值，则对进行交叉操作产生子代，否则对母体进行变异产生子代。

步骤5种马策略。选择其他母体重复进行步骤4直到所有母体都被选择，将父体和交叉变异得到的种群进行合并，得到规模为N的新一代种群。

步骤6中止判断。如果迭代次数到达设定的迭代次数，则结束算法，否则返回步骤4。

3 实例验证

3.1 实验设计

选用2013年1月7日以北京首都国际机场为中转机场的旅客行程数据及相应航班运行数据进行验证模型，部分数据见表1。当日内北京首都机场起降航班共计1 521 架次，而参与中转的前序航班和后序航班共有973 架次，占所有航班的64%。在中转行程中，发生延误的前序航班有212 架次，占前序航班总数的近33%。由此可见，有必要对航班中转行程进行时刻优化。

表1 北京首都国际机场旅客客流数据(部分)

根据首都机场发布的中转最短衔接时间(minimum connection time,MCT)，国内转国内的旅客最短衔接时间应为120 min，所以设置旅客最短衔接时间为120 min。设置每个可选择的航班副本间隔为1 min，每个航班有15个可供调整的航班副本，采用Stud GA优化求解，经过多次试验，参数选择为：群体规模为50，交叉概率为0.6，变异概率为0.1，最大迭代次数为500。

3.2 结果分析

按照1.2和1.3节中的目标函数和约束条件，以及2节中设计的优化算法进行算例实施，以航班副本为染色体进行编码，采用锦标赛选择法，在每次迭代时选择部分航班抽样择优进行求解，其目标均值与每代最优值的变化情况如图3所示，可以看出旅客延误在90 代内快速降低，在迭代91 代后达到最优，错过中转旅客与后序航班旅客的总延误由初始的74 517 min减少至52 165 min，旅客延误得到了大幅度降低，由于离场时间为整值，优化调整后的后序航班时刻表见表2。

图3 中转中产生的旅客延误随迭代次数的变化

表2 优化后的后序航班离场时间(部分)

由于机场的中转最短衔接时间可能会根据旅客流量、机场设施、中转程序的变化而进行调整，中转旅客延误的时间也会发生变化，所以本文比较了不同旅客最短衔接时间下模型的优化效果，分析模型在不同条件下的适用性。

随着智能化技术的发展和基础设施的改善，机场中转流程更加畅通和高效，旅客的最短衔接时间也将逐步缩小。对此分别设置中转最短衔接时间为90 min和60 min，采用行程优化模型对其进行优化，结果见表3。

表3 不同中转最短衔接时间下的优化结果比较

由表3可知，当中转最短衔接时间缩短后，代表机场中转水平提高，中转所需要的最大时间缩短，错过航班的旅客人数减少，同时后序航班也不用进行调整，所以旅客延误将会减少。同时通过对不同旅客最短衔接时间设置下的优化结果进行比较，可以看出，虽然优化的程度略有不同，但差异并不明显，整体优化百分比为25%～30%，表明模型有较好的稳定性，可以使中转行程中的旅客延误达到一定程度的优化。

3.3 算法对比

为说明算法选择的合理性，分别使用经典遗传算法(Simple GA，SGA)、增强精英保留遗传算法(Strengthen Elitist GA，SEGA)和种马遗传算法对行程优化模型进行求解，求解时设置旅客最短衔接时间为120 min，3种算法参数均与3.1节中所设参数一致，图4为3种算法迭代对比。

图4 不同算法求解的迭代结果对比

对比图4中采用不同算法求解的迭代曲线，发现Stud GA的收敛速度最快，种群在90代后趋于稳定，种群中最优个体出现在91 代，而SEGA和SGA分别在145 代和275 代时达到最优，在收敛速度上均弱于Stud GA，这表明Stud GA在复杂的搜索空间内，在不牺牲优化效果的前提下，具有更高的搜索能力和稳定性，在解决大规模复杂问题方面具备效率优势。