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

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

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

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

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

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

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

1 引 言

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

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

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

2 問題分析

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

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

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

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

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

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

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

3 模型構(gòu)建

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

3.1 費用計算方法

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

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

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

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

（2）乘務(wù)工作班費用.

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

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

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

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

②間休時間懲罰費用.

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

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

③就餐時間懲罰費用.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

式中 Tyh為最長作業(yè)時間標(biāo)準(zhǔn)；Tyq為最短作業(yè)時間標(biāo)準(zhǔn).

一個乘務(wù)工作班的總懲罰費用為

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

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

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

約束條件如下：

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

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

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

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

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

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

3.3 乘務(wù)工作班生成模型

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

約束條件包括：

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

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

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

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

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

4 求解算法設(shè)計

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

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

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

（1）基本方案.

具體操作步驟如下：

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

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

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

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

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

⑥重復(fù)步驟③—⑤，直至S=φ，算法結(jié)束，否則轉(zhuǎn)入步驟③.

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

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

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

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

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

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

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

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

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

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

4.2 乘務(wù)工作班生成算法

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

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

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

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

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

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

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

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

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

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

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

⑧重復(fù)過程②—⑦，直到滿足算法的結(jié)束條件為止.

（3）算法結(jié)束.

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

5 算例分析

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

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

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

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

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

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

表4 乘務(wù)排班方案Table 4 Crew scheduling results

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

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

計算表明：間休時間1的平均值為42分，間休時間2的平均值為32分，平均超出標(biāo)準(zhǔn)間休時間22分.

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

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

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

6 研究結(jié)論

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

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

［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]趙鵬.高速鐵路動車組和乘務(wù)員運用的研究[D].北京交通大學(xué),1998.

［5]王瑩,劉軍,苗建瑞.客運專線乘務(wù)交路計劃編制的優(yōu)化模型與算法[J].鐵道學(xué)報.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]田志強.高速鐵路乘務(wù)計劃編制優(yōu)化理論與方法研究[D].西南交通大學(xué),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]李獻忠,徐瑞華.基于時問耗費的城市軌道交通乘務(wù)排班優(yōu)化[J].鐵道學(xué)報.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]陳仕軍,沈吟東,蘇璇,等.帶中式用餐約束的乘務(wù)調(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

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

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