某机场客舱清洁部排班优化算法研究

吴植英，汪春华，曹紫萱，杜晴晴，徐伟彬

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

0 引言

目前随着国内航空事业的不断扩大，国内各大航空公司的飞机数量也在不断增加。如何合理地进行排班管理，有效利用人力资源，提高员工的劳动绩效，降低整体的运营成本，提高生产力以及整个客舱清洁部门的投资回报率，是每一个机场发展到一定阶段，管理者都要面临的问题。

客舱清洁排班管理研究的目的是科学合理地安排人力资源，从而有效地分配任务，让最适当的人，在最适当的时间，担任最适合的任务，以达到人员与飞机的合理匹配。对管理者而言，其不仅要能有效地管理客舱清洁部门的人力资源，节约人力成本，而且还要进一步满足客户服务的要求，从而达到提升客舱清洁部门的运用管理水平，降低调度频率以及客舱清洁部门的运营成本，提高整个航空公司的投资回报，增加企业收益。

排班问题是一个时间表问题，是运筹学领域中组合优化问题之一，就是运用数学、计算机等领域的方法，在有限的时间内去寻找一个最优组合。国外研究人员对员工排班问题的研究起步较早，研究方向主要集中在员工排班问题的建模和算法实现两个方面。

1976年，Baker K[1]提出了基于员工工作负荷拍板的数学模型，并将该模型应用于多个工种类型的领域内。1990年，Nagraj Balarishnan和Richard T Wong[2]运用网络流技术，研究了基于工作负荷的员工排班问题，将排班模型的所有约束都集成到所建立的网络中，而最佳排班方案就是所建立网络中的一条路径，最后的计算结果说明该方法非常适用于解决大型的排班问题。2001年，C K CHU[3]研究了机场地勤员工弹性排班问题，排班模型是整数规划模型，目标是在排班结果维持一定员工富余量的基础上，最小化需要加班员工数量。2003年，Luca Di Gaspero等[4]提出了最少排班次数模型，其目标在满足员工负荷和实际需求负荷之差在一定可接受范围内的情况下，最小化员工排班次数和最小化员工使用数。2010年，Sin C Ho和Janny M Y Leung[5]研究了飞机配餐排班问题，由于受到航班时刻表和服务质量的限制，此类问题是带有时间窗和工作等级限制的排班问题，即每一架航班都需要在特定的时间内和拥有该资质的员工提供配餐，文中运用禁忌算法和模拟退火算法解决了该问题，并发现禁忌算法的效果更佳。2002年，孙宏和杜文[6]针对国内航空公司运行与管理的特点，在单枢纽机场的情况下，提出了航班节的概念，建立了机组乘员排班模型，并设计了一种标号算法进行求解，通过对一个算例的分析说明了该算法的应用。2004年，刘德刚[7]研究了飞机客舱清洁人员的排班问题。具体分为两个子问题：首先是通过合理的倒班方案，满足高峰期对清洁队人力资源的需求；其次是对清洁队的作业流程进行优化，使资源得到充分利用。2009年，许建国等[8]对机场安检人员上班模式的问题进行了研究，建立了安检人员日排班优化模型和年度配置优化模型，并用实例验证此方法比原有上班模式更高效。2010年，程元军和罗利[9]利用排队论和整数规划建立了银行柜员弹性排班模型，并运用CPLEX求解实例，验证了该方法的可行性。2018年，卢敏和王莉[10]研究了面向班型动态生成的地服人员排班算法，其核心思想是通过Block Gibbs抽样迭代优化班型内人员构成、班型内航班集和班型生成，并在某机场值机人员的数据集中验证此算法的可行性。试验结果表明，在满足员工层次资质、员工白夜班和班型动态生成的约束下，算法能够生成合理的班型。上述文献虽然都依据其所研究的部门建立对应的模型，但研究的排班单元只涉及到个人，并没有考虑小组协作的情况，因此对本文所研究的客舱清洁室并不适用。

本文以某国际大型枢纽机场为例，通过前期的调研，先为客舱清洁室建立统一的排班标准以及排班约束，再建立出相应的数学模型；设计整体的排班算法，在其中嵌入Gurobi的分支定界算法以求解模型；最后将结果与目前该室的手工排班表进行相应指标的比较，验证排班算法的有效性及领先程度。

1 客舱清洁排班优化模型的建立

1.1 问题分析

1.1.1 清洁部门概况

目前客舱清洁部门有4个分队，每个分队有14个小组，共有56个小组，每个小组中有5～6名员工，总数约为297人。每天清洁任务数200～500个，其中包括航前清洁，需求员工数1人；航后清洁，根据机型的不同，需求人数不同，一般为1～5组，清洁时间在40 min左右；过站清洁，根据机型的不同，需求人数也不同，一般为1～5组，清洁时间为15 min左右；排班周期以月为单位。具体情况如图1所示。

图1 客舱清洁部

1.1.2 排班问题分析

当前排班是以小组为单位排班，这是基于每次的任务地点不同，需要通过运载车将员工送到指定地点，以小组为单位方便运载，同时由分队长管理组长，组长管理员工，达到分层管理的效果。

以小组为排班单位，则会导致本来人力资源紧缺的客舱清洁部排班可用的人力资源进一步被压缩，此时，清洁任务的精确分配就显得尤为重要，因为精确的小组——任务对应模式可以有效地提高人力资源的利用率。精确分配任务的优化问题体现在如何对清洁排班的实际问题抽象出各种变量与约束，并以此建立出符合排班员期望的数学模型，该模型的优化目标主要体现在各小组之间的日工时、月工时、月夜班数、月休息天数、月上班时间等的均衡。排班单位特点对比如表1所示。

表1 排班单位对比

1.2 模型分析

对以组为单位的客舱部门排班模型，各组进行排班时要充分考虑到组内员工执行任务时所受到的各种限制，比如小组在同一时刻不能同时执行两个任务、小组在执行连续两个任务时需要满足任务间隔时间约束等限制。与此同时，排班员希望排出来的结果能实现各员工的上班时间均衡、休假天数均衡等目标。

在通过调研后，提取出了以下几条基本约束和基本目标。

（1）基本约束。任务需求组数满足约束；连续任务间隔时间约束；班次时长的限制约束等。

（2）基本目标。日工时均衡；休假天数均衡等。

1.3 模型建立

1.3.1 模型目标函数

日上班工时均衡目标函数为：

式中：wi为第i组员工的日上班工时。

周休息天数均衡目标函数为：

式中：ri为第i组员工的周休息天数。

1.3.2 模型约束

任务需求满足约束：

式中：xij为第i组员工是否领取了第j个任务，领取了则xij＝1，否则为0；qj为第j个的需求人数。

日工时上限约束：

式中：wi为第i组员工的日上班时长；Wub为日上班工时上限。

2 客舱清洁部排班模型数据的无解机制

2.1 基于约束松弛的求解法

2.1.1 约束松弛表的建立

通过调研白云机场的客舱清洁部，结合实际排班时需满足的需求和历史排班数据分析，得到的约束松弛如表2所示。

表2 约束松弛表

2.1.2 约束松弛的流程设计

约束松弛求解流程如图2所示。

图2 约束松弛求解流程

2.2 基于引入虚拟资源的求解法

引入虚拟资源求解流程如图3所示。

图3 引入虚拟资源求解流程

2.3 整合无解应对机制后的算法流程

完整的排班求解流程如图4所示。

图4 完整的排班求解流程

3 排班结果分析

根据实际需要，算法模型中以小组为排班单位，共56个小组，在一个排班周期内尽量完成约1 882个大任务，拆分成子任务，则将获得约3 831个子任务，每个子任务都需要有1个小组去完成。进行排班时，在众多约束作用下，以上述目标函数如均衡排班、降低成本等为优化方向，实现了客舱清洁部排班模型的优化求解，最后得出的排班结果较精确解，以Excel的形式进行结果输出，包括排班数据表、排班表、未分配任务表，结果证明此排班结果是比较合理的。

分别对手工排班表和本文涉及的自动排班算法设计出的自动排班表做数据处理及指标统计，分别得到手工排班分析表及自动排班分析表，统计结果如表3～4所示。

表3 手工排班指标统计表

表4 自动排班指标统计表

综合比较表3～4，得到如表5所示的结果分析比较表。如表所示，自动排班算法所排出来的排班表相比手工的排班表，有着以下几个较为显著的优势：

表5 结果分析比较表

（1）提高了约16.60%的平均任务覆盖率，即相当于机场客舱清洁室的服务质量提高了约16.60%；

（2）人均上班时长均值提高12 min可以带来将近1h的人均有效工时均值的提高，即在一定范围内，延长员工的上班时长可以带来5倍等效时长的劳动力之多；

（3）有效工时占比提高了9.74%，意味着员工的工作效率提高了9.74%；

（4）上班时长极差均值减少了3.20 h，有效工时极差均值减少了2.11 h，意味着自动排班使得员工的上班时长相比以往更加公平。

4 结束语

本文经过对客舱清洁部排班优化算法的研究，利用IE运筹优化的思想、软约束逐步松弛的方法和引入虚拟资源求解机制，以应对模型进行算法求解时无解的状况；利用约束简化和拆分数据量，分层求解，重组合求解的思想，解决了因数据量庞大而导致求解时间过长的问题。通过对上述问题的逐一解决，针对客舱清洁部门排班问题建立了一套自动排班方案，该方案涉及算法同样可推广到国内各大机场客舱清洁部门的排班，以及其他以任务驱动模式排班的行业。