葉玉玲，何嘉棋

（1.同濟大學交通運輸工程學院，上海 201804; 2.同濟大學道路與交通工程教育部重點實驗室，上海 201804）

貨運機車乘務交路是指貨運機車乘務組（又稱機班）擔當值乘任務的周轉區(qū)段，可表示為機車乘務組從乘務基地（一般為機務段所在站）至乘務換乘站 （一般為折返段所在站） 之間往返的線路區(qū)段。 貨運機車乘務交路計劃的編制不僅影響貨運列車能否按計劃行車， 還關系到乘務工作效率和運輸經濟效益。 目前我國貨運機車乘務交路以機務段管理人員憑人工經驗編制為主， 需要花費較長的時間，有時難以得到較優(yōu)方案，甚至產生機車乘務超勞、 值乘任務不均衡、 乘務資源浪費等問題。 而且當鐵路運輸市場需求或線路條件發(fā)生變化時，列車運行圖需要進行不定期調整，機車乘務計劃也需要同步調整，人工編制方法難以適應。 利用計算機技術輔助編制貨運機車乘務交路計劃，對于提高乘務工作效率和降低鐵路運輸企業(yè)成本具有重要的現實意義。

國內外學者在航空運輸[1-2]、鐵路運輸[3-9]、城市公交[10-11]等領域都開展了有關乘務計劃的研究。 但因各種運輸方式特點不同且各國運輸組織制度存在差異， 乘務交路的編制流程和約束條件也有所不同， 難以直接用來解決我國鐵路貨運機車乘務交路問題。 國內有關鐵路乘務交路計劃問題的理論研究主要集中在客運專線上，王媛媛等[12]考慮了乘務繼乘的情況， 將乘務交路編制問題看作特殊的旅行商問題（traveling salesman problem，TSP）問題，設計了改進蟻群算法進行求解；張哲銘等[13]基于單一循環(huán)乘務值乘計劃提出了閉環(huán)排班和非閉環(huán)排班的概念， 研究了結合乘務休息規(guī)則的排班方案；符卓等[14]研究了帶立即折返的高速動車組乘務交路優(yōu)化問題。

現有研究在貨運機車乘務交路方面，主要結合線路實際情況或機車交路對乘務機班存在問題進行定性分析[15-16]，缺乏對貨運乘務交路計算機編制方法的量化研究。

因此，在借鑒鐵路客運乘務交路編制方法的基礎上， 考慮貨運機車乘務的實際工作要求和特點，研究貨運機車乘務交路計劃的編制方法，構建貨運機車乘務交路編制優(yōu)化模型，并設計相應的求解算法，為鐵路運營企業(yè)實現計算機輔助編制貨運機車乘務交路提供理論依據。

1 乘務交路計劃

乘務交路計劃編制 （crew scheduling problem，CSP）是鐵路運輸組織的一個重要問題，受到列車運行圖、沿線車站性質、機車交路和乘務規(guī)則等多因素影響[17-18]。目前我國貨運機車乘務形式為非立即折返型，即機班從乘務基地出勤后，擔當去程乘務片段的值乘任務到達換乘站， 按乘務作業(yè)時間標準間休后， 再擔當返程乘務片段的值乘任務返回乘務基地。 具體的貨運機車乘務交路計劃編制步驟如下。

1） 數據收集。 獲取貨運列車運行信息、機車交路圖，確定乘務基地、折返段及可換乘的車站，明確乘務基地的任務范圍，梳理機車乘務員的工作時間和休息時間要求。

2） 劃分值乘片段。 結合貨運機車交路信息，選擇合適的乘務制度和值乘模式，根據乘務一次連續(xù)工作時間標準，以可換乘的車站為分割點，將列車運行線劃分為若干個值乘片段。

3） 組成乘務交路。根據乘務規(guī)則，考慮工作、休息時間標準約束和機務本段、 折返段的空間約束，一般按先到先走的原則，將值乘片段組合成乘務交路，作為貨運機班一次乘務工作的內容。

4） 組成乘務交路循環(huán)?？紤]到機車乘務員對所駕駛機車類型和線路的熟悉程度，原則上一個機班通常安排在固定的乘務交路循環(huán)中值乘；因此需要將區(qū)段內的乘務交路組成若干個乘務交路循環(huán)，由若干個機班依次循環(huán)執(zhí)行。 貨運乘務交路循環(huán)的接續(xù)主要考慮擔當兩相鄰乘務交路之間乘務員在本段的休息時間標準，優(yōu)化乘務交路循環(huán)順序能有效縮短乘務的排班周期。

CSP 問題的最終目標是確定乘務交路循環(huán)，保證乘務交路集合完全覆蓋全部值乘片段和列車運行線[19]。 根據乘務交路計劃的編制步驟，在步驟1）、步驟2）確定的條件下，考慮乘務交路及其循環(huán)的組合方法，構建乘務交路編制優(yōu)化模型。

2 優(yōu)化模型構建

鐵路貨運機車乘務調度成本主要受機班數量決定，而值乘時間占總工作時間的比例是決定機班數量的重要因素。 也就是說在符合勞動時間標準的前提下，乘務值乘時間比例越高，說明乘務調度越充分，所需要的總機班數量也就越少。 為了降低乘務交路編制問題的復雜性，以乘務交路非值乘時間最少， 即值乘片段間的接續(xù)時間最少為模型目標。根據乘務交路計劃的編制步驟，模型分為乘務交路問題和乘務交路循環(huán)問題，其中乘務交路問題的解為乘務交路循環(huán)問題的輸入條件， 乘務交路問題主要求解機班一次乘務工作的內容， 乘務交路循環(huán)問題是確定機班執(zhí)行各交路任務的值乘順序。

2.1 乘務交路問題

對于若干個值乘片段i=1，2，…，n，構成乘務交路需要滿足的條件為[20]

1） 第一個值乘片段的起始地點與最后一個值乘片段的結束地點為同一機務本段；

2） 相鄰兩值乘片段i，j， 前一值乘片段的結束地點sdi與后一值乘片段的起始地點soj相同；

3）相鄰兩值乘片段i，j，前一值乘片段的結束時間tdi小于后一值乘片段的起始時間toj，且接續(xù)時間滿足乘務在外段休息時間標準。

通過構造值乘片段之間接續(xù)時間tij（單位：min）的n 階矩陣來表示各個值乘片段之間的接續(xù)可能性。

式中：M 為一個足夠大的正整數， 表示值乘片段i，j之間由于不滿足地點接續(xù)性而不能組合成乘務交路。

根據乘務休息時間約束， 機車乘務員在本段的休息時間每次不應少于16 h，即960 min；在外段調休的時間不得小于5 h，即300 min；在外段駐班休息時間不得少于10 h，即600 min；輪乘制外段換班繼乘休息時間不得少于6 h， 即360 min。需要根據值乘片段i 的結束地點和換班方式對tij進行調整。

式中：t′ij+1 440 表示值乘片段j 可與第2 天的值乘片段i 接續(xù)。

因此，tij≠M 時說明值乘片段j 與值乘片段i接續(xù)間有一定的休息時間， 有可能形成乘務交路。為了最小化乘務交路所需要的總機班數，保證乘務在外段停留時間越少越好， 即去程值乘片段i 與回程值乘片段j 的接續(xù)時間tij越小越好， 在編制乘務交路時遵循乘務先到先走原則，即先到達外段的去程值乘片段優(yōu)先接續(xù)最早出發(fā)的回程值乘片段，形成最優(yōu)乘務交路方案。

2.2 乘務交路循環(huán)問題

由于單循環(huán)排班方式有利于均衡乘務員之間的工作量以及提高機班對值乘機車類型和值乘區(qū)段的熟悉程度，在我國貨運機車乘務領域可操作性強。 本文采用單循環(huán)的乘務排班方式，即將某乘務基地管轄范圍內所有的乘務交路，在符合乘務規(guī)則的條件下組成一個有序的循環(huán)，乘務員按照乘務交路循環(huán)的順序依次值乘。 對于同一乘務基地而言，任意2 個乘務交路p，q 的起始和結束地點相同，滿足空間接續(xù)性。

通過構建有向圖以更好地描述乘務交路循環(huán)問題，如圖1 所示。 設G=（V，E）為有向圖，V 表示有向圖的頂點集合，E 表示有向圖的弧集合，Vp（p=1，2，…，n）表示第p 條乘務交路，?。╬，q）∈E 表示乘務交路p 與乘務交路q 接續(xù)關系， 弧上的權值tpq（單位：min） 表示乘務交路p 與乘務交路q 之間的接續(xù)時間。 可構建接續(xù)時間矩陣Tpq，表示乘務交路p 與乘務交路間q 的接續(xù)時間，為非對稱矩陣。

圖1 乘務交路循環(huán)有向圖Fig.1 Directed graph of crew routing cycle

對于單循環(huán)的乘務排班方式，尋求乘務交路循環(huán)最優(yōu)方案的實質，是找到各個乘務交路之間的接續(xù)次序，同時保證總接續(xù)時間最短，可視為尋找該有向圖內經過所有頂點的最短路徑。 乘務交路循環(huán)問題可轉化為非對稱旅行商問題[21]。

對于若干乘務交路p=1，2，…，n（p∈V），不同交路之間的接續(xù)時間為tpq，定義決策變量xpq

3 求解算法設計

3.1 基于先到先走的遍歷搜索算法設計

當一個乘務交路去程的值乘片段i 與之可接續(xù)的回程值乘片段不止一個時，為了最小化所需要的總機班數，需要保證乘務在外段停留時間越少越好， 即去程值乘片段i 與回程值乘片段j 的接續(xù)時間tij越小越好。 在滿足機車乘務員外段休息的時間標準下，基于先到先走原則，即先到達外段的去程值乘片段優(yōu)先接續(xù)最早出發(fā)的回程值乘片段，設計求解乘務交路問題的遍歷搜索算法，如圖2 所示。

圖2 基于先到先走原則的遍歷搜索算法流程圖Fig.2 Flowchart of the traversal searching algorithm based on “first come first serve” principle

步驟1 輸入值乘片段、接續(xù)時間矩陣Tij和機務段所在站；

步驟2 將出發(fā)地點為本段的值乘片段按退勤時間由早到晚排序，并組成集合S；

步驟3 取集合S 中的第一個值乘片段進行判斷；

步驟4 若片段x 的接續(xù)時間全為0，則按順序取下一片段重新判斷；若不是所有接續(xù)時間為0， 則找出值乘片段x 接續(xù)時間最小對應的值乘片段j，并將值乘片段x，j 加入待選集合Un中；

步驟5 判斷片段j 的到達地點是否為本段，若是， 則集合Un中的值乘片段按順序組為一個乘務交路；若否，則返回步驟4 繼續(xù)尋找片段j 接續(xù)時間最小的片段；

步驟6 直至集合S 中所有的片段都被遍歷，則生產乘務交路集合V。

3.2 遺傳算法設計

與旅行商問題相似， 乘務交路循環(huán)問題是NP難的組合優(yōu)化問題，當交路數目不是很多時，可采用精確算法求解；對于乘務交路數目較多、問題規(guī)模較大、方案編制較為復雜的情況，選擇啟發(fā)式算法有利于提高計算效率、減少計算時間，得到較優(yōu)的全局解[22]。 本文設計了遺傳算法對乘務交路循環(huán)問題進行求解，算法流程如下。

1） 編碼個體。一個乘務交路循環(huán)可直接以交路的次序來表示，例如包含6 個乘務交路的循環(huán)可表示為[3，4，1，2，5，6]，即循環(huán)從交路3 開始依次經歷交路4，1，2，5，6，然后重新值乘交路3，滿足所有交路均遍歷一次且僅一次。

2） 生成初始種群。隨機產生一組包含n 個個體的初始種群，每個個體代表一個可行解。

3） 計算適應度。乘務交路循環(huán)問題為最小化問題，可以取目標函數的倒數為適應度函數，符合適應度越高、選擇概率越大的要求。 考慮到最優(yōu)解可能有多個，為了使乘務交路的接續(xù)時間分布盡量均衡， 適應度函數同時考慮了接續(xù)時間方差的大小，具體如下

式中：F 為適應度函數；Z 為2.2 節(jié)中乘務交路循環(huán)問題的目標函數；V（tpq）為該乘務交路循環(huán)的接續(xù)時間方差；C1，C2為參數，根據Z 和V（tpq）的數量級來確定。

4） 選擇。 采用輪盤賭選擇法對種群進行選擇。取適應度的指數倍為計算依據，以擴大個體間的優(yōu)劣差距。

5） 交叉。 根據交叉概率Uc對個體交叉進行部分匹配交叉操作，保證形成的子代基因無沖突。

6） 變異。 根據變異概率Uv在變異個體中隨機產生2 個變異點，進行逆轉變異操作。

7） 取代。 經過選擇、交叉、變異后，產生的子代種群代替換原有父代種群，利用子代繼續(xù)重復步驟3）至步驟6），直至迭代次數N 大于500 或連續(xù)50代的適應度未改變，則停止迭代，最終得到的種群中適應度最好的個體為該問題的最優(yōu)解。

4 算例分析

選取某鐵路機務段為研究對象，該機務段管轄范圍如圖3 所示，包括6 個技術站，其中車站C 為貨運車間Ⅰ所在站，E 為貨運車間Ⅱ所在站，均為乘務基地。

圖3 某機務段的管轄范圍Fig.3 Jurisdiction of the locomotive depot

貨運車間Ⅰ負責A～E 的直達、直通和區(qū)段貨物列車牽引任務， 以C 站為支點實行半循環(huán)制式，上行列車機車乘務在C 站直通不換班，下行列車乘務在C 站換班。 貨運車間Ⅱ負責E～F 的直達、直通和區(qū)段貨物列車牽引任務，以E 站為支點，實行肩回制。 下面以貨運車間Ⅱ的乘務計劃為例具體說明。

1） 數據收集。根據《鐵路機車運用管理規(guī)則》規(guī)定，貨運機車乘務每月應安排1～2 次不少于48～72 h的大休時間； 在E 站的換班休息時間每次不少于16 h，即960 min；在F 站的換班休息時間每次不少于6 h，即360 min；月度大休時間最小值為48 h，即2 880 min。

2） 劃分值乘片段。 由于E～F 區(qū)段的最長運行時間不超過乘務最長工作時間標準， 可將該區(qū)段內每列車視為一個值乘片段。 假定出勤時間比列車出發(fā)時間提前70 min， 退勤比列車到達時間晚30 min，出退勤時間主要用于完成乘務報到、列車運行預告、接受派班、領取和歸還值乘物件、準備機車出庫、交接班等作業(yè)。 該區(qū)段的貨物列車信息和值乘片段信息見表1。

3） 求解乘務交路方案。 根據2.1 節(jié)值乘片段接續(xù)時間的定義，計算表1 值乘片段的接續(xù)時間矩陣Tij，見表2。

表1 貨運車間Ⅱ的列車信息和值乘片段信息Tab.1 Trains and crew duties of the railway freight workshop Ⅱ

表2 貨運車間Ⅱ的值乘片段間接續(xù)時間矩陣Tab.2 Connection time matrix of crew duty fragments of the railway freight workshop Ⅱmin

利用3.1 節(jié)基于先到先走的遍歷搜索算法，得到表3 中編號1～16 的交路方案。 由于貨物列車并非成對開行， 在求解時會存在一些值乘片段沒有回程片段接續(xù)的情況，無法形成完整的乘務交路。在實際工作中有兩種處理辦法：一是便乘，即對乘務員進行異地調度， 使其在不擔任值乘任務的情況下， 從上一結束車站乘車至下一任務的起始車站，一般會產生額外支出；二是調整值乘范圍，即安排這些乘務員繼乘其它區(qū)段的貨物列車牽引任務，但這對乘務員的業(yè)務能力要求較高，他們需要熟悉不同區(qū)段的線路情況甚至需要操縱不同類型的機車。

貨運車間Ⅱ還有4 個無法成對的值乘片段，根據便乘規(guī)則， 按基于先到先走原則的遍歷搜索算法，得到表3 中編號17～20 的交路方案。

4） 求解乘務交路循環(huán)方案。 根據2.2 節(jié)乘務交路接續(xù)時間的定義， 計算表3 中20 個乘務交路的接續(xù)時間矩陣Tpq，見表4。

表3 貨運車間Ⅱ的乘務交路集合Tab.3 Set of crew routing of the railway freight workshop Ⅱ

表4 貨運車間Ⅱ的乘務交路接續(xù)時間矩陣Tab.4 Connection time matrix of crew routing of the railway freight workshop Ⅱ min

在利用3.2 節(jié)遺傳算法求解乘務交路循環(huán)方案時，規(guī)定遺傳種群內個體個數n=50，適應度函數參數C1=106，C2=0.01， 并取適應度的10 次冪來計算累積概率， 以放大不同個體間的適應度值差距。 設交叉概率Uc=0.7， 變異概率Uv=0.005。遺傳算法適應度變化曲線如圖4 所示，當迭代次數N=364 時開始收斂。 乘務交路循環(huán)本段接續(xù)時間總和變化曲線如圖5 所示， 迭代至42 代開始本段接續(xù)時間總和TW趨于穩(wěn)定。 得到最 優(yōu) 乘 務 交 路 循 環(huán) 方 案 為：1 →20 →17 →14 →10→11→13→15→9→6→5→4→18→12→8 →2→16→7→3→19。

圖4 遺傳算法適應度變化曲線Fig.4 Fitness variation of genetic algorithm

圖5 乘務交路循環(huán)本段接續(xù)時間總和變化曲線Fig.5 Total connecting time variation at locomotive depot of the crew routing cycle

該循環(huán)中， 乘務值乘時間TZ為15 065 min，外段休息時間TB為11 407 min， 本段休息時間TW為25 213 min，乘務交路循環(huán)總時間T 為51 685 min。

根據勞動強度要求和月大休時間標準，可計算乘務交路循環(huán)方案的月循環(huán)次數和機班配備數。

式中：P 為機班配備數；β 為乘務交路循環(huán)每個月可循環(huán)的次數；取β1，β2中的較小值；C 為月平均工作時間最大值，根據《中華人民共和國勞動法》取176 h，即10 560 min；TM為剔除一次48 h 大休時間后的月時間換算值，一個月按30 d 計算，取40 320 min。計算得到，β＝β1＝0.701，完成該乘務交路循環(huán)所需要配備的機班43 個。

同樣的計算方法可得到貨運車間Ⅰ的乘務編制計劃，結果見表5，完成該乘務交路循環(huán)方案共需要配備124 個機班。

表5 貨運車間Ⅰ的乘務交路循環(huán)方案Tab.5 Result of crew routing cycle of the freight workshop Ⅰ

5） 結果分析。 通過分析上述算例的結果，得出以下結論。

①該模型能有效節(jié)省貨運機車乘務資源。利用優(yōu)化模型所計算得到的貨運機班數量相比原有人工經驗方案的要少，2 個車間分別有效節(jié)省了22.5%和17.6%的乘務資源，具體見表6。

表6 乘務交路編制結果對比Tab.6 Results contrast of crew scheduling

②該算法能有效提高乘務交路編制效率。上述算例利用本文所設計的基于先到先走遍歷搜素算法和遺傳算法，平均用時3.35 s 能求得該優(yōu)化模型的乘務交路計劃編制方案，且收斂性較好，相比目前我國鐵路機務段現場工作的人工經驗編制方法，編制效率和質量大大提升。

③單一交路循環(huán)能均衡乘務工作量并減少機班配備數。 本模型所采用的單一乘務交路循環(huán)方法，相比各乘務交路獨立循環(huán)或若干乘務交路成組循環(huán)的方法，能保證同一貨運車間的機車乘務員同屬一個循環(huán)組，組內值乘時長、休息時間、月大休時間相同，對于均衡各機車乘務員的工作量和收入水平具有實際意義。 同時，單一乘務交路循環(huán)方法能盡可能地減少乘務交路的接續(xù)時間，整體上減少總循環(huán)時長，可相應地減少乘務組的配備數。

5 結論

1） 提出了以乘務員非值乘時間最少為優(yōu)化目標的乘務交路計劃編制優(yōu)化模型，符合鐵路貨運機車乘務交路計劃編制問題的原理和流程，考慮了機班工時符合勞動管理規(guī)定、乘務交路的時間和空間約束，滿足乘務交路覆蓋所有車次。

2） 根據模型特點分別設計了基于先到先走原則遍歷搜索算法和遺傳算法，確定求解思路和具體步驟，能有效提高貨運部門乘務交路編制的效率。

3） 以某鐵路貨運機務段為算例，驗證了本文提出的模型和算法可以完整求解鐵路貨運乘務交路計劃方案，并且與人工經驗方法相比，有效減少了貨運機班的配備數，具有一定的實際意義。