© 2024 Journal of Northwestern Polytechnical University. All rights reserved.

近年来, 民航运输行业的不断发展为人们出行提供了极大的便利。然而, 航班架次的不断攀升造成了机场资源短缺, 给地勤保障车辆调度带来极大的压力。中国民用航空局于2022年5月发布了2021年民航行业发展统计公报[1]。据公报显示, 全国客运航空公司共执行航班378.59万班次, 比上一年有大幅提升, 但是平均延误时间长达10 min。机场航班正常运营下准时率偏低, 这将产生航班延误的传播, 导致后续航班延误[2]。当航班准备下一次飞行时, 需要地勤车辆与装备为其提供服务, 包括牵引服务、清水服务、加油服务等[3]。其中加油车提供的加油服务是地面服务流程中不可或缺的关键一环, 本文将对加油车动态调度展开讨论。

机场地面保障车辆调度问题, 可以简化为序贯决策问题, 面对航班时刻表建立待服务航班序列, 依次选择符合要求的车辆进行服务。在该过程中存在机场航班架次多、服务车辆数量有限、地面保障服务复杂等问题[4–5]。从而导致机场实际运营中决策者需要同时关注多个性能指标, 因此考虑多指标之间的权衡较为符合当前机场地面服务的真实情况。文献[6]将最早到期日算法与蚁群算法相结合, 解决了以最少车辆数量、最小服务航班的总开始时间和最小车辆总流动时间为目标的多目标组合优化问题。文献[7]考虑了多种地面服务操作, 构建了以车辆等待时间与服务总完成时间最小化为目标的优化模型, 并利用约束规划以及大领域搜索对不同的操作进行分解, 最终求得地勤车辆对航班序列的调度方案。然而, 该研究仅考虑了飞行计划, 没有考虑到可能出现的航班提前到港或延误。文献[8]考虑到航班时刻的不确定性, 建立以行驶路径最短与任务均衡为目标的混合整数规划模型，并建立了动态规划时间窗, 利用改进的分支定价算法进行求解。然而面对大规模延误时其实时性无法保证。文献[9]利用机会约束的方法描述不确定的航班时间, 以最小化服务成本与时间建立混合整数规划模型, 利用CPLEX内置的分支定价方法对模型进行求解, 但是没有考虑到航班取消以及同样无法保证面对大量航班异常时算法的实时性。

针对上述研究出现的问题以及机场保障车辆调度的马尔可夫特性, 强化学习成为一种解决该问题较为有效的方法, 其中深度Q网络(deep Q-network, DQN)[10]能够根据实时获取的航班数据, 在有航班需要服务时对加油车辆进行动态调度, 具有极强的实时性, 适用于求解序贯决策以及动态优化问题。本研究建立了加油车动态调度模型, 兼顾了加油任务准时率与平均空闲车辆占比2个优化目标; 将加油车调度抽象成马尔可夫决策过程(Markov decision process, MDP), 并建立了包含状态、动作、奖励的交互环境, 在此基础上将多目标深度强化学习优化框架与DQN相结合, 使DQN适用于多目标问题求解, 并分析了不同参数对实验结果的影响; 最后将实验结果与实际人工调度进行比较, 并给出部分时间段具体的调度方案。

1 加油车调度问题描述与建模

1.1 加油车调度问题描述

传统加油车调度问题中, 地勤服务公司根据提前制定的航班时刻计划表来确定次日的服务车辆工作计划, 并经常以保障车辆为主体编排服务队列。这样的方法可以将相邻停机位或是相邻时间的航班编排进一个服务队列, 在一定程度上节约车辆以及人力资源成本。但是考虑实际情况, 可能会出现的机械故障、天气、临时交通管制等事件导致航班提前或推迟到达机场, 使得相应的服务车辆因等待造成大量的时间浪费以至于造成该服务队列后续航班架次出现延误。因此, 本文以航班为单位, 制定加油服务车辆的动态调度计划。机坪上的停机位和车场可以被视为节点, 航班停靠进停机位可以被视为该位置有服务需求, 根据动态的需求来选择加油车辆为其服务[11]。定义节点集N={0, 1, …, n}, 其中0为停车场, 所有车辆从停车场出发最终回到停车场; 边集E={(i, j)|i, j∈N}; d_i为节点i的需求量; 加油车v∈V(V={1, 2, …, V}), 其中V为加油车的数量; 航班编号f∈F(F={1, 2, …, F}), 其中F为当日计划服务航班总数量。

1.2 加油车调度问题建模

1.2.1 目标函数

在本研究中, 第一个目标是最大化加油任务准时率(以下称任务准时率)。加油车辆在航班可接受服务时间窗范围内对航班进行服务, 则符合准时执行加油任务的标准。这一目标直接影响其他服务车辆对航班的服务流程, 最终影响航班是否能够按时离港。目标函数如(1)式所示。

式中：T为当前时刻；F_T为调度开始至当前时刻服务航班总量; x_f∈{0, 1}, x_f为1表示航班f接受加油服务的时间在时间窗内, x_f为0则相反。

第二个目标函数是最大化平均空闲车辆占比。空闲车辆占比大意味着在调度过程中加油车数量总数不变时, 使用车辆数量少、车辆等待时间少, 相对于时间取平均值能够反映加油车整体的使用情况。目标函数为

式中：σ_vt∈{0, 1}, 当σ_vt为1时表示车辆v在t时刻处于空闲状态；σ_vt为0时则相反, t为从调度周期开始的时间步。

当车辆空闲占比大时, 使用车辆数量少会造成对航班服务的不及时, 导致任务准时率降低。2个目标函数都为无量纲数值, 对其进行线性加权, 用一个总目标函数来衡量总体优化的目标, 将多目标问题转化为单目标问题进行求解。设μ为目标1的权重, 1-μ为目标2的权重, 定义总目标函数max I=μI₁+(1-μ)I₂, 其中μ∈(0, 1), 则目标转化为使得总目标最大。

1.2.2 约束条件

针对时间变量, t_ij为车辆从节点i到节点j的转移时间, t_f为航班f接受加油服务所需要的时间, t_sf^v为车辆v服务航班f的开始时间, t_ef^v为车辆v服务航班f的结束时间; 航班f可接受服务的时间窗定义为[t_lf, t_uf], 其中t_lf为时间窗左限, t_uf为时间窗右限, 即航班f最早接受加油服务时间为t_lf, 最晚接受加油服务时间为t_uf; q_v为车辆v的容量; 决策变量y_vf={0, 1}, 为1表示航班f由车辆v服务, 否则为0。假定服务序列中, 航班h为航班f的后序航班编号。约束条件如下

其中, (3)式保证加油车辆对航班的服务开始时间不能早于该航班可接受服务的时间窗左限; (4)式不仅保证一架航班仅会接受一次加油服务不会被重复服务, 还确保一辆服务车辆同时只能服务一架航班; (5)式确保服务序列中前序航班与后序航班接受服务时间的优先级; (6)式确保加油车容量大于航班燃油需求量。

为使该模型更加贴合实际情况做出如下假设:

1) 规定所有加油车在机坪道路上均为匀速行驶, 速度为20 km/h[12]。

2) 输油管道线路在各主要机场普及程度大, 且各主要机场的加油车辆大都为管道式加油车, 车辆容量不被限制, 假定d_i∈{0, 1}, d_i为1表示停靠在节点i的航班需要加油服务, d_i为0则表示该节点没有需要服务的航班, 车辆容量q_v被赋予一个较大的值。

3) 为方便对车辆进行统一管理, 若车辆在完成服务前没有被安排下一班次任务, 立即返回车场。

2 基于DQN的MDP模型设计

利用深度强化学习算法求解加油车动态调度问题需要建立相应的MDP模型。定义5个车辆状态特征值用以描述加油车群的实时信息; 然后将车辆状态特征输入DQN, 再定义2种对加油车辆的调度方案作为深度Q网络的输出; 进而制定合适的奖励函数对DQN进行训练。最后得到成熟的DQN模型, 从而能够实时地根据变化的航班信息选择不同的调度方案为航班进行加油服务。

2.1 机坪加油车状态特征

为更加直观地观测加油车群实时的信息变化, 建立了车辆信息列表, 见表 1。车辆信息列表记录了不同车辆在t时刻时的空闲状态和车辆的任务执行情况, 帮助计算加油车群的整体状态特征。

在本文的马尔可夫决策模型中, 车辆状态特征由5个部分组成;

动态的任务准时率

动态的任务准时率标准差

航班平均延误时间

航班延误时间方差

为描述机坪加油车群中车辆实时使用情况, 加油车群的空闲占比

综上，在t时刻得到车辆状态特征s_t={O(t), O_sd(t), L(t), L_va(t), P(t)}。

2.2 航班加油服务车辆的动态调度策略

以往面对车辆调度问题建立的MDP模型中, 专家学者们会选择车辆作为动作集合[11], 从计划角度出发, 通过直接选择车辆的方式完成任务。然而在机坪环境下, 受到不确定的航班时间、服务时间等因素干扰, 直接用车辆作为动作集合与优化目标关联程度低。因此, 针对机坪环境, 根据本文提出的2个目标, 制定了2种相应的单指标性能最优的加油车调度策略作为动作集合, 使得DQN能够根据当前实时的车辆状态选择合适的车辆调度策略, 从事件驱动的角度对目标进行优化。2种策略具体操作如下。

1) 在t时刻, 得到任务准时率最高的方案

算法1    第1种加油车辆调度策略

step1   从机场协同决策系统(airport collabora-tive decision making, ACDM)中获取t+1时刻的航班数据;

step2   选择车辆v=arg max|t_sf^v-t_lf|为航班f服务;

step3   执行该调度策略, 更新车辆信息列表;

step4   更新车辆状态s_t;

2) 在t时刻, 得到使用加油车数量最小的方案

算法2    第2种加油车辆调度策略

step1   遍历车辆信息列表, 找出空闲状态车辆集合V_f={v_f|σ_ft=1, v_f∈V}与非空闲状态车辆集合V_nf={v_nf|σ_ft=1, v_nf∈V}, v_f为空闲车辆, v_nf为非空闲状态车辆;

step2   从ACDM中获取t+1时刻的航班数据;

step3   若V_nf不为Ø, 选择车辆v=arg max(t_ef^v_nf)对航班f服务, t_ef^v_nf为非空闲状态车辆完成服务时间;

step4   若V_nf为Ø, 随机选择车辆为航班f服务;

step5   执行该调度策略, 更新车辆信息列表;

step6   更新车辆状态s_t;

根据2种车辆调度策略, 定义动作集合a_t∈{0, 1}, 当DQN在t时刻动作选择为0时, 选择算法1进行车辆调度; 当DQN在t时刻动作选择为1时, 选择算法2进行车辆调度。在加油车动态调度过程中, 同一时刻机场通过ACDM系统仅收到一架航班数据, 对于新增的服务需求, 仅需安排一辆加油车进行服务即可, 因此算法1与算法2的复杂度都为O(V)。在t时刻执行车辆调度方案后, 根据车辆实时信息与车辆各状态计算公式以及新增航班数据, 可以计算出t+1时刻的车辆状态特征值, 从而实现状态转移。

2.3 加油车动态调度的奖励机制

设DQN的目标值为δ_t=r_t+γQ(s_t+1, a_t+1, ϕ), 其中r_t为t时刻DQN输出的调度方案后得到的奖励; γ为DQN的衰减系数, γ∈[0, 1], 值越小表示越看重当下收益, 值越大表示越重视未来收益; Q(s_t+1, a_t+1, ϕ)为t时刻agent的未来期望收益, 其中Q(s_t+1, a_t+1)=max E(γ⁰r_t+1+γ¹r_t+2+…), ϕ为DQN的网络参数。本文确立了任务准时率最高以及平均空闲车辆占比最大2个互斥的目标, 将车辆的实时状态输入DQN得到该时刻下2种方案中最优的车辆调度策略。因此, 为2种不同的策略设置不同的奖励，帮助DQN找到该时刻最优的策略以最大化未来总回报, 制定了如下的奖励机制。

算法3    DQN奖励计算流程

step1   计算t+1时刻的总合目标I(t+1), 若I(t+1)≥I(t), r_t+1=r_t+1;

step2   计算t+1时刻任务准时率O(t+1), 若O(t+1)≤O(t), r_t+1=r_t+0.5否则r_t+1=r_t-5;

step3   计算t+1时刻的航班延误时间方差L_va(t+1), 若L_va(t+1)≤L_va(t), r_t+1=r_t+0.2否则r_t+1=r_t-0.2;

step4   计算t+1时刻空闲车辆占比P(t+1), 若P(t+1)≥P(t), r_t+1=r_t+0.3否则r_t+1=r_t-0.3;

step5   若所有加油任务已完成r_t+1=r_t+10·I(t+1)。

在算法3中, 对总目标以及车辆状态中加油服务平均准时率、航班延误时间方差以及空闲车辆占比的变化、所有加油任务是否完成进行了相应的奖励制定。值得注意的是, 航班可接受加油服务的时间窗为硬时间窗, 当加油车辆开始服务时间大于该时间窗右限时, 造成加油任务平均准时率降低, 该航班将会延误, 因此给予相对严重的惩罚, 奖励值设定为-5。

3 多目标框架下的DQN算法

本研究将DQN算法与多目标深度强化学习框架结合, 多目标框架如图 1所示[13]。

通过MDP模型中的状态设计模块对原始航班数据的状态特征进行提取, 随后输入由多个全连接层组成的多层感知结构得到不同目标对应的一系列参数。算法流程如图 2所示。

其中在线网络与目标网络的结构与初始参数完全一致, 如图 3所示。神经网络结构由输入层、隐含层、输出层组成。将加油车5个状态特征作为神经网络的输入, 输入层节点数量设定为5。隐含层层数过多对结果影响较小且极大地增加模型的训练时间, 因此将隐含层设定为4层, 每层8个节点。输出层设定为2个节点, 网络输出结果代表智能体执行2种调度方案对应的Q值。激活函数选择线性整流单元(rectified linear unit, ReLU)函数。算法训练过程如算法4所示。

算法4    多目标DQN算法训练过程

step1   初始化目标网络参数ϕ^-与在线网络参数ϕ、记忆池、迭代次数e_poch;

step2   重置状态空间, 清空调度结果, 以接收第一架航班数据开始作为0时刻, 最后一架航班的服务完成时间t_ed作为结束时刻, 以分钟做时间步, 初始化t=0, 调度完成标志d_one=0, 初始化状态特征值s₀={0, 0, 0, 0, 0};

step3   若t时刻有需要服务的航班转到step4, 否则转到step11;

step4   生成一个0~1的随机数, 若未命中随机策略概率ε, 计算Q=max Q(s_t, a_t, ϕ); 选择a_t+1=arg maxQ(s_t, a_t, ϕ), 即选择2种调度方案中Q值最大的方案, 否则随机选择一个调度方案;

step5   执行该调度方案, 更新加油车信息列表, 根据从ACDM中获取的航班数据计算t+1时刻的状态s_t+1, 当前时刻奖励值r_t以及实现状态转移, t=t+1。若所有航班得到服务, 则d_one=1;

step6   将(s_t, a_t, s_t+1, r_t, d_one)存入记忆池, 当记忆池长度大于1 000时, 从记忆池中抽取b_atch组数据输入目标网络;

step7   计算目标网络输出最大Q值，, 其中(s_batch, a_batch)为从记忆池中抽取的b_atch组数据;

step8   根据Q与计算损失函数并梯度下降, 更新在线网络的参数ϕ;

step9   若d_one≠1, 转到step3;

step10   若d_one=1, e_poch=e_poch+1, 转到step12;

step11   更新车辆空闲状态, 计算s_t+1并状态转移, t=t+1转到step3;

step12   每过C代令ϕ^-=ϕ, 即将在线网络参数赋值给目标网络。当e_poch>100时, 算法终止, 否则转到step2;

b_atch是人为设定值, 从记忆池中随机抽取b_atch组数据可以打乱数据之间较强的相关性与连续性, 使网络训练更加稳定, C为固定常数。算法中DQN采用ε-greedy策略[14], 若命中，ε概率择选择最大的Q值对应的调度方案, 否则在动作空间中随机选择动作。贪婪参数

e_pocht为当前的迭代次数。ε₁初始值为1逐渐递减至0.02, 保留一定的环境探索能力。使用Adam优化器对网络参数进行优化。损失函数[10]

当DQN模型训练完成后, 可以在任意时刻针对需要服务的航班做出合理的车辆调度方案。

图1 多目标深度强化学习框架

图2 多目标DQN算法流程图

图3 多层感知神经网络结构

4 案例分析

本文使用深度强化学习算法求解机坪加油车群动态调度问题, 实验环境为python3.9, 框架为torch1.12.1, 处理器为AMD Ryzen 7 5800H, 内存为16.0GRAM。

4.1 实验数据与数据预处理

4.1.1 航班数据

以天津滨海国际机场为例, 主要涉及64个停机位, 停机位之间的距离如表 2所示。除此之外, 对真实航班到达与离港时间进行采样与扩充, 固定车辆数量为10, 在2小时内均匀地生成20, 50与90个离港航班实例分别模拟加油车数量过剩、临界充足以及缺乏情景, 分别称为F20, F50与F90。在机场实际运营中, 起降时间偏离计划时间超过15 min的航班被视为异常航班[9]。过站航班的到港时间将极大地影响加油车调度, 图 4统计该机场当日过站航班的到港时间正常情况。根据客机载客量将飞机分为大型、中型、小型客机, 其燃油加注时间分别为30, 25和20 min[15], 包括了加油服务前准备时间, 加油时间以及加油服务后收置设备时间。

图4 某大型机场过站航班的到港时间统计

4.1.2 数据预处理

机场方面可以从ACDM系统中获取当前时刻确定的航班进港或者离港的时间数据, 并在获取数据后即可安排服务车辆对航班进行服务。民航局规定航班需在乘客登机前5 min完成燃油加注, 乘客一般在航班预计离港前30 min登机。离港航班可以分为该机场的始发航班和过站航班。

始发航班可接受加油服务时间窗

过站航班可接受加油服务时间窗

时间窗右限的计算方式与始发航班相同。(14)式中t_re为接收消息时间, (15)式中t_dt为预计离港时间。(16)式中t_at为预计到港时间。在机场正常运营, 仅考虑前序航班的延误或提前抵达时, 航班的离港时间取决于航班开始接受地勤服务的时间, 因此不论是始发航班还是过站航班, 其时间窗右限的计算方式相同, 都取决于航班预计离港时间。

4.1.3 网络参数

DQN网络参数见表 3。

4.2 实验结果与对比分析

4.2.1 消融实验

本文设计的消融实验目的是验证MDP模型中动作设计与随机策略参数ε选择的有效性, 并评估ε-greedy策略与经典贪婪算法之间的差异。实验数据选择规模为50的实例, 目标权重定为0.5。

1) 随机策略参数。面对动态的航班信息, 网络训练的每一代中, 智能体在面对同样的状态下选择的动作, 最终Q值不一定相等, 这取决于航班到港时间是否正常, 因此需要智能体尽可能多地收集环境信息。为此, 本文额外评估了2种不同随机策略参数ε的取值, 具体如下:

式中：ε₂形式为反比例函数, 在训练开始时较大, 随着迭代次数的增加逐渐趋向0；ε₃为常数形式, 0.1是在DQN相关研究中随机策略参数选择较多的值。

2) 动作设计。为验证以调度策略为动作集合的有效性, 重新设计了以车辆编号为动作集合的MDP模型——DQN(Act-v), 在决策点直接选择车辆为航班服务。

3) 动作选择策略。除带有随机参数的贪婪策略外, 还对基于经典贪婪算法的动作选择策略进行测试以验证随机策略参数ε选择的有效性。

消融实验结果如图 5所示。从图中可以看出DQN(Act-v)无法收敛且总目标值明显低于以调度策略为动作集合的MDP模型设计方式。基于公式(17)的ε选择在训练开始迅速收敛, 达到了较好的结果。然而, 随着训练的进行ε值逐渐接近0.01, 小于ε₁的最终值0.02, 却依然出现较大波动。证明由于训练前期ε值缩小过快导致环境探索不完整, 训练结果不稳定。基于公式(18)的ε选择虽然偶尔可以达到最大总目标值, 然而其波动更为剧烈。基于经典贪婪算法的动作选择策略一直保持Q值最大的选择, 遏制了智能体对周围环境的探索, 基本保持初始值不变, 与ε-greedy策略存在较大差距。本文选择的ε值ε₁在训练进行中逐渐缩小, 充分探索了状态特征空间, 最终收敛到总目标最大值并较为稳定。

图5 消融研究的训练曲线

4.2.2 双目标实验结果

对2个目标的变化情况进行了跟踪, 保持参数不变, 结果如图 6所示。从整体上看, 随着迭代进行, 任务准时率与平均空闲车辆占比收敛到一个稳定的值。当任务准时率大时, 平均空闲车辆占比下降, 符合实验预计以及实际情况。

图6 双目标训练曲线

4.2.3 目标权重取值分析

为验证不同的目标权重对结果的影响, 本文对不同目标权重取值进行了实验。由于车辆充足时已验证目标1达到1以及目标2收敛到稳定值, 因此为更好地展示不同权重下的任务准时率与平均空闲车辆占比情况, 选择实验数据选择规模为90的实例, 确保目标1与目标2的值有较为明显的变化。每个权重取值下进行10次实验取平均值。具体变化如表 4所示。

当μ=0.1时, 此时平均空闲车辆占比最大, 任务准时率最低; 当μ=0.9时, 此时任务准时率最高, 平均空闲车辆占比最低, 在调度过程中车辆使用数量最多。即随着目标权重值增大, 任务准时率逐渐提升, 平均空闲车辆占比下降, 符合实验预期。同时, 由于MDP模型的奖励部分中给予目标1较高的奖励以及在车辆不足情况下目标2的值接近0, 因此总目标值随着目标权重增加而增加。综合车辆充足与车辆不足2种情况, 证明了目标权重μ的取值影响了2种目标的偏向, 最佳的权重值为0.9。

4.2.4 泛化研究

使用训练完成的DQN模型对不同数量的加油车和不同数量的航班实例进行了验证, 固定目标权重, 结果如表 5所示。通过横向对比可以发现, 在相同的车辆数量下随着航班实例的增加, 总目标值随着任务准时率与空闲车辆的下降而下降, 运行时间也有所上升。通过纵向对比可以发现, 同时扩大车辆数量以及航班实例, 虽然运算时间有所增加, 但是依然保持较短的求解时间, 证明了算法对于求解不同规模、不同车辆情况的决策能力以及算法的实时性。

4.2.5 对比分析

本研究建立的优化目标中含有当前时间T, 其具有强时间特征, 无法利用传统的分支定价以及智能优化算法求解, 这些方法只能得到一个全局的可行解而无法计算实时的优化目标。因此, 使用连续7天的实际航班数据, 将DQN调度结果与DQN(Act-v)、先入先出(first in first out, FIFO)以及实际应用的人工调度结果进行对比, 对比结果如表 6所示。

在按时完成加油任务数量方面, 由于将MDP模型中的动作集设计为选择车辆策略, 增强了动作与奖励之间的联系, 在使用连续一周真实数据进行的测试中, 效果显著。DQN算法连续7天最大, 总计比人工多完成66个任务, 平均每天多完成约9.43个任务, FIFO算法与人工调度结果接近, DQN(Act-v)效果最差。在平均使用车辆数量方面, DQN、FIFO与人工调度相接近, 平均每天DQN比人工调度的平均使用车辆少约0.04辆, DQN(Act-v)按时完成任务数量最少, 因此平均使用车辆数量最大。相较于人工调度, DQN加油车群平均每日总工作时间少57.6 min。结果表明, 该方法对车辆的使用更加高效, 有较高的实际应用价值。表 7展示了周三部分航班的调度结果。

5 结论

机场地勤车辆调度一直是智慧机场建设的重要组成部分。本文以加油车为例, 结合实际需要建立了多目标优化模型以及相应的MDP模型, 利用DQN算法解决了加油车动态调度问题。相较于大领域搜索以及分支定价算法在面对航班到港时间异常时较长的运算时间, 本文算法可以直接调用训练好的模型, 极大降低了运算时间。并利用连续7天的实际数据对本文算法进行了验证, 显示了本文算法在解决动态调度问题上的有效性。

References

All Tables

All Figures

	图1 多目标深度强化学习框架
In the text

	图2 多目标DQN算法流程图
In the text

	图3 多层感知神经网络结构
In the text

	图4 某大型机场过站航班的到港时间统计
In the text

	图5 消融研究的训练曲线
In the text

	图6 双目标训练曲线
In the text