机场地面服务人员须要承担航班、行李、乘客等一系列保障任务[1]．地服人员执行保障任务须要满足时间、空间等要求，例如须要在航班降落后进行接机工作、在航班起飞前完成送机工作等，这些工作是以航班为单位进行的．而航班的起降时间往往是动态变化的，使得人员排班须要进行动态的调整．此外，当航班密集时，将出现多架航班同时起飞或降落，使得人员排班容易发生时间、空间等冲突，故机场地服人员动态排班问题具有很大难度．在人员排班或类似问题的研究中，优化目标主要是任务完成率、员工工作时长和资源利用率[2-9]等，使用的方法主要有排队论[2]和模拟退火[7]等．文献[6]以班型为保障单元，以员工资质为主要约束，以员工工作时长为优化目标，对机场的动态班型进行求解，其中班型是由同一时间段的航班构成，即将员工的工作内容按时间段划分．此外，该研究认为传统的启发式方法不适应动态排班，然而该研究只针对当前解进行优化，没有对将来的状态进行预估．文献[2]使用了排队论预测员工的需求，具有一定前瞻性，并实时对排班结果进行动态调整，但不是以航班为单位的动态排班．以航班为单位的人员排班能够更好地应对航班密集的情形．根据文献[10-12]，国内枢纽机场航班集中在7︰00—15︰00，在该时间段，排班须要面临密集的航班任务，此时员工往往须要先后服务多个航班．可见地服人员知道自己工作的时间段是不够的，还须要知道自己服务于哪个航班，并按时完成具体任务．而根据文献[13]，一个航班的地面服务必须在飞机关闭舱门之前全部完成，否则将大概率导致航班延误．所以在机场的实际排班过程中往往须要以航班为单位，将人员分配到具体航班中．深度Q网络(DQN)[14]能够较好地根据动态变化的数据，在决策点选择最优策略，适用于求解动态优化问题．本研究建立地服人员排班的优化模型，该模型以航班为单位，以航班时刻、需求、员工资质等为约束，综合了任务完成率与员工工作时长两个优化目标；采用DQN算法对模型进行求解，针对优化模型，建立合理的DQN交互环境，提出适用于多目标优化的奖励机制；最后将实验结果与人工排班结果进行对比，并对优化模型参数进行了分析．1 机场地服人员排班问题定义与建模以某国际机场旅服中心为例，该中心的排班须要在将员工分配到班型的基础上，进一步对航班需求进行分析，给员工分配具体的保障任务．由于该过程中任务数量较多，且对任务完成时间、完成数量有要求，因此须要建立面向任务的排班优化模型．1.1　问题定义旅服中心的地服人员排班问题是一个动态排班问题，须要考虑航班的种类、时刻、保障需求，以及员工的数量、资质等因素，同时须满足员工空间约束、员工资质约束、航班时刻约束，使得员工能妥善执行航班的若干旅服任务．本研究对这些约束进行了一定的简化与归纳，总结如下：a．在同一时间，每个员工只能服务一个航班，不能发生人员冲突；b．满足航班任务需求对应的资质或职责；c．员工必须在航班离港前完成任务．本研究暂不考虑由极端天气、空中管制等特殊原因导致的机场航班大面积延误中的员工重排班问题．1.2　问题建模问题的优化目标为最大化航班任务的计划执行率与最小化员工的有效工作时长．若员工可以按照任务的计划时间完成任务，则满足任务计划的执行要求，否则将影响计划执行率．设Y为排班结束时刻，NY为该机场旅服中心一共服务航班数，M为员工总数，Ti为第i个航班中按照任务的计划时间完成的任务数，eik为第i个航班的第k类任务需要的资质数，则航班中按照任务的计划时间完成的任务数所占的比例R可表示为R=∑i=1NYTi  /∑k=1Heik/NY．(1)设σjt为员工j在t时刻的累计工作时长，则在Y时刻员工的有效工作时长占比U可表示为U=∑j=1MσjY/Y/M．(2)设λ为优化目标的加权值，λ∈[0，1]，则根据R和U可以得到总优化目标为I=λ(1-R)+(1-λ)U．根据约束、定义的模型变量和优化目标I，本研究建立的优化模型的优化目标为Min I．约束条件可归纳为：a．maxj∑i=Nt-1Ntbij≤1,∀t，若第i个航班分配了第j个员工执行工作，则bij=1，否则bij=0，该约束代表员工同一时间只能服务一个航班；b．∑jbijqjk≥eik,∀i,k，其中qjk∈{0，1}为第j个员工是否具备执行第k类任务，该约束代表员工须要满足航班的资质数需求；c．bijxjt≤maxk(dik),i∈[Nt-1,Nt],∀t,j，其中，xjt为t时刻第j个员工最后一个任务的完成时间，dik为航班i第k类任务的结束时间，该约束代表分配的员工必须在航班离港前完成任务；d．航班任务还须满足基本约束，即gik-dik0，其中gik为航班i第k类任务的开始时间．2 基于DQN机场地服人员排班建模求解机场动态排班问题，首先须要根据机场地服人员排班的特点和排班优化模型，定义6个状态特征值描述排班状态；然后将特征值作为DQN的输入，定义两个分配方法作为DQN的输出；进而定义适用于机场排班的奖励函数对DQN进行训练；最后得到训练成熟的DQN，从而能够实时地采取不同分配方法求解排班模型．2.1　针对机场动态排班的状态特征设在t时刻中心累计服务的航班数为Nt，根据式(1)，在计划执行率方面，动态的平均计划执行率为R(t)=∑i=1NtTi/∑k=1Heik/Nt，动态的平均计划执行率标准差为Rstd(t)=∑i=1NtTi/∑k=1Heik-R(t)2/Nt1/2．根据式(2)，在工作有效时长方面，动态员工平均有效工作时长占比为U(t)=∑j=1Mσjt/t/M，员工工作时长的标准差为Ustd(t)=∑j=1Mσjt/t-U(t)2/M．此外，为描述整体的排班情况，按计划时间执行的任务数与总任务数的比值为O(t)=∑i=1NtTi/∑i=1Nt∑k=1Heik．设员工j在时刻t的空闲状态为μjt∈{0，1}，μjt=1表示空闲，则员工的空闲程度占比为C(t)=∑j=1Mμjt/M．根据上述的各状态值计算公式，可以得到智能体在决策时刻t的状态值为s(t)={R(t)，Rstd(t)，U(t)，Ustd(t)，O(t)，C(t)}．2.2　针对机场动态排班的分配方法考虑每一时刻的计划执行率和工作时长占比两个因素，定义两种不同的员工分配方法作为机场动态排班的动作集．a．在时刻t，对于航班i，生成有效工作时长最小的员工集合的分配方法如下．算法1 第一种员工分配方法步骤1 生成所有满足约束的员工分配方案Wt={Bi1'，Bi2'，…，Bic'，…}，其中Bic'={bi1，bi2，…，bij，…，biM}；步骤2 计算实施Wt每一个方案后，对应每个方案的员工的有效工作时长集合{σ1t'，σ2t'，…，σMt'}；步骤3 计算员工集合Bi'=argminB'∈Wt∑jσjt'；步骤4 航班i的员工集合Bi=Bi'，更新员工空闲状态C(t+1)=C(t)．b．在时刻t，对于航班i，生成与航班i的时间匹配最相近的员工集合的分配方法如下．算法2 第二种员工分配方法步骤1 随机员工分配数组Bi={bi1，bi2，…，bij，…，biM}；步骤2 若Bi不满足航班i的模型约束，则初始化员工集合Pi={j|μjt = 1，qjk 0}；步骤3 分配员工w=argminPi∑kxjt-gik；步骤4 选择w员工服务航班i，即biw=1，验证Bi是否满足航班i约束，若满足则算法终止，否则转到步骤2．进而，根据两个分配方法，定义在任意时刻t，DQN的输出为at，当at=1时，对每个未分配员工的航班采用算法1执行排班；当at=2时，对每个未分配员工的航班采用算法2执行排班．排班过程中，状态特征值s、员工空闲状态等会随时间发生变化．在时刻t，根据某国际机场的机场协同决策(ACDM)系统，获取在t+1时刻的航班动态信息，包括航班类型、机位、登机口和起降时间等；然后可以确定对于新增航班i，i∈[Nt+1，Nt+1]，新增任务需求为{ei1，ei2，…，eiH}；根据新增的航班任务，执行所选的分配方法，进而可以计算出t+1时刻的状态特征s(t+1)，实现排班状态的转移．3 机场动态排班奖励机制设在t时刻的决策为at，rt为智能体需要的奖励值，γ为DQN衰减系数，yt=rt+γQ(s(t+1)，at+1；w)为DQN的目标值，其中：w为DQN的网络权重；Q(s(t+1)，at+1；w)为t时刻的未来期望收益．本研究根据状态特征值，设定针对排班过程的奖励机制．算法3 DQN奖励的计算方法步骤1 计算t+1时刻的优化目标I(t+1)；步骤2 若优化目标减小，则I(t+1)I(t)，rt=1；步骤3 若空闲员工比例增大，即C(t+1)C(t)，则rt=0.5；步骤4 若整体执行率减小，即O(t+1)O(t)，则rt=-0.5；步骤5 若整体执行率增大，即O(t+1)O(t)，则rt=0.5；步骤6 若整体执行率不变，即O(t+1)=O(t)，则rt=0；步骤7 若排班完成，则rt=[1-I(t+1)]×10；步骤8 若排班失败，无法继续分配，则rt=-10．在算法3所示的步骤中，依次根据优化目标I、空闲员工比例C和整体执行率O的变化情况进行相应奖励．此外，当排班完成时，须要根据最终的优化目标进行正奖励；当排班无法继续分配，即不存在当前时刻的可行解时，进行负奖励．4 基于DQN机场地服人员排班求解本研究采用DQN方法求解机场动态排班问题，基于Matlab 2021a开发环境，处理器为Intel Core i7-8750H CPU @2.20 GHz，内存为16.0 GiB RAM．4.1　实验数据与参数本研究所参照的数据来源为某国际机场的旅服中心，该中心主要负责过站航班与离港航班两种类型的地面服务保障．选取的航班计划数据是该中心连续7 d的7︰00—15︰00时间段航班计划数据；选取工作于该时间段的14人班型如表1所示．员工须要承担的任务分为送机、接机、主班(也称外场监护)、导乘和分队长共5种，表中：“是”代表该员工在当天可以承担对应工作；“否”代表不能．地服人员须要承担的任务分为送机、接机、主班、导乘和分队长共5种，各任务持续时长分别为60，15，60，30，30 min．10.13245/j.hust.221106.T001表1旅服中心部分员工职责划分表员工代号送机接机主班导乘分队长1是是否否否2是是否否否3是是是否否4是是是否否5是是否是否6是是否是否7是是是否否航班的需求类型与航班号、停靠廊桥类型、飞机型号、承载人数和旅客等因素有关，本研究根据航班需求的资质组合，将航班需求分为13种主要类型．任务需求类型与对应人数如表2所示．10.13245/j.hust.221106.T002表2部分航班任务需求表航班类型需求类型送机接机主班导乘分队长过站普通22000过站载客数3011000过站主班22100离港主班、导乘10100离港特殊机位20100离港载客数6020111此外，DQN的训练须要设置相应参数．本研究所选用的DQN经验集大小设为64，γ=0.99，初始随机动作概率ε=1，随机动作概率衰减系数ω1=0.99，初始学习率l1=0.100，最小学习率l2=0.001，网络输入层节点数为6，隐含层层数为4，隐含层节点数为32，网络输出层节点数为2．DQN采用的神经网络由输入层、4个全连接层构成的隐含层，输出层组成，激活函数选用线性整流单元(Relu)激活函数，网络结构如图1所示．10.13245/j.hust.221106.F001图1网络输入输出示意图4.2　实验步骤基于DQN方法的基本原理，具体训练步骤如下．算法4 针对机场排班的DQN训练步骤步骤1 初始化经验回放队列F、Q网络与网络权重参数w、员工初始数据、迭代次数α=1；步骤2 重置状态空间，清空排班结果，以7︰00作为0时刻，初始化t=0 min，排班完成结束标志z=0，初始化状态特征值s0={0， 0， 0， 0，0， 0}；步骤3 生成0～1的随机数，若命中随机策略概率ε，则at=arg max Q(st，a；w)，否则随机选择一个分配方法；步骤4 根据at，执行分配方法，根据分配结果与新加入的航班，计算t+1时刻的状态特征st+1和奖励值rt，若无后续航班，则z=1；步骤5 (st，at，st+1，rt，z)存入经验队列F，t=t+1；当经验队列F的长度64时，回放64条经验，更新w；步骤6 若z≠1，则转到步骤3；步骤7 若z＝1，则α=α+1，当α1×104时，算法终止，否则转到步骤2．训练成熟的DQN可以在每一个时刻下达有利于优化模型的员工分配决策．4.3　实验结果在λ=0.5的情况下，模型1×104代的训练过程中，计划执行率R的变化过程如图2所示，员工有效工作时长占比U变化过程如图3所示．10.13245/j.hust.221106.F002图2计划执行率变化图10.13245/j.hust.221106.F003图3有效工作时长占比变化图在训练过程中，由于航班起降时间的不确定性和采集的经验样本存在随机性，因此两个优化目标的变化过程在1 000～6 000代之间出现了一定程度的波动，而在6 000代后波动减小．整体上看，计划执行率随迭代次数增加而增加，员工工作时长占比随迭代次数增加而减少，符合实验预期，部分排班结果如表3所示．10.13245/j.hust.221106.T003表3部分航班排班结果表航班号机位登机口进港时间离港时间员工HU788915#15#—7︰201，5SC88127#8#—7︰252，3SC875513#13#—7︰358CA43698#8#—7︰509SC470514#14#—8︰0010SC228117#17#—8︰0011…CA415216#13#9︰4511︰252CA12937#10#11︰1012︰453HU738813#11#—13︰307CA147714#14#12︰0513︰354，14SC469911#17#—13︰401HU724615#15#12︰4513︰509注：“—”表示无此项；“…”表示省略上午时段的普通类型离港航班．4.4　实际人工排班对比分析本研究将DQN排班结果与实际人为排班结果进行了比对．采用某国际机场7 d的实际航班动态数据，比对了DQN与人工排班的效果，λ=0.5．对比实验结果如表4所示．10.13245/j.hust.221106.T004表4连续7天DQN与人工排班对比表周一周二周三周四周五周六周日求和按时完成任务数人工93112114122113107124785DQN93113114124112107125788有效工作时长/min人工2 6953 1803 4553 3253 0553 0753 50022 285DQN2 6903 1753 2553 2953 0452 9903 46521 915在按计划时间完成的任务数方面，DQN与人工结果接近，总计比人工多完成3个任务，平均每天多完成约0.43个；在有效工作时长方面，DQN相较节约了370 min，平均每天比人工少约53 min．结果表明：DQN的排班结果具有明显优势，对人员的利用更加充分．4.5　参数分析本研究对λ的影响进行了分析，λ分别取0.1，0.3，0.5，0.7，0.9，统计7 d的排班结果的计划执行率与工作时长占比，并计算平均值．计划执行率变化如图4所示，平均工作时长变化占比如图5所示．10.13245/j.hust.221106.F004图4平均7 d计划执行率随λ变化图10.13245/j.hust.221106.F005图5平均7 d员工有效工作时长占比随λ变化图当λ=0.1时，排班的工作时长占比最优，任务完成率较差；当λ=0.9时，任务完成率最优，工作时长占比较高，员工负担较重．任务完成率与工作时长占比都随λ增大而增大，符合预期，证明了λ的取值可以一定程度影响目标值的对任务完成率与工作时长占比的偏向．5 结语本研究针对机场地服人员动态排班问题，提出了一套有效的解决方案．该方案具有如下特点：a．当航班密集时，以航班为单位对员工进行排班，员工的工作内容更加详细；b．考虑员工资质与任务相匹配、任务按时完成、员工时间不冲突三个约束，以员工工作时长与任务完成率两个指标作为优化目标，建立优化模型；c．考虑航班时刻的动态生成，采用DQN方法，在不同时刻选择不同的员工分配方法，有利于综合目标值的动态优化，并达到预期效果．本研究也存在值得进一步探讨的方面：由于选择的状态特征与策略有限，因此使用的深度神经网络结构较为简单，若能引入更加复杂的结构，则可能达到更好的效果；未考虑一些特殊的排班逻辑，例如停机位相隔较近的航班可以调遣同一个员工执行任务等．