機場國際值機室人員排班研究

詹智勇，陳慶新，毛 寧，劉建軍，程 宇

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

0 引言

經(jīng)濟的快速發(fā)展使得人們對于出國旅游的接受度和熱情日漸提高，這直接導(dǎo)致了機場國際航班業(yè)務(wù)量的快速提升。當前，機場設(shè)有專門的國際值機室負責國際航班的值機服務(wù)。值機室除值班主任與各值機員工外，還配有排班員負責值機員工的班表編排。這種排班員手工排班的方式缺乏有效的排班理念與工具，不僅排班效率低下，處理規(guī)模有限，而且難以排出滿足現(xiàn)有各類約束的方案。面對機場國際航班業(yè)務(wù)量與國際值機室值機員工的快速增長，手工排班的方式已無力應(yīng)對。因此，機場亟需引入一種高效可行的方式以解決國際值機室的人員排班問題。

人員排班問題起源于1954年Edie[1]提出的收費站員工分配問題，旨在快速、有效且合理地將員工分配到班次任務(wù)上[2]，其本質(zhì)上是一類組合優(yōu)化問題。醫(yī)護人員的排班一直是人員排班問題研究的熱點[3-4]，但隨著經(jīng)濟的快速發(fā)展，人員排班研究開始向服務(wù)業(yè)各個領(lǐng)域擴展。作為旅客獲取航空服務(wù)的核心場所，機場所提供的服務(wù)種類復(fù)雜，每一項服務(wù)都設(shè)有對應(yīng)的業(yè)務(wù)室負責，Clausen[5]將其分為圍繞飛機進行的停機坪任務(wù)和圍繞旅客進行的航站樓任務(wù)。停機坪任務(wù)包括行李裝卸、客艙清潔、給油給水等。劉德剛[6]將機艙清潔的人力資源優(yōu)化分為人員排班和現(xiàn)場調(diào)度兩個子問題，保證高峰時期人力需求得到滿足以及人力資源得到最優(yōu)利用。Ho等[7]則對飛機的航空餐配送服務(wù)展開研究，其需要為業(yè)務(wù)室員工組建團隊并分配任務(wù)，該問題兼具人員排班與路徑規(guī)劃的特征。事實上，絕大多數(shù)停機坪任務(wù)都具有這樣的特點。

航站樓任務(wù)的人員排班研究多集中在安保和值機服務(wù)，這些服務(wù)的人員需求與旅客的到達分布息息相關(guān)，因此常使用排隊論對各時段的人員需求進行預(yù)測[8-9]。Stolletz[10]考慮具有時間需求與層次資質(zhì)的人員排班問題，其將各航班的值機人數(shù)需求轉(zhuǎn)換為各時段的人數(shù)需求，以此確定值機員工的輪班安排。Zamorano[11]針對具有單一資質(zhì)的值機員工排班問題設(shè)計混合整數(shù)模型，并基于模型結(jié)構(gòu)設(shè)計分支定界算法進行求解。Lin等[12]則以減少值機柜臺開放數(shù)量與員工上班時間為目標，在總結(jié)旅客行為與一系列服務(wù)需求特征的基礎(chǔ)上構(gòu)建了基于特定時間窗的線性規(guī)劃模型。

上述研究幾乎都是基于確定班次展開，以滿足各時段的人員需求為基本目標，并不能直接應(yīng)用于國際值機室的人員排班。實際上，國際值機室的人員排班具有非常明確的值機任務(wù)信息，包括任務(wù)的開始結(jié)束時間與資質(zhì)、人數(shù)要求。且由于各值機員工所具備的資質(zhì)組合并不相同，因此國際值機室的排班是直接將值機任務(wù)指派到各員工的，這是一類基于確定任務(wù)的排班方式。本文以機場國際值機室為背景，構(gòu)建機場國際值機人員排班優(yōu)化模型。同時，針對模型約束結(jié)構(gòu)設(shè)計休息時間約束壓縮規(guī)則，其能在減少模型約束數(shù)量的同時加強模型的約束強度，進而加快求解速度?；趯嶋H數(shù)據(jù)集的仿真實驗驗證了本文模型與規(guī)則的有效性。

1 問題定義與建模

1.1 問題定義

機場國際值機人員排班是指在給定值機任務(wù)集合與值機員工信息的前提下，滿足實際排班所要求的各項約束，將值機任務(wù)全部指派到員工，進而確定各員工每工作日的上下班時間。

機場國際值機室以一周7個工作日為長度進行排班，以J表示排班周期長度，令j＝1,2,…,J。待排班的國際值機任務(wù)集為其中I為值機任務(wù)總數(shù)。對每一任務(wù)i有：Tis為任務(wù)的開始時間；Tie為任務(wù)的結(jié)束時間；Ji為任務(wù)所屬的工作日；Ni為完成該任務(wù)所需的人數(shù)；Qi為任務(wù)所要求的資質(zhì)，不具備對應(yīng)資質(zhì)的員工不允許完成該任務(wù)。Ω中的任務(wù)按照所屬工作日、任務(wù)開始時間、任務(wù)結(jié)束時間升序排列，保證排序靠前的任務(wù)早于排序靠后的任務(wù)開始。

參與排班的值機員工集合P＝{1 ,2,…,K}。對每一員工k，記Qk為該員工所具備的資質(zhì)集合。值機員工的Qk與值機任務(wù)的Qi可正交出資質(zhì)矩陣Q。對Q中的每一元素Qik有：若員工k具備任務(wù)i所要求的資質(zhì)，即Qi∈Qk時，有Qik＝1；否則有Qi?Qk，Qik＝0。

模型決策變量xik∈{0 ,1}表示員工k是否執(zhí)行任務(wù)i：xik＝1表示執(zhí)行。依據(jù)xik可推導(dǎo)出變量wdjk表示員工k第j個工作日是否上班。另外設(shè)置變量wtdjk≥0計算員工k第j個工作日的上班工時。

1.2 問題建模

結(jié)合國際值機室的實際排班要求與上述定義，機場國際值機室人員排班問題建模如下：

將該模型稱為模型P。式（1）為模型優(yōu)化目標，旨在均衡各員工排班周期內(nèi)的上班工時。式（2）表示任務(wù)必須指派到足夠數(shù)量的員工。式（4）～（5）計算并約束員工每工作日的上班工時，為該員工工作日內(nèi)完成任務(wù)的總工時。通過控制式（5）的作用：當員工該工作日不上班時有被約束為0；當員工該工作日上班時有wdjk＝1，員工的上班工時被控制在規(guī)定的上下限范圍內(nèi)，。式（6）控制員工在排班周期內(nèi)的上班天數(shù)不會超過規(guī)定的上限。式（7）計算員工排班周期內(nèi)的上班工時。式（8）～（10）為變量定義。易知，當Qik＝0時，決策變量xik會退化為常數(shù)0。為避免這類無效變量的生成，當Qik＝1時才會生成對應(yīng)變量，以保證生成的變量都是有效變量。另外，在具有xik參與構(gòu)建的約束中均加入來自Q的限制，避免這些約束加入沒有定義的變量。

式（3）為休息時間約束，其通過限制員工分配到部分任務(wù)組合以保證員工在排班周期內(nèi)能夠有足夠的休息時間。對具有資質(zhì)的兩任務(wù)i1和i2（i1早于i2開始），當兩任務(wù)的時間關(guān)系滿足如下條件時，員工不能同時分配到該兩任務(wù)：（1）若兩任務(wù)屬同一工作日，該兩任務(wù)之間的時間間隔不足TtR；（2）若兩任務(wù)屬同一工作日，該兩任務(wù)組成的班次長度長于L，此處班次長度包含完成值機任務(wù)的工時與任務(wù)之間的休息時間；（3）若兩任務(wù)分屬不同的工作日，該兩任務(wù)之間的時間間隔不短于條件（1）保證員工在完成兩值機任務(wù)之間能有足夠的任務(wù)間休息時間；條件（2）保證員工該工作日上班時班次長度不會過長；條件（3）保證員工在連續(xù)若干工作日上班時，相鄰兩個工作日班次之間能有足夠的班次間休息時間。使用集合Ct＝{ }( )Ip,k 表示模型存在的所有休息時間約束，其中

2 休息時間約束壓縮規(guī)則

觀察模型，休息時間約束（式（3））占據(jù)模型約束的絕大部分，這些約束僅由2個決策變量構(gòu)成，結(jié)構(gòu)松散。若將模型的決策變量映射為頂點，這些休息時間約束映射為邊，那么這些約束可映射為一張圖。由于這些休息時間約束是同一員工的決策變量生成的，不同員工的決策變量不存在這種關(guān)系。因此這張圖實際上是由K互不連通的子圖組成。

如圖1所示，令其為這些子圖中的一張，這張圖包含12個頂點與36條邊，表示員工k可完成的12個值機任務(wù)與這些任務(wù)之間共36條休息時間約束。觀察該圖，圖中頂點1、2、5相互連接，構(gòu)成該圖的一個團結(jié)構(gòu)。同時，團結(jié)構(gòu)中連接頂點的邊其對應(yīng)約束相互制約，使得該員工最多只能完成這3個任務(wù)中的一個，這一約束可表示為x1＋x2＋x5≤1，稱這類約束為團約束。與圖中各條邊所對應(yīng)的休息時間約束相比，這條基于團結(jié)構(gòu)生成的團約束不僅包含團中所有邊的約束信息，同時還具有更緊湊的約束形式與更強的約束能力。

圖1 員工k休息時間約束映射

繼續(xù)觀察該圖，圖中頂點10與頂點1、2、5相互連接，團結(jié)構(gòu)在原來的基礎(chǔ)上進一步擴大，其對應(yīng)的團約束為x1＋x2＋x5＋x10≤1。隨著團結(jié)構(gòu)的擴大，團約束所包含的約束信息越來越多，同時其約束能力也越來越強。因此可將模型中的休息時間約束替換為對應(yīng)的團約束，同時達到壓縮模型約束規(guī)模與增強約束能力的目的。為最大程度利用團約束的這些特性，用以替換的團約束應(yīng)包含盡可能多的任務(wù)，故應(yīng)盡量枚舉出對應(yīng)圖的極大團，即增加任一頂點都不再符合團定義的團[13]。另外，團約束必須完整包含模型原有的休息時間約束。基于上述要求，本文設(shè)計休息時間約束壓縮規(guī)則，旨在將模型中的休息時間約束替換為團約束。嵌入規(guī)則的模型求解流程如圖2所示。

圖2 嵌入規(guī)則的模型求解流程

規(guī)則獲取待操作的模型以及所需數(shù)據(jù)作為輸入，包括該模型的休息時間約束集合Ct與值機員工集合。模型需要在現(xiàn)有Ct的基礎(chǔ)上構(gòu)建并添加團約束，因此首先需要刪除Ct所包含的約束，保證模型不存在任何形式的休息時間約束。

對員工k完成上述定義后，對Ik中的每一任務(wù)i調(diào)用constraintMerge算法。該算法基于圖論中極大團枚舉的BK算法進行改進[14]，旨在找出覆蓋所有休息時間約束且包含盡可能多任務(wù)的團結(jié)構(gòu)。constraintMerge算法包含3個輸入：cur為當前解，表示當前搜索到組成團結(jié)構(gòu)的任務(wù)集合，令cur＝{}i；cond為備選集，表示可加入當前團結(jié)構(gòu)的任務(wù)集合，cond＝condi；ret為結(jié)果集，其包含該算法找到的所有團結(jié)構(gòu)，初始化ret＝?。constraint-Merge算法流程如表1所示。

表1 constraintMerge算法流程

算法首先判斷cond是否為空。cond為空表示當前輸入的cur以是算法搜索到最大的團結(jié)構(gòu)。在加入到ret前，cur需要與當前ret保存的團結(jié)構(gòu)cl進行比對，以確保ret不會保存重復(fù)的團結(jié)構(gòu)：若比對到cur?cl，則表示ret已保存有該團結(jié)構(gòu)的信息，算法將停止比對并返回上一層遞歸；若比對到cl?cur，則表示cur保存有該團結(jié)構(gòu)的信息，算法將刪除該團結(jié)構(gòu)。比對完成后cur將加入到cur中并返回上一層調(diào)用。

若cond非空，則表示當前輸入的cur仍可進一步擴大，可繼續(xù)向cur添加任務(wù)。算法依次從cond彈出序號最小的任務(wù)i并加入到cur中。此時因cur增加了任務(wù)，故需要更新cond以保證其包含的任務(wù)均可加入到更新后的cur組成更大的團結(jié)構(gòu)。cond與任務(wù)i的備選集condi做交集后，進行算法的遞歸調(diào)用。如此循環(huán)直至cond為空，算法返回上一層調(diào)用。

對員工k的constraintMerge算法執(zhí)行完成后，ret保存算法搜索到所有的團結(jié)構(gòu)，對每一個團結(jié)構(gòu)cl所包含的任務(wù)，員工k最多只能完成一個，這一約束可表示為：

該約束即為團約束，對ret中的所有團結(jié)構(gòu)構(gòu)建這一約束并寫入模型中。當所有員工均完成上述步驟后，規(guī)則返回更新后的模型。

3 仿真實驗與結(jié)果分析

3.1 實驗數(shù)據(jù)

實驗數(shù)據(jù)選自某大型國際機場國際值機部2019年不同時期共4周的生產(chǎn)數(shù)據(jù)集，包括值機任務(wù)數(shù)據(jù)與值機員工信息，數(shù)據(jù)集具體信息如表2所示。

表2 數(shù)據(jù)集信息

模型構(gòu)建及算法采用Java編寫，模型使用Gurobi求解器進行求解，運行硬件環(huán)境為Intel（R）Xeon（R）CPUE5-2695 v4＠2.1GHz，8G內(nèi)存。依據(jù)國際值機室實際排班規(guī)定，模型參數(shù)設(shè)置如表3所示。

表3 模型參數(shù)設(shè)置

模型P為一混合整數(shù)規(guī)劃模型，求解器往往需要花費大量時間以證明當前找到的解為最優(yōu)解。為避免實際排班過程中排班員的等待時間過長，求解器需要設(shè)置求解時間相關(guān)參數(shù)，如表4所示。

表4 求解器參數(shù)設(shè)置

3.2 實驗結(jié)果與分析

4個實際案例的模型優(yōu)化結(jié)果與手工排班結(jié)果對比如表5所示。由于參與排班的任務(wù)與員工規(guī)模龐大，4個案例的手工排班均需要約1周的時間，且由于排班需要遵守的休息時間約束復(fù)雜，手工排班方案存在部分不能滿足約束的情況。而模型排班結(jié)果均在規(guī)定的求解時間相關(guān)參數(shù)設(shè)置下求出，不僅完全滿足模型所有約束，同時得到的排班結(jié)果均比手工排班更優(yōu)。

表5 案例結(jié)果對比

表6所示為4個案例所生成模型的約束數(shù)量情況，表中其余約束為模型中除休息時間約束/團約束以外其余約束的數(shù)量；壓縮比則為團約束與休息時間約束的比值。原模型中休息時間約束占據(jù)模型約束的絕大部分，而基于規(guī)則生成的團約束則僅以約10%的規(guī)模完全覆蓋休息時間約束。同時，團約束所帶來約束強度的提升也加快了求解器的求解速度。觀察表5：案例3、4均以更短的求解時間求得低于規(guī)定MIPGap值的解；案例1、2則是在規(guī)定的求解時間內(nèi)求得/證得具有更優(yōu)Gap值的解。

表6 模型約束情況

4 結(jié)束語

本文以機場國際值機室為背景，研究一類基于確定任務(wù)的人員排班問題。針對手工排班存在的效率低下、處理規(guī)模有限等問題，基于值機室排班要求構(gòu)建國際值機人員排班模型，并考慮模型約束結(jié)構(gòu)設(shè)計休息時間約束壓縮規(guī)則?；趯嶋H案例的實驗表明，本文所構(gòu)建模型得到的排班結(jié)果在求解時間與解優(yōu)度均優(yōu)于手工排班方案。同時，休息時間約束壓縮規(guī)則能有效減少模型約束數(shù)量，約束強度的提升也進一步提升了模型求解速度。目前本文研究成果已應(yīng)用在某機場的自動排班系統(tǒng)中，極大提高了值機室的排班效率。