黃夢婷　繆彬

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

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

一、引言

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

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

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

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

二、問題模型構建

（一）問題描述

1. 模型相關概念

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

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

2. 模型的基本假設

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

航班為周期性重復假設：模型假設航空公司的航班計劃是周期性重復的。面對周期性的航班計劃，機場地勤服務部門能以一定的周期為單位對地勤人員進行編排。

（二）模型構建

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

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

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

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

（一）算法的基本思想

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

（二）受限主問題模型

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

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

（三）子問題模型構建

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

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

）

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

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

（四）求解算法

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

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

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

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

Step4：將新生成的任務序列傳遞給集合分割主問題，增加主問題的列數即增加主問題的任務序列，轉到Step2。

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

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

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

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

Step1：對所有任務按時間劃分，分別尋找早中晚班的所有任務對其劃分。

Step2：將早、中、晚班中時間沒有沖突的任務進行組合。

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

Step3：寫出初始可行班期組任務序列。由于前面已經對時間進行劃分則各班期對應的班期組任務序列集合可相應得到。

Step4：求得各個任務對應的任務序列。

四、實驗及分析

（一）實驗數據

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

（二）實驗結果

算法的參數設置如下：

成本設置：將測試模型的班期設置成本設為8500元/班；而任務不被覆蓋的懲罰成本則假設為10000元/項；任務重復覆蓋的懲罰成本為9000元/項。

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

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

五、結語

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

參考文獻：

[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]藍伯雄，張米.考慮延誤因素的機組排班模型研究[J].中國管理科學，2015，23（12）：167-176.

[4]王秀利，徐悅，胡修武.中小呼叫中心月度排班優(yōu)化模型與算法[J].中國管理科學，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].計算機應用與軟件，2015，32（10）：256-259.

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

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

[11]馮霞，唐菱，盧敏.面向層次資質的機場外航服務人員排班研究[J].交通運輸系統(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.

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

（作者單位：昆明理工大學管理與經濟學院?？姳驗橥ㄐ抛髡撸?/p>