基于航班延误情况下的登机桥作业调度方法的研究

丁 芳 沙常涛

(中国民航大学电子信息与自动化学院 天津 300300)

0 引 言

登机桥调度包含航班进港和离港使用登机桥的时间段。航班延误原因一般有以下几个因素：天气、空中交通管制、航空公司自身失误、机场作业不当、以及军事活动[1]。航班大面积延误多由天气造成的，延误发生后，旅客就会给航空公司很低的评分反馈[2]，也会降低该机场在航空公司的好感度。航班延误就必然影响到机场登机桥的预调度方案，依靠人工进行登机桥调度效率低且难度大。因此，在延误情况下，建立登机桥动态调度模型对机场运行至关重要。航班延误后需根据延误航班的实时进离港时间及机型对登机桥进行再调度，确保延误航班的地面服务和服务旅客的需求。

针对登机桥多目标调度优化问题，国内外众多学者将多个目标融合进行更全面的研究。2006年，王力、刘长友使用禁忌搜索策略对模型进行调度求解[3]。2013年，文献[4]考虑到旅客满意度及舒适度提出旅客进港用时最短为目标来求解。2015年，陈骁睿提出了改进粒子群算法的调度方法，以各个停机位负载达到均衡和旅客移动距离为最短目标[5]。2016年，李亚玲等[6]提出了一种基于禁忌搜索方法的动态调度方案，此方案以利用率最大化及旅客移动距离最小为目标。同年，薛清文等[7]考虑到航空公司的利益，以航空公司成本最小化及均衡成本为目标，建立了动态分配模型。

在分析某大型机场登机桥配置信息及当天固定时间段航班信息的基础上，本文提出了一种在航班延误情况下的登机桥调度的改进ABC算法。以停靠在远机位航班数、航班与登机桥原有对应关系的改动数及旅客进港用时最短加权之和最小为优化目标的整数规划模型。

1 登机桥调度问题的问题描述

机场多数情况下不需要对登机桥预分配方案进行改动，通常在当航班延误发生时，才需要对登机桥进行动态调度，登机桥调度包括对近机位廊桥和远机位登机梯的调度。本文所提方法基于如下假设：

(1) 机场为单跑道；

(2) 登机桥数量一定，即机场根据当天监控系统，实时统计出可用登机桥，且登机桥数量满足当天航班需求；

(3) 默认机场与航空公司没有签订登机桥强制性使用哪种廊桥；

(4) 所有进港航班均采用先到先服务原则；

(5) 停靠在相邻两个登机桥的航班满足安全的距离。

1.1 符号表

i：航班序列号，表示第i个航班(0≤i≤M)；

k：登机桥序列号，表示第k个登机桥(0≤k≤N)；

xik：第i个航班停靠在第k个登机桥上，则xik=1，否则xik=0；

Wik：航班i预调度在登机桥k的作业时间；

Lik：航班i预调度驶离登机桥k的时间；

Nik：登机桥k的无任务时间；

Ci：航班i的机型，1、2、3分别代表小、中、大型航班；

Bk：登机桥k的类型，1、2、3分别代表小、中、大型登机桥；

Dk：登机桥k的开始可用时间；

Rk：登机桥k的结束可用时间；

Jik：登机桥k服务航班i的时间；

δ：登机桥安全时间间隔；

di：若航班i再分配的登机桥与预分配的登机桥不同，则di=1，否则di=0；

Yi：航班i被分配至远机位，则Yi=1，否则Yi=0；

Uik：航班i从着陆开始停靠到登机桥k所用的时间；

Hik：航班i在登机桥k上的地面保障时间；

zijk：若航班i和航班j停靠在相同登机桥上，且航班j在航班i之后到达，则zijk=1，否则zijk=0。

1.2 航班延误的机场登机桥再调度模型

(1) 停靠在远机位航班数最少 当航班数量过多，近机位廊桥个数无法满足需求时，需要将航班分配至远机位使用登机梯对旅客进行服务。而多数情况下旅客是不希望在远机位登机的，所以要把调度到远机位航班数降到最小，表示为：

(2) 航班与登机桥原有对应关系改动数最小 航班与登机桥原有对应关系改动数应降到最小，可将其表示为：

(3) 旅客进港用时最小 旅客进港用时包括从航班降落至跑道滑行到登机桥及航班在登机桥上所需的地面保障时间的和，旅客进港用时最小公式为：

参考模型的假设条件，约束条件如下：

(1) 每个等待起降的航班必须被调度且只能被调度到一个登机桥。

(2) 登机桥在被调度给某航班的该时间段内，不能将该登机桥再调度给其他航班。即在相同登机桥上，每个航班只能有一个前序航班和一个后续航班。

(3) 根据民航局的规定，相同登机桥前序航班任务离开与后续航班任务的停靠之间必须要有一定的时间间隔，以防止航班发生碰撞等现象。

Wjk≥Lik+δi,j∈N,k∈M,Wjk≥Wik

(7)

(4) 由于航班靠桥后地服人员还需对航班进行安全检查及航餐、加油的服务，因此同一航班任务驶离登机桥时刻与靠桥时刻的差应大于登机桥实际服务航班的时长。

Lik-Wik≥Jik

(8)

(5) 使用同一登机桥的相邻两个航班任务之间的空余时间，等于后面航班的预进港时间减去前面航班的预离港时间。

Nik=Wjk-Liki,j∈N,k∈M,Wjk≥Wik

(9)

(6) 由于受登机桥端口高度和航班机舱高度的约束，小型航班只能停靠小型登机桥，中型登机桥可以停靠中、小型航班，大型登机桥可以停靠大、中、小三种航班。即航班类型只能小于等于需停靠的登机桥的类型。

Ci≤xikBk

(10)

(7) 小、中、大型航班类型Ci及小、中、大型登机桥类型Bk从小到大都分别用1、2、3表示。

Ci={1,2,3}Bk={1,2,3}

(11)

目标函数表示为调度员在已知延误航班信息的基础上，以调度到远机位的航班数、航班登机桥原有对应关系的改动数及乘客进港所用时长加权之和最小。登机桥再调度模型的目标函数为：

minF=αF1+βF2+χF3

(12)

式中:α=0.3，β=0.3，χ=0.4，代表每个子任务的权重。不管是航空公司还是机场，最终目的都是服务乘客，所以权重应适当大一些。

2 改进的人工蜂群算法

算法与登机桥再调度模型的映射关系如表1所示。

2.1 构造食物源编码

采用二进制编码方式进行食物源编码，设现有N个航班要分配给M个登机桥，x为N行M列的矩阵。每个航班都在M个登机桥中取值，每个种群初始解都有N×M个基因，每个基因取值只有0或1。

其中xik=1表示将第i个航班分配给第k个登机桥，否则xik=0。

2.2 种群初始解

种群初始解的质量直接决定了最终解的质量高低，种群初始解分布越均匀，范围越大，就会更容易产生最优解。

进行登机桥再调度问题时，应考虑登机桥调度的各种约束条件和降低登机桥再调度对原预调度方案的改动性，因此，采用贪婪算法产生初始可行解。由如下搜索步骤产生：

步骤1：读取登机桥原调度方案，删除延误航班的登机桥预调度方案。

步骤2：读取延误航班信息，将n个延误航班按进港时间Wik升序排列，得到延误航班排序队列FN=fi(i=1，2，…n)。

步骤3：从Fn中选出一个延误航班fi，根据约束条件，计算其目标函数值，在可选登机桥集合中选取目标函数值最小的登机桥分配给该延误航班，更新该登机桥的开始可用时间Dk和结束可用时间Rk，从FN中删除fi。

步骤4：判断FN集合是否再无取值可能，如果无取值结果，则输出相应的延误航班的登机桥再调度方案，否则跳转至步骤3继续往下执行。

初始可行解的搜索流程如图1所示。

图1 初始可行解搜索流程图

2.3 适应度评价函数

本文中，采用文献[8]的对数适应度评估方式，将各种群间的差异区分开来，改进后的适应度评价方式为[8]：

2.4 改进局部搜索机制

原始ABC算法中，全局搜索较好，但后期局部搜索的随机性太强，易陷入局部最优，导致对种群初始解没有充分地搜索。对于文献[12]中只是将每一代中的最优解提取出来加入到跟随蜂及侦察蜂的搜索策略当中，容易导致更优解的丢失。所以本文提出一种基于Logistic混沌搜索的更优解改进策略，在每一代中最优解的基础上，再进行k次的混沌迭代搜索，并且将更优解策略加入到跟随蜂及侦察蜂的搜索策略当中，这样更容易找出更优解。

原始logistic混沌映射为：

xk+1=μxk(1-xk)

(14)

式中：k为迭代次数，k=(1,2，…，K)，K为最大迭代次数。当μ=4时，y1∈(0,1)，且y1≠(0.25,0.5,0.75)，此时，式(14)是一个混沌系统。

本文采用文献[9]的映射模型：

xk÷1=ωxk-2tanh(ξxk)exp(-3xk2)

(15)

当μ=4，y1=0.65，ω=0.5，ξ=2.7时，式(14)及式(15)对应的混沌系统如图2和图3所示。由图可知，式(14)混沌系统产生的解分布在(0,1)之间，式(15)混沌系统产生的解分布在(-1,1)之间。在产生最优解的过程中，由于引进了当前代最优解的概念，所以选择式(15)产生的随机序列有更大的范围及更好的遍历性，能产生较高质量的个体。

图2 式(14)混沌系统

图3 式(15)混沌系统

2.5 改进跟随蜂局部搜索策略

跟随蜂在雇佣蜂搜索完成产生的最好个体xgbest基础上再次搜索更好个体[10-11]，然后在xgbest附近根据式(16)再进行k次混沌搜索，得到k个个体，比较k个个体中质量最高的个体作为xkbest，比较xgbest与xkbest的适应度值，选择大的成为最优个体xbest。本文中观察蜂搜索就是将某个航班在其可停靠的登机桥集合里重新选择一个登机桥进行替换。

在xgbest附近进行混沌搜索的公式为：

yk=xgbest+xk

(16)

产生新食物源的更新公式为Vik：

Vik=xbest+τ(xik-xbest)+φ(xr1,k-xr2,k)

(17)

式中:i=1,2,…,SN；k=1,2,…,D；gbest表示当前代最优个体，r1、r2表示邻域内随机解，D表示解的维数,SN表示种群数量，φ在[-1,1]随机取值。τ为比例系数，大小为[12]：

式中：iter是当前迭代次数，MCN为总迭代次数。

2.6 改进的侦查蜂局部侦查策略

在进行局部搜索时，原始ABC算法侦查峰没有很好地找出更优食物源的能力，易陷于局部最优。在本文中，侦察蜂搜索即航班随机的变换登机桥，形成新的候选解，每次搜索产生的候选解数量与种群规模保持一致。搜索时，在依靠跟随蜂最优解基础上加入比例系数策略，如下式所示：

Vik=xbest+rand(0,1)×τ×xbest

(19)

2.7 改进后的人工蜂群算法的流程

改进后ABC算法工作流程图如图4所示。

图4 改进ABC算法的流程图

3 仿真实验及分析

基于国内某大型机场某时间段的航班信息进行仿真实验，航班信息如表2所示。

表2 航班信息表

续表2

根据机场实际距离及民航运输标准[13]计算出的各个阶段的用时如表3所示。数字序号1-8代表远机位登机梯，航班到达时所需的靠桥用时为3.5 min，101-108代表近机位廊桥，所需的靠桥用时为5 min。只有远机位需用摆渡车。

表3 登机桥类型及停靠用时 min

登机桥预调度方案如表4所示。

表4 登机桥预调度方案

在进行模拟登机桥再调度时，在这32个航班中选择任意8个航班作为延误航班，航班延误信息如表5所示。

表5 航班延误信息表

通过上文提出的改进人工蜂群算法与所建立的航班延误的登机桥再调度模型进行求解，需对参数初始化，SN=32，D=16，MCN=3 000，Limit=50，K=200。登机桥使用最小时间间隔δ=5 min。实验采用MATLAB R2014a进行仿真，选择第100,200,…,3 000代的目标函数值仿真出的收敛曲线对比图如图5所示。

图5 目标函数收敛曲线

由图5可知，文献[12]提出的MMABC在1 000代前算法的收敛速度快，但是之后的收敛速度接近于0，且没有达到收敛的条件，也没有产生可行的解。未加混沌特性且改进了适应度评价方式后的ABC算法在1 000代前期收敛速度较快，且1 000代以后的收敛相较于MMABC效果更好，只能产生可行解，目标函数值为148.3 min。加入混沌搜索后的改进ABC算法的图像收敛速度更快，产生更优解的时间明显缩短，这不仅与所需要的进化次数和群体规模有关，而且还与当前迭代的初代个体有关，初代个体的质量越高，就更容易达到更优解，目标函数值为142.6 min。

登机桥再分配方案如表6所示。

表6 登机桥再调度方案

分析实验结果表明：

(1) 航班登机桥原有对应关系的改动数变小 在选择的8个延误航班中，有4个航班被指派到与预调度方案相同的登机桥，4个航班被分配到别的登机桥。对登机桥再调度后，有6架航班登机桥进行了调整，分别为第3、15、19、21、24、29。

(2) 航班可能停靠在近机位廊桥的概率增大 在延误航班中，第6、11、21、24号航班进行了靠桥，当将延误航班全部安排到远机位登机梯时，靠桥率为0%，根据以上方法靠桥率达到了50%。

(3) 减少了旅客进港用时总和 若将延误航班全部安排到远机位，则按照预调度的远机位登机梯安排方案如表7所示。

表7 预调度的远机位登机梯安排方案

按照此方案，延误航班进港用时总和为123.9 min，按照本文的优化方案，延误航班的进港用时总和为104.55 min，减少了旅客的进港用时。

4 结 语

本文研究了在航班发生大面积性延误时，机场对登机桥的再调度问题。考虑了顾客满意度、登机桥类型、航班类型及航班的进离港时间等因素，以减少使用远机位登机梯的航班数、减少对原调度方案的改动性及减少旅客进港用时为目标。根据机场实际标准建立约束条件，建立了航班延误时登机桥再调度的多目标模型，以国内某机场航班延误情况为实验样本，验证了所提方法的可行性。本文所研究的登机桥再调度问题属于再调度的NP-hard问题，目前还没有找到可以高效解决该问题的方法，本文根据改进的ABC算法仿真结果来看算法的收敛性较好。结合模型、算法和实验数据进行仿真研究，证明了实验得出的登机桥再调度方案在三个目标上都得到较优的效果。后续工作还要去深入分析机场登机桥在多跑道条件下的多目标综合调度问题，并设计出更合理有效的调度求解方法，以此来获得更优的调度方案是未来工作的关键和难点。