机场地面保障服务车辆协同调度和仿真优化

徐 晨, 王笑天, 刘 博

(民航中南空管设备工程(广州)有限公司, 广州 510080)

航班地面保障是机场为了保证航班正常运行而提供的一系列清洁、配餐和加油等活动的服务。地面保障服务分别由不同部门和单位通过不同类型保障车辆来执行,具有流程复杂、车辆资源受限和协同调度难度大等特点。现如今越来越多的机场依托运行经验,研究科学的地面保障车辆调度智能化系统,解决机场和航空公司的地面保障资源信息不完全对称、航班地面保障服务需求量和地面保障资源供应量间不同程度失衡的问题。

机场地面保障车辆调度研究涉及:单种地面保障车辆的路径与调度问题、多种地面保障车辆的协同调度问题和利用仿真软件优化车辆路径与调度问题三个方面。

Norin等[1]设计了贪婪随机自适应搜索算法实现单种车辆调度的最小化航班延误和最小化行驶里程;王一飞[2-3]、陈鑫和刘长有[3]应用蚁群算法解决车辆调度动态规划问题;Christian和Asvin[4]以一种用于生成可行调度表的后向标记方法研究车辆路线和车辆司机调度问题;钟建华[5]采用基于改进NSGA-Ⅱ算法求解飞机牵引车调度问题;王博等[6]基于机场协同决策系统提出了机坪牵引车调度方法。

Padrón等[7]、任子云[8]、王俊义[9]、樊伟等[10]、许晨晨和邵荃[11]考虑不同的车辆,结合多种车辆进行结合考虑并优化整个地面保障流程。以工作负荷相对均匀和资源节约为设计原则,综合多种车辆相互运作关系,得到优化方案。

廖丹和黄宝军[12]用AirTOp仿真建模,实现了机场地面保障车辆与航空器的联合建模;衡红军和王芳[13]建立了基于多智能体系统(multi-agent system,MAS)的实时调度算法,分布式规划服务车辆路径并组合形成方案。

机场地面保障服务车辆调度问题随着智能仿生算法的发展已日趋成熟,但大部分研究针对单一车辆或场景,无法很好地实现从基础理论到实际复杂场景应用的过渡。针对机场地面保障服务的流程和特点,分析实际运行中多种模式下各地服车辆与所保障航班的关联性,解决多航班、多种地服车辆、多车库中心、多目标的复杂协同问题。采用Anylogic软件进行机场场面保障服务流程仿真,验证方案的合理性和实用性。

1 机场地面运行保障分析

地面资源服务模式以航班运行流程为主线进行分类,包括始发、过站、过夜和快速过站航班4种模式的航空器流程保障标准。过站航班运行模式所涉及的地面保障服务车辆最齐全且服务流程要求最高,需要航空器保障车辆、旅客服务车辆、场道保障车辆及应急救援车辆为其提供服务。

1.1 航空器地面保障服务流程

地面保障服务从航空器到达本站前分配机位开始,至航空器撤轮档后结束为止。每种车辆所需的提前到位等待、对接和服务时间各不相同。这些时间还与所服务航空器的机型和航空器停放机位属性相关。

在满足规范要求的前提下,统计地服车辆的历史服务时间,可初步确定各类地面保障车辆的标准作业时间。对国内某大型枢纽机场2019年9月25日至2020年6月24日1 225架次航班的清水车作业时间进行调研,得到服务近机位C类航空器清水配供作业时间统计图(图1)。同一类型车辆的服务时间存在不确定性,将95%箱体值作为服务于C类航空器的清水车标准作业时间。

图1 清水车作业时间统计(C类)

同理得到其他各类地服车辆的标准作业时间,如表1所示。

表1 航空器保障车辆标准作业时间汇总

与旅客服务相关的地服保障标准作业时间,如表2所示。

表2 旅客服务车辆标准作业时间汇总

由机型(C、D、E、F)和航班停放机位类型(近/远机位),地服车辆服务最早/最晚开始时间、结束时间、标准作业时间及关键工序,可以确定航空器地面保障服务流程。停放近机位的C类航空器的过站地面保障流程如图2所示。

图2 航空器地面保障流程的关键工序示意图

将航班保障涉及流程解析为26个时间节点,归纳为地面保障流程的时间工序模型如图3所示。

图3 C类航空器过站航班地面保障流程(近机位)示例

各节点紧前、紧后工序等参数说明如表3所示。

表3 地面保障流程关键工序的时间参数说明

节点23～25为地服车辆的提前到位准备工序。

针对地服车辆服务流程优化,可有效地缩短航班过站时间,从而提高场面资源调度和运行效率。

1.2 车辆路径规划问题

机场除了跑道、滑行道和联络道,还专门设有地服车辆的行驶道路、服务区域及车库中心等区域,保证航空器飞行活动安全有序进行。地服车辆调度是经典车辆调度问题(vehicle routing problems, VRP)的一种衍生问题。若干空闲车辆从车库出发,前往航空器所在机位提供地面保障服务,服务完成后如有新的需求,则前往下一航空器所在机位提供服务,否则返回车库中心。地面保障车辆有使用限制,即服务完一定架次数量的航空器后,应保留合适剩余油量前往指定地点(特种车辆加油站或补给中心)补充资源。

将这一过程归纳为带容量和时间窗的多目标车辆路径规划问题(capacitated vehicle routing problems with time windows, CVRPTW)。通过车辆数限制、车辆容量限制、服务时间窗限制等基本约束生成地服车辆服务航空器的顺序集合、车辆数和车辆行驶距离的调度方案。

2 CVRPTW模型

CVRPTW模型包含一个车库中心K,因为同种地服车辆所属不同地服公司其容量和服务时间也有差异,所以区分同一种地服车的不同属性(如地服公司属性)进行建模。

2.1 目标函数

模型包含三个基本目标,式(1)为总使用车辆数量最小、式(2)为行驶总路径最短、式(3)为超出地面保障服务时间限制数目最小、式(4)为地服车辆服务次数差异最小。

(1)

(2)

(3)

(4)

式(3)中包含一个惩罚函数Nti,用于表征当前车辆服务时间和计划时间差值,按式(5)计算。

(5)

图4 惩罚函数

2.2 约束条件

约束条件如下所示。

(6)

(7)

(8)

(9)

∀k∈K,∀i,j∈C

(10)

∀k∈K,∀i∈C

(11)

(i=0,1,…,n+1)

(12)

(13)

(14)

(15)

3 CVRPTW问题的优化

针对地服保障特点,进一步优化CVRPTW模型,解决多种地服车辆、多航班、多车场、多目标的复杂场面问题。

3.1 多车场的车辆调度问题

在上述地面保障服务协同调度模型基础上增加每个车库的车辆数量约束,如式16所示。

(16)

用国际Solomon算例C101进行验证,结果如图5和图6所示。单车库的最短行驶路径为191.1,指定车库中心的多车场情景(3个车库)车辆的总行驶距离是109.8。可以看出,多车库中心比单车库中心的车辆路径规划行驶距离更短,充分考虑机场地面保障资源的布局情况,从而有效减少耗油、碳排放和冲突等各种与距离成正比的成本。

图5 单车库中心最优配送方案路线

图6 单车库中心最优配送方案路线

此外,车库中心的分布对车辆行驶路径结果的影响也很大。实验表明,指定车库的总行驶路径迭代次数均高于未指定车库中心的迭代次数。因此,对于新、改建机场,若未确定车库中心位置,可采用距离分配法,通过行驶距离矩阵计算出多个较优车库中心位置,然后将待服务航班进行分类,依次分别放入合适的车库中心集合中,从而确定最佳车库中心位置,为机场场面车库规划设计科学合理的指导建议。

3.2 高维多目标车辆路径规划问题

CVRPTW模型是一个高维多目标问题,即行驶距离最短、车辆数最少、超出时间窗惩罚函数最小和车辆任务均衡的多目标。

以Eclipse-MOEA Framework 2.13 JDK 8为实验平台,采用基于分解的多目标进化算法[14](multi-objective evolutionary algorithm based on decomposition, MOEA/D)的高维多目标算法进行求解。该算法得到的POF(Pareto optimal front,Pareto最优前沿)效果较好,在使用车辆数尽可能小的情况下,无论是整体还是单个车辆的行驶距离都较小,车辆任务分布和时间窗违背函数(TWVariance)都很均匀,可以看作一组满意解。

4 基于Anylogic的优化仿真

以北京大兴国际机场某天航班为例进行验证,得到的多车辆、多航班、多车场动态多目标资源调度信息如下。

清水车、垃圾车车库统称特种车库,加油车、污水车、行李车、配餐车有各自专用车库,获取车库代号及坐标。不同地服公司的车辆类型不同,每种车的初始位置和现有资源数量如表4所示。

表4 地服车辆信息

用代号“01”“02”和“03”分别表示东航地服、南航地服和首新地服,加油车服务不区分地服代理公司,由“04”表示。

地服车辆在各节点之间的行驶距离,如表5所示。

表5中对角线数据是地服车辆从车库到机位的行驶时间,其他数据为车辆在机位间的行驶时间。

选取典型日航班计划作为实验数据,共计390个航班,其中C类航空器337架次,E类53架次,统计所有航班到达机位时间和离开机位时间,并以此时间节点作为地面保障服务流程整体开始时间和最晚结束时间设计资源调度和配置方案,航班和地服车辆信息如表6所示。

表6 航班时刻表(部分)

以清水车(01)资源配置和调度为例展示方案。图7中1～129号为航班服务顺序,130～133为4个车库中心,得到21 861个Pareto前沿。POF解集的使用车辆数为11,行驶距离为60 541.23(相对距离无量纲),最优解的平均推迟时间为11.77s(推迟时间以最早服务开始时间为标准进行计算,所有清水调度未造成延误),车辆间服务方差为8.31。

图7 北京大兴国际机场地服车辆调度信息(01清水车)

基于AnyLogic软件工具验证车辆调度算法,生成地服车辆的实时调度信息表,验证方案的可行性。

Anylogic是一款基于JAVA语言的仿真软件,支持迅速拖曳建模。创建航班、停机位和航班调度需求等7个智能体,构建地服车辆智能体系统模型架构,如图8所示。

图8 基于Anylogic的地服车辆模型多智能体面板

仿真规则设定为航空器按航班计划时间到达指定机位,向车库中心发送地面保障服务需求消息,车库调度中心接收消息,根据机型匹配信息、车辆所在位置、车辆服务状态和车辆服务规则等因素搜索合适车辆,生成调度计划并给相应车辆转发消息。指定车辆前往航空器所在机位提供地面保障服务,服务完成后判断车库中心是否有新的需求订单,若有,则前往下一航空器所在机位提供服务,否则返回车库中心。

仿真得到航班计划所需各地服车辆数量、行驶距离、延误累计等情况,如表7所示。

表7 仿真结果——地服车辆使用情况统计

地服车辆调度信息如表8所示。

表8 仿真结果-地服车辆服务时间统计(部分)

通过Anylogic软件仿真界面实时监控地服车辆使用情况、车辆调度时间、车辆调度情况和车辆调度情况。

仿真结果显示,所有车辆均在航班待服务时间窗内,未造成航班延误,同时车辆调度方案与实际运行中航空公司地服资源车辆与航班相互匹配的复杂情况相符合,具有较好的实用价值。

5 结论

对地面保障资源的类型、特点、分类和服务模式进行全面的概述,确定了“合理使用、超前配置”的原则,针对过站航班构建带容量和时间窗的车辆行驶路径规划CVRPTW模型。

优化CVRPTW地面保障车辆调度模型,实现多种地服车辆、多航班、多车场和多目标的车辆路径规划问题研究,可减少由于地服车辆调度造成的航班延误和运行成本。

1)提出预先分配车库中心和计算车库中心两种情境的CVRPTW解决方案。研究发现多车库且可计算车库位置的情境下车辆使用数量和行驶距离均较短,可为机场规划建设地面保障车辆车库中心设置提供科学可靠的理论依据。

2)用基于分解的进化算法MOEA/D求解车辆数、行驶距离、时间窗惩罚函数和任务数均衡的4维多目标问题,能得到较为满意解集。

3)基于Anylogic仿真软件进行方案验证。统计服务于390架次航班的6种/16类地服车辆(共288辆)使用情况,实时监测地服车辆的调度信息和机位占用情况。结果显示,所得到的理论研究对于实际地面保障服务复杂情景较符,具备应用价值。