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

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

0 引言

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

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

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

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

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

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

表1 輪班單元計(jì)劃Table 1 Unit rostering

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

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

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

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

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

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

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

2 模型構(gòu)建

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

2.1 輪班劃分模型

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

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

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

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

2.2 輪班分配模型

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

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

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

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

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

3 求解算法

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

3.1 輪班劃分模型求解算法

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

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

(1)初始化.

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

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

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

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

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

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

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

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

4 案例研究

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

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

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

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

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

(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)度均衡度分析.

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

①班次類型均衡程度.

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

表4 班次類型均衡程度對(duì)比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)度更加均衡.

②工作時(shí)間與駕駛時(shí)間均衡程度.

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

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

5 結(jié)論

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