盧 敏，王 莉

(1.中國民航大學(xué)a.中國民航信息技術(shù)科研基地，b.計算機(jī)科學(xué)與技術(shù)學(xué)院，天津300300；2.中山大學(xué)機(jī)器智能與先進(jìn)計算教育部重點實驗室，廣州510275)

0 引言

為了快速且有效地保障航班地面服務(wù)，大型機(jī)場地面服務(wù)部門需生成員工排班方案，將員工分配到班型(組)中，以班型為航班的保障單元，其原由是：①班型有利于地服部門以組為單位監(jiān)控服務(wù)質(zhì)量和計算員工工作時長；②班型落實了低資質(zhì)員工需要高資質(zhì)員工從旁指導(dǎo)和協(xié)助的硬性要求；③班型能滿足員工自愿組對的個性化需求.

由于機(jī)場地服無法獲知班型數(shù)，機(jī)場地服人員排班本質(zhì)是融合班型動態(tài)生成、員工層次資質(zhì)和員工白夜班等約束的人員排班問題.人員排班是指通過最大化任務(wù)完成率和員工滿意度將員工分配到任務(wù)上[1]，被應(yīng)用于交通[2]、醫(yī)療[3]、酒店[4]等領(lǐng)域.班型動態(tài)生成是指自動生成班型，在此基礎(chǔ)上將員工和航班分配到班型中，且要求班型內(nèi)員工能夠滿足組內(nèi)航班的資質(zhì)需求.資質(zhì)是指員工執(zhí)行任務(wù)的能力，而層次資質(zhì)是指員工教育程度和工作經(jīng)驗使得員工資質(zhì)存在層次關(guān)系[4].員工白夜班指員工每天只能從事白天或夜晚的航班.由于班型內(nèi)的人員分配、班型內(nèi)航班分配都是建立在已知班型數(shù)的重要前提下，而實際應(yīng)用中班型數(shù)是未知而需要動態(tài)生成，使得機(jī)場地服排班是一個具有挑戰(zhàn)性的問題.

直觀上可借助面向?qū)哟钨Y質(zhì)的排班算法[5-7]和面向班型的排班算法[8-9]解決機(jī)場地服人員排班.然而，面向?qū)哟钨Y質(zhì)的排班算法[5-7]未考慮班型約束，而面向班型的排班算法[8-9]則是在已知班型數(shù)前提下優(yōu)化班型內(nèi)的人員構(gòu)成和任務(wù)集，不適用班型數(shù)未知的排班問題.此外，它們采用的列生成技術(shù)、啟發(fā)式算法和貪婪算法不適用班型動態(tài)生成約束.

為解決上述問題，提出面向班型動態(tài)生成的地服人員排班算法.算法首先生成滿足員工層次資質(zhì)和白夜班的可行解，在此基礎(chǔ)上將優(yōu)化問題分解為班型內(nèi)人員構(gòu)成、班型內(nèi)航班集、優(yōu)化班型等3個子問題，通過block Gibbs有放回抽樣快速優(yōu)化上述子問題.

本文主要貢獻(xiàn)為：①提出了面向班型動態(tài)生成的地服人員排班算法，解決了大型樞紐機(jī)場地服人員排班問題，可拓展應(yīng)用于機(jī)組人員排班和醫(yī)生/護(hù)士值班等；②針對班型未知的排班問題，提出基于block Gibbs替換抽樣求解算法，通過迭代合并、分裂、重組合班型以更新班型，并在此基礎(chǔ)之上重新調(diào)整班型內(nèi)的人員構(gòu)成和任務(wù)構(gòu)成.

1 問題定義與建模

1.1 問題定義

機(jī)場人員排班是在給定航班計劃和員工資質(zhì)集前提下，生成以組為單位的排班方案.同一組內(nèi)航班需滿足的規(guī)則為：

(1)同一組內(nèi)航班必須為歸屬同一天；

(2)同一組內(nèi)航班白夜班類型須一致；

(3)滿足組內(nèi)航班的層次資質(zhì)數(shù).

S={1,2,…,|S|}表示航班地面保障的任務(wù)種類，|S|表示總?cè)蝿?wù)類型數(shù)；L={1,2,…,|L|}表示航班保障涉及的員工資質(zhì)種類.

假設(shè)員工集合P={1 ,2,…,d}.每名員工i具備資質(zhì)集合SKi∈{0,1}|S|×|L|，其值為 1 表示員工i在任務(wù)類型s上具備l類型資質(zhì).員工工作經(jīng)驗不同使得員工在同一種任務(wù)類型上具有向下兼容的層次資質(zhì)，即當(dāng)

優(yōu)化變量xijg∈{0,1}表示員工i是否服務(wù)第j天第g個班型，取值為1代表執(zhí)行.據(jù)xijg生成1周班型集合Φ={(djg,bjg,ejg,Rjg,Pjg,Χjg)|j=1,…,7;g=1,…,nj} ，分別表示第j天第g個班型的白夜班類型、開始時間、結(jié)束時間、資質(zhì)需求數(shù)、員工集合和航班集合，其中班型開始(或結(jié)束)服務(wù)時間為班型內(nèi)所有航班中最早開始(或最晚結(jié)束)服務(wù)時間.

1.2 數(shù)學(xué)建模

基于上述建模，面向班型動態(tài)生成的地服人員排班優(yōu)化目標(biāo)為

式(1)旨在最小化員工總工作時長，其中員工i第j天的工作時長等于員工i在第j天保障所有航班的時長總和.式(2)表示員工只能選擇服務(wù)白天或夜晚的班型.式(3)和式(4)表示每個班型內(nèi)任務(wù)所需的資質(zhì)數(shù)需得到滿足，式(3)融入員工資質(zhì)層次結(jié)構(gòu)，即高資質(zhì)員工可彌補(bǔ)需要低資質(zhì)員工的空缺；式(4)表示為班型分配的總?cè)藬?shù)恰好等于班型所需的總?cè)藬?shù).式(5)表示同一個班型內(nèi)所有航班來自同一天.式(6)表示同一個班型內(nèi)所有航班的白夜班類型一致.

2 求解算法

提出基于block Gibbs的快速求解算法以優(yōu)化式(1)～式(6)，如Algorithm 1所示.其核心思想是：首先設(shè)計一子模塊生成滿足員工層次資質(zhì)和白夜班的可行解，然后設(shè)計另一子模塊迭代優(yōu)化班型內(nèi)人員構(gòu)成、優(yōu)化班型內(nèi)航班集、優(yōu)化班型，最終生成以班型為單位的排班方案.

Algorithm 1:面向班型動態(tài)生成的地服人員排班算法輸入：航班集合Ω；員工集合P；迭代次數(shù)niter；退火溫度T；衰減因子β輸出：員工任務(wù)排班方案{xijg}初始化：生成初始解foriter=1,…,niter：fori=1,…,N：xijg=0,j=1,…,7;g=1,…,nj采用式(9)抽取yi～p(?|y-i,x-i)foreachΦjg∈Φ：if(RQjg-SKi＜RQjganddig=yi)thenxijg=1 if(式(7)的值等于∑mj)then break//生成初始解迭代優(yōu)化：優(yōu)化班型、優(yōu)化班型內(nèi)人員構(gòu)成和航班集foriter=1,…,niter：子問題I：優(yōu)化班型內(nèi)人員構(gòu)成fori=1,…,N：xijg=0,j=1,…,7;g=1,…,nj采用式(9)抽樣yi～p(?|y-i,x-i)forΦjg∈Φ：if(式(3)和式(4)不滿足)thenxijg=1,yi=djg elseif(djg=yiandRQjg-SKi＜RQjg)then將班型Φjg加入到候選班型集合Φ1中foreachΦhr∈Φ1：xihr=1,Γ ={i|xihr=1,i=1,…,N}采用式(10)抽樣i1～p(i1∈Γ|x,y)令xi1hr=0子問題II：優(yōu)化班型內(nèi)航班集foreachΩjk∈Ω：從航班Ωjk所在班型Φjg1中移除航班Ωjk，修改班型Φjg1的開始和結(jié)束時間foreachΦj'g∈Φ：if(j'!=jor式(3)和式(4)不滿足)then continue將班型Φj'g加入到候選班型集合Κ中根據(jù)式(11)抽樣Φhr～p(Φhr∈Κ|Φ)將航班Ωjk加入到班型Φhr中，修改班型Φhr開始和結(jié)束時間子問題III：優(yōu)化班型foreachΦjg∈Φ：//班型合并foreachΦj'g'∈Φ：if(j'!=jordj'g'!=djg)then continue將班型Φj'g'加入到班型集合Κc中根據(jù)式(11)抽樣Φhr～p(Φhr∈Κc|Φ)，將服務(wù)班型Φjg的員工集和航班集全部加入到班型Φhr中，修改班型Φhr的開始和結(jié)束時間foreachΦjg∈Φ：//班型拆分foreachΩjk∈ Χjg：以航班Ωjk的開始時間為分界線將班型Φjg中航班分為2組航班將2個班型加入到班型對集合Θjt中根據(jù)式(11)抽樣Θkjt～p(Θkjt∈Θjt|Φ)，將班型Φjg中航班拆分為Θkjt中包含的2個班型，修改2個班型的開始和結(jié)束時間，原始班型中員工分別服務(wù)拆分后的2個班型T=T?β

2.1 初始可行解生成

為了快速生成滿足員工資質(zhì)和員工白夜班約束的初始可行解，設(shè)計了優(yōu)化目標(biāo)和約束，即

式(7)為優(yōu)化目標(biāo)，統(tǒng)計滿足資質(zhì)需求的航班數(shù).若每個航班的資質(zhì)需求都得到滿足，則式(7)目標(biāo)值等于總航班數(shù)∑mj；否則存在未滿足資質(zhì)需求的航班，無法得到初始解.式(8)為約束條件，表示員工只能選擇白天或夜晚航班.

初始解生成核心是確定員工的白夜班類型和保障航班分配所需資質(zhì)數(shù).引入Xi表示員工i的任務(wù)集，yi表示員工i的白夜班類型，yi抽樣分布如式(9)所示.I[A]為指示函數(shù)，當(dāng)條件A成立時取值為1，否則為0.ε=le-06為平滑項.式(9)表示當(dāng)存在不滿足約束式(3)的班型時，將yi設(shè)置為此班型對應(yīng)的白夜班類型，否則根據(jù)白天夜晚班型數(shù)量進(jìn)行抽樣.

2.2 迭代優(yōu)化求解

優(yōu)化班型內(nèi)人員構(gòu)成的核心是通過對同一班型內(nèi)員工有放回的抽樣，即先增加1名員工后抽樣撤銷1名員工，實現(xiàn)班型內(nèi)人員調(diào)整以縮短員工總工作時長.具體過程為：首先確定員工白夜班類型，即撤銷員工所保障的班型，判斷是否存在不滿足資質(zhì)需求的班型，若有則將員工白夜班類型設(shè)置為不滿足資質(zhì)需求班型的白夜班類型，反之通過式(9)抽樣確定員工白夜班類型.然后，調(diào)整員工i的保障候選班型集合Φ1中每一個班型Φhr，即xihr=1.保障班型Φhr的員工集合為Γ={i|xihr=1,i=1,…,N}，此時員工集合Γ比需求多1名員工，根據(jù)式(10)抽樣1名員工i1，從該班型中撤銷員工i1，即xi1hr=0.此過程保證不違反約束式(3)和式(4).

優(yōu)化班型內(nèi)航班集的核心是優(yōu)化航班的所屬班型，本質(zhì)是將航班從當(dāng)前班型調(diào)整到另一個班型中.首先針對航班Ωjk從原始所屬班型中撤銷，修改原始班型的開始和結(jié)束時間，然后構(gòu)造航班Ωjk可放入的班型集合Κ，在班型集合Κ中通過式(11)抽樣得到1個班型Φhr，最后將航班Ωjk放入班型Φhr中，修改此班型的開始和結(jié)束時間.其中班型集合Κ中的每一個班型需要滿足：①白夜班類型須與航班Ωjk一致；②與航班Ωjk在同一天；③班型所包含的員工能夠滿足航班Ωjk的資質(zhì)需求.

優(yōu)化班型的核心是結(jié)合員工工作時長，通過分裂和合并現(xiàn)有班型以更新班型.

班型合并的核心是將2個班型合并為1個班型.針對班型Φjg∈Φ，將與班型Φjg同一天且白夜班類型相同的班型加入班型集合Κc中，通過式(11)在班型集合Κc中進(jìn)行抽樣，得到班型Φhr，將班型Φjg與班型Φhr包含航班和員工合并，修改合并后班型的開始與結(jié)束時間.

班型拆分的核心是將1個班型拆分成2個班型.針對班型Φjg∈Φ，以班型Φjg中航班的開始時間為準(zhǔn)將班型內(nèi)航班分成2組，構(gòu)成班型對集合Θjg，根據(jù)式(11)在班型對集合中抽樣得到1個班型對Θkjg，將原始班型Φjg中的員工分別分配到被拆開的2個班型中.

3 實驗及分析

3.1 實驗數(shù)據(jù)

實驗數(shù)據(jù)集是某機(jī)場1周航班計劃和值機(jī)員工的資質(zhì)集.每個航空公司的所有航班歸屬于同一任務(wù)，涉及的3種資質(zhì)，分別為“組長”“控制人員”“普通員工”.為描述方便，采用3表示組長，2表示控制人員，1表示普通員工，0表示沒有服務(wù)資質(zhì).

航班數(shù)據(jù)包括49個航班，屬性包括星期、航班號、任務(wù)類型、開始時間、結(jié)束時間、所需組長人數(shù)、所需控制人員數(shù)、所需普通員工人數(shù)，數(shù)據(jù)樣本如表1所示.員工資質(zhì)集則是39名員工在各航空公司(任務(wù))的資質(zhì)信息，數(shù)據(jù)樣本如表2所示.

表2 員工信息數(shù)據(jù)示例Table 2 Samples from persons with skills

3.2 實驗結(jié)果

算法需要人工預(yù)先設(shè)置3個參數(shù)，分別為迭代次數(shù)niter、退火溫度T、衰減系數(shù)β.實驗過程中T和β設(shè)置參考經(jīng)驗值，分別為T=100，β=0.99，niter=200,300,400.本次實驗中niter設(shè)置為200，在第3.3節(jié)算法收斂性中驗證niter取值200的合理性.

實驗結(jié)果部分?jǐn)?shù)據(jù)，如表3所示.表3中1行是1個班型，包含班型的開始時間、結(jié)束時間、班型內(nèi)的航班列表和班型內(nèi)的員工名單.例如，星期一第1個班型包括2個航班“PK852”“J2067”，而根據(jù)表1航班PK852共需6名員工，航班J2067需1名員工，據(jù)表2員工“王巖”同時具備“PK”“J2”類型航班資質(zhì)，即能夠滿足班型對資質(zhì)需求.

以員工“李仁驥”為例展示1周的服務(wù)班型，如表4所示，其中“21:30-02:30”指當(dāng)天晚上的21:30到第2天02:30.員工“李仁驥”1周的班型都是夜晚班型，滿足員工白夜班約束.此外，員工“李仁驥”在星期一和星期三都同時服務(wù)2個班型，究其原因是算法為了最小化員工總工作時長，會將員工分配到2個相鄰的班型中.例如星期一的2個班型之間的間隔只有20 min.

表3 實驗結(jié)果數(shù)據(jù)示例Table 3 Samples from experimental results

表4 員工“李仁驥”的1周任務(wù)示例Table 4 Tasks for Renji Li at one week

3.3 實驗分析

3.3.1 班型分析

算法主要是最小化員工工作時長以生成班型，為此從兩方面對班型進(jìn)行分析：

(1)1周中每天航班個數(shù)與班型個數(shù)如表5所示.表5結(jié)果表明：平均每天將員工分為4組，而每組平均服務(wù)7個航班.如將班型分成白天班型和夜晚班型的情況下，則每天平均會有2個白班班型和2個夜晚班型，對管理人員更方便管控員工的上下班時間.

(2)每個班型的時長如圖1所示.班型時長大多分布在[3,4)h和[4,5)h，對于機(jī)場值機(jī)人員每個班型時長[3,5)h較為合理.

表5 航班個數(shù)和班型個數(shù)Table 5 The number of flights and shifts

圖1 班型時長分布Fig.1 Groups duration distribution

3.3.2 算法特性分析

分析算法收斂性，即隨著迭代次數(shù)增加，目標(biāo)函數(shù)取值的變化程度，如圖2所示.算法在前50輪迭代中總工作時間迅速減少，之后趨于穩(wěn)定，驗證迭代次數(shù)取值200是合理的.

圖2 算法收斂性分析圖Fig.2 Algorithm convergence analysis

分析算法穩(wěn)定性，即多次運行算法，比較員工總工作時長和算法運行時長，如圖3所示.從圖3可知，隨著算法運行次數(shù)的增加，工作時長、運行時間趨于穩(wěn)定狀態(tài).

圖3 算法穩(wěn)定性分析圖Fig.3 Algorithm stability analysis

4 結(jié)論

針對機(jī)場地服人員排班過程中班型數(shù)未知和員工層次資質(zhì)等約束，提出了面向班型動態(tài)生成的地服人員排班算法.算法首先把每個航班作為1個班型，利用一子模塊生成滿足得到滿足員工層次資質(zhì)和員工白夜班的可行解.在此基礎(chǔ)上，設(shè)計了基于block Gibbs有放回抽樣算法，以迭代優(yōu)化班型內(nèi)人員構(gòu)成、班型內(nèi)航班集和班型動態(tài)生成.在國內(nèi)某大型機(jī)場地服人員排班數(shù)據(jù)集上實驗結(jié)果表明算法的可行性與穩(wěn)定性.未來可進(jìn)一步開展具有組內(nèi)約束的人員排班，如班型內(nèi)航班沖突和人員沖突等.