面向过站航班地面保障过程的均衡优化建模

2022-03-07邢志伟王思博

江苏大学学报（自然科学版） 2022年2期

邢志伟，王思博，李彪，廉冠

(1. 中国民航大学电子信息与自动化学院，天津 300300； 2. 中国民航大学航空工程学院，天津 300300； 3. 桂林电子科技大学建筑与交通工程学院，广西桂林 541004)

航班地面保障过程是指飞机经引导进入机位后开展的一系列针对飞行器、旅客和货邮的地面处理过程，是提高机场运行效率的核心环节之一.在航班推出前合理配置资源利用情况，不但有助于缩减运行时间和运营成本，而且能有效改善延误、资源闲置浪费等瓶颈问题.目前，机场航班地面保障过程的运行是由多参与方合作开展.然而，整个过程协同能力差、资源配置不均衡等现象时有发生.因此，开展以资源均衡优化为目标的保障过程建模、优化方案制定、均衡效果评估将有望缓解上述困境.针对航班地面保障过程建模及优化问题，国内外研究学者分别从保障过程核心环节[1]、环节协同[2]和保障过程整体[3]出发建立优化模型并验证其合理性.但这些模型的建立仅侧重于优化运行时间，并未考虑过程中资源配置的均衡性.按优化对象可将保障过程优化问题分为车辆调度和人员配置优化两类.车辆调度方面，M. FINK等[4]基于时空网络构建多保障车辆运行模型，实现对车辆运行路径的合理优化，用以缩短保障过程运行时间.GUO W. A.等[5]针对机场行李运输车为飞机作业保障的场景，设计出一种基于遗传算法的保障车辆运行优化方法，提高了算法的求解能力.人员配置方面，C. MALANDRI等[6]由机场特殊场景出发，分析因人力资源突变导致过站时间增加问题，构建相应模型求出阈值，作为优化机场运行模态的依据.S.HIEMSTRA-VAN MASTRIGT等[7]采取不同优化方案减缓影响因素对旅客登机的干扰，以确保降低航班延误率.S.PADRN等[8]以西班牙机场实际数据为例，建立双目标优化模型求出对应的Pareto解，为过站航班提供合理优化方案.但以上研究仅注重解决某一环节的资源优化，并未对保障过程整体均衡形成优化方案.上述优化方法仍无法解决面向多模态下的保障资源均衡优化问题.

文中拟构建面向多目标的保障过程资源均衡优化模型，基于实际数据和运行场景展开求解并得出优化方案.通过均衡评估指标对模型的可行性进行分析验证，为机场航班地面保障过程的精细化管理提供客观依据.

1 航班地面保障过程分析

1.1 航班地面保障过程业务特点分析

结合过站航班实际运行情况和相关标准可知，航班地面保障各环节不但在时间上具有严格的时间窗和优先顺序约束，还在设备配置上具有多样性的特点.由于各环节资源需求量存在差异性，进而形成了保障环节的多种运行模态.在运行模态和资源种类的限制下，导致保障过程资源均衡优化的实现需考虑多个优化目标.而保障过程的完成不仅需要单一环节的优化，而且需要多个环节协同运行.因此，还需考虑由多个环节构成的工作流的运行状态.如图1所示，航班地面保障过程可分为飞机、旅客和行李3个工作流，并且每个工作流中存在串行和并行2种形式.

图1 过站航班地面保障作业流程图

总之，航班地面保障过程均衡优化问题属于一类子环节多模态共存、工作流形式复杂、保障资源种类多样的多目标协同优化问题.

1.2 航班地面保障资源均衡影响要素分析

根据保障环节运行特性和机场实际运行数据，结合多因素分析法对航班地面保障资源均衡影响要素进行初步分析，并构建影响要素拓扑图，如图2所示.

图2 过站航班地面保障作业影响要素图

在实际运行过程中，保障资源约束涉及的设备、人员和物质具有多样性.针对以上资源种类进行合理分类并定义资源类型.

定义1在保障过程推进中，不会因为环节的实现而造成消耗、但在规定时间段内有约束的资源称为可循环资源.例如，人力、设备等资源.

定义2随着保障过程推进，某一环节消耗后会造成其他航班需求量无法满足的资源称为不可循环资源.例如，物资、不可再生资源等.

在实际运行过程中，根据前序环节的实际运行状态进行实时调整，以实现保障过程的按时完成.故将运行模态分为加急模态、常规模态和放缓模态3类.运行模态效用是通过对人员和设备合理配置来实现.

除了以上2种关键因素外，影响保障过程资源均衡性的因素还包括机型影响、保障设备作业方式、航班密度等.

其他在保障过程资源均衡过程中所涉及的因素可以由空管、机场、航空公司等部门协同解决，因此文中对这些因素忽略不计.

2 航班地面保障过程资源均衡优化模型

2.1 问题描述

结合保障过程中的实际需求，设定航班地面保障过程资源均衡优化中共含有I个保障环节，各环节需要消耗R种资源，有r1种可循环资源，仅考虑可循环资源；各环节运行模态为pi(i=1，2，…，I)，而pi=1、2、3分别表示加急、常规、放缓模态；每种运行模态pi存在对资源的不同需求，包括环节开始时间t和可循环资源YR.环节Ti运行模态可表示为(Tip,YRip1,…,YRipr1).过站航班地面保障资源均衡优化问题可描述如下：在满足保障过程标准完成时间和资源总量的前提下，如何合理安排每个环节的实际开始时间和运行模态，使保障过程内各类资源的时间消耗量和资源利用量均衡度最大，即保障资源综合消耗量方差最小.

目标如下：① 最小化保障环节运行有效偏差，即有效确定保障环节是否处于稳定状态，将为保障资源均衡优化提供可靠的前提；② 最小化保障环节作业时间，即保障过程结束的总时间尽可能提前，为机场运行中出现航班延误现象节省出更多处理时间，确保其他航班计划可按时执行；③ 最小化保障资源综合消耗量，即通过合理调度资源(时间资源和物质资源)，有效节约机场实际资源消耗量，缓解机场运行压力.

2.2 基本假设

文中研究航班地面保障过程资源均衡优化调度问题，需要满足如下假设：① 保障环节一旦开始不产生中断，运行时间按min来计量；② 保障过程中，各环节存在多种运行模态，不同模态下的资源利用率、运行时间消耗量不同；③ 在航班降落前，已完成对其跑道和机位的预分配，并不会对其做出临时调整；④ 从单个保障环节看，在其持续时间内，各个时段资源使用量均衡分布.

2.3 多目标多约束模型描述

2.3.1符号变量说明

决策变量包括：Ci=1、0分别表示i需要、不需要特种车辆；pi′=1、0分别表示i取加急、其他模态；zr取值如下：

2.3.2优化目标

结合有向图理论与保障过程实际运行标准，将传统有向图加以改造，得到保障作业过程有向图，如图3所示.

图3 过站航班地面保障作业过程有向图

设定上轮挡为基准环节，建立保障过程的均衡优化模型，此时基准环节的特点为实际开始时间与标准开始时间均为0，资源综合消耗量为实际和标准值，各环节与基准环节的时间间隔可表示为相应的时刻.

根据上述分析，资源均衡优化模型的优化目标如下：最小化保障环节运行有效偏差为

(1)

最小化保障环节作业时间为

minf2=min{timax}，

(2)

最小化保障资源综合消耗量为

(3)

2.3.3约束条件

根据保障过程运行特点可知，针对单个环节需满足时间窗和资源消耗量的约束；同时还需考虑由多个环节组成的工作流，即环节间优先顺序和运行模态的限制.综上，资源均衡优化模型的约束条件如下：

|ti′-ti|

(4)

|ta-tb′|>0，

(5)

|tb-ta′|>0，

(6)

(7)

(8)

(9)

(10)

(11)

其中：式(4)表示某一环节实际开始时间不得超过标准时间的一个定值，若不满足视为不均衡，其中N为一个足够大的常量；式(5)、(6)表示保障环节a和b间服务先后顺序的约束；式(7)表示保障过程的实际时间不得超过标准时间的一个范围，其中N′为一个足够大的常量，且满足N′≠20N；式(8)表示每一个环节必须分配相应的资源完成对其操作；式(9)、(10)表示某一环节必须选取一种运行模态操作中途不许发生改变，若超过半数环节采用加急模态视为该过程不具有均衡优化意义；式(11)表示同一保障资源不能同时分配给两个保障环节.

2.4 模型转化方法

根据优化目标要求，资源均衡优化模型需同时实现3个目标函数功能.为了使模型更好与后续算法结合，需采用LP-量纲法对目标函数2和3进行量纲一处理.

(12)

式中：M2和M3分别为两个目标函数值；K为权重系数，由决策者给出.2个目标函数分别为作业时间最小化f2和资源综合消耗量最小化f3，所以将式(2)、(3)代入(12)，目标函数可转化为

(13)

联立式(1)、(4)-(11)、(13)，可得出航班地面保障过程均衡优化模型.

3 基于混沌与差分进化NSGA-Ⅱ算法的模型求解

NSGA-Ⅱ算法即带有精英保留策略的非劣解排序遗传算法，是对NSGA算法的优化，具有鲁棒性好、计算效率高等优点[9].因此，文中采用一种改进混沌与差分进化的非劣解排序遗传算法.该算法在NSGA-Ⅱ算法的基础上，融合了混沌搜索技术和差分进化思想.其中，混沌迭代公式为

zi+1=μzi(1-zi),i=1,2,…,I,μ∈(0,4，

(14)

式中：zi为保障环节i的混沌变量；μ为混沌系数[10].混沌搜索技术增强了初始种群在最优解周围分布的均匀性，提高算法的求解效率和质量.

由于传统算法对变异算子在总时间范围内只能计算1次，故引入试探向量.根据差分进化的思想改进基础向量可有：

Yi,d=Xi1,d-1+U(Xi2,d-1-Xi3,d-1)，

(15)

式中：Y为试探向量；X为基础向量；U为比例系数，U∈[0,1]；d为进化代数.改进后加快了算法的收敛速度[11-12].结合航班地面保障过程的环节运行有效偏差、作业时间和资源综合消耗量等计算模型，保障过程均衡优化模型的算法流程如图4所示.

图4 算法流程图

依据改进混沌与差分进化的NSGA-Ⅱ算法所求出的Pareto最优解不被Pareto前沿面之外的解(以及Pareto前沿曲线以内的其他解)所支配的性质，Pareto最优解只能优化Pareto前沿面之外的解.Pareto最优解可以为工程项目提供最优施工方案，最大限度协调各函数之间的矛盾，实现各目标函数的协调优化.所以，改进混沌与差分进化的NSGA-Ⅱ算法在求解保障过程均衡优化模型上具有一定可行性.

4 实例分析与讨论

4.1 试验数据及其预处理

试验选用国内中部某枢纽机场实际运行保障数据，具体样例如表1-2所示.

表1 过站航班基本信息实际录入

表2 过站航班保障过程核心环节运行数据

预处理过程如下：

1) 筛选出机型相同、降落时间相近和机位属性一致的航班，以降低旅客人数、航班密度和车辆路径不同对保障过程带来的间接影响.

2) 考虑到一些保障环节数据偏差较大，采用数据拟合的方式来确定各环节服从何种分布.

3)剔除因区域管制、天气条件等因素造成延误的保障运行记录，保留因保障运行产生延误的运行记录.

5) 以保障环节i0为基准环节，对各环节的开始时间和标准时间进行参数优化，以实现时间点对时间间隔的代替.

4.2 试验设置

首先进行模型设置.为达到保障过程资源配置的均衡性和过站时间同时优化的目的，沿用上文简化后的均衡优化模型，在求解时为更具有实际意义形成分层优化双模型：模型1单为目标优化问题，最小化保障环节运行有效偏差，由式(1)、(4)-(7)构成；模型2为双目标协同优化问题，同时最小化航班保障资源综合消耗量和保障环节作业时间，由进行量纲一处理后的式(4)-(11)、(13)构成.

其次进行算法参数设置.为了有效保证算法性能，先要对算法所用到的所有参数进行校验和设定.改进混沌与差分进化的NSGA-Ⅱ算法有5个运行参数：每级存放的种群规模popsize∈{120,130,140，150}；进化代数D∈{80,90,100,110}；交叉常数Pc∈{0.7,0.8,0.9,1.0}；混沌系数μ∈{1,2,3,4}；比例系数U∈{0.7,0.8,0.9,1.0}.利用minitab进行田口试验，计算了16组参数组合，得出最佳参数组合为popsize=140，D=100，Pc=0.9，μ=4，U=0.8.

4.3 试验过程

1) 基准环节设定：首先将上轮挡作为基准环节，其标准开始时间和实际开始时间记为0，资源消耗以实际投入为基准.

2) 环节状态预判：结合目标函数1，分别以各环节的标准时间和实际时间作为输入进行对比，确定各环节实际运行模态，为后续环节提供新的运行模态.

3) 均衡效果检验：结合所得结果对保障过程运行总时间和资源消耗总量是否超出标准限制进行检验.

4) 均衡效果评估：通过均衡率BP、时间损失系数ε和资源平滑系数SI对均衡优化模型的优化效果进行评估.

4.4 试验结果及分析

为了验证均衡优化模型对航班地面保障过程的优化效果，以同一航班在5月的保障过程服务记录为例，首先预判保障过程中各环节的均衡状态，以便于为后续环节配置合适的运行模态.图5为保障过程中核心环节旅客下机的环节运行有效偏差优化过程适应度曲线.

图5 下客环节运行有效偏差优化过程

由图5可见，环节运行有效偏差在迭代20次左右就达到了最优效果，收敛速度较快.该环节运行有效偏差的最优解为31.

确定环节所处均衡状态后，为紧后环节匹配合适的运行模态以达到优化目标.在匹配运行模态时，还需兼顾总时间和各环节资源总量的限制.得到保障过程和资源消耗量的双目标最优解，如图6所示.

图6 总时间-资源消耗量均衡多目标优化解集

由图6可见，保障环节作业时间优化在64.073 min，资源消耗量集中在34.86.

为进一步验证算法的求解速度，将目标函数分层优化，得到最终的优化解集和各函数与求解时间关系图，证明模型的可行性与算法求解速度，关系如图7、8所示.

图7 过站航班地面保障均衡模型最优解集

从图8可见，随着种群规模的逐渐增加，各目标函数递减，优化效果明显.当种群规模达到70以后，目标函数2逐渐变小，算法优化能力逐渐趋于稳定.同时种群越大，算法求解的时间越快.当总时间达到64 min以后，种群规模增加，资源消耗量逐渐缩减，说明算法开始优化目标函数3，在目标函数2和3确定的情况下，可能存在一种方案.最后将过程的总时间优化为64 min，过程资源综合消耗量限制在34.8，此时过程优化效果最佳.

图8 不同种群规模下模型最优解与求解时间

4.5 均衡优化方案对比分析

为了进一步验证文中所用资源均衡优化模型的有效性，将所得结果分别转化为甘特图和资源均衡优化方案图2种形式.分析保障过程中各环节在时间上优化效果和资源上消耗情况，并对比优化前后方案，得出各环节实际具体优化效果，如图9所示.

图9 不同调度方案下环节运行时间甘特图

由图9可见，在调整紧后环节的运行模式后，各环节时间提前量与环节优化节省时间具有明显提升.以环节12为例，优化前其开始时间为20 min，作业时间为47 min；优化后其开始时间为15 min，作业时间为42 min.开始时间提前了5 min，过程运行总时间缩短了10.6%，充分验证模型在过站时间上的有效性.

优化前后的各环节资源消耗情况如图10所示，着色区域为资源闲置总量.