基于懲罰費用的城市軌道交通乘務排班優(yōu)化模型與算法

張增勇，毛保華，杜 鵬，許 奇，吳珂琪

（北京交通大學 城市交通復雜系統(tǒng)理論與技術教育部重點實驗室，北京100044）

基于懲罰費用的城市軌道交通乘務排班優(yōu)化模型與算法

張增勇，毛保華＊，杜 鵬，許 奇，吳珂琪

（北京交通大學 城市交通復雜系統(tǒng)理論與技術教育部重點實驗室，北京100044）

乘務排班計劃是城市軌道交通運營的核心問題之一.本文首先分析了乘務排班問題，接著基于懲罰費用構建了乘務排班優(yōu)化模型,并提出了相應懲罰費用計算方法.根據(jù)乘務排班計劃步驟可知，模型分為乘務作業(yè)段生成模型和乘務工作班生成模型，其中乘務作業(yè)段生成模型為乘務工作班生成模型的下層，乘務作業(yè)段生成模型的解為乘務工作班生成模型的輸入條件.隨后針對建立的雙層模型，分別設計了改進的Dijkstra算法和離散粒子群算法.最后，采用某地鐵線路的運行數(shù)據(jù)對模型和算法進行了驗證.結果表明，間休時間的均值為37分，工作時間的均值為6小時41分，并且所有的乘務工作班分布均勻，證明了模型與算法的有效性.

城市軌道交通；乘務排班計劃；作業(yè)段；工作班；離散粒子群算法

1 引 言

乘務計劃是城市軌道交通運營中的重要環(huán)節(jié)，主要解決軌道交通司機的值乘問題.國內(nèi)多數(shù)城市的乘務計劃由各線路乘務中心手工編制完成，一般消耗數(shù)周時間.為應對安全事故引起的能力變化，以及大型活動引起的客流波動，需要預制多個方案或者提前編制臨時乘務計劃.這種形式存在靈活性較差、對突發(fā)情況應變能力弱等問題，進而影響到城市軌道交通的運營效率與服務水平.

從編制內(nèi)容上看，城市軌道交通乘務計劃可分為乘務排班與乘務輪班兩大部分，其中乘務排班是重點.國外關于乘務排班計劃有一系列的研究成果，主要在國鐵方面.乘務模型以集合覆蓋和集合分割為主，求解算法多采用列生成技術，以及基于列生成技術的分支定價算法[1-3].國內(nèi)關于乘務計劃自動編制的研究主要集中在國家傳統(tǒng)鐵路、客運專線，以及高速鐵路等[4-6].Chu、李獻忠等[7,8]研究了基于智能算法的城市軌道交通乘務計劃編制模型.陳仕軍與沈吟東研究了公交排班問題[9].

求解乘務排班問題涉及條件眾多，條件自身的變通性差，求解難度較大.不同乘務環(huán)境下的乘務排班模型及其求解方法也有所差異.鑒于此，本文首先分析了乘務排班問題，建立了乘務排班優(yōu)化模型；提出了相關費用計算方法，構建了乘務作業(yè)段生成和乘務工作班生成的雙層模型與求解算法；通過算例驗證了模型和算法的有效性.

2 問題分析

按操作步驟，城市軌道交通乘務排班計劃可分為列車運行任務分解、乘務作業(yè)段集合生成、乘務工作班集合生成三大部分.

從列車運行圖中摘出的運行任務為不同車底執(zhí)行的車次鏈集合，車次鏈為同一車底一次出、入車輛段或者停車場所執(zhí)行的按時間順序排列的車次集合.運行任務分解的節(jié)點為車輛段與值乘車站，分解后的片段稱為乘務片段，可表示為

式中 n表示乘務片段編號，最大為N；r(k)表示第k個列車的車底編號，列車數(shù)最大為K；tS表示乘務片段的開始時刻；tE表示乘務片段的結束時刻；dS表示乘務片段的開始地點；dE表示乘務片段的結束地點；P表示乘務片段集合.

由同一車底中臨近的一個或者多個乘務片段組成的片段集合為乘務作業(yè)段.乘務作業(yè)段可表示為

式中 n'表示乘務作業(yè)段編號，最大為 N'，N'≤N；S表示乘務作業(yè)段集合.

乘務排班計劃中，作業(yè)段集合方案是乘務排班方案的輸入數(shù)據(jù)，乘務工作班作業(yè)段可以是不同的車底、不相關聯(lián)的乘務作業(yè)段.一個乘務工作班可表示為

式中 n''表示乘務工作班編號，最大為N''，N''≤N'；R(k)表示乘務工作班w中所包含的車底號集合；W表示乘務工作班集合.

3 模型構建

根據(jù)乘務排班步驟，本文構建了乘務作業(yè)段集合生成模型和乘務工作班生成模型，乘務作業(yè)段集合生成模型的解為乘務工作班生成模型的輸入條件.在兩層模型的構建中，求解目標均為與時間相關的廣義費用.

3.1 費用計算方法

乘務排班相關的計算費用包括乘務作業(yè)段費用和乘務工作班費用兩大部分.

（1）乘務作業(yè)段費用.

乘務作業(yè)段生成模型的費用為時間費用.一個乘務作業(yè)段由數(shù)個乘務片段組成，乘務作業(yè)段的費用表示為

式中 Tzh表示列車從車輛段發(fā)出時的整備時間標準；Tjb表示列車的交接班時間標準；α為0-1變量，乘務片段為段發(fā)時取1，否則為0；β為0-1變量，乘務片段為回段時取1，否則為0.

（2）乘務工作班費用.

乘務工作班費用為懲罰費用，按時間計算，并區(qū)分為不同值乘點間懲罰費用、間休時間懲罰費用、就餐懲罰費用、工作時間與作業(yè)時間懲罰費用.

①不同值乘點間懲罰費用.

不同值乘點間的懲罰費用可表示為

式中 Tijz表示不同值乘點間的走行時間標準，i、 j為交接班的兩個值乘點的編號；a表示不同值乘點間值乘費用懲罰因子.

②間休時間懲罰費用.

間休時間的懲罰費用可表示為

式中 b表示間休時間懲罰因子；Tc表示司機就餐時間長度的標準；Tx表示間休時間標準；γ為0-1變量，相鄰乘務作業(yè)段為不同值乘點時取1，否則為0；χ也為0-1變量，相鄰乘務作業(yè)段間存在就餐時間時取1，否則為0.

③就餐時間懲罰費用.

本文考慮的就餐時間[9]為午餐和晚餐，這兩個時間的懲罰費用計算方法相同.懲罰費用計算時，就餐時間定為間休時間中靠近就餐正點的部分，其中，就餐時段為乘務排班過程中司機正常就餐的時間段（通常為：中午11點至13點、下午17點至19點），就餐正點Tzc為司機就餐的最佳時間（通常為：中午12點、下午18點）.

就餐時間完全處于就餐時段內(nèi)時，就餐時間懲罰費用為0.

就餐時間部分位于就餐時段外時，懲罰費用只計算時段外的部分.就餐時間在就餐正點前時，懲罰費用為

式中 Tcq表示就餐正點的最大前延時刻，就餐正點的最大后延時刻表示為Tch，最大前延時刻和最大后延時刻與正點的時間差距相同；f表示就餐時間懲罰因子.

就餐時間在就餐正點后時，懲罰費用為

就餐時間完全處在就餐時段外時，懲罰費用按全部就餐時間計算.就餐時間完全在正點前時，有

就餐時間完全在就餐正點后時，懲罰費用為

④工作時間和作業(yè)時間懲罰費用.

工作時間懲罰費用為單向上限懲罰，即工作時間超限時進行懲罰.作業(yè)時間采用雙向懲罰，即作業(yè)時間過長或者過短均進行懲罰.工作和作業(yè)時間的偏離采取兩段式懲罰方案，一般地，工作時間有最長界定值，作業(yè)時間有最長和最短界定值.工作時間超出標準但在最長界定范圍內(nèi)計算懲罰費用，超出最長界定范圍后計算加重懲罰費用.

對工作時間，超出標準時間，但仍在規(guī)定最長工作時間以內(nèi)時，懲罰費用可表示為

式中 g表示工作時間懲罰因子；Tw表示標準工作班時間長度；Ns表示一個乘務工作班中包含的乘務作業(yè)段數(shù)目.

超出規(guī)定最長工作時間后的加重懲罰費用為

式中 Twh表示工作班時間上限.

作業(yè)時間指司機在工作班內(nèi)的實際勞動時間.平均工作量較大，在設計懲罰函數(shù)時，懲罰因子值可偏大一些.

對作業(yè)時間，超出標準作業(yè)時間，但仍在規(guī)定的上下界范圍內(nèi)，懲罰費用為

式中 h表示作業(yè)時間懲罰因子；Njb表示一個乘務工作班中包含的不同值乘點交接班數(shù)目；Nzh表示一個乘務工作班中包含的司機帶車出段次數(shù)；Ty表示工作班中的作業(yè)時間總和標準.

超出作業(yè)時間上下界范圍時，懲罰費用為

式中 Tyh為最長作業(yè)時間標準；Tyq為最短作業(yè)時間標準.

一個乘務工作班的總懲罰費用為

3.2 乘務作業(yè)段生成模型

乘務作業(yè)段生成模型目標函數(shù)為目標費用最小化：

式中 q表示任一可行乘務作業(yè)段；Q表示所有可行乘務作業(yè)段的集合；xq表示0-1變量，q被選中時為1，否則為0.

約束條件如下：

（1）同一乘務片段僅允許在一個乘務作業(yè)段中出現(xiàn)，即

式（16）中，Q(p(n))表示包含乘務片段 p(n)的所有可行乘務作業(yè)段集合.

（2）同一車次鏈中任意兩個乘務作業(yè)段的連續(xù)作業(yè)時間之和大于Ts，即

（3）同一個作業(yè)段中，相鄰乘務片段間需滿足

（4）同一個作業(yè)段中，所有乘務片段需滿足

式中 Np表示乘務作業(yè)段中所包含的乘務片段數(shù)目.

3.3 乘務工作班生成模型

工作班生成模型目標函數(shù)為

約束條件包括：

（1）一個乘務作業(yè)段只能出現(xiàn)在某個乘務工作班中，即

式中 Q'(s(j))表示包含乘務作業(yè)段s(j)的所有可行乘務工作班集合.

（2）乘務工作班中的間休時間不得小于Tx，即

（3）就餐時間長不得少于Tc，即

除上述約束外，若司機在執(zhí)行某一工作班時，上班時刻早于 2Tcq-Tzc，同時下班時刻晚于2Tch-Tzc，則必須為該組司機在工作班中間預留就餐時間.

4 求解算法設計

針對構建的雙層模型，下層模型采用改進的Dijkstra算法，上層模型采用離散粒子群算法.

4.1 乘務作業(yè)段生成算法

生成算法分為基本方案和方案調(diào)整兩部分.

（1）基本方案.

具體操作步驟如下：

①將運行圖中的運行任務按車底號依次摘出，得到一組車次鏈；這里，對某車底一天中多次出入段時視為多個車底的車次鏈，以標號區(qū)別.

②設置集合S=φ、集合P=φ、變量n'=1，將車次鏈分割得到的乘務片段以tS大小從1起依次編號，直到最大值N，將p置入S.

③從S中選取tS最小的乘務片段p(i)，生成乘務作業(yè)段s(n')；

④從S的剩余片段中搜索與s(n')同車底、時間最近的乘務片段 p(j)，與s(n')組成新的乘務作業(yè)段s(n')；

⑤重復步驟④，直到s(n')滿足一個乘務作業(yè)段的條件，或者S中已無滿足條件的乘務片段，將s(n')置入集合P，同時n'=n'+1；

⑥重復步驟③—⑤，直至S=φ，算法結束，否則轉入步驟③.

上述過程得到的解為乘務作業(yè)段集合的初始方案，通過對初始方案的調(diào)整，產(chǎn)生新的方案，每一個方案為乘務工作班集合生成提供一次輸入數(shù)據(jù).

（2）方案調(diào)整.

乘務作業(yè)段方案調(diào)整以車次鏈為基礎，同一車次鏈的乘務作業(yè)段為一組.若某車次鏈中存在乘務片段數(shù)少于均值的作業(yè)段，將其定義為小乘務作業(yè)段.一個車次鏈中只允許出現(xiàn)一個小乘務作業(yè)段.不存在小乘務作業(yè)段的車次鏈不進行調(diào)整；對于存在小乘務作業(yè)段的車次鏈以車底出段時間早晚分別編號為1，2，3，…，M.

乘務作業(yè)段集合方案調(diào)整過程可描述如下：

①設重新編號車次鏈的乘務作業(yè)段數(shù)為N，按時間早晚可依次編為1，2，3，…，N.小乘務作業(yè)段可分布在N個位次上；

②將1號車次鏈中的小乘務作業(yè)段分布在位次1上，按基本方案生成算法依次得到新的編號為2，3，…，N的乘務作業(yè)段，其他方案不變，此即為調(diào)整后的一個方案；

③依次調(diào)整1號車次鏈中的小乘務作業(yè)段分布位次為2，3，…，N，其他車底方案不變；

④調(diào)整2號車次鏈，將小乘務作業(yè)段依次分布在位次1，2，3，…，N上，針對每個位次，重復步驟②—③，剩余車底方案不變；

⑤調(diào)整3號車次鏈，將小乘務作業(yè)段依次分布在位次1，2，3，…，N上，針對每個位次，重復步驟②—④，剩余車底方案不變；

⑥按照步驟②—⑤的操作方法，依次調(diào)整編號為4，5，…，M的車次鏈中的小乘務作業(yè)段位次，直到所有的車次鏈中的小乘務作業(yè)段位次調(diào)整完.

4.2 乘務工作班生成算法

乘務排班問題的輸入為乘務作業(yè)段集合方案，計算過程分為初始方案生成、尋優(yōu)過程、算法結束三部分.

（1）初始方案生成.

初始方案生成計算同樣采用改進的Dijkstra算法.

（2）尋優(yōu)過程.

尋優(yōu)過程采用離散粒子群算法，先對解集合空間Q'中的粒子位置和速度進行定義，如表1所示.

表1 粒子的位置和速度定義Table1 Definitions of a particle’s position and velocity

粒子的位置更新可表示為

具體優(yōu)化過程如下：

①用改進的Dijkstra算法生成I個初始解初始位置Xi(0)；

②更新粒子Xi(j)的位置：首先將粒子中的乘務工作班根據(jù)作業(yè)時間（作業(yè)時間相同時，選擇工作時間）從短到長依次編號為1，2，3，…，N''，計算Xi(j)的適應度值Ci(j)，同時令n''=1；

③ 將 Xi(j) 中 組 合 為 工 作 班wi(n'',R(k),tS,tE,dS,dE)的數(shù)個乘務作業(yè)段重新分開，再將這些乘務作業(yè)段分別組合到剩余的乘務工作班上，組合原則為新生成的乘務工作班懲罰費用最小.計算分解—組合后的適應度值Ci'(j)：

若Ci'(j)＜Ci(j)，則Ci(j+1)=Ci'(j)，將 Xi(j)更新為Xi(j+1)，V-i(j)為分解—組合前參與分解—組合的相關乘務工作班集合j)為之后相關的乘務工作班集合，粒子的當前最優(yōu)位置LWi(j+1)=Xi(j+1)，如果LWi(j+1)在I個粒子中的適應度值為最小值，則PW(j+1)=LWi(j+1)，同時n''+1；

若Ci'(j)≥Ci(j)，將分解的乘務作業(yè)段重新組合為wi(n'',R(k),tS,tE,dS,dE)，粒子的其他值保持不變，粒子位置更新，同時n''+1；

④重復過程③，直到所有的乘務工作班均被分解—組合一次，即n''=N''+1時終止；

⑤對Xi(j)各粒子中的乘務工作班根據(jù)作業(yè)時間（作業(yè)時間相同時，選擇工作時間）從短到長重新編號為1，2，3，…，N''，同時令n''=1；

⑥以粒子i中的wi(n'',R(k),tS,tE,dS,dE)為基礎，依次與粒子中剩余工作班進行乘務作業(yè)段置換，原則為：降低乘務工作班懲罰費用，置換后的適應度為Ci'(j)：

若Ci'(j)＜Ci(j)，則Ci(j+1)=Ci'(j)，將 Xi(j)更新為Xi(j+1)，(j)為置換前參與置換的相關乘務工作班集合，(j)為之后相關的乘務工作班集合，粒 子當 前 最優(yōu) 位 置 LWi(j+1)=Xi(j+1)；若LWi(j+1)在 I個 粒 子中適應度最小，則PW(j+1)=LWi(j+1).同時n''=n''+1；

若Ci'(j)≥Ci(j)，將置換的乘務作業(yè)段重新回歸原工作班，其他值保持不變，更新粒子位置，同時n''=n''+1；

⑦重復過程⑥，直到所有的乘務工作班均被置換驗證一次，即n''=N''+1時終止；

⑧重復過程②—⑦，直到滿足算法的結束條件為止.

（3）算法結束.

根據(jù)對迭代精度的要求終止尋優(yōu)過程.具體操作為：當粒子在第J次迭代中相鄰最優(yōu)位置的適應度值之差小于PC時，算法終止.

5 算例分析

本文的算例為某地鐵環(huán)線，含一個車輛段、一個值乘點；運行圖數(shù)據(jù)共包括9列車，分為182個乘務片段，具體如表2所示.

相關的參數(shù)設置如表3所示.

根據(jù)表2和表3的相關數(shù)據(jù)，應用本文構建的模型與相應的算法，求得乘務排班的方案如表4所示.

從表4可以看出，乘務排班方案中包括30個乘務工作班、89個乘務作業(yè)段，存在2個內(nèi)部含有不同值乘點交接班的工作班，1個只有2個乘務作業(yè)段的工作班.

乘務工作班中的間休時間反映了乘務排班方案質量優(yōu)劣.本方案中，一個乘務工作班中平均含有2個間休時間段，其分布如圖1所示.

表3 參數(shù)取值Table3 Parameter value

表4 乘務排班方案Table 4 Crew scheduling results

圖1 間休時間分布Fig.1 Rest time distribution

從圖1中可以看出，間休時間長短相互穿插，依次遞進.這說明不同時間段均存在編制較為困難的乘務作業(yè)段.從整體分布看，存在兩個間休時間高峰，從表4可看出，乘務工作班均位于不同乘務工作班交接點、約束條件較多的區(qū)段，證明類似時間段內(nèi)工作班編制較困難.

計算表明：間休時間1的平均值為42分，間休時間2的平均值為32分，平均超出標準間休時間22分.

工作時間、作業(yè)時間、間休時間是乘務排班計劃方案的三個最重要指標，工作時間一定的條件下，作業(yè)時間與間休時間成反比.本方案中，工作時間、作業(yè)時間與間休時間的分布如圖2所示.

圖2 工作時間、作業(yè)時間、間休時間分布Fig.2 Work time,operating time and break time distribution

算例中，工作時間均值為6小時41分，略低于標準值，這與算例中運行任務結構與模型懲罰機制有關.該算例一個工作班平均含有3個乘務作業(yè)段，時間約5小時.當一個工作班中含有4個乘務作業(yè)段，作業(yè)段時間之和將超過6小時；考慮間休時間、交接班時間等，一個乘務工作班實際時間將超過7小時.此外，模型中工作時間采取單向上限懲罰，故理論上工作時間均值將低于標準值，與算例中的計算結果相符合.

6 研究結論

良好的乘務排班計劃可有效降低城市軌道交通企業(yè)運營成本.通過模型及算例發(fā)現(xiàn)：不同時間段均存在編制較困難的乘務作業(yè)段，尤其是在不同乘務工作班交接點、約束條件較多的時段；對工作時間及間休時間的整體分布分析表明，工作時間均值為6小時41分，低于標準工作時間19分鐘；間休時間均值為37分，超出標準時間22分鐘.此外，除了含有2個乘務作業(yè)段的工作班，剩余工作班的時間分布較均勻.這說明本文構建的模型與算法能夠有效求解城市軌道交通乘務排班問題.

本文研究的是一般條件下的單交路城市軌道交通乘務排班計劃優(yōu)化方法，實際運營中，不同線路的乘務環(huán)境不同，比如不同客流分布條件、網(wǎng)絡化運營條件等，采用的乘務計劃編制方法不同，有待進一步地探討.

［1]Dennis H.A column generation approach for the rail crew re-scheduling problem[J].European Journal of Op?erational Research,2007,180(1):163-173.

［2]Lucas P V,Daniel P,Dennis H,et al.Railway crew re?scheduling with retiming[J].Transportation Research Part C.2012,20(1):95-110.

［3]Silke J,Ulrich W T.Divide-and-price:A decomposi?tion algorithm for solving large railway crew scheduling problems[J].European Journal of Operational Research, 2012,219(2):214-223.

［4]趙鵬.高速鐵路動車組和乘務員運用的研究[D].北京交通大學,1998.

［5]王瑩,劉軍,苗建瑞.客運專線乘務交路計劃編制的優(yōu)化模型與算法[J].鐵道學報.2009,31(1):15-19. [WANG Y,LIU J,MIAO J R.Modeling and solving the crew scheduling problem of passenger dedicated line[J]. Journal of the China Railway Society,2009,31(1):15-19.]

［6]田志強.高速鐵路乘務計劃編制優(yōu)化理論與方法研究[D].西南交通大學,2011.[TIAN Z Q.Study on theo?ry and methods of crew planning problem of high-speed railway[D].Chengdu:Southwest Jiaotong University, 2011.]

［7]Chu S C K,Chan E C.Crew scheduling of light rail tran?sit in Hong Kong:form modeling to implementation[J]. Computers Ops Res.1998,25(11):887-894.

［8]李獻忠,徐瑞華.基于時問耗費的城市軌道交通乘務排班優(yōu)化[J].鐵道學報.2007,29(1):21-25.[LI X Z, XU R H.Optimization of crew scheduling for urban rail transportation based on time costs[J].Journal of the Chi?na Railway Society,2007,29(1):21-25.]

［9]陳仕軍,沈吟東,蘇璇,等.帶中式用餐約束的乘務調(diào)度問題[J].交通運輸系統(tǒng)工程與信息.2013,13(2):90-95.[CHEN S J,SHEN Y D,SU X,et al.A crew schedul?ing with Chinese meal break rules[J].Journal of Trans?portation Systems Engineering and Information Technol?ogy,2013,13(2):90-95.]

Urban Rail Transit Crew Scheduling Model and Algorithm Based on Punishment Costs

ZHANG Zeng-yong,MAO Bao-hua,DU Peng,XU Qi,WU Ke-qi
(Ministry of Education Key Laboratory of Complex System Theory and Technology of Urban Traffic，Beijing Jiaotong University，Beijing l00044，China)

Crew scheduling is one of the core issues of urban rail transit operations.This paper develops an optimization model of crew scheduling based on punishment costs,and proposes corresponding punishment cost calculation method.From the process of crew scheduling,it is found that the models include a crew operating segment generation model and a crew work shift generation model.The crew operating segment generation model is the lower model,and its results are the inputs of crew work shift generation model.Then,for the double-layer model,the paper formulates the improved Dijkstra algorithm and discrete particle swarm optimization.Finally,a subway line’s operational data are used to validate the model and algorithms.The results show that the average rest time is 37 minutes,the average working time is 6 hours 41 minutes,and the crew work shifts are uniformly distributed.All of these demonstrate the effectiveness of the models and its algorithms.

urban rail transit;crew scheduling;operating segment;work shift;discrete particle swarm optimization

1009-6744（2014）02-0113-08

U292.6

A

2013-12-05錄用日期：2013-12-28

國家自然科學基金重點項目(71131001)；國家基礎研究計劃項目(2012CB725406).

張增勇（1985-），男，山西運城人，博士生.*通訊作者：bhmao@china.com