民航機場地面服務(wù)人力資源兩階段運籌優(yōu)化算法

羅 軍，程 宇，余龍水，吳植英，張家華※

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

0 引言

隨著航空業(yè)務(wù)量的快速增加，高效地利用機場現(xiàn)有人力資源對于降低機場人力成本、保證航班準(zhǔn)點起飛、保證機場有序運行起著至關(guān)重要的作用。在這之中，機場運營成本中的人力成本越發(fā)地成為了不可忽視的機場支出項，排班管理作為機場信息化管理中的重要一環(huán)也因此變得越發(fā)重要。

針對排班問題，國內(nèi)外學(xué)者對此研究進行大量相關(guān)的研究并取得了許多了成果。在班次設(shè)計方面：一個完整的班次應(yīng)包含班次的有效開始和結(jié)束時間，甚至規(guī)定了一次或幾次用餐或休息時間[1]；Herbers[2]在機場地勤排班問題上研究出了通過移動任務(wù)塊平滑需求曲線及在增添班次模板的基礎(chǔ)上可快速求得較優(yōu)班次設(shè)計的算法；Raik[3]在柜臺值機排班問題上通過班次規(guī)則生產(chǎn)可用班次集合后，可用CPLEX 對班次設(shè)計模型進行快速求解；Lishun Zeng[4]在機場地勤排班問題中提出通過使高職能員工可向下兼容低職能工作的方式并采用分支定價算法來進行人力配置的優(yōu)化；2019 年，胡修武[5]在呼叫中心坐席人員排班問題中為班次設(shè)計增添了用于加班的短班次，并運用鄰域搜索算法對模型進行了求解，實現(xiàn)了為公司降低用人成本的同時也為員工增加了創(chuàng)收的機會。2020 年，胡修武[6]在呼叫中心坐席人員排班問題中為班次設(shè)計模型增加了班種與兩段班的概念，并用啟發(fā)式算法求出模型初始解，再以鄰域搜索算法對解進行優(yōu)化，提高了坐席人員工作時間的規(guī)律性。

在人員排班方面，人員排班旨在快速、合理且有效地將人力資源分配到各個班次任務(wù)上[7]，實際上是一類組合優(yōu)化問題。艾杰[8]通過調(diào)研分析建立了帶有強、弱約束的護士排班模型，采用整數(shù)規(guī)劃的分支定界算法對模型進行求解和分析。楊琨等[9]對急診醫(yī)生的周計劃排班問題進行研究，建立了基于馬爾科夫鏈模型和均勻化方法的系統(tǒng)定量評估方法，并設(shè)計禁忌搜索算法對問題加以求解優(yōu)化。李獻忠[10]，張增勇[11]以及豐富[12]等學(xué)者分別從最小化非作業(yè)時間、設(shè)計并最小化懲罰費用、設(shè)計并最大化時間均衡度三個目標(biāo)分別對這個問題進行建模與求解。

國外機場和航空公司目前已有通過建立智能排班系統(tǒng)作為實現(xiàn)這一戰(zhàn)略的重要手段。國內(nèi)機場對于排班算法的研究尚處于起步階段，鮮有實際的應(yīng)用案例。機場地面服務(wù)人員排班運籌優(yōu)化算法作為全國較早研究機場排班算法的實際應(yīng)用，在中國民航業(yè)內(nèi)有開創(chuàng)性的意義。

本文研究以人力資源、人力需求曲線已知作為前提，通過配置每天的班次、確定班次的起始與結(jié)束時間以及所需人力；再根據(jù)員工個性化需求來安排員工在哪一天哪個班次上班，使得班次的人力曲線盡可能貼合任務(wù)需求負荷曲線，同時使排班方式將不再依靠單體的輪詢規(guī)則來進行。相比于歷史排班數(shù)據(jù)，本文提出的兩階段算法使機場的人力資源利用率、排班均衡性顯著提高，機場人力成本顯著降低。

1 問題描述及解決方案

在實際運營中，眾多機場面臨著日益增長的客流量與技術(shù)服務(wù)發(fā)展之間不平衡的問題，其中非常重要的是地面服務(wù)人力資源與利用，主要包括：班次時間劃分與各班次安排人力、人員及崗位技能與數(shù)量規(guī)劃、員工最合理化排班等問題。

經(jīng)過深入地調(diào)研分析，某機場傳統(tǒng)的排班方式是利用員工的豐富經(jīng)驗來設(shè)置長期固定班次組合，一旦班次組合確定，將會在較長的一段時間內(nèi)穩(wěn)定。由于沒有標(biāo)準(zhǔn)的處理過程，每次人為劃分班次都需要耗費不少時間和精力，這也是導(dǎo)致人力利用無法進一步提升的主要原因之一。當(dāng)可供現(xiàn)場調(diào)度的工作人員配備不足，將會導(dǎo)致工作內(nèi)容無法被完成；而當(dāng)配備過多的人員時，這對企業(yè)運營成本來說也是極大的壓力。

通過前面對問題的層層描述，發(fā)現(xiàn)當(dāng)前機場人員排班問題可以被劃分為兩個方面：一是太依賴個人經(jīng)驗導(dǎo)致人力資源安排未能很好的與任務(wù)負荷相對應(yīng)；二是太依賴規(guī)律排班導(dǎo)致靈活地安排人力資源受到一定的限制以及員工之間工作量均衡性差。所以問題的解決方案將從下面的兩個階段來得到實現(xiàn)。

（1）班次設(shè)計階段：該階段需打破原來的憑借排班員經(jīng)驗來確定班次的班次生成方式，根據(jù)任務(wù)需求負荷來在某一時段提供合理的人力數(shù)量，使人力曲線盡可能的去貼合任務(wù)需求負荷曲線以此來達到降低人力資源浪費的情況，減少員工時忙時閑的現(xiàn)象。在一段時期內(nèi)，可用人力資源總量一般是相對穩(wěn)定的，所以在人力需求曲線能夠相對準(zhǔn)確提供的條件下，合理設(shè)計各班次開始時間、班次長度以及班次需求人力是具有現(xiàn)實可行性的。

（2）優(yōu)化排班階段：在上一階段根據(jù)實際負荷設(shè)計好的班次前提下，本階段需打破原先輪詢的規(guī)律排班方式，按照輸入的排班規(guī)則和優(yōu)化方向進行優(yōu)化排班以及排班結(jié)果的輸出，明確每一位員工每天上班時間并保證員工間排班的均衡性。員工上什么班次將不再依靠單一的輪詢規(guī)則來定。該階段主要就是解決員工之間排班不均衡的現(xiàn)象，降低員工之間的抱怨，提高員工工作效率以及服務(wù)質(zhì)量。整體的實現(xiàn)流程如圖1所示。

圖1 整體設(shè)計流程

2 班次設(shè)計

對于有能力提供較為準(zhǔn)確的人力需求曲線的部室，班次設(shè)計能為其優(yōu)化人力的配置，對有限的人力資源進行時間上的重分配，使其在滿足各時段人力需求的前提下，又減少了各時段人力資源的浪費，使得人力資源利用率達到一個較高的水平。

2.1 班次設(shè)計需求分析

一般而言，班次設(shè)計需要兼顧管理的難易程度和生產(chǎn)效益的高低，而影響管理因素的包括每天的班次數(shù)量、每天安排的上班人數(shù)、員工的休假規(guī)律等。通過整理各部門的班次設(shè)計需求，總結(jié)出了以下幾點主要約束：（1）日班次數(shù)量的上下限；（2）班次時長的上下限；（3）日可用人力資源的上限。其中，日班次數(shù)量（種類）與部門管理者的管理能力相關(guān)，一般而言，日班次數(shù)量（種類）與管理難度的關(guān)系、日班次數(shù)量（種類）與班次設(shè)計的效益的關(guān)系以及日可用人力資源與班次設(shè)計的效益的關(guān)系分別如圖2～4所示。

圖2 日班次數(shù)量（種類）與管理難度的關(guān)系

圖3 日班次數(shù)量（種類）與班次設(shè)計的效益的關(guān)系

圖4 日可用人力資源與班次設(shè)計的效益的關(guān)系

在滿足上述約束的前提下，班次設(shè)計的優(yōu)化方向?qū)⒁载摵沙d量最少以及資源浪費量最少為目標(biāo)。在資源充足的情況下，本文所述班次設(shè)計結(jié)果如圖5，班次設(shè)計所形成的在崗人力曲線可以貼合地覆蓋各時段的負荷曲線，使得負荷超載量（負荷曲線高于人力曲線的時段的面積總和）最少的同時，人力資源浪費量（人力曲線高于負荷曲線的時段的面積總和）最少。

圖5 班次設(shè)計樣例

2.2 班次設(shè)計模型構(gòu)建

2.2.1 模型目標(biāo)函數(shù)

（1）負荷超載量最小目標(biāo)函數(shù)

式中：H為每天的時段數(shù)（一般取24 h）；C為一天可選的班次數(shù)；ytct為第t天編號為ct的班次所配置的強度；為第t天編號為c的班次是否覆蓋了h時段，是則置1，否則置0；P為單個員工的負荷處理能力；Bth為第t天h時段的負荷量。

（2）資源浪費量最小目標(biāo)函數(shù)

符號含義同上一條目標(biāo)函數(shù)。

2.2.2 模型約束

（1）班次數(shù)量限制約束

式中：為第t天日班次數(shù)的下限值；為第t天日班次數(shù)的上限值；xtct為第t天是否存在編號為ct的班次，是則置1，否則置0。

（2）班次的存在與班次資源強度配置相關(guān)性的約束

式中：ytct為第t天編號為ct的班次所配置的強度；xtct為第t天是否存在編號為ct的班次，是則置1，否則置0；M為極大值。

2.3 班次設(shè)計算法流程

班次設(shè)計算法流程包括了輸入數(shù)據(jù)的解析、輸入數(shù)據(jù)的歸類、輸入數(shù)據(jù)的檢測、班次矩陣的構(gòu)建等幾大塊。輸入數(shù)據(jù)的歸類要求了輸入數(shù)據(jù)必需包含班次設(shè)計所需的負荷信息、參數(shù)信息、預(yù)設(shè)班次信息、約束信息、優(yōu)化目標(biāo)信息。數(shù)據(jù)檢驗要求各項輸入信息必需完備，一旦輸入數(shù)據(jù)被檢測出有諸如格式或者信息的錯漏的問題，應(yīng)當(dāng)及時反饋給排班員，讓其修正數(shù)據(jù)后再進行班次設(shè)計。在輸入信息完備后，需要構(gòu)建好一個合理的班次矩陣，該班次矩陣是班次設(shè)計模型搭建的基礎(chǔ)，模型約束以及目標(biāo)的構(gòu)建都離不開班次矩陣。

本文所構(gòu)建的所有模型都將以Gurobi 求解器進行求解，在求解結(jié)束后，需提取求解器的求解數(shù)據(jù)，進行結(jié)果整理，并進行班次設(shè)計結(jié)果表的輸出。具體的班次設(shè)計算法流程如圖6所示。

圖6 班次設(shè)計算法流程

3 優(yōu)化排班

優(yōu)化排班階段需要在班次信息、人力信息、約束目標(biāo)函數(shù)信息等已知的情況下，分資質(zhì)完成員工與班次之間的指派。在模型求解過程中需考慮工時均衡、班次類型均衡、最小化虛擬人力、資質(zhì)滿足等問題，最大化地保證排班的公平性，減少員工之間的抱怨，提高員工工作效率以及服務(wù)質(zhì)量。

3.1 優(yōu)化排班需求分析

從本質(zhì)上來講，優(yōu)化排班是在各類硬軟約束的限制下完成人員到班次的一個指派問題。通過對各崗位排班需求的整理，得出代表性的排班需求有班次人數(shù)匹配、班次間隔約束、月工時、最大連續(xù)休假等約束。

班次人數(shù)匹配約束保證為每一個班次指派的人數(shù)等于其需求人數(shù)，最小班次間隔約束保證員工所上的相鄰兩個班次之間的時間間隔不會小于機場規(guī)定的員工休息時間，以上兩條約束屬于模型硬約束保證求解的結(jié)果的可行性。月工時上下限約束保證員工在一個排班周期里的工作量在機場規(guī)定的范圍內(nèi)，最大連續(xù)休假約束保證各員工的上班天數(shù)在一個周期里均勻分布，后兩條約束保證排班的公平性在各員工之間得到一定程度上的保證。

3.2 優(yōu)化排班模型構(gòu)建

3.2.1 模型目標(biāo)函數(shù)

（1）虛擬人數(shù)最小化目標(biāo)函數(shù)

式中：為各班次虛擬人力；為虛擬人力最大值，最小值；Nsf為班次數(shù)量。

（2）工時均衡最小化目標(biāo)函數(shù)

式中：xdmax、xdmin為員工中工時最大值和最小值。

3.2.2 模型約束

（1）班次人數(shù)匹配約束

式中：xij為各員工是否上個班次，是置1，否則置0；Nx為員工數(shù)量；為各班次需求人力。

（2）最小班次間隔約束

式中：cfik為各班次的間隔時間是否小于規(guī)定的休息時間，是置1，否則置0。

（3）月工時上下限約束

式中：為月工時約束上下限值。

（4）最大連續(xù)休假約束

式中：Cr為最大休息天數(shù)；T為排班天數(shù)；wlj為表示各員工在每一天是否上班，是置1，否則置0。

3.3 優(yōu)化排班算法流程

優(yōu)化排班算法流程主要包含了數(shù)據(jù)完善檢驗，模型求解，排班結(jié)果輸出3個階段。圖7所示為優(yōu)化排班算法的具體流程。

圖7 優(yōu)化排班算法的具體流程

（1）數(shù)據(jù)完善檢驗階段。對輸入的數(shù)據(jù)進行格式轉(zhuǎn)換，根據(jù)已知信息補充其他排班的必要信息等；當(dāng)數(shù)據(jù)完善完畢則需要對輸入的數(shù)據(jù)進行錯誤檢驗，檢驗項包括重要數(shù)據(jù)項是否缺失、重要數(shù)據(jù)是否存在常識性錯誤、模型參數(shù)是否沖突等。

（2）模型求解階段。根據(jù)班次人員信息構(gòu)建決策變量；根據(jù)資質(zhì)信息、人員狀態(tài)信息、預(yù)排班信息等對相關(guān)決策變量進行上下限的修改；再根據(jù)約束信息，目標(biāo)函數(shù)信息構(gòu)建模型約束及模型目標(biāo)函數(shù)；最后設(shè)置模型求解時間、求解節(jié)點、MIPGap值等參數(shù)；然后啟動求解。

（3）排班結(jié)果輸出階段。需要根據(jù)決策變量的取值來確定每個人與每個班次的指派關(guān)系，結(jié)合班次的開始結(jié)束時間，生成各員工在排班周期里上下班時刻表。

4 實施效果

本節(jié)選取客艙清潔室作為案例分析，著重討論班次設(shè)計及排班優(yōu)化的結(jié)果對比以往經(jīng)驗排班的優(yōu)越性?？团撉鍧嵤乙酝陌啻卧O(shè)計是通過該部門分隊長的經(jīng)驗來完成設(shè)置的。其設(shè)定的日班次數(shù)為方便管理一般為10，班次時長為12 h，各班次依據(jù)經(jīng)驗分布在一天中的各個時段，每個班次的人數(shù)配置也根據(jù)歷史經(jīng)驗進行劃定，而后各個清潔小組以輪詢方式進行班次之間的指派。

4.1 班次設(shè)計結(jié)果比對

為方便優(yōu)化結(jié)果的展示，在本節(jié)中僅截取班次設(shè)計周期內(nèi)某一天的班次設(shè)計結(jié)果作討論。通過對比發(fā)現(xiàn)：班次設(shè)計結(jié)果生成的人力曲線相比于手工班次人力曲線更為貼合負荷曲線，并且對負荷曲線進行了全覆蓋，在資源浪費上，班次設(shè)計顯然比手工班次的浪費更少，人力資源的利用率更高。具體如圖8。

圖8 班次人力與負荷變化曲線

對上述的手工班次及班次設(shè)計結(jié)果進行指標(biāo)統(tǒng)計，得到如表1 所示結(jié)果。對比手工所設(shè)計班次，算法設(shè)計班次在平均每小時的人力浪費量上減少了約5 個人，在人力資源利用率上提高了約18.67%，即本文所研究的班次設(shè)計算法對于提高機場地勤人員的利用率以及減少人力資源的浪費上有著顯著的作用，可有效降低機場運營成本。

表1 手工班次及班次設(shè)計數(shù)據(jù)信息表

4.2 排班優(yōu)化結(jié)果比對

在優(yōu)化排班方面，主要以客艙清潔室各員工在排班周期內(nèi)的上班天數(shù)與上班總工時上的差異來展示算法排班相對于手工排班的優(yōu)異性。通過統(tǒng)計，算法排班無論是在上班總天數(shù)還是總工時，其均衡性（取值分布范圍）都比手工排班表現(xiàn)要出色不少，且員工總工時分布在明顯低于手工排班。具體如圖9～10所示。

圖9 手工與算法排班上總天數(shù)分布情況

由于借助計算機的計算能力，其耗費人力成本，時間成本都比手工排班要少很多。用方差體現(xiàn)各員工間上邊天數(shù)，上班時長的均衡性。那么在上班總天數(shù)和上班總工時兩方面優(yōu)化的效果如表2所示。

圖10 手工與算法排班之間員工總工時的分布情況

表2 手工與人力排班在工時和上班天數(shù)均衡性方面的優(yōu)化效果

5 結(jié)束語

伴隨著中國經(jīng)濟的高速增長，中國民航業(yè)也正在經(jīng)歷迅速發(fā)展階段，但是在地勤管理方面仍然存在信息化程度不高、無法動態(tài)精準(zhǔn)按需分配等問題。本文針對上述問題，機場地面服務(wù)人員兩階段運籌優(yōu)化算法的研究通過對機場一線員工的崗位資質(zhì)和工作量進行估算、設(shè)計、優(yōu)化和調(diào)整，在機場一線員工中高效地利用各種人、財、物資源，提高運營效率，降低運營成本，建立一個結(jié)果正確、響應(yīng)及時、可人工干預(yù)、整體聯(lián)動，并根據(jù)航班信息、員工資質(zhì)、保障任務(wù)、約束條件，并通過混合算法運籌優(yōu)化排班結(jié)果的機場地面服務(wù)運籌優(yōu)化算法及系統(tǒng)。

本文所進行的研究取得的成效：（1）班次設(shè)計及優(yōu)化排班算法均已上線使用，極大地優(yōu)化了機場人力的配置；（2）本次研究產(chǎn)品上線之前，國內(nèi)還沒有機場真正投入并使用了地服人員智能排班系統(tǒng)，本次研究的產(chǎn)品在國內(nèi)市場上具備獨有性，擁有十分廣闊的市場前景；（3）本次研究在技術(shù)上的具有一定領(lǐng)先性，具體包括算法模型求解上采用混合算法、算法處理過程允許多級松弛、數(shù)據(jù)處理上有雙重檢驗。