某機(jī)場客艙清潔部排班優(yōu)化算法研究

吳植英，汪春華，曹紫萱，杜晴晴，徐偉彬

（1.廣東工業(yè)大學(xué)機(jī)電工程學(xué)院，廣州 510006；2.廣東機(jī)場白云信息科技有限公司，廣州 510470）

0 引言

目前隨著國內(nèi)航空事業(yè)的不斷擴(kuò)大，國內(nèi)各大航空公司的飛機(jī)數(shù)量也在不斷增加。如何合理地進(jìn)行排班管理，有效利用人力資源，提高員工的勞動(dòng)績效，降低整體的運(yùn)營成本，提高生產(chǎn)力以及整個(gè)客艙清潔部門的投資回報(bào)率，是每一個(gè)機(jī)場發(fā)展到一定階段，管理者都要面臨的問題。

客艙清潔排班管理研究的目的是科學(xué)合理地安排人力資源，從而有效地分配任務(wù)，讓最適當(dāng)?shù)娜?，在最適當(dāng)?shù)臅r(shí)間，擔(dān)任最適合的任務(wù)，以達(dá)到人員與飛機(jī)的合理匹配。對(duì)管理者而言，其不僅要能有效地管理客艙清潔部門的人力資源，節(jié)約人力成本，而且還要進(jìn)一步滿足客戶服務(wù)的要求，從而達(dá)到提升客艙清潔部門的運(yùn)用管理水平，降低調(diào)度頻率以及客艙清潔部門的運(yùn)營成本，提高整個(gè)航空公司的投資回報(bào)，增加企業(yè)收益。

排班問題是一個(gè)時(shí)間表問題，是運(yùn)籌學(xué)領(lǐng)域中組合優(yōu)化問題之一，就是運(yùn)用數(shù)學(xué)、計(jì)算機(jī)等領(lǐng)域的方法，在有限的時(shí)間內(nèi)去尋找一個(gè)最優(yōu)組合。國外研究人員對(duì)員工排班問題的研究起步較早，研究方向主要集中在員工排班問題的建模和算法實(shí)現(xiàn)兩個(gè)方面。

1976年，Baker K[1]提出了基于員工工作負(fù)荷拍板的數(shù)學(xué)模型，并將該模型應(yīng)用于多個(gè)工種類型的領(lǐng)域內(nèi)。1990年，Nagraj Balarishnan和Richard T Wong[2]運(yùn)用網(wǎng)絡(luò)流技術(shù)，研究了基于工作負(fù)荷的員工排班問題，將排班模型的所有約束都集成到所建立的網(wǎng)絡(luò)中，而最佳排班方案就是所建立網(wǎng)絡(luò)中的一條路徑，最后的計(jì)算結(jié)果說明該方法非常適用于解決大型的排班問題。2001年，C K CHU[3]研究了機(jī)場地勤員工彈性排班問題，排班模型是整數(shù)規(guī)劃模型，目標(biāo)是在排班結(jié)果維持一定員工富余量的基礎(chǔ)上，最小化需要加班員工數(shù)量。2003年，Luca Di Gaspero等[4]提出了最少排班次數(shù)模型，其目標(biāo)在滿足員工負(fù)荷和實(shí)際需求負(fù)荷之差在一定可接受范圍內(nèi)的情況下，最小化員工排班次數(shù)和最小化員工使用數(shù)。2010年，Sin C Ho和Janny M Y Leung[5]研究了飛機(jī)配餐排班問題，由于受到航班時(shí)刻表和服務(wù)質(zhì)量的限制，此類問題是帶有時(shí)間窗和工作等級(jí)限制的排班問題，即每一架航班都需要在特定的時(shí)間內(nèi)和擁有該資質(zhì)的員工提供配餐，文中運(yùn)用禁忌算法和模擬退火算法解決了該問題，并發(fā)現(xiàn)禁忌算法的效果更佳。2002年，孫宏和杜文[6]針對(duì)國內(nèi)航空公司運(yùn)行與管理的特點(diǎn)，在單樞紐機(jī)場的情況下，提出了航班節(jié)的概念，建立了機(jī)組乘員排班模型，并設(shè)計(jì)了一種標(biāo)號(hào)算法進(jìn)行求解，通過對(duì)一個(gè)算例的分析說明了該算法的應(yīng)用。2004年，劉德剛[7]研究了飛機(jī)客艙清潔人員的排班問題。具體分為兩個(gè)子問題：首先是通過合理的倒班方案，滿足高峰期對(duì)清潔隊(duì)人力資源的需求；其次是對(duì)清潔隊(duì)的作業(yè)流程進(jìn)行優(yōu)化，使資源得到充分利用。2009年，許建國等[8]對(duì)機(jī)場安檢人員上班模式的問題進(jìn)行了研究，建立了安檢人員日排班優(yōu)化模型和年度配置優(yōu)化模型，并用實(shí)例驗(yàn)證此方法比原有上班模式更高效。2010年，程元軍和羅利[9]利用排隊(duì)論和整數(shù)規(guī)劃建立了銀行柜員彈性排班模型，并運(yùn)用CPLEX求解實(shí)例，驗(yàn)證了該方法的可行性。2018年，盧敏和王莉[10]研究了面向班型動(dòng)態(tài)生成的地服人員排班算法，其核心思想是通過Block Gibbs抽樣迭代優(yōu)化班型內(nèi)人員構(gòu)成、班型內(nèi)航班集和班型生成，并在某機(jī)場值機(jī)人員的數(shù)據(jù)集中驗(yàn)證此算法的可行性。試驗(yàn)結(jié)果表明，在滿足員工層次資質(zhì)、員工白夜班和班型動(dòng)態(tài)生成的約束下，算法能夠生成合理的班型。上述文獻(xiàn)雖然都依據(jù)其所研究的部門建立對(duì)應(yīng)的模型，但研究的排班單元只涉及到個(gè)人，并沒有考慮小組協(xié)作的情況，因此對(duì)本文所研究的客艙清潔室并不適用。

本文以某國際大型樞紐機(jī)場為例，通過前期的調(diào)研，先為客艙清潔室建立統(tǒng)一的排班標(biāo)準(zhǔn)以及排班約束，再建立出相應(yīng)的數(shù)學(xué)模型；設(shè)計(jì)整體的排班算法，在其中嵌入Gurobi的分支定界算法以求解模型；最后將結(jié)果與目前該室的手工排班表進(jìn)行相應(yīng)指標(biāo)的比較，驗(yàn)證排班算法的有效性及領(lǐng)先程度。

1 客艙清潔排班優(yōu)化模型的建立

1.1 問題分析

1.1.1 清潔部門概況

目前客艙清潔部門有4個(gè)分隊(duì)，每個(gè)分隊(duì)有14個(gè)小組，共有56個(gè)小組，每個(gè)小組中有5～6名員工，總數(shù)約為297人。每天清潔任務(wù)數(shù)200～500個(gè)，其中包括航前清潔，需求員工數(shù)1人；航后清潔，根據(jù)機(jī)型的不同，需求人數(shù)不同，一般為1～5組，清潔時(shí)間在40 min左右；過站清潔，根據(jù)機(jī)型的不同，需求人數(shù)也不同，一般為1～5組，清潔時(shí)間為15 min左右；排班周期以月為單位。具體情況如圖1所示。

圖1 客艙清潔部

1.1.2 排班問題分析

當(dāng)前排班是以小組為單位排班，這是基于每次的任務(wù)地點(diǎn)不同，需要通過運(yùn)載車將員工送到指定地點(diǎn)，以小組為單位方便運(yùn)載，同時(shí)由分隊(duì)長管理組長，組長管理員工，達(dá)到分層管理的效果。

以小組為排班單位，則會(huì)導(dǎo)致本來人力資源緊缺的客艙清潔部排班可用的人力資源進(jìn)一步被壓縮，此時(shí)，清潔任務(wù)的精確分配就顯得尤為重要，因?yàn)榫_的小組——任務(wù)對(duì)應(yīng)模式可以有效地提高人力資源的利用率。精確分配任務(wù)的優(yōu)化問題體現(xiàn)在如何對(duì)清潔排班的實(shí)際問題抽象出各種變量與約束，并以此建立出符合排班員期望的數(shù)學(xué)模型，該模型的優(yōu)化目標(biāo)主要體現(xiàn)在各小組之間的日工時(shí)、月工時(shí)、月夜班數(shù)、月休息天數(shù)、月上班時(shí)間等的均衡。排班單位特點(diǎn)對(duì)比如表1所示。

表1 排班單位對(duì)比

1.2 模型分析

對(duì)以組為單位的客艙部門排班模型，各組進(jìn)行排班時(shí)要充分考慮到組內(nèi)員工執(zhí)行任務(wù)時(shí)所受到的各種限制，比如小組在同一時(shí)刻不能同時(shí)執(zhí)行兩個(gè)任務(wù)、小組在執(zhí)行連續(xù)兩個(gè)任務(wù)時(shí)需要滿足任務(wù)間隔時(shí)間約束等限制。與此同時(shí)，排班員希望排出來的結(jié)果能實(shí)現(xiàn)各員工的上班時(shí)間均衡、休假天數(shù)均衡等目標(biāo)。

在通過調(diào)研后，提取出了以下幾條基本約束和基本目標(biāo)。

（1）基本約束。任務(wù)需求組數(shù)滿足約束；連續(xù)任務(wù)間隔時(shí)間約束；班次時(shí)長的限制約束等。

（2）基本目標(biāo)。日工時(shí)均衡；休假天數(shù)均衡等。

1.3 模型建立

1.3.1 模型目標(biāo)函數(shù)

日上班工時(shí)均衡目標(biāo)函數(shù)為：

式中：wi為第i組員工的日上班工時(shí)。

周休息天數(shù)均衡目標(biāo)函數(shù)為：

式中：ri為第i組員工的周休息天數(shù)。

1.3.2 模型約束

任務(wù)需求滿足約束：

式中：xij為第i組員工是否領(lǐng)取了第j個(gè)任務(wù)，領(lǐng)取了則xij＝1，否則為0；qj為第j個(gè)的需求人數(shù)。

日工時(shí)上限約束：

式中：wi為第i組員工的日上班時(shí)長；Wub為日上班工時(shí)上限。

2 客艙清潔部排班模型數(shù)據(jù)的無解機(jī)制

2.1 基于約束松弛的求解法

2.1.1 約束松弛表的建立

通過調(diào)研白云機(jī)場的客艙清潔部，結(jié)合實(shí)際排班時(shí)需滿足的需求和歷史排班數(shù)據(jù)分析，得到的約束松弛如表2所示。

表2 約束松弛表

2.1.2 約束松弛的流程設(shè)計(jì)

約束松弛求解流程如圖2所示。

圖2 約束松弛求解流程

2.2 基于引入虛擬資源的求解法

引入虛擬資源求解流程如圖3所示。

圖3 引入虛擬資源求解流程

2.3 整合無解應(yīng)對(duì)機(jī)制后的算法流程

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

圖4 完整的排班求解流程

3 排班結(jié)果分析

根據(jù)實(shí)際需要，算法模型中以小組為排班單位，共56個(gè)小組，在一個(gè)排班周期內(nèi)盡量完成約1 882個(gè)大任務(wù)，拆分成子任務(wù)，則將獲得約3 831個(gè)子任務(wù)，每個(gè)子任務(wù)都需要有1個(gè)小組去完成。進(jìn)行排班時(shí)，在眾多約束作用下，以上述目標(biāo)函數(shù)如均衡排班、降低成本等為優(yōu)化方向，實(shí)現(xiàn)了客艙清潔部排班模型的優(yōu)化求解，最后得出的排班結(jié)果較精確解，以Excel的形式進(jìn)行結(jié)果輸出，包括排班數(shù)據(jù)表、排班表、未分配任務(wù)表，結(jié)果證明此排班結(jié)果是比較合理的。

分別對(duì)手工排班表和本文涉及的自動(dòng)排班算法設(shè)計(jì)出的自動(dòng)排班表做數(shù)據(jù)處理及指標(biāo)統(tǒng)計(jì)，分別得到手工排班分析表及自動(dòng)排班分析表，統(tǒng)計(jì)結(jié)果如表3～4所示。

表3 手工排班指標(biāo)統(tǒng)計(jì)表

表4 自動(dòng)排班指標(biāo)統(tǒng)計(jì)表

綜合比較表3～4，得到如表5所示的結(jié)果分析比較表。如表所示，自動(dòng)排班算法所排出來的排班表相比手工的排班表，有著以下幾個(gè)較為顯著的優(yōu)勢(shì)：

表5 結(jié)果分析比較表

（1）提高了約16.60%的平均任務(wù)覆蓋率，即相當(dāng)于機(jī)場客艙清潔室的服務(wù)質(zhì)量提高了約16.60%；

（2）人均上班時(shí)長均值提高12 min可以帶來將近1h的人均有效工時(shí)均值的提高，即在一定范圍內(nèi)，延長員工的上班時(shí)長可以帶來5倍等效時(shí)長的勞動(dòng)力之多；

（3）有效工時(shí)占比提高了9.74%，意味著員工的工作效率提高了9.74%；

（4）上班時(shí)長極差均值減少了3.20 h，有效工時(shí)極差均值減少了2.11 h，意味著自動(dòng)排班使得員工的上班時(shí)長相比以往更加公平。

4 結(jié)束語

本文經(jīng)過對(duì)客艙清潔部排班優(yōu)化算法的研究，利用IE運(yùn)籌優(yōu)化的思想、軟約束逐步松弛的方法和引入虛擬資源求解機(jī)制，以應(yīng)對(duì)模型進(jìn)行算法求解時(shí)無解的狀況；利用約束簡化和拆分?jǐn)?shù)據(jù)量，分層求解，重組合求解的思想，解決了因數(shù)據(jù)量龐大而導(dǎo)致求解時(shí)間過長的問題。通過對(duì)上述問題的逐一解決，針對(duì)客艙清潔部門排班問題建立了一套自動(dòng)排班方案，該方案涉及算法同樣可推廣到國內(nèi)各大機(jī)場客艙清潔部門的排班，以及其他以任務(wù)驅(qū)動(dòng)模式排班的行業(yè)。