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

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

0 引言

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

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

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

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

1 問題定義與建模

1.1 問題定義

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

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

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

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

1.2 問題建模

結(jié)合國(guó)際值機(jī)室的實(shí)際排班要求與上述定義，機(jī)場(chǎng)國(guó)際值機(jī)室人員排班問題建模如下：

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

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

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

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

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

圖1 員工k休息時(shí)間約束映射

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

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

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

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

表1 constraintMerge算法流程

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

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

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

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

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

表6 模型約束情況

4 結(jié)束語(yǔ)

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