基于集分割模型的復(fù)雜機(jī)場(chǎng)地勤人員排班研究

黃夢(mèng)婷　繆彬

摘要：為了優(yōu)化機(jī)場(chǎng)地勤人員的調(diào)配管理，提升機(jī)場(chǎng)服務(wù)質(zhì)量，文章對(duì)傳統(tǒng)的排班模式進(jìn)行研究并改進(jìn)，結(jié)合我國(guó)機(jī)場(chǎng)運(yùn)營(yíng)實(shí)況，借鑒國(guó)內(nèi)外排班優(yōu)化模型的理論與研究成果，建立以最小化班期成本為目標(biāo)的集合分割排班模型，以最小化各項(xiàng)任務(wù)成本為目標(biāo)，采用列生成算法對(duì)模型進(jìn)行求解。該研究成果能夠有效優(yōu)化機(jī)場(chǎng)地勤人員的調(diào)配，在一定程度上提升機(jī)場(chǎng)服務(wù)質(zhì)量，同時(shí)能快速解決機(jī)場(chǎng)地勤人員排班問題，對(duì)進(jìn)一步推進(jìn)人員排班模型及算法的研究有著積極作用。

關(guān)鍵詞：地勤人員排班；集合分割模型；列生成算法；組合優(yōu)化

一、引言

機(jī)場(chǎng)逐年增加的吞吐量會(huì)造成對(duì)地勤人員需求的增加，同時(shí)對(duì)其排班的難度也大幅增加，具體原因如下：不同任務(wù)類型需要不同的人員資質(zhì)；多種工種，不同工種具有不同的排班規(guī)則；地勤排班計(jì)劃對(duì)算法的魯棒性和時(shí)間需求較高。因此，機(jī)場(chǎng)地勤人員排班本質(zhì)上是，綜合考慮航班到達(dá)不確定性、多任務(wù)、多工種情況下的復(fù)雜排班問題。

人員排班的主要研究?jī)?nèi)容是通過定義要完成的任務(wù)，及其開始時(shí)間段、工作持續(xù)時(shí)間、休息時(shí)間間隔等，為每個(gè)員工構(gòu)建工作時(shí)間表以滿足各種地勤服務(wù)需求，被廣泛應(yīng)用于醫(yī)療保健領(lǐng)域、交通運(yùn)輸、呼叫中心等領(lǐng)域。參考機(jī)組排班計(jì)劃問題將地勤人員排班問題劃分為人員派工和人員指派兩個(gè)子問題。派工是地勤人員排班計(jì)劃的主要任務(wù)，是將機(jī)場(chǎng)保障服務(wù)按要求匹配成一串沒有時(shí)間沖突的任務(wù)序列，人員指派則是在人員派工的基礎(chǔ)上，指派具體的不同資質(zhì)的員工完成具體的保障任務(wù)。本文則具體研究作為排班計(jì)劃核心階段的人員派工問題。

目前，圍繞地勤人員排班計(jì)劃生成的研究有：Soukour等為降低地勤服務(wù)調(diào)度模型的復(fù)雜性，將其分為三個(gè)步驟求解：休息日安排、輪班安排和員工分配；Ip等將地面服務(wù)的調(diào)度優(yōu)化問題描述為具有多個(gè)不同車輛的時(shí)間窗的車輛路徑問題，為了解決這個(gè)問題，提出了一種混合編碼的遺傳算法；Clausen研究了多任務(wù)、面向?qū)哟钨Y質(zhì)需求的地勤人員排班問題，并使用模擬退火算法對(duì)模型進(jìn)行求解。國(guó)內(nèi)關(guān)于地勤服務(wù)調(diào)度問題的研究大多集中于車輛調(diào)度優(yōu)化以及航班進(jìn)出港排序優(yōu)化問題上；盧敏、馮霞等分別研究了面向班型動(dòng)態(tài)生成和面向?qū)哟钨Y質(zhì)的機(jī)場(chǎng)地服人員排班問題，克服了傳統(tǒng)人員排班模型中的單一任務(wù)、單一資質(zhì)問題。

上述研究成果一般集中于對(duì)地勤服務(wù)流程和模型約束條件的改進(jìn)，且這些研究中大部分是針對(duì)單一的或特定類別的地勤服務(wù)進(jìn)行調(diào)度，很少考慮從全局角度為機(jī)場(chǎng)地勤人員建立模型進(jìn)行統(tǒng)一排班調(diào)度。為解決該問題，本文建立集合分割排班模型，以最小化各項(xiàng)任務(wù)成本為目標(biāo)，采用生成算法對(duì)模型進(jìn)行求解，為每一個(gè)班期生成可行的任務(wù)序列，建立更加全面的機(jī)場(chǎng)地勤人員協(xié)同排班模型。

二、問題模型構(gòu)建

（一）問題描述

1. 模型相關(guān)概念

班期組：根據(jù)機(jī)場(chǎng)地勤保障的要求，按時(shí)間窗劃分所需的不同班期類型，班期規(guī)定了地勤服務(wù)人員的到崗時(shí)間和離崗時(shí)間。班期組是指同一時(shí)間窗內(nèi)的多個(gè)同類型班期的集合。

任務(wù)序列：就是指一串沒有時(shí)間沖突的任務(wù)串，排班派工階段的任務(wù)就是要找到適配于每個(gè)班期的最優(yōu)的任務(wù)序列。

2. 模型的基本假設(shè)

相關(guān)成本假設(shè)：模型目標(biāo)函數(shù)為班期成本最小化。模型的成本主要包括：任務(wù)不被覆蓋的懲罰成本；班期的設(shè)置成本以及任務(wù)津貼。任務(wù)津貼具體包括員工執(zhí)行任務(wù)的固定成本以及人員資質(zhì)成本。

航班為周期性重復(fù)假設(shè)：模型假設(shè)航空公司的航班計(jì)劃是周期性重復(fù)的。面對(duì)周期性的航班計(jì)劃，機(jī)場(chǎng)地勤服務(wù)部門能以一定的周期為單位對(duì)地勤人員進(jìn)行編排。

（二）模型構(gòu)建

本文將地勤人員排班問題刻畫為集合覆蓋問題，建立如下模型：

式中：r表示任務(wù)序列，r∈R，R為全部可行任務(wù)序列集合；t表示任務(wù)，t∈T，T為所有待執(zhí)行任務(wù)集合；s表示班期，s∈S，S為所有可能的班期類型；當(dāng)r∈Rt時(shí)，xr的0-1取值表示r任務(wù)序列中是否包含t任務(wù)；當(dāng)r∈Rs時(shí)，xr的0-1取值表示s班期中是否包含任務(wù)序列r，yt的0-1取值表示任務(wù)t是否沒有被覆蓋；zt表示任務(wù)t是否被多次覆蓋；cr表示任務(wù)序列r的成本（含人力成本、物資成本）；c■■表示取消任務(wù)t的懲罰成本；c■■表示任務(wù)t被多次覆蓋的懲罰成本。

式（1）為主問題模型的優(yōu)化目標(biāo)，任務(wù)執(zhí)行的總成本最小；式（2）為任務(wù)覆蓋約束，要求所有任務(wù)t∈T都被覆蓋且僅被覆蓋一次；式（3）為班期數(shù)量約束，要求每個(gè)班期組內(nèi)的班期數(shù)量，要大于該班期時(shí)間段內(nèi)可執(zhí)行的任務(wù)序列個(gè)數(shù)；式（4）表示xr為0～1變量，表示第r個(gè)任務(wù)序列是否被選擇；式（5）表示yt為0～1變量，表示任務(wù)t是否沒有被覆蓋；式（6）表示zt為0～1變量，表示任務(wù)t是否被多次覆蓋。

三、基于列生成的模型求解算法

（一）算法的基本思想

列生成算法求解思路源于單純形法，區(qū)別在于，列生成算法不需要計(jì)算驗(yàn)證原問題的所有的檢驗(yàn)數(shù)，是以隱枚舉方式為原問題提供較優(yōu)“基變量”。基于本文，是將原問題分解為一個(gè)尋找最優(yōu)派工方案組合的主問題和一個(gè)尋找新任務(wù)序列的子問題。主問題中的只包含部分可行任務(wù)序列，為受限的集合分割問題，對(duì)主問題進(jìn)行松弛后求解，將得到的對(duì)偶解傳遞給子問題；帶有成本約束的最短路子問題模型利用主問題的對(duì)偶信息尋找新的任務(wù)序列并加入主問題模型，通過這樣的循環(huán)迭代，主問題不斷增加新變量，其求解結(jié)果逐漸逼近原問題的最優(yōu)解，當(dāng)模型系統(tǒng)滿足一定收斂準(zhǔn)則時(shí)即完成模型的求解。具體算法流程如圖1所示。

（二）受限主問題模型

本文將所有單個(gè)任務(wù)作為主問題的初始可行變量，即一個(gè)任務(wù)就代表一個(gè)任務(wù)序列。受限主問題表示如下：

其中，R1表示部分初始可行任務(wù)序列的集合，R1＜<R，R■<<Rt，R■<<Rs。

（三）子問題模型構(gòu)建

由于對(duì)任務(wù)序列的時(shí)間跨度約束主要體現(xiàn)在“班期組s的任務(wù)序列集合Rs”上，即除了為每個(gè)班期組生成任務(wù)序列集合，還要求集合中每個(gè)任務(wù)序列是可以在該班期組工作時(shí)間窗內(nèi)被執(zhí)行的任務(wù)序列。在派工階段，每一個(gè)班期組對(duì)應(yīng)一個(gè)子問題，通過求解多個(gè)子問題模型，為每個(gè)班期組尋找更好的任務(wù)序列，作為新的列，加入限制主問題。因此在子問題模型中選取任務(wù)序列不再需要對(duì)任務(wù)執(zhí)行時(shí)間的約束進(jìn)行考慮。

子問題模型的目標(biāo)是向主問題提供可行的任務(wù)序列，可行任務(wù)序列的定義是：加入主問題的可行的任務(wù)序列必須是差額成本大于零，否則停止迭代，具體子問題模型如下：

）

式中：αi表示i任務(wù)的機(jī)會(huì)成本（即任務(wù)覆蓋約束對(duì)應(yīng)的對(duì)偶變量）；ci表示i任務(wù)的執(zhí)行成本；πs表示s班期的機(jī)會(huì)成本（即班期數(shù)量約束對(duì)應(yīng)的對(duì)偶變量）；b（i）表示i任務(wù)的前可連接任務(wù)集合；a（i）表示i任務(wù)的后可連接任務(wù)集合；sis表示班期s是否從i任務(wù)開始；eis表示班期s是否以i任務(wù)結(jié)束；xijs表示s班期中的任務(wù)i是否與任務(wù)j相連；gi表示任務(wù)i的執(zhí)行時(shí)間；maxs表示班期的最長(zhǎng)時(shí)限。

式（13）表示子問題的目標(biāo)函數(shù)，為主問題尋找新的任務(wù)序列；式（14）表示流量平衡約束；式（15）表示任務(wù)序列只能有一個(gè)任務(wù)起點(diǎn)；式（16）表示任務(wù)序列只能有一個(gè)任務(wù)終點(diǎn)；式（17）表示地勤人員的任務(wù)執(zhí)行時(shí)間小于規(guī)定的班期時(shí)間段；式（18）表示xijt，xjit，sit，eit為0～1變量。

（四）求解算法

模型的求解大概思路及步驟。

Step1：建立集合分割模型，對(duì)數(shù)據(jù)進(jìn)行初始化，運(yùn)用啟發(fā)式算法獲得盡可能高質(zhì)量的初始集合（可行任務(wù)序列）。

Step2：求解松弛的集合分割模型，并求對(duì)偶解。

Step3：利用主問題求得的對(duì)偶解對(duì)子問題進(jìn)行求解，若子問題中的差額成本小于零則停止生成任務(wù)序列，否則繼續(xù)執(zhí)行第四步。

Step4：將新生成的任務(wù)序列傳遞給集合分割主問題，增加主問題的列數(shù)即增加主問題的任務(wù)序列，轉(zhuǎn)到Step2。

Step5：恢復(fù)主問題的整數(shù)約束并對(duì)其求解，獲取最后的排班方案。

（五）啟發(fā)式算法求解初始集合

因地勤人員排班只是對(duì)一天的任務(wù)進(jìn)行排列，且任務(wù)是根據(jù)航空公司的航班飛行計(jì)劃安排的，各個(gè)任務(wù)的大概開始和結(jié)束時(shí)間是已知的，因此其算法步驟較為簡(jiǎn)單。

首先，根據(jù)所有輸入的任務(wù)可生成一天三個(gè)時(shí)間段的班期：s1：4：00～12：30、s2：12：00～20：00、s3：19：30～02：30。

Step1：對(duì)所有任務(wù)按時(shí)間劃分，分別尋找早中晚班的所有任務(wù)對(duì)其劃分。

Step2：將早、中、晚班中時(shí)間沒有沖突的任務(wù)進(jìn)行組合。

由于不同任務(wù)可能要求不同資質(zhì)人員執(zhí)行，人員若不能滿足多種資質(zhì)要求的任務(wù)序列，則該任務(wù)序列為不可行任務(wù)序列，否則就將其列為初始的可行任務(wù)序列，轉(zhuǎn)第三步。

Step3：寫出初始可行班期組任務(wù)序列。由于前面已經(jīng)對(duì)時(shí)間進(jìn)行劃分則各班期對(duì)應(yīng)的班期組任務(wù)序列集合可相應(yīng)得到。

Step4：求得各個(gè)任務(wù)對(duì)應(yīng)的任務(wù)序列。

四、實(shí)驗(yàn)及分析

（一）實(shí)驗(yàn)數(shù)據(jù)

數(shù)據(jù)選用A機(jī)場(chǎng)地勤服務(wù)部2020年11月01日一整天的航班到達(dá)計(jì)劃數(shù)據(jù)，共452個(gè)任務(wù)信息，包括任務(wù)的類型（航班號(hào)）、任務(wù)開始時(shí)間、任務(wù)結(jié)束時(shí)間、航班降落跑道，如表1所示；模型的生成以及模型求解的算法均采用SQL SERVER編寫，試驗(yàn)的硬件環(huán)境是Intel（R）Core（TM）i5-10210u，2.11GHz主頻，16G 內(nèi)存，Windows操作系統(tǒng)的計(jì)算機(jī)，使用LINGO 18.0軟件對(duì)模型進(jìn)行求解，最后借助EXCEL工具對(duì)LINGO的求解結(jié)果進(jìn)行篩選整理。

（二）實(shí)驗(yàn)結(jié)果

算法的參數(shù)設(shè)置如下：

成本設(shè)置：將測(cè)試模型的班期設(shè)置成本設(shè)為8500元/班；而任務(wù)不被覆蓋的懲罰成本則假設(shè)為10000元/項(xiàng)；任務(wù)重復(fù)覆蓋的懲罰成本為9000元/項(xiàng)。

任務(wù)銜接條件設(shè)置：所有任務(wù)的執(zhí)行時(shí)長(zhǎng)統(tǒng)一定為30分鐘，同一跑道區(qū)域的所屬任務(wù)，兩兩時(shí)間間隔≥30分鐘的任務(wù)可相互銜接；不同跑道區(qū)域的所屬任務(wù)，不可相互銜接。

從班期所保障的任務(wù)序列角度展示排班結(jié)果，表2中的行代表一個(gè)班期，規(guī)定了班期開始時(shí)間、班期結(jié)束時(shí)間以及保障的任務(wù)（航班號(hào)）。例如表2中的第1個(gè)班期數(shù)據(jù)表示：第1個(gè)班期實(shí)際開始時(shí)間為07：55，實(shí)際結(jié)束時(shí)間為12：10（屬于類班期—早班），該班期保障的任務(wù)序列為：任務(wù)2、任務(wù)13、任務(wù)16、任務(wù)32、任務(wù)44和任務(wù)79。

五、結(jié)語

本文以機(jī)場(chǎng)航班過站期間的地勤服務(wù)問題為例，以運(yùn)營(yíng)成本最小化為目標(biāo)，建立了集分割排班模型，由于地勤人員排班問題是典型的NP難問題，要窮盡所有可行的任務(wù)序列是幾乎不可能的，故實(shí)現(xiàn)模型的求解非常困難，于是提出了列生成算法來求解該排班模型。利用A機(jī)場(chǎng)的實(shí)際數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，結(jié)果表明，相較于傳統(tǒng)的排班模型，集分割排班模型能夠有效減少模型變量個(gè)數(shù)，在更短的時(shí)間內(nèi)得到員工班期方案，并且模型求解得到的班期方案能夠有效優(yōu)化機(jī)場(chǎng)地勤人員的調(diào)配，提升機(jī)場(chǎng)服務(wù)質(zhì)量。

參考文獻(xiàn)：

[1]Griffiths P，Saville C，Ball J，et al. Nursing workload，nurse staffing methodologies and tools：A systematic scoping review and discussion[J].International journal of nursing studies，2020，103：103487.

[2]Santosa B，Krisnawati M，Rusdiansyah A.Solving crew rostering using metaheuristics，a case study in Indonesia[J].International Journal of Metaheuristics，2020，7（04）：307-329.

[3]藍(lán)伯雄，張米.考慮延誤因素的機(jī)組排班模型研究[J].中國(guó)管理科學(xué)，2015，23（12）：167-176.

[4]王秀利，徐悅，胡修武.中小呼叫中心月度排班優(yōu)化模型與算法[J].中國(guó)管理科學(xué)，2021，29（04）：169-178.

[5]Soukour A A，Devendeville L，Lucet C，et al.A memetic algorithm for staff scheduling problem in airport security service[J].Expert Systems with Applications，2013，40（18）：7504-7512.

[6]Ip W H，Wang D，Cho V.Aircraft ground service scheduling problems and their genetic algorithm with hybrid assignment and sequence encoding scheme[J]. IEEE Systems Journal，2012，7（04）：649-657.

[7]Clausen T.A Rule-Based Local Search Algorithm for General Shift Design Problems in Airport Ground Handling[J]. transporta，2010.

[8]樊瑋，吳建波，衡紅軍.基于多 Agent 的機(jī)場(chǎng)地面服務(wù)車輛調(diào)度方法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2015，32（10）：256-259.

[9]張建同，楊文娟.基于優(yōu)先級(jí)的進(jìn)離港航班排序優(yōu)化問題研究[J].運(yùn)籌與管理，2018，27（06）：115-121.

[10]盧敏，王莉.面向班型動(dòng)態(tài)生成的地服人員排班算法[J].交通運(yùn)輸系統(tǒng)工程與信息，2018，18（04）：54-60.

[11]馮霞，唐菱，盧敏.面向?qū)哟钨Y質(zhì)的機(jī)場(chǎng)外航服務(wù)人員排班研究[J].交通運(yùn)輸系統(tǒng)工程與信息，2018，19（02）：231-237.

[12]Van Hoai T，Reinelt G，Bock H G.Advanced column generation techniques for crew pairing problems[M]//Modeling， Simulation and Optimization of Complex Processes.Springer，Berlin，Heidelberg，2005：203-214.

＊基金項(xiàng)目：云南省教育廳省院省校合作項(xiàng)目“邊疆欠發(fā)達(dá)地區(qū)中小企業(yè)創(chuàng)新發(fā)展對(duì)策研究”（課題編號(hào)KKDA202008001）。

（作者單位：昆明理工大學(xué)管理與經(jīng)濟(jì)學(xué)院。繆彬?yàn)橥ㄐ抛髡撸?/p>