陳紹寬，馬卓然，彭小波，金 華，王志美

(1.北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點實驗室，北京100044；2.中國鐵路設(shè)計集團(tuán)有限公司，天津300251)

0 引言

乘務(wù)輪班計劃是指在乘務(wù)排班計劃編制完成后，按照一定的規(guī)則，建立班次與乘務(wù)人員對應(yīng)關(guān)系的過程.乘務(wù)輪班計劃的質(zhì)量不僅關(guān)系到運行圖所制定的運輸任務(wù)能否順利完成，而且和運輸人工成本密切關(guān)聯(lián)，對運輸企業(yè)的運營管理具有重要意義[1].

乘務(wù)輪班計劃廣泛應(yīng)用于航空、鐵路、地鐵、公交等不同的運輸行業(yè)部門.國內(nèi)外學(xué)者針對其建模及求解算法開展了一系列的研究，例如，Dohn等將乘務(wù)輪班計劃定義為一個廣義的集合分割模型并使用分枝定價算法求解[2].Nishi等將乘務(wù)輪班計劃分解為上層主問題與下層子問題，主問題的求解采用分枝定界算法[3].Lu?ic等構(gòu)建了乘務(wù)輪班計劃的多目標(biāo)優(yōu)化模型，求解時首先應(yīng)用“飛行員連接飛行員”的啟發(fā)式算法生成初始解，再采用模擬退火算法對初始解進(jìn)行優(yōu)化[4].Maenhout等采用禁忌搜索方法求解乘務(wù)計劃問題[5].劉濤將乘務(wù)輪班計劃構(gòu)建為多層次均衡指派問題并設(shè)計了基于遺傳算法的求解方法[6].Xie等將乘務(wù)計劃問題轉(zhuǎn)化為多商品流問題并采用商業(yè)軟件CPLEX進(jìn)行求解[7].彭小波[8]將乘務(wù)輪班計劃問題的求解分為輪班劃分和輪班分配兩個階段順序求解，在輪班劃分階段不區(qū)分同類型的班次，輪班分配階段將具體班次分配到劃分階段的結(jié)果中，可有效優(yōu)化大規(guī)模乘務(wù)輪班計劃.Sodhi等[9]曾在研究兩階段方法求解倫敦地鐵乘務(wù)輪班問題時，證明了分階段求解與一體化求解相比最優(yōu)解的差距在2%之內(nèi)，但可大幅度減少求解時間.因此，兩階段方法受到了較為廣泛的應(yīng)用[7-10].

基于上述研究，本文考慮實際生產(chǎn)工作中對乘務(wù)輪班計劃的一般性約束，以工作強(qiáng)度均衡為目標(biāo)構(gòu)建乘務(wù)輪班問題的兩階段模型，并設(shè)計混合智能算法求解所構(gòu)建的模型，為乘務(wù)輪班計劃的編制與優(yōu)化提供依據(jù).

1 乘務(wù)輪班計劃及其編制

地鐵乘務(wù)輪班計劃通?；谂虐嘤媱澋慕Y(jié)果，尋找覆蓋所有班次的可行輪班模式來安排司機(jī)某天具體值乘的班次，其編制目標(biāo)之一是實現(xiàn)司機(jī)工作量的均衡.單一循環(huán)模式是目前地鐵運營實踐中經(jīng)常采用的一種手工編制方法，其核心思想是將所有班次按一定順序由所有乘務(wù)員依次循環(huán)執(zhí)行，乘務(wù)員在該類型的輪班計劃中工作內(nèi)容完全相同.循環(huán)周期長度等于所有班次和休息次數(shù)之和，當(dāng)工作班數(shù)較多時，輪班計劃的循環(huán)周期較長.

地鐵運營組織中乘務(wù)工作班制復(fù)雜、乘務(wù)人員規(guī)模較大，導(dǎo)致單一輪班循環(huán)周期較長，因而在一定時間段內(nèi)實現(xiàn)乘務(wù)員工作量均衡較為困難.本文提出基于周期循環(huán)的乘務(wù)輪班計劃編制方法，采用基于循環(huán)“輪班單元”而非單個班次的形式獲得輪班計劃，如表1所示，其中M、D、N、R分別表示早班、白班、夜班、休息.表1中列表示1周7天，行表示輪班單元，即周數(shù)，每一周對應(yīng)1位乘務(wù)員.同組的乘務(wù)人員采用相同的輪班單元計劃，從不同的行(周數(shù))開始執(zhí)行.例如，表1中共有5個輪班單元，對應(yīng)5位乘務(wù)人員.若輪班周期為30天，則第1位乘務(wù)員值乘的班次序列以輪班單元和班次表示為001-002-003-004-D-D，第2位乘務(wù)員為002-003-004-005-N-M，以此類推，第5位乘務(wù)員對應(yīng)005-001-002-003-M-R.

表1 輪班單元計劃Table 1 Unit rostering

采用引入“輪班單元”的周期循環(huán)模式時，大周期內(nèi)乘務(wù)人員的工作安排是相同的，因此以“輪班單元”為單位考慮均衡度優(yōu)化.通常從兩個角度考慮均衡：一是從班次角度，對“輪班單元”的不同類型班次數(shù)和總班次數(shù)的均衡；二是從具體工作指標(biāo)角度，對工作時間和駕駛時間的均衡.本文針對平日及雙休乘務(wù)計劃展開研究，輪班單元的長度選為7天，主要考慮以下的計劃制定要素.

(R1)班次覆蓋性.每一個班次均有乘務(wù)員值乘且每位乘務(wù)員每天最多值乘1個班次.

(R2)連續(xù)工作與休息時間限制.乘務(wù)人員連續(xù)工作與休息不能超過規(guī)定天數(shù).考慮到夜班特殊性，連續(xù)值乘的夜班數(shù)量也不能超過規(guī)定值.

(R3)值乘模式約束.依據(jù)工作規(guī)章制度避免某種值乘序列出現(xiàn)，常見的為避免連續(xù)休息日中單獨1天工作的班次連接，即避免“休息—工作—休息”的組合形式.

(R4)班次接續(xù)關(guān)系.連續(xù)兩天規(guī)定班次間必須或避免存在的接續(xù)關(guān)系，例如考慮“夜—早同員”的制度.

(R5)間隔時間限制.乘務(wù)員連續(xù)兩天值乘的班次間必須滿足一定的時間間隔.

(R6)休息頻率限制.總的休息天數(shù)占輪班周期長度的比例在限定范圍內(nèi).

2 模型構(gòu)建

在前述分析基礎(chǔ)上以工作強(qiáng)度均衡為目標(biāo)構(gòu)建乘務(wù)輪班計劃的兩階段優(yōu)化模型.

2.1 輪班劃分模型

輪班劃分階段獲得確定班次類型的輪班單元計劃，以乘務(wù)員值乘每類班次和休息的個數(shù)與均值的偏差表示工作強(qiáng)度的均衡程度，表示為乘務(wù)員值乘每類班次數(shù)量的標(biāo)準(zhǔn)差與總值乘班次數(shù)標(biāo)準(zhǔn)差的加權(quán)和.目標(biāo)函數(shù)為

模型約束條件如式(2)～式(10)所示.

式中：L表示將全部輪班單元首尾相銜接形成的長鏈；Xjl,k表示若長鏈L特定位置jl為第k類班次則取1，否則取 0；Kn表示夜班班次的集合；Cd、Cr和Cn分別表示最長連續(xù)工作天數(shù)、最長連續(xù)休息天數(shù)和最長連續(xù)值乘夜班天數(shù)；ka和kb表示必須相連的兩類班次，kc和kd表示避免相連的兩類班次，ka,kb,kc,kd∈K；Rmin和Rmax分別表示輪班單元內(nèi)休息日數(shù)量上、下限.

式(2)為由規(guī)則(R1)規(guī)定的覆蓋約束，周期循環(huán)輪班計劃需將輪班單元的首尾相連形成循環(huán)閉環(huán)，因此構(gòu)造部分約束時需同時兼顧輪班單元內(nèi)部和相互之間的銜接.式(3)表示變量間的對應(yīng)關(guān)系.式(4)～式(6)對應(yīng)規(guī)則(R2)，確保長鏈內(nèi)部及首尾銜接處滿足連續(xù)工作與休息時間約束.式(7)對應(yīng)規(guī)則(R3)，避免班次序列中出現(xiàn)“休息—工作—休息”的接續(xù)方式.式(8)與(R4)對應(yīng)式(9)與規(guī)則(R6)相關(guān)，確保輪班單元內(nèi)的休息日數(shù)量在規(guī)定范圍內(nèi).

2.2 輪班分配模型

輪班分配階段分配具體的乘務(wù)班次.不同班次工作時間和駕駛時間之間存在差異且兩者均為反映工作強(qiáng)度的重要指標(biāo).其中，工作時間指司機(jī)從出勤到退勤的時間，駕駛時間則指司機(jī)的在車時間.工作時間和駕駛時間的均衡程度分別用乘務(wù)員值乘各類班次的總工作時間標(biāo)準(zhǔn)差之和與總駕駛時間標(biāo)準(zhǔn)差之和表示，目標(biāo)函數(shù)為

式中：λd和λt表示權(quán)重系數(shù)；q表示1天中的第q個班次；Qj為第j天的班次集合；Qj,k表示第j天第k類班次的集合；dj,q、tj,q、sj,q和ej,q分別表示第j天班次q的工作時間、駕駛時間、出勤時刻與退勤時刻；Averdk、Avertk分別對應(yīng)輪班單元長度內(nèi)第k類班次的人均工作時間和人均駕駛時間；yi,j,q為決策變量，若第i位乘務(wù)員在第j天值乘第q個班次則取1，否則為0.

模型約束條件如式(12)～式(15)所示.

式中：C表示連續(xù)值乘的兩個班次間最小間隔時間；T表示1天的時間，即24 h.

式(12)是劃分模型求解產(chǎn)生的匹配約束，在確定值乘班次類型后，該位置僅分配對應(yīng)類型的具體班次；式(13)含義同式(3)；式(14)對應(yīng)規(guī)則(R5)，連續(xù)值乘的兩個班次間不小于最小間隔時間C.

3 求解算法

本文設(shè)計基于粒子群和模擬進(jìn)化算法的混合算法對所建兩階段模型進(jìn)行求解，該算法中粒子群算法可快速縮小解空間范圍而模擬進(jìn)化算法具有較強(qiáng)的局部搜索能力.

3.1 輪班劃分模型求解算法

輪班劃分模型求解算法的種群中每個粒子表示乘務(wù)計劃的1個解，每個解可表示為一個Imax×Jmax的二維矩陣，矩陣內(nèi)k表示班次類型，0表示休息.算法的適應(yīng)度函數(shù)為，S表示粒子.

粒子群優(yōu)化算法由初始化、粒子適應(yīng)度評價、粒子狀態(tài)更新、終止條件判斷4個步驟組成，其中初始化和粒子狀態(tài)更新2個步驟根據(jù)模型的特征進(jìn)行相應(yīng)改進(jìn).

(1)初始化.

初始種群構(gòu)建時，依據(jù)覆蓋性約束將每天各類班次隨機(jī)分配給所有乘務(wù)員，未分配位置用0表示，此時二維矩陣的每一列均滿足覆蓋約束；再根據(jù)其他約束調(diào)整初始解時為保證覆蓋約束不被破壞，僅允許在列上進(jìn)行重排，禁止列與列之間的交換.

(2)更新粒子狀態(tài).

編碼時粒子表示班次的序列，采用遺傳算法交叉算子、變異算子及設(shè)計接續(xù)誘導(dǎo)算子來完成該步驟.

交叉算子采用當(dāng)前粒子及其到目前為止的最優(yōu)個體、該群體到目前為止的最優(yōu)個體三者交叉，新生成的粒子隨機(jī)包含這三者中某一片段，為維持覆蓋約束，交叉時只允許相同位置列交叉互換；變異算子值按概率隨機(jī)選取并打亂1天中班次順序，當(dāng)種群平均適應(yīng)度值接近種群中最大適應(yīng)度值時，突增變異概率以增加種群的多樣性；接續(xù)誘導(dǎo)算子通過導(dǎo)向變異相關(guān)基因誘導(dǎo)種群中個體向更優(yōu)的方向進(jìn)化，具體為輪班單元內(nèi)部在每次變異后，對任意相鄰兩天的班次進(jìn)行調(diào)整，通過在列上交換位置滿足班次接續(xù)關(guān)系約束；輪班單元銜接處通過深度優(yōu)先算法調(diào)整輪班單元的順序，使其首尾相連后滿足班次的接續(xù)關(guān)系.

粒子群算法達(dá)到設(shè)定迭代次數(shù)后，將其最優(yōu)解引入模擬進(jìn)化算法中.評價個體與種群適應(yīng)度時以每天輪班順序的懲罰函數(shù)值作為個體適應(yīng)度函數(shù)值.當(dāng)滿足所有約束時，懲罰函數(shù)值為0，個體的適應(yīng)度為正無窮.個體重組從輪班的角度，為隨機(jī)打亂1天或幾天的班次，使其重新排列，同時加入誘導(dǎo)算子將重組的個體調(diào)整到可行.具體算法流程如圖1所示.

3.2 輪班分配模型算法設(shè)計

輪班分配模型的求解算法步驟與輪班劃分模型相似.編碼時Imax×Jmax的二維矩陣內(nèi)q表示具體班次，0表示休息.所有輪班單元中的每一個位置班次類型均固定，在加入動態(tài)變異算子與重組個體的過程中如需將1天內(nèi)班次順序打亂(即在列上進(jìn)行重排)，則僅允許相同類型班次的順序重新排列而禁止不同類型班次間的交換.算法流程如圖2所示.

圖1 輪班劃分階段算法流程圖Fig.1 Algorithm flow chart of partition stage

4 案例研究

本文以北京地鐵某線路平日及雙休日運行計劃為例，開展乘務(wù)輪班計劃優(yōu)化研究.該線路全長19.0 km，設(shè)13座車站.既有乘務(wù)計劃班次類型共6種，各類班次數(shù)量如表2所示.

表2 平日及周末各類班次數(shù)量Table 2 Number of shifts on weekdays and weekends

該輪班計劃是基于六班五運轉(zhuǎn)的單一班制，按照“白—夜—早—休—夜—早”的單一循環(huán)模式編制而成.每日100個值乘班次(其中含8個休息補(bǔ)足班次)，20個休息班次.

(1)參數(shù)設(shè)置.

案例中共有120名乘務(wù)員，輪班單元長度為7，包含6種類型的班次，因此，Imax=120、Jmax=7、Kmax=6，aj,k取值根據(jù)表2獲得，其余各參數(shù)如表3所示.考慮夜早同員，兩者銜接即為最小間隔時間.

(2)模型求解.

種群規(guī)模設(shè)為100.輪班劃分模型采用粒子群算法迭代1 500代，搜索到接近可行解后將結(jié)果引入模擬進(jìn)化算法中，繼續(xù)優(yōu)化2×105代.最終適應(yīng)度值收斂為0.23，目標(biāo)函數(shù)值為4.31.輪班分配模型算法迭代次數(shù)與劃分模型相同，適應(yīng)度值收斂為2.91×10-3，目標(biāo)函數(shù)為344.5 min.

圖2 輪班分配階段算法流程圖Fig.2 Algorithm flow chart of allocation stage

表3 案例參數(shù)取值Table 3 Value of parameters

(3)工作強(qiáng)度均衡度分析.

案例中輪班單元長度為7天，取7天的既有輪班方案與模型優(yōu)化結(jié)果進(jìn)行對比分析.

①班次類型均衡程度.

既有輪班方案的班次類型均衡度與模型優(yōu)化后結(jié)果如表4所示.

表4 班次類型均衡程度對比Table 4 Comparisons on the balance of shift types

由表4可知，各班次和休息的均衡度較既有方案分別優(yōu)化了25.7%，32.4%、32.4%和21.3%，預(yù)備班次的均衡程度相同.優(yōu)化模型的目標(biāo)函數(shù)值較既有方案的5.35優(yōu)化了19.4%，表明乘務(wù)員值乘各類班次數(shù)量差別更小，乘務(wù)員之間工作強(qiáng)度更加均衡.

②工作時間與駕駛時間均衡程度.

對比既有方案乘務(wù)員值乘各類班次工作時間、駕駛時間的標(biāo)準(zhǔn)差和模型優(yōu)化結(jié)果，如圖3所示.模型優(yōu)化結(jié)果的各標(biāo)準(zhǔn)差均小于或等于既有方案，除預(yù)備班外，均有大幅度的優(yōu)化.駕駛時間均衡程度的優(yōu)化率均超過50%，輪班分配模型的目標(biāo)函數(shù)值為344.5 min，較既有方案的650.3 min優(yōu)化了47%.

圖3 模型求解與既有方案對比Fig.3 Comparison between model solution and existing method

5 結(jié)論

在分析地鐵乘務(wù)輪班計劃實際需求基礎(chǔ)上，提出基于“輪班單元”的周期循環(huán)乘務(wù)輪班計劃優(yōu)化方法.以乘務(wù)員工作強(qiáng)度均衡為目標(biāo)構(gòu)建輪班計劃兩階段模型，設(shè)計了嵌套粒子群和模擬進(jìn)化算法的混合智能算法對模型進(jìn)行求解.通過案例研究，優(yōu)化結(jié)果與既有輪班方案相比，兩階段優(yōu)化模型的目標(biāo)函數(shù)值分別改善了19.4%和47%，有效提高了乘務(wù)員間工作量均衡程度.本文研究成果適用于具有周期性規(guī)律的乘務(wù)輪班計劃，主要考慮工作強(qiáng)度的均衡程度，未來研究還應(yīng)進(jìn)一步考慮線路運營組織(多交路、跨線運營等)、乘務(wù)員個性需求(如周末休息等)等影響因素及求解算法效率以滿足大規(guī)模乘務(wù)計劃優(yōu)化的需要.