考虑时间执行偏差的多目标机位分配问题

朱承元，王志巍，王毅鹏

（1.中国民航大学空中交通管理学院，天津 300300；2.中国国际航空股份有限公司运行控制中心，北京 101312）

机场场面运行复杂多变，场面滑行、场面车辆调度以及机场的天气情况等因素都会影响机位的实际运行时间，基于机位计划运行时间产生的机位分配方案与实际运行存在较大的时间执行偏差。由于机位分配方案的关联性，当执行偏差过大时，会增大场面车辆的调度频率，从而增加指挥的难度，同时增加场面冲突的次数，不仅会影响机场运行效率，也增加机场运行风险。因此，对减少机位时间执行偏差问题的探讨与研究是当前提高机位分配效率与安全性的关键。

张晨等[1]提出了基于概率论的晚点传播方法，以连续同机位航班间隔最小为目标并通过禁忌搜索算法进行求解；Dorndorf等[2]将最大化的航班缓冲时间作为目标，减少场面运行的随机扰动影响；卫东选等[3]提出了主动避免潜在冲突的模型，在相邻机位之间加入了安全时间间隔，以机位空闲时间均衡为目标，将其转化为线性问题求解；李军会等[4]统计分析不同航空公司的延误水平对航班时间间隔进行了分析，以机位冲突概率最小为目标，使用贪婪禁忌算法[5]求解；冯霞等[6]以北京首都国际机场实际运行数据为依据，分析时间偏差规律，建立了缓冲时间成本函数，使用禁忌搜索算法进行求解；孙淑光等[7]以最小空闲时间、最大机位使用效率为目标，将遗传算法与禁忌搜索算法组合求解并与单一禁忌搜索算法进行对比。

以上国内外学者针对机位分配方案执行偏差较大的问题都在机位计划运行时间的基础上加入一定的缓冲时间，减少滑行冲突、场面车辆调度、机场天气等随机事件对机位分配方案的影响。这种加入缓冲时间的方法一定程度上减少了随机事件对机位分配方案产生的扰动以及场面滑行中产生冲突的概率，增加了分配方案的鲁棒性，但加入缓冲时间也增加了航班占用机位的时间，从而一定程度上增加了机场运行成本，降低了机场运行效率，机位时间执行偏差大的问题并没有得到有效解决。

为减少机位计划运行时间的执行偏差，使用全空域与机场建模工具（TAAM，total airspace and airport modeller）建立跑道、滑行、机坪一体化机场场面模型，模拟场面实际运行情况，对计划时间进行模拟仿真，优化生成机位时间执行偏差较小的初始机位分配方案，再通过基于熵权法的禁忌搜索算法求解兼顾旅客、机场、航空公司三方面效益的多目标模型。

1 多目标机位分配模型

1.1 模型假设及符号定义

针对多目标机位分配模型进行如下假设：

（1）运行开始时所有机位可以使用；

（2）机场拥有充足的机位资源，可以为执行每一个航班的飞机分配一个可行的机位资源；

（3）机位分配优化所需的基本信息是完备、确定、已知的；

（4）飞机从脱离跑道滑行至任一机位的滑行路径固定且已知。

模型变量定义如表1 所示。

表1 模型变量定义Tab.1 Definition of variable of the proposed model

1.2 模型建立

机位分配问题涉及到旅客、机场、航空公司三方面利益，因此对旅客行走距离、机场运行效率及安全、航空公司效益等方面的单一变量建模并不能较好地解决机位分配的实际问题。为兼顾三方需求，分别构造基于旅客、机场、航空公司利益的目标函数。参考相关文献[8-9]，分别以旅客总行走时间、总机位占用不均衡度、各航空公司航空器平均滑行距离均衡为目标函数，并加入相邻机位的安全间隔等约束建立多目标机位分配模型。

1.2.1 目标函数

l 为航空公司数量；| | 表示集合中元素的个数；式（1）为旅客目标，表示旅客登机总用时最少；式（2）为机场效率目标，表示机场所有机位使用时间的不均衡度最小；式（3）为航空公司公平性目标，表示各航空公司平均滑行距离的不均衡度最小。

1.2.2 约束条件

式中：约束（4）表示航空器只能占用一个停机位；约束（5）表示前后连续进入相同机位的航班顺序；约束（6）表示同一机位进出避免冲突的安全时间间隔；约束（7）～（9）表示相邻机位进出航班之间3 种情况的安全时间间隔；约束（10）表示航班机型符合机位可停靠机型；约束（11）～（13）表示模型各参数的取值范围。

2 算法实现

2.1 算法设计

通过TAAM 产生机位分配的初步方案，并基于熵权法[10]使用禁忌搜索算法实现多目标机位分配模型求解，算法思想如下。

（1）为解决分配方案执行偏差较大的问题，使用TAAM 仿真模型根据原始计划航班信息数据进行模拟仿真。在TAAM 中加入机场实际起降、滑行、停靠规则，并设置滑行路径、速度、机位使用限制、跑道方向等约束，加入滑行油量、滑行速度的随机性，滑行冲突的自动解脱，使仿真模型更精确地模拟机场实际运行。根据上述运行条件利用TAAM 对计划机位运行时间进行初步优化，产生与实际运行场景机位时间执行偏差较小的机位运行时间，并产生没有优化要求但实际可行的初始机位分配方案，作为禁忌搜索算法求解的初始方案。

（2）为解决多目标求解过程中人为因素影响较大的问题，在禁忌搜索过程中加入熵权法将多目标问题转化为单目标问题进行求解。该方法可以避免专家打分法、分层序列法[11]等由于打分或优先级的确定等人为因素带来的影响，使权重计算更具有客观公正性。

（3）为加快寻优速度，改进随机选择的邻域搜索方法，将机位代号按照机位占用时间由长至短进行排序。插入操作，选择排序靠前的机位作为操作对象，随机选择该机位的几个航班插入排序靠后的机位；互换操作，选择排序靠前和靠后的两个机位作为操作对象，分别从两机位随机选择一个航班进行机位互换。

2.2 算法步骤

机位分配算法步骤如下。

步骤1将计划航班信息和滑行、机位等参数输入TAAM中，仿真得到一个可行的初始解x0=（α1，α2，…，αm），m 为参与分配的航班数，αi表示i 号航班停靠的机位代号。

步骤2将初始解输入禁忌算法，并加入禁忌表。

步骤3设置终止准则final，即最大迭代次数。

步骤4判断当前迭代次数fi，若满足fi≥final 则输出结果，不满足则继续步骤5。

步骤5从当前解出发搜索其邻域，通过下列两种操作分别得到两个候选解。

计算出当前解在各个机位的占用时间，并排序Tk≥…≥Tl：

1）插入操作

将解分配在k 机位的i 号航班，重新分配至d 机位，得到x1解，即

2）互换操作

将x0解分配在k 机位的e 号航班与分配在l 机位的i 号航班进行机位互换，得到x1解，即

按照机位排序依次搜索邻域，选取候选解x1，x2，x3，x4。

步骤6对多目标模型利用熵权法[9]处理Zi，1≤i≤3，x∈{x1，x2，x3，x4}，生成决策矩阵（Z1，Z2，Z3）×（x1，x2，x3，x4）T。对决策矩阵进行归一化处理，并计算信息熵、权重向量（λ1，λ2，λ3），得到候选方案的当前综合属性值，即

步骤7若满足藐视准则wi≥w，w 为3 个目标函数值的综合特征值，结果直接作为下次搜索的当前解；如果不满足，则将非禁忌对象的各候选解通过结果排序筛选出当前最优解xi。

步骤8将xi代入步骤4 继续搜索。

算法流程如图1 所示。

图1 算法流程图Fig.1 Flow chart of algorithm

3 实例计算

3.1 数据来源及参数设置

选取兰州中川国际机场2019 年某日8 点—24 点中国国际航空股份有限公司、中国南方航空集团有限公司、中国东方航空集团有限公司、海南航空控股股份有限公司、四川航空股份有限公司5 个航空公司共50 个航班。航班计划信息如表2 所示（只列出部分航班信息）。

表2 航班计划信息表Tab.2 Information table of flight plan

机场使用18 号跑道运行，设定所有航班通过A5快速脱离道脱离，起飞通过A1 滑行道进入跑道等待起飞，滑行距离按照上述运行计算。所有机位全天开放，按照该机场管制实际运行规定，上述航空公司可使用机位（近机位101～107，远机位201～207）及机位信息如表3 所示。为了便于计算求解，将航班按表格顺序编号为1～50（只列出部分机位数据），将停机位101～107、201～207 分别对应机位1～7、8～14。

表3 机位信息表Tab.3 Information table of gate

其他条件：飞机滑行速度为15 km/h；由于近、远机位旅客登机方式不同，近机位旅客行走速度按照正常人5 km/h 计算，远机位旅客乘坐摆渡车按照平均行驶速度15 km/h 计算；避免冲突的安全间隔，分别取同机位安全间隔15 min，相邻机位安全间隔5 min；禁忌搜索算法循环迭代次数500 次。

3.2 过程与结果

图2 的TAAM 仿真运行界面中，棕色数字为机位代号，白色为航空器呼号，红色线条为滑行道中线，淡蓝色矩形为跑道。

图2 TAAM 仿真运行界面Fig.2 Operation interface of TAAM simulation

通过TAAM 对机位预计时间处理后，机位初始分配方案甘特图如图3 所示。

图3 TAAM 初始分配方案甘特图Fig.3 Gantt chart of TAAM initial solution

禁忌搜索算法每次迭代产生的综合属性值以及最佳综合属性值出现的迭代序列如图4 所示。

图4 综合属性值变化曲线Fig.4 Change curves of synthetic attribution value

算法求解结果的机位分配方案如图5 所示。初始解、最终解等迭代解的各目标值结果如表4 所示。

图5 优化结果甘特图Fig.5 Gantt chart of optimized results

表4 算法结果Tab.4 Resolution results of algorithm

3.3 机位时间执行偏差验证

将最终机位分配方案输入TAAM 仿真模型，模拟实际运行情况下该分配方案的机位运行时间。以TAAM 仿真验证模型机位运行时间为基准，对比计划时间、算法最终解与其执行偏差，如图6 和图7 所示。

图6 进入机位时刻执行偏差图Fig.6 Time execution deviation for entering the gate

图7 离开机位时刻执行偏差图Fig.7 Time execution deviation for leaving the gate

3.4 结果分析

从图4 中Matlab 产生的目标曲线可以看出，算法迭代次数到达33 次时，综合属性值达到了最佳，得到各目标值结果，如表4 所示，旅客总登机时间下降了8%，机位占用的不均衡度下降了7%，航空公司滑行的不均衡度下降了13%。旅客登机耗时、机场机位使用的均衡性、航空公司的公平性都得到了一定的改善。图6—图7 的TAAM 验证结果表明，优化后执行偏差明显小于机位计划时间产生的执行偏差，且与TAAM模拟实际时间执行偏差较小。

4 结语

使用TAAM 对机位计划运行时间进行优化处理可以有效减小计划时间产生的执行偏差，且可以避免使用增加缓冲时间方法而产生额外的机位占用时间，在降低执行偏差的基础上，使用较客观的熵权法，综合旅客、机场、航空公司三方面利益进行机位分配策略的优化。在保证旅客登机耗时较短、航空公司较公平的基础上，提高了机位分配方案与实际运行的匹配程度，增加了分配方案的抗干扰性，有效地减少场面指挥、车辆调度、人员配置的工作负荷，从而提高了机场的运行效率。