基于机场协同决策系统的机坪牵引车调度方法

王 博, 王剑辉, 彭笑非, 苏 刚

(1.中国民航飞行学院空中交通管理学院, 广汉 618307； 2.中国民用航空总局第二研究所民航空管工程技术研究所, 成都 610041)

航空器推出作业是指牵引车将航空器由停机位牵引至滑行道的过程,是机坪保障的重要环节。但在实际保障过程中,航空器推出时刻不易预测、牵引车在机位间的行驶耗时和作业耗时存在波动,都会对牵引车的调度产生影响。随着机场协同决策(airport collaborative decision making,A-CDM)在机场运行控制中心的实施,航空器推出时刻能够被精准的预测,在此基础上充分考虑车辆行驶耗时和航空器推出作业耗时的不确定性有利于机坪牵引车调度工作的展开。

机坪牵引车调度属于某种车辆完成多架航空器某一类保障作业的调度问题[1],具有多目标、多约束等特性,作为一类非确定性多项式(non-deterministic polynomial hard)[2]问题,以往的研究多建立具有时间窗约束的车辆路径规划模型[3-5],多采用启发式算法[6-7]、蚁群算法[8]和遗传算法[9-10]等智能算法进行求解,但研究工作精细化程度不够,保障作业耗时常取经验值或高斯分布随机数值[11-12],车辆行驶速度多为固定值,尚未考虑航空器推出作业可能引发的运行冲突问题,得到的调度方案难以指导现场实地保障作业。

为此，在航空器推出时刻能够被精准预测的前提下,建立以某一时段、单一保障区内航空器推出作业产生的总费用最小、参与作业的牵引车数量最少、牵引车服务的航空器数量保持均衡的多目标优化模型；通过分析历史数据,针对性地设计随机数生成方式以确定航空器推出作业耗时和牵引车行驶耗时；基于停机位的分布情况设置约束条件,避免航空器发生推出冲突,然后设计多目标遗传算法、结合实例进行验证,最后采用MATLAB-GUI软件设计可视化调度程序,以便应用在现场实地保障作业中。

1 问题分析与建模

1.1 问题分析

牵引车服务过程是指牵引车由停放区开出,行驶到各指定机位为航空器提供牵引服务后回到停放区,如图1所示；航空器的推出耗时是指牵引车进入某机位开始作业直至结束该项作业离开机位所花费的时间；航空器的推出冲突是指在机坪某些区域必须将航空器错时推出,如图2所示。需要解决的问题是在避免航空器推出冲突的前提下合理调度牵引车,使得推出作业产生的总费用尽可能小、参与作业的牵引车尽可能少、牵引车服务的航班数量更加均衡。

A′、B′、C′为牵引车停放区；S1～Sn为牵引车调度过程图1 牵引车服务过程Fig.1 The service procedure of towing tractors

图2 航空器推出冲突Fig.2 The conflict of Push-Back between aircraft

为解决该多目标优化问题,首先引入Pareto支配关系的概念[13],对于目标函数fi(x),i=1,2,…,n,任意给定两个决策变量Xa、Xb,假定优化方向为最小化,如果有以下两个条件成立,则称为Xa支配Xb:①∀i∈1,2,…,n,都有fi(Xa)≤fi(Xb)成立；②∃i∈1,2,…,n,使得fi(Xa)>fi(Xb)成立。

如果对于一个决策变量,不存在其他决策变量能够支配他,即无法在改进任何目标函数的同时不削弱至少一个其他目标函数,这种解称作Pareto最优解。

1.2 数学模型

航空器推出耗时、牵引车行驶耗时和推出作业产生的费用取值如下。

1.2.1 航空器推出作业耗时

航空器推出耗时ti,d在因素∂1,∂2,…,∂N的影响下有不同的时间分布,可从该分布中取随机值,记为

(1)

1.2.2 牵引车行驶耗时

1.2.3 推出作业费用

i,j=1,2,…,w；i≠j

(2)

假设牵引车Vh从停放区S0出发,依次为航空器Fi,Fj,…,Fl提供牵引服务,最后回到停放区,在此期间,可以从停放区S0任意增派车辆为其他航空器服务,直到完成该保障区所有航空器的推出作业。在航空器推出作业耗时、牵引车行驶耗时、推出作业费用取值的基础上构建机坪牵引车调度多目标优化模型,具体可表示为

(3)

(4)

(5)

(6)

式中：式(3)和式(4)、式(5)分别求取所有航空器牵引作业产生的总费用最小、参与作业的车辆数目最小、不同车辆服务的航空器数量方差最小；M为一个极大的正数；λ为0～1变量,若车辆Vh为航空器Fi提供服务后直接驶往航空器Fj所停机位时,λ=1；否则λ=0,该式保证车辆在航空器之间的作业时序关系得到满足；ti,e≥ti,sp+ti,d保证航空器Fi的推出耗时得到满足；|tu,s-tv,s|≥td通过设置缓冲时间(td),保证航空器Fu、Fv不会产生推出冲突；xih为0～1变量,若航空器Fi由车辆Vh服务,xih=1,否则,xih=0,该式保证同一个航空器只能被一辆牵引车服务；q为该保障区可提供牵引车的最大数量。

2 算法设计

机坪牵引车调度问题包含航空器推出作业总费用最小、参与作业的牵引车数量最少和牵引车服务的航班数量保持均衡3个目标函数的同时优化,为了权衡不同目标之间的利益,需要得到一组 Pareto 解集。结合 NSGA-II 算法进行求解,所用函数如表1所示,算法流程如图3所示,具体步骤如下。

步骤1染色体编码与种群初始化。在多目标遗传算法中,染色体作为实际的优化对象,其编码主要分为直接编码和间接编码[9]两类。为提高效率,本算法直接对一段时间内待保障航空器编号和牵引车编号进行编码,每一条染色体pe由基因片段[x]、[y]、[f]组成。其中片段[x]={x1,x2,…,xw}={randperm(w)},即将w个航空器编号随机排成一行；片段[y]={y1,y2,…,yq}={randi[q,1,w]},将指定对编号为xi(i=1,2,…，w)的航空器提供服务的牵引车编号yj(j=1,2,…,q)排列在基因片段[x]之后；片段[f]=[F1,F2,F3]为该套调度方案的目标函数值,并依次排在片段[y]后。按照编码规则随机生成种群规模为N的个体,将得到的所有个体记为初始种群P0。

步骤2适应度设计。为避免航空器推出作业发生冲突,判断编号为yj(j=1,2,…,q)的牵引车服务的航空器中是否存在Fu、Fv,若存在,则让其作业实际开始时刻间隔td,并更新该个体的目标函数值。之后按照快速非支配排序和拥挤度算子进行适应度设计,非支配排序[13]是基于个体的目标函数值,按个体非劣解水平对种群分层,向Pareto最优解的方向进化；拥挤度算子是为优先选择拥挤距离较大的个体,保证种群多样性。

步骤3非支配排序与拥挤度计算。基于NSGA-Ⅱ算法对初始种群P0进行快速非支配排序与拥挤度计算,并将层序irank值、拥挤度id一同写入到染色体中。

步骤4选择父代个体。

表1 函数释义

图3 算法流程图Fig.3 The flow chart of algorithm

设配对池容量为N/2,选择层序irank最小的个体加入配对池,如果有irank值相同的个体,则任选拥挤度id最大的个体加入配对池；反复进行该操作直到配对池容量已满,得到父代种群P1。

步骤5去重交叉操作。从父代种群P1中成对选择染色体pv、pv+1,若满足交叉概率pc,则对其进行交叉操作。

针对片段[xv]、[xv+1]进行交叉操作:①令{v}=randi(w,1,2),设v1,v2∈v；r=v1≤v2；②将片段[xv]、[xv+1]上第r位基因进行互换,互换前的值分别记为rv、rv+1；③分别在片段[xv]、[xv+1]上找到与rv+1、rv相等的基因,将其变为rv、rv+1;④判断r与v2的大小关系,若r>v2,则结束交叉操作,否则,r=r+1,回到步骤②。

针对片段[yv]、[yv+1]进行交叉操作:令q=randi(w),将片段[yv]前q个基因与片段[yv+1]第q位以后的基因进行组合,得到染色体p′v,将[yv+1]前q个基因与片段[yv]第q位以后的基因组合,得到染色体p′v+1。

经过交叉操作的个体组成子代种群P2,计算每一个体的目标函数值,更新片段[f]的基因,整个交叉过程如图4所示。

图4 染色体交叉示意图Fig.4 The diagram of chromosomal chiasma

步骤6变异操作。针对种群P2的染色体pd(d=1,2,…,N),若满足变异概率pm,则对其进行变异操作。令{s1,s2,…,sw}=randperm(w),将片段[xd]上第s1、s2个基因互换；令s=randi(w),将片段[yd]上第s个基因r′变为q+1-r′。经过变异操作的个体组成子代种群P3,计算每一个体的目标函数值,更新片段[f]的基因。

步骤7种群融合。将父代种群P1与子代种群P3进行融合,对融合种群P4进行非支配排序与拥挤度计算,得到非支配层级和对应非支配层的拥挤度,写入到染色体中。

步骤8精英保留。在一个的空种群中依次添加融合种群P4中irank={1,2,…,n}的个体,直到进一步添加层级i后种群规模将超过N,对层级i中个体按拥挤距离id由大到小逐个填充直到种群规模等于N,由此得到新的种群P5。

步骤9迭代。返回至步骤4,进行下一次迭代操作,直至达到最大迭代次数gen,最终得到的新种群Ppop即为优化问题的帕累托最优解集。

3 算法验证

3.1 数据获取与处理

以中国西南某一机场为例,基于该机场A-CDM系统得到某一保障责任区内40架航空器的预计推出时刻和即将停靠机位,部分示例如表2所示。

航空器推出作业耗时的影响因素∂主要考虑时间段和机型,时间段具体分为Night(19：00—5：00)、Day(5：00—19：00),机型分为A(小型飞机)、B(中型飞机)、C(大型飞机),通过统计分析不同时段、不同机型共计1 200架航空器的推出作业所耗时长确定航空器推出作业时长的分布范围,如图5 所示。

基于机场基础数据获取牵引车停放区与各停机位以及各停机位间的距离dij。综合考虑作业时间段和天气因素对牵引车行驶速度的影响,结合机场方面的运行数据将因素设为0.8；针对可能产生推出冲突的航空器,将其作业实际开始时刻的间隔值td设为5 min；结合机场方面的相关经验,将牵引车行驶耗时转化系数γ设为1,牵引车早到、迟到费用系数α、β分别设为5和10。

图5 推出作业耗时统计图Fig.5 The statistical chart of time-consuming of Push-Back

表2 部分航空器作业信息

3.2 计算结果

将种群规模N设为300,迭代次数(gen)设为 1 000,交叉概率(pc)设为0.75,变异概率(pm)设为0.3,利用MATLAB软件求解,计算耗时为4.3 min,单条染色基因信息如图6所示,Pareto解集如图7所示,具体信息如表3所示；以解序4为例,绘制牵引车作业甘特图,如图8所示,在特殊机位可能产生运行冲突的航空器,其推出作业实际开始时刻均间隔在 5 min 以上。

3.3 方案对比与应用扩展

采用相同的基础数据,将基于遗传算法得出的调度方案中解序4的结果与传统人工调度方案进行对比,前者可使总费用降低31.67%,服务航班数方差降至0,方案制定时间缩短71.15%,如表4所示。

图6 单条染色体基因信息Fig.6 The gene information of single chromosome

图7 Pareto解集图Fig.7 The diagram of Pareto sets

表3 Pareto解集信息

图8 牵引车作业甘特图Fig.8 The gantte chart of towing tractors’service

表4 方案对比结果

利用MATLAB-Gui软件制作可视化的调度程序,通过获取A-CDM数据、导入基础运行数据,利用多目标遗传算法输出一组调度方案,为一线运营人员提供决策参考,如图9所示。

图9 牵引车调度程序Fig.9 The software of scheduling of towing tractors

4 结论

以某一时段、机坪单一保障区内航空器推出作业产生的总费用最小、参与作业的牵引车数量最少、牵引车服务的航空器数量保持均衡为优化目标,结合A-CDM系统和多目标遗传算法设计出机坪牵引车调度方法,得到以下结论。

(1)与传统的人工调度方法相比,该方法下的调度方案可使作业总费用降低31.67%、各牵引车服务的航空器数量更加均衡、方案制定时间缩短71.15%。

(2)通过该方法设计的可视化牵引车调度程序能指导实际保障作业,为一线运营人员提供决策参考。

后续将针对多种车辆完成多类航班保障作业的调度问题展开研究。