机场国际值机室人员排班研究

詹智勇，陈庆新，毛 宁，刘建军，程 宇

（1.广东工业大学机电工程学院，广州 510006；2.广东机场白云信息科技有限公司，广州 510470）

0 引言

经济的快速发展使得人们对于出国旅游的接受度和热情日渐提高，这直接导致了机场国际航班业务量的快速提升。当前，机场设有专门的国际值机室负责国际航班的值机服务。值机室除值班主任与各值机员工外，还配有排班员负责值机员工的班表编排。这种排班员手工排班的方式缺乏有效的排班理念与工具，不仅排班效率低下，处理规模有限，而且难以排出满足现有各类约束的方案。面对机场国际航班业务量与国际值机室值机员工的快速增长，手工排班的方式已无力应对。因此，机场亟需引入一种高效可行的方式以解决国际值机室的人员排班问题。

人员排班问题起源于1954年Edie[1]提出的收费站员工分配问题，旨在快速、有效且合理地将员工分配到班次任务上[2]，其本质上是一类组合优化问题。医护人员的排班一直是人员排班问题研究的热点[3-4]，但随着经济的快速发展，人员排班研究开始向服务业各个领域扩展。作为旅客获取航空服务的核心场所，机场所提供的服务种类复杂，每一项服务都设有对应的业务室负责，Clausen[5]将其分为围绕飞机进行的停机坪任务和围绕旅客进行的航站楼任务。停机坪任务包括行李装卸、客舱清洁、给油给水等。刘德刚[6]将机舱清洁的人力资源优化分为人员排班和现场调度两个子问题，保证高峰时期人力需求得到满足以及人力资源得到最优利用。Ho等[7]则对飞机的航空餐配送服务展开研究，其需要为业务室员工组建团队并分配任务，该问题兼具人员排班与路径规划的特征。事实上，绝大多数停机坪任务都具有这样的特点。

航站楼任务的人员排班研究多集中在安保和值机服务，这些服务的人员需求与旅客的到达分布息息相关，因此常使用排队论对各时段的人员需求进行预测[8-9]。Stolletz[10]考虑具有时间需求与层次资质的人员排班问题，其将各航班的值机人数需求转换为各时段的人数需求，以此确定值机员工的轮班安排。Zamorano[11]针对具有单一资质的值机员工排班问题设计混合整数模型，并基于模型结构设计分支定界算法进行求解。Lin等[12]则以减少值机柜台开放数量与员工上班时间为目标，在总结旅客行为与一系列服务需求特征的基础上构建了基于特定时间窗的线性规划模型。

上述研究几乎都是基于确定班次展开，以满足各时段的人员需求为基本目标，并不能直接应用于国际值机室的人员排班。实际上，国际值机室的人员排班具有非常明确的值机任务信息，包括任务的开始结束时间与资质、人数要求。且由于各值机员工所具备的资质组合并不相同，因此国际值机室的排班是直接将值机任务指派到各员工的，这是一类基于确定任务的排班方式。本文以机场国际值机室为背景，构建机场国际值机人员排班优化模型。同时，针对模型约束结构设计休息时间约束压缩规则，其能在减少模型约束数量的同时加强模型的约束强度，进而加快求解速度。基于实际数据集的仿真实验验证了本文模型与规则的有效性。

1 问题定义与建模

1.1 问题定义

机场国际值机人员排班是指在给定值机任务集合与值机员工信息的前提下，满足实际排班所要求的各项约束，将值机任务全部指派到员工，进而确定各员工每工作日的上下班时间。

机场国际值机室以一周7个工作日为长度进行排班，以J表示排班周期长度，令j＝1,2,…,J。待排班的国际值机任务集为其中I为值机任务总数。对每一任务i有：Tis为任务的开始时间；Tie为任务的结束时间；Ji为任务所属的工作日；Ni为完成该任务所需的人数；Qi为任务所要求的资质，不具备对应资质的员工不允许完成该任务。Ω中的任务按照所属工作日、任务开始时间、任务结束时间升序排列，保证排序靠前的任务早于排序靠后的任务开始。

参与排班的值机员工集合P＝{1 ,2,…,K}。对每一员工k，记Qk为该员工所具备的资质集合。值机员工的Qk与值机任务的Qi可正交出资质矩阵Q。对Q中的每一元素Qik有：若员工k具备任务i所要求的资质，即Qi∈Qk时，有Qik＝1；否则有Qi∉Qk，Qik＝0。

模型决策变量xik∈{0 ,1}表示员工k是否执行任务i：xik＝1表示执行。依据xik可推导出变量wdjk表示员工k第j个工作日是否上班。另外设置变量wtdjk≥0计算员工k第j个工作日的上班工时。

1.2 问题建模

结合国际值机室的实际排班要求与上述定义，机场国际值机室人员排班问题建模如下：

将该模型称为模型P。式（1）为模型优化目标，旨在均衡各员工排班周期内的上班工时。式（2）表示任务必须指派到足够数量的员工。式（4）～（5）计算并约束员工每工作日的上班工时，为该员工工作日内完成任务的总工时。通过控制式（5）的作用：当员工该工作日不上班时有被约束为0；当员工该工作日上班时有wdjk＝1，员工的上班工时被控制在规定的上下限范围内，。式（6）控制员工在排班周期内的上班天数不会超过规定的上限。式（7）计算员工排班周期内的上班工时。式（8）～（10）为变量定义。易知，当Qik＝0时，决策变量xik会退化为常数0。为避免这类无效变量的生成，当Qik＝1时才会生成对应变量，以保证生成的变量都是有效变量。另外，在具有xik参与构建的约束中均加入来自Q的限制，避免这些约束加入没有定义的变量。

式（3）为休息时间约束，其通过限制员工分配到部分任务组合以保证员工在排班周期内能够有足够的休息时间。对具有资质的两任务i1和i2（i1早于i2开始），当两任务的时间关系满足如下条件时，员工不能同时分配到该两任务：（1）若两任务属同一工作日，该两任务之间的时间间隔不足TtR；（2）若两任务属同一工作日，该两任务组成的班次长度长于L，此处班次长度包含完成值机任务的工时与任务之间的休息时间；（3）若两任务分属不同的工作日，该两任务之间的时间间隔不短于条件（1）保证员工在完成两值机任务之间能有足够的任务间休息时间；条件（2）保证员工该工作日上班时班次长度不会过长；条件（3）保证员工在连续若干工作日上班时，相邻两个工作日班次之间能有足够的班次间休息时间。使用集合Ct＝{ }( )Ip,k 表示模型存在的所有休息时间约束，其中

2 休息时间约束压缩规则

观察模型，休息时间约束（式（3））占据模型约束的绝大部分，这些约束仅由2个决策变量构成，结构松散。若将模型的决策变量映射为顶点，这些休息时间约束映射为边，那么这些约束可映射为一张图。由于这些休息时间约束是同一员工的决策变量生成的，不同员工的决策变量不存在这种关系。因此这张图实际上是由K互不连通的子图组成。

如图1所示，令其为这些子图中的一张，这张图包含12个顶点与36条边，表示员工k可完成的12个值机任务与这些任务之间共36条休息时间约束。观察该图，图中顶点1、2、5相互连接，构成该图的一个团结构。同时，团结构中连接顶点的边其对应约束相互制约，使得该员工最多只能完成这3个任务中的一个，这一约束可表示为x1＋x2＋x5≤1，称这类约束为团约束。与图中各条边所对应的休息时间约束相比，这条基于团结构生成的团约束不仅包含团中所有边的约束信息，同时还具有更紧凑的约束形式与更强的约束能力。

图1 员工k休息时间约束映射

继续观察该图，图中顶点10与顶点1、2、5相互连接，团结构在原来的基础上进一步扩大，其对应的团约束为x1＋x2＋x5＋x10≤1。随着团结构的扩大，团约束所包含的约束信息越来越多，同时其约束能力也越来越强。因此可将模型中的休息时间约束替换为对应的团约束，同时达到压缩模型约束规模与增强约束能力的目的。为最大程度利用团约束的这些特性，用以替换的团约束应包含尽可能多的任务，故应尽量枚举出对应图的极大团，即增加任一顶点都不再符合团定义的团[13]。另外，团约束必须完整包含模型原有的休息时间约束。基于上述要求，本文设计休息时间约束压缩规则，旨在将模型中的休息时间约束替换为团约束。嵌入规则的模型求解流程如图2所示。

图2 嵌入规则的模型求解流程

规则获取待操作的模型以及所需数据作为输入，包括该模型的休息时间约束集合Ct与值机员工集合。模型需要在现有Ct的基础上构建并添加团约束，因此首先需要删除Ct所包含的约束，保证模型不存在任何形式的休息时间约束。

对员工k完成上述定义后，对Ik中的每一任务i调用constraintMerge算法。该算法基于图论中极大团枚举的BK算法进行改进[14]，旨在找出覆盖所有休息时间约束且包含尽可能多任务的团结构。constraintMerge算法包含3个输入：cur为当前解，表示当前搜索到组成团结构的任务集合，令cur＝{}i；cond为备选集，表示可加入当前团结构的任务集合，cond＝condi；ret为结果集，其包含该算法找到的所有团结构，初始化ret＝∅。constraint-Merge算法流程如表1所示。

表1 constraintMerge算法流程

算法首先判断cond是否为空。cond为空表示当前输入的cur以是算法搜索到最大的团结构。在加入到ret前，cur需要与当前ret保存的团结构cl进行比对，以确保ret不会保存重复的团结构：若比对到cur⊆cl，则表示ret已保存有该团结构的信息，算法将停止比对并返回上一层递归；若比对到cl⊆cur，则表示cur保存有该团结构的信息，算法将删除该团结构。比对完成后cur将加入到cur中并返回上一层调用。

若cond非空，则表示当前输入的cur仍可进一步扩大，可继续向cur添加任务。算法依次从cond弹出序号最小的任务i并加入到cur中。此时因cur增加了任务，故需要更新cond以保证其包含的任务均可加入到更新后的cur组成更大的团结构。cond与任务i的备选集condi做交集后，进行算法的递归调用。如此循环直至cond为空，算法返回上一层调用。

对员工k的constraintMerge算法执行完成后，ret保存算法搜索到所有的团结构，对每一个团结构cl所包含的任务，员工k最多只能完成一个，这一约束可表示为：

该约束即为团约束，对ret中的所有团结构构建这一约束并写入模型中。当所有员工均完成上述步骤后，规则返回更新后的模型。

3 仿真实验与结果分析

3.1 实验数据

实验数据选自某大型国际机场国际值机部2019年不同时期共4周的生产数据集，包括值机任务数据与值机员工信息，数据集具体信息如表2所示。

表2 数据集信息

模型构建及算法采用Java编写，模型使用Gurobi求解器进行求解，运行硬件环境为Intel（R）Xeon（R）CPUE5-2695 v4＠2.1GHz，8G内存。依据国际值机室实际排班规定，模型参数设置如表3所示。

表3 模型参数设置

模型P为一混合整数规划模型，求解器往往需要花费大量时间以证明当前找到的解为最优解。为避免实际排班过程中排班员的等待时间过长，求解器需要设置求解时间相关参数，如表4所示。

表4 求解器参数设置

3.2 实验结果与分析

4个实际案例的模型优化结果与手工排班结果对比如表5所示。由于参与排班的任务与员工规模庞大，4个案例的手工排班均需要约1周的时间，且由于排班需要遵守的休息时间约束复杂，手工排班方案存在部分不能满足约束的情况。而模型排班结果均在规定的求解时间相关参数设置下求出，不仅完全满足模型所有约束，同时得到的排班结果均比手工排班更优。

表5 案例结果对比

表6所示为4个案例所生成模型的约束数量情况，表中其余约束为模型中除休息时间约束/团约束以外其余约束的数量；压缩比则为团约束与休息时间约束的比值。原模型中休息时间约束占据模型约束的绝大部分，而基于规则生成的团约束则仅以约10%的规模完全覆盖休息时间约束。同时，团约束所带来约束强度的提升也加快了求解器的求解速度。观察表5：案例3、4均以更短的求解时间求得低于规定MIPGap值的解；案例1、2则是在规定的求解时间内求得/证得具有更优Gap值的解。

表6 模型约束情况

4 结束语

本文以机场国际值机室为背景，研究一类基于确定任务的人员排班问题。针对手工排班存在的效率低下、处理规模有限等问题，基于值机室排班要求构建国际值机人员排班模型，并考虑模型约束结构设计休息时间约束压缩规则。基于实际案例的实验表明，本文所构建模型得到的排班结果在求解时间与解优度均优于手工排班方案。同时，休息时间约束压缩规则能有效减少模型约束数量，约束强度的提升也进一步提升了模型求解速度。目前本文研究成果已应用在某机场的自动排班系统中，极大提高了值机室的排班效率。