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

黃夢婷　繆彬

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

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

一、引言

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

人員排班的主要研究內(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ī)場保障服務(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ì)需求的地勤人員排班問題，并使用模擬退火算法對模型進(jìn)行求解。國內(nèi)關(guān)于地勤服務(wù)調(diào)度問題的研究大多集中于車輛調(diào)度優(yōu)化以及航班進(jìn)出港排序優(yōu)化問題上；盧敏、馮霞等分別研究了面向班型動(dòng)態(tài)生成和面向?qū)哟钨Y質(zhì)的機(jī)場地服人員排班問題，克服了傳統(tǒng)人員排班模型中的單一任務(wù)、單一資質(zhì)問題。

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

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

（一）問題描述

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

班期組：根據(jù)機(jī)場地勤保障的要求，按時(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ù)的。面對周期性的航班計(jì)劃，機(jī)場地勤服務(wù)部門能以一定的周期為單位對地勤人員進(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ù)序列，為受限的集合分割問題，對主問題進(jìn)行松弛后求解，將得到的對偶解傳遞給子問題；帶有成本約束的最短路子問題模型利用主問題的對偶信息尋找新的任務(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)建

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

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

）

式中：αi表示i任務(wù)的機(jī)會(huì)成本（即任務(wù)覆蓋約束對應(yīng)的對偶變量）；ci表示i任務(wù)的執(zhí)行成本；πs表示s班期的機(jī)會(huì)成本（即班期數(shù)量約束對應(yīng)的對偶變量）；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表示班期的最長時(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：建立集合分割模型，對數(shù)據(jù)進(jìn)行初始化，運(yùn)用啟發(fā)式算法獲得盡可能高質(zhì)量的初始集合（可行任務(wù)序列）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

數(shù)據(jù)選用A機(jī)場地勤服務(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軟件對模型進(jìn)行求解，最后借助EXCEL工具對LINGO的求解結(jié)果進(jìn)行篩選整理。

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

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

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

任務(wù)銜接條件設(shè)置：所有任務(wù)的執(zhí)行時(shí)長統(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ī)場航班過站期間的地勤服務(wù)問題為例，以運(yùn)營成本最小化為目標(biāo)，建立了集分割排班模型，由于地勤人員排班問題是典型的NP難問題，要窮盡所有可行的任務(wù)序列是幾乎不可能的，故實(shí)現(xiàn)模型的求解非常困難，于是提出了列生成算法來求解該排班模型。利用A機(jī)場的實(shí)際數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，結(jié)果表明，相較于傳統(tǒng)的排班模型，集分割排班模型能夠有效減少模型變量個(gè)數(shù)，在更短的時(shí)間內(nèi)得到員工班期方案，并且模型求解得到的班期方案能夠有效優(yōu)化機(jī)場地勤人員的調(diào)配，提升機(jī)場服務(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].中國管理科學(xué)，2015，23（12）：167-176.

[4]王秀利，徐悅，胡修武.中小呼叫中心月度排班優(yōu)化模型與算法[J].中國管理科學(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ī)場地面服務(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ī)場外航服務(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ā)展對策研究”（課題編號(hào)KKDA202008001）。

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