基于改进NSGA-Ⅱ算法的飞机牵引车安全调度

钟建华

(中国民航局 第二研究所； 成都民航空管科技发展有限公司， 成都 610041)

航班停机坪作业是航班运行的重要环节，航班都要在这完成上下旅客、装卸货物、添加燃油及接受各种补给和服务工作。每一架航班起飞前和降落后至少有十多辆地面车辆围着它给它提供服务，因此，作业车辆调度是航班停机坪作业的重要环节，而机坪牵引车的调度是车辆调度中最难以调控的，特别是在以往运行中，由于缺乏机位保障各作业的关键节点时间，机坪牵引车调度依赖于车辆调度部门的人工经验，容易出现由于牵引作业而导致的航班延误。

在以往关于机坪保障作业车辆调度研究中，邵晓根对飞机牵引车辆在推出开始时间、推出作业耗时不确定的情形下，把问题看成模糊job-shop问题，并利用混合遗传算法来进行求解[1]；朱新平等人采取Petri网建立机坪过站保障作业模型，并开展了多种保障车辆作业集中式调度算法研究[2]。总体来看，以往研究多把机坪保障车辆调度问题视为基于时间窗的车辆路径规划问题即VRPTW(Vehicle Routing Problem with Time Windows)，多采用Insertion Heuristic、Large Neighborhood Searc(LNS)和Multi-objective optimization进行求解，由于缺乏A-CDM(机场协同放行)系统的支持，难以确定各机位保障作业的具体开始时间导致无法更新各机位航空器预计关舱门时刻，使得求解结果难以满足实时运行保障的需求。

随着A-CDM系统在各机场运行控制中心的广泛应用，机位保障关键作业节点时间能够及时获取，本文基于A-CDM系统提供的实时运行数据，对机坪牵引车调度展开研究，针对单一保障责任区内的牵引车资源调度，分别建立以某一时段内牵引车保障造成的航班运行延误总时长最小和牵引车行驶耗时最小的多目标优化函数，利用A-CDM系统提供的实时的各机位飞机预计关舱门时刻，按照预计关舱门时刻早的飞机先接受服务的原则，对4台牵引车为50架飞机进行牵引作业为数据，采用改进后的NSGA-II算法进行求解得到不同安全调度策略，并对各策略进行了分析。

1 问题分析与建模

1.1 问题分析

牵引车保障作业过程是指牵引车由停放区开出，行驶到指定机位提供飞机牵引服务最后回到停放区的过程，如图1所示。实际运行中，通常会划定某一机坪区域为一定数量牵引车辆的保障责任区。A-CDM系统可用来更新各机位航空器的预计关舱门时刻，基于FCFS原则可确定航空器的推开排序。进一步地，考虑相应机场关舱门至开始推出所耗时长经验数据，可确定各航空器推出的预计开始时间。本文在航空器推出排序既定的前提下，开展单一机坪保障责任区内的牵引车安全调度问题研究。

图1 飞机牵引作业车辆调度过程

1.2 数学模型

设某一保障责任区某时段内待保障的飞机集合F={Fg}(g=1,2,…,n)；飞机所停靠机位集合A={Ai}(i=1,2,…,w)；牵引车集合V={Vh}(h=1,2,...,k)。

机位Ai所停飞机Fg预计关舱门时刻设为ti,c、关舱门至开始推出耗时设为ti,d1、推出所耗时长设为ti,d2，机位Ai所停飞机Fg牵引作业预计开始、预计完成和实际完成时间分别设为ti,s、ti,p、ti,e，其中ti,s=ti,c+ti,d1,ti,p=ti,s+ti,d2；牵引车Vh由机位Si行驶到机位Sv耗时设为tivh。假设牵引车由停放区开出完成所指派的任务后才回到停放区，分别以牵引车保障造成的航班运行总延误最小和车辆行驶耗时之和最小为优化目标，其数学模型为：

(1)

(2)

st:tv,e+M(1-λ)-tivh≥ti,e

(3)

α(tv,s-ti,s)≥0

(4)

ti,e≥ti,s+ti,d2

(5)

其中，(1)式求取由牵引车保障导致的航班运行延误总时长最小，某一航班的运行延误为机位Ai所停飞机Fg牵引作业实际完成时间和预计完成时间之差；(2)式求取牵引车行驶总时长最小；(3)式中的λ为0-1变量，若车辆Vh从机位Si直接行驶到机位Sv，λ=1，否则λ=0；M为一个无穷大的数，该式保证车辆在飞机之间的作业时序关系得到满足；(4)式中的α为0-1变量，当停靠在机位Av上的飞机预计关舱门时刻tv,c晚于停靠在机位Ai上的飞机预计关舱门时刻ti,c时α取1，否则α取0，该式保证关舱门时刻早的飞机先开始推出作业；(5)式保证推出作业耗时需求得到满足。

2 牵引车安全调度求解策略

2.1 改进的NSGA-Ⅱ算法

传统NSGA-Ⅱ算法的初始种群是由一组随机数组成的，易使种群陷入局部帕累托最优解集，出现早熟现象；另外交叉算子采用模拟二进制交叉，局部搜索能力强而全局搜索能力差，使种群很难得到全局的帕累托最优解集。本文为提高传统NSGA-Ⅱ算法的搜索能力、避免种群陷入局部帕累托最优解集，对算法进行了改进。改进的NSGA-Ⅱ算法求解速度快，克服了传统NSGA-Ⅱ算法初始种群多样性低、易陷入局部最优解等不足。

2.1.1 初始种群的改进

Tizhoosh于2005年提出了反向学习(OBL)的概念，他对反向数的定义为：设在区间[a,b]上存在一 个实数x，则x的反向数为x′=a+b-x，并且该反向解要比当前解有高近50%的概率靠近全局优。并将反向个体与当前个体一起参与竞争，优秀个体进入下一代。由此，对初始种群的生成进行改进：

在区间[1,k]内生成一组随机数，多组随机数组成种群P，将种群P中的N个个体反向产生对应数量的反向个体，得到反向群体P′，计算P∪P′中所有个体的适应度值并进行排序筛选出N个适应度值好的个体作为初始种群。由此，可以提高找到更好初始种群的概率，从而抑制算法的早熟现象。

2.1.2 交叉算子的改进

为了使种群中等级优，分布度好的个体在种群中占据较大的比例，这里引入算术交叉算子[3]，在算术交叉算子中将人工系数λ的取值与当前个体的非支配排序等级和拥挤度联系在一起[4]，即：

x′1j=λx1j+(1-λ)x2j

x′2j=(1-λ)x1j+λx2j

(6)

上式中：x1jrank、x2jrank为当代个体x1j、x2j的非支配排序等级；x1jd、x2jd表示当代个体x1j、x2j的拥挤距离。

算术交叉算子全局搜索能力强，模拟二进制交叉局部搜索能力强，故在对算术交叉算子进行改进后还可根据不同的进化代数将两者结合起来提高算法的多样性，在进化代数不大于2/3pop时，采取算术交叉；在进化代数大于2/3pop时，采取模拟二进制交叉。其中，模拟二进制交叉算子[5]如下：

μj=rand(1)

x′1j=0.5×[(1+γj)x1j+(1-γj)x2j]

x′2j=0.5×[(1-γj)x1j+(1+γj)x2j]

(7)

2.2 算法步骤

本文所提出的改进NSGA-II算法步骤如下：

1)初始化。随机生成N组随机数，每组随机数由w个在区间[xmin(j),xmax(j)]内的优化变量x(j)组成，其中：

x(j)=xmin(j)+(xmax(j)-xmin(j))*rand(1)，j=1,2,...,w

并将其设为种群P，利用反向学习方法，得到反向群体P′，计算P∪P′中所有个体的适应度值并进行排序，筛选出N个适应度值好的个体作为新的初始种群P1。

2)快速非支配排序。根据快速非支配排序策略，比较种群P1中各个体的目标函数值，将各个体进行分级排序，计算各层级中各个体的拥挤距离，记录各个体的xjrank和xjd。

3)锦标赛选择。先将种群P1平均分为两个种群1和2，采取二元锦标赛选择策略，每次从种群1中随机的取出两个个体，根据适应度值选择较小的一个进入子代种群。重复该操作，直到新的种群1*的规模达到种群1的规模；同理对种群2*进行该操作，得到新的种群2*，并将新种群1*与2*合并得到数量规模为N的父代种群P2。

4)生成子代种群。利用改进后的交叉算子和多项式变异算子对父代种群P2进行交叉、变异操作，生成子代种群P3。

5)种群混合。将父代种群P2和子代种群P3混合成种群规模为2N的中间种群P4，并对其进行快速非支配排序。

6)精英保留。在一个种群规模为N的空种群中依次添加层级为1，2…的非支配个体集合，直到进一步添加层级i后种群规模将超过N，对层级i中个体按拥挤距离由大到小逐个填充直到种群规模等于N，由此得到新种群P5。

7)迭代。返回至步骤3)，到最大迭代次数后停止迭代，最终得到的新种群Ppop即为优化问题的帕累托最优解集。

3 算法验证

3.1 获取数据

为确定各飞机关舱门至开始推出耗时ti,d1，采集西南某一机场不同时段不同机位共100架飞机的推出作业相关数据，从图2可知，耗时ti,d1比较集中，故以平均值1 min作为验证环节ti,d1的时长。

图2 西南某机场100架飞机ti,d1耗时统计图

由于不同机型的推出耗时ti,d2略有差异，根据该机场不同时段大量的实际运行数据得出该责任区内50架飞机所对应的推出耗时ti,d2。之后利用西南某一机场的航班运行数据，先推算该责任区内50架飞机的预计关舱门时刻ti,c，用数字1～50对各航空器所处机位重新编号，编号数越小代表飞机预计关舱门时刻越早。最后根据A-CDM系统提供的各机位实时保障数据更新一部分飞机的预计关舱门时刻，并作为已知数据输入到算法中。至此，该责任区飞机牵引作业信息表如表1所示。

表1 飞机牵引作业信息

续表1

航班号预计关门时刻关门至开始推出推出耗时飞机型号机位编号HO344507:511 min6 minA321-231103U886907:541 min6.5 minA330-34311MF508507:561 min6.5 minA330-343123U852507:591 min6 minA321-27113G5871908:041 min6 minA321-27114HO342508:061 min6 minA321-27115MU200508:151 min5.5 minA320-23216CZ497308:171 min5 minA319-13317NH94808:201 min8 minB767-30018CA670208:261 min8 minB767-30019MU404308:301 min6 minA321-231203U161508:341 min7 minA350-94121EU224908:351 min6 minA321-23122TV637108:391 min6.5 minA330-34323CA418508:411 min6 minA321-23124ZH418508:441 min6 minA321-23125G5871308:501 min6 minA321-231263U580708:541 min5.5 minA320-232278L773208:571 min5 minA319-13328MU549908:581 min7 minA350-94129ZH452909:001 min6 minA321-23130TV644909:031 min6.5 minA330-34331CA421109:071 min6 minA321-23132ZH421109:101 min6 minA321-23133TV632509:111 min7 minA350-941343U509509:171 min6 minA321-23135MU565309:181 min6.5 minA330-34336MU263709:201 min7.5 minB737-30037MU532109:221 min7.5 minB737-30038G5864709:251 min6.5 minA330-34339MU395509:271 min6.5 minA330-34340CA40309:301 min8 minB767-30041UA00809:331 min8 minB767-300423U881109:341 min6 minA321-23143KY941009:401 min6 minA321-23144CA451309:411 min6.5 minA330-34345MU582509:441 min7.5 minB737-300463U501109:461 min6.5 minA330-34347CA721709:511 min8 minB787-800483U866909:541 min6 minA321-231498L967209:561 min6.5 minA330-34350

3.2 算例结果与分析

以西南某一机场的数据为基础，按照预计关舱门时刻早的飞机先接受服务的原则，安排4台牵引车为表1内的50架飞机进行牵引作业，利用改进后的NSGA-Ⅱ算法进行求解，其中算法参数为：最大迭代次数为100；种群规模为300;交叉概率为0.95;变异概率为0.05，模拟二进制交叉参数与多项式变异参数均设为20。图3为利用matlab软件运行改进后的NSGA-Ⅱ算法求得的pareto解集图。

图3 pareto解集图

根据图3所示的pareto解集图，选取航班运行总延误时长最小的4组非劣解进行方案比选，其结果如下图4所示。

图4 基于pareto解集的策略比选图

由图4可知，策略1的航班运行总延误时长最小，为53.4 min，策略4牵引车总行驶时长最小，为95.4 min；策略2的航班运行总延误时长和牵引车总行驶时长均表现良好，考虑以策略2为例，绘制牵引车作业甘特图和各航班运行延误时长图，分别如图5和图6所示。

图5 牵引车作业甘特图

图6 各航班延误时长统计图

由图3可知，策略3得出的由于牵引保障导致的航班运行总延误时长为53.9 min，牵引车行驶总耗时为97.5 min；由图5可知，四辆牵引车的任务分布较为均衡，3号车的作业任务略轻；由图6可知，13号机位的飞机的运行延误时长最长，为6 min，其他机位的飞机因牵引作业导致的运行延误时长较短。

为了验证改进的NSGA-Ⅱ算法的牵引车调度问题中求解的优势，将其与传统的NSGA-Ⅱ算法进行比较。将两种算法在相同条件下独立运行，改进的NSGA-Ⅱ计算耗时为51.3 s，传统的NSGA-Ⅱ计算耗时为61.7 s。

利用Matlab绘制出不同目标函数外部解的收敛曲线，如图7所示。外部解是指在每代的帕累托最优解集中，各个子目标函数值最优时的解。对于以最小值为最优解的目标函数，其对应的外部解越小，说明解集内个体分布越广泛，算法搜索能力越强[2]。

图7 目标函数f1的外部解收敛曲线

图8 目标函数f2的外部解收敛曲线

由上图7、图8可知，改进后的NSGA-Ⅱ算法相较于传统算法，解的分布性更广，收敛性更好，搜索能力更强，并且计算耗时降低10 s，能更好的应用于实际运行过程中。

4 结束语

本文针对停机坪单一保障责任区内的牵引车调度问题，以牵引车保障造成的航班总延误时长最小和牵引车行驶耗时之和最小为多目标函数模型，结合西南某一机场A-CDM系统实时更新的各机位航空器的预计关舱门时刻，按照预计关舱门时刻早的飞机先接受服务的原则，对4台牵引车为50架飞机进行牵引作业为数据，采用改进后的NSGA-Ⅱ算法进行求解得到不同安全策略，并对各策略进行了分析，为机坪保障人员快速制定出新的牵引车安全调度策略提供一定的参考。