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

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

0 引言

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

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

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

1 乘務輪班計劃及其編制

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

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

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

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

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

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

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

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

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

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

2 模型構建

在前述分析基礎上以工作強度均衡為目標構建乘務輪班計劃的兩階段優(yōu)化模型.

2.1 輪班劃分模型

輪班劃分階段獲得確定班次類型的輪班單元計劃，以乘務員值乘每類班次和休息的個數(shù)與均值的偏差表示工作強度的均衡程度，表示為乘務員值乘每類班次數(shù)量的標準差與總值乘班次數(shù)標準差的加權和.目標函數(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分別表示輪班單元內休息日數(shù)量上、下限.

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

2.2 輪班分配模型

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

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

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

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

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

3 求解算法

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

3.1 輪班劃分模型求解算法

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

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

(1)初始化.

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

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

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

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

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

3.2 輪班分配模型算法設計

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

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

4 案例研究

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

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

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

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

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

(2)模型求解.

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

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

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

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

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

①班次類型均衡程度.

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

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

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

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

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

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

5 結論

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