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

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

（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 結束語

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