楊文韜，周 強

（1. 中國鐵道科學研究院 運輸及經(jīng)濟研究所，北京 100081；2. 南昌鐵路局 運輸處，江西 南昌 330002）

動車組交路計劃是鐵路運輸部門根據(jù)中國鐵路總公司下達的列車運行計劃、動車組檢修里程及檢修基地能力等情況而編制的動車組運用計劃。該交路計劃決定動車組的使用數(shù)量，同時也是影響運營成本及運輸組織的重要因素。由于動車組交路計劃編制為非確定多項式 NP 問題，存在限制條件多、求解維度大等特點，至今還沒有比較滿意的算法。為此，在分析動車組交路計劃編制特點的基礎上，提出基于裝箱問題的動車組交路計劃編制模型及算法。

1 既有算法概述

目前對動車組交路計劃的研究主要基于以下 2種算法，分析其特點如下。

（1）基于先到先發(fā)接續(xù)算法[1-2]。該算法的思想是在大閉環(huán)內的動車組先到先發(fā)，然后按照交路的長度進行分割并調整，動車組每次接續(xù)的都是當前列車在其所在站所能接續(xù)的最早出發(fā)的列車。但是隨著列車的不斷接續(xù)，動車組到達某車站時，已經(jīng)不是最早到達該站的列車，其接續(xù)的列車可能應由在其之前到達的列車來接續(xù)，若調整時沒有考慮這一點，會導致該動車組在非動車段所在站長時間占用到發(fā)線。

（2）基于回溯算法的搜索算法。該算法以回溯為主要思想進行可行解的搜索，在每次得到不可行解時，回退前一步并更換選擇后繼續(xù)進行接續(xù)，直至完成所有交路。該算法存在以下不足：一是當搜索到后期遇到不滿足條件的解時，可能需要對已經(jīng)獲得的序列進行大量調整，降低算法效率；二是該算法同樣不能保證動車組交路在非動車段所在站得到滿意的接續(xù)。

2 列車接續(xù)方式分析

基于以上分析，針對動車段所在站和非動車段所在站分別制定接續(xù)方式的動車組交路提出計劃編制方法。按照編制方法將客運專線上的車站分為 2類：一是非動車段所在站，主要指中間站，一般只辦理旅客乘降作業(yè)或少量的始發(fā)終到列車；二是動車段所在站，是列車始發(fā)和終到的主要場所。針對這2類車站分別制定動車組接續(xù)方式如下。

（1）在非動車段(所) 所在站的接續(xù)方式?？瓦\專線的中間站到發(fā)線數(shù)量較少，始發(fā)、終到列車也較少，到達該站的列車如果不接續(xù)最早可接續(xù)的列車，將等待很長時間才會出現(xiàn)下一列可接續(xù)列車，造成動車組長時間占用到發(fā)線。由于中間站一般不配備備用動車組，當?shù)竭_列車發(fā)生晚點時，有可能導致接續(xù)的始發(fā)列車無動車組可用。為解決這樣的問題，有可能采用較早到達的列車在站停留一定時間來預備接續(xù)較晚出發(fā)的列車，該方法同樣也會造成列車長時間占用到發(fā)線。對于整個交路計劃而言，只要動車組數(shù)量不增加，則中間站的接續(xù)方式不會影響動車組的總接續(xù)時間。因此，在中間站是否考慮使用某列較早到達的動車組擔當備用任務，或在站停留多長時間，應根據(jù)具體情況由計劃編制人員來指定，其余動車組則應盡量采用先到先發(fā)的方式接續(xù)。

（2）在動車段(所) 所在站的接續(xù)方式。由于所有在非動車段(所) 所在站的始發(fā)、終到列車都已經(jīng)確定了接續(xù)關系，則可以將所有動車組視為從動車段(所) 始發(fā)，以動車段(所) 為終到站。為了使所接續(xù)的動車組交路滿足檢修標準的限制，對該問題建立基于裝箱問題的數(shù)學模型?？紤]到問題的復雜度，主要針對單基地的動車組交路計劃進行研究。

3 模型建立

3.1 問題描述

編制動車組交路計劃的主要目標是使用最少的動車組數(shù)來滿足所有運行線需要，并且保證動車組受到檢修時間和里程的約束[1-2]。一般來說，動車組檢修里程可以在一定范圍內波動，但是不能超過檢修標準的上限和下限。但在實際運用中，允許少量動車組的走行里程略大于或小于檢修標準的下限，同時為提高動車組的利用率設置相應的罰函數(shù)，其值隨動車組走行里程與檢修標準差值的增大而增大。

動車組交路計劃的上述特性與裝箱問題非常相似，即用最少的箱子完成所有物品的裝箱工作，并且所裝物品不能超過箱子的容量。為將動車組交路計劃的編制問題轉換為裝箱問題，如圖1 所示，對其進行如下處理。

圖1 動車組交路計劃編制問題向裝箱問題轉化

（1）將動車組交路計劃視為箱子，列車運行線視為待裝箱的片狀物品(設物品形狀與箱子的截面相同)。

（2）列車運行線之間的接續(xù)時間視為物品之間的保護層，保護層的最小厚度即為列車接續(xù)時間標準。

（3）列車必須按照時間方向接續(xù)，因此物品必須正放，而且物品底面代表列車在車站的出發(fā)時間，物品頂面代表列車在車站的到達時間。

3.2 定義函數(shù)

假定用來裝物品的箱子具有以下特性：箱子的容量標準為 C，容許所裝物品的總量在 C(1±α)之間浮動(α 為浮動系數(shù)，一般取 10%)。但當物品的總量超過C 時，對因超重給予一定的懲罰；而當物品總量沒有達到C，但大于浮動下限時，對所產生的箱子能力的浪費也給予一定的懲罰，當所有物品的總重未達到浮動下限時，應對其給予額外的懲罰，懲罰函數(shù)設計按下式計算。

式中：F(m) 為懲罰值；M 為一個很大的數(shù)；m 為物品的總量；k1為當重量介于容量標準與容量上限之間的懲罰系數(shù)；k2為當容量介于容量標準與容量下限之間的懲罰系數(shù)；k3為容量低于容量下限的額外懲罰。

3.3 建立模型

目前部分動車組運用計劃研究[3]將動車組運用的均衡性作為編制動車組交路計劃的第二個目標，該目標雖然會使各交路的累計走行里程與檢修標準的差值較均衡，但是會導致較多的交路達不到檢修標準。因此，不將交路的均衡性作為目標，而是考慮盡可能多的動車組交路具有較小的懲罰值，即接近或達到其檢修標準。由于考慮盡可能多的交路達到檢修標準，針對個別交路與檢修標準差距較大的情況，當列車發(fā)生晚點時可以將這些交路的動車組作為熱備車使用，從而減少備用車的數(shù)量。綜上所述，建立基于裝箱問題的動車組交路計劃編制問題的數(shù)學模型。

式中：z(y)min為最小化動車組的使用數(shù)量，即最小化所使用的箱子數(shù)；Kmax為最大化滿足罰值限制的交路數(shù)，即接近動車組檢修標準的動車組交路數(shù)量；⑴式表示交路中運行線的總走行公里小于交路標準；⑵式、⑶式表示所有的運行線都有且僅有 1 組動車組擔當；⑷式表示動車組接續(xù)時間大于接續(xù)時間標準；⑸式表示動車組進行一級修時的接續(xù)時間大于一級修時間標準。其中，yi為動車組序號；ωj為承擔運行任務的運行線里程；xij為j動車組擔當1條運行線i的任務；eij為j 動車組擔當i運行線任務后形成的車站間隔時間；Tjx為動車組在站最小接續(xù)時間；Tyjx為動車組在段一級修最小接續(xù)時間；Fbz為相關類型動車組檢修里程標準。

4 遺傳算法設計

4.1 遺傳表示

對于裝箱問題主要采用基于種群的表示方法。設有以下編碼方式表示的列車交路序列[3]，其中染色體的物品部分為 1435234，這標志著第1列車放入交路1，第2列和第 7 列車放入交路 4，第3 列和第6列車放入交路3，第4列車放入交路 5，第5列車放入交路2。染色體的群體部分僅表示交路，這里采用帶方括號的數(shù)字來表示交路，通過查詢交路，可以得到群體名表示含義：[1]={1}，[2]={5}，[3]={3，6}，[4]={2，7}，[5]={4}，如圖2所示。

圖2 列車交路序列

在圖2 中，群體表示有意義的積木塊，列車部分僅用于判定由哪些列車形成該群體，按照所屬解的期望質量來轉運信息。遺傳算法的關鍵之處是利用遺傳算子對染色體的群體部分進行操作。

4.2 遺傳算子

4.2.1 雜交

基于種群的雜交包含交路和列車 2個部分。因此雜交需要處理可變長度的染色體，該染色體用基因表示交路，步驟如下。

Step 1：隨機選擇 2個雜交位置，對每個父代選定雜交部分。

Step 2：將第一個父代雜交部分的內容插入到第二個父代的雜交位置之前。由于雜交對染色體的部分群體進行操作，即從第一個父代插入一些群體到第二個父代中。

Step 3：從產生的后代中的原有的交路中去掉所有重復出現(xiàn)的列車，使得這些列車原先的從屬關系讓位于“新”插入的交路，因而產生的后代中的某些群體發(fā)生了改變。

Step 4：如果需要，采用 FF(First Fit) 方法或BF 方法調整新產生的交路。

Step 5：改變 2個父代的角色并重新應用Step 1 — Step 4 生成第二個子代。

雜交過程圖如圖3 所示。

4.2.2 變異

圖3 雜交過程圖

變異是指隨機刪除 1個動車組交路，然后采用FF 啟發(fā)式方法進行修補的策略。從問題的形式可以看出，懲罰值小的交路接近檢修標準，懲罰值大的交路遠離檢修標準。當懲罰值大的交路被刪除時，其產生新解的變化較小，而當懲罰值小的交路被刪除時，產生新解的變化較大。因此，采用輪盤賭的方法選擇將要進行變異的染色體，染色體被選擇進行變異的概率與交路的懲罰值成反比。

4.2.3 適應值函數(shù)

基于裝箱問題的動車組交路計劃編制模型的首要目標是使動車組的使用數(shù)量最小化，在降低設備成本的同時最大化接近檢修標準的交路數(shù)量。建立適應值函數(shù)計算公式為

式中：N 為解中使用的動車組數(shù)量；Fi(m) 為第 i個交路的懲罰值；Fbz為可接受的罰函數(shù)標準；k 為對接近檢修標準的交路的重視程度，常數(shù)(k>1)，k 值越大，接近檢修標準的交路比一般的交路受到的重視就越大，此處 k 取 2。

4.2.4 初始解的構造

裝箱問題有 2種產生初始種群的方法：隨機方法和啟發(fā)式方法。隨機產生初始解雖然簡單，但解的性能不能保證，用 FF 啟發(fā)式方法產生裝箱問題所有的個體也比較容易，同時解的性能與隨機產生相比有較大提高。因此，主要采用 FF 啟發(fā)式方法生成初始解。

5 實例分析

動車組交路計劃編制的目標是最小化動車組的使用數(shù)量，從而降低設備成本，現(xiàn)以南昌鐵路局杭深線福州南動車所動車組所運行的實際交路為實例進行模擬對比。

5.1 杭深線福州南動車所設備及運用情況

福州南動車所設有動車組檢查庫和存車線，配屬 CRH1A 動車組 23 組(圖定運用動車 19 組，熱備車 1 組，檢備車 3 組)，CRH1E 動車組7組(圖定運用動車6組，檢備車 1 組)。每晚動車組入庫一級修18～19 組。在實際運營中，福州南動車所每日使用26 組動車組開行跨局至上海虹橋站、杭州南站和南昌鐵路局管內廈門、龍巖站的動車組列車共48對，總運行距離38250km，平均單組動車組運行距離1530km。

5.2 裝箱模型計算

模擬程序采用 VS2008 平臺下的 Visual C++ 編程語言，按照遺傳算法定義染色體和遺傳算子并構造初始解，根據(jù)適應值函數(shù)進行迭代求解。在迭代過程中將交叉概率設置為 0.5，變異概率設置為0.2，經(jīng)過 20次迭代后發(fā)現(xiàn)最優(yōu)解已經(jīng)沒有變化，所以選擇迭代終止。動車組實際運營交路與計算機模擬改進交路對比分析如表1 所示。

由于福州南動車所動車組配屬數(shù)量及檢修能力有限，并且部分開行至上海虹橋、杭州南站的車次運行距離較長。因此，現(xiàn)場實際運用和計算機模擬2個方案在動車組使用數(shù)量上沒有差別，均為 19 組。在單組動車組運用里程和時間上二者也較為接近，僅在確認列車的開行和最早、最晚 1 趟車次的安排上有較小差別(如 D3109 和 D6257)。雖然計算機模擬結果沒有顯示動車組運用數(shù)量上的節(jié)省，但是驗證了裝箱模型的可行性及遺傳算法求解的有效性，模擬迭代產生的動車組運用效率指標分析如表2所示。

表1 實際交路與模擬交路對比表

表2 動車組模擬交路運用效率指標分析表

通過計算機模擬，得出動車組運行距離總計為31 102km，平均單組動車組運行距離為 1 636km，計算機模擬動車組的運行效率略高。從與實際交路完全相同的動車組計算機模擬運用效率指標來看，部分動車組利用效率較低，非生產時間超過 500min，等待服務和檢修的時間也都接近400min，其中運用效率指標最差的 3 組動車組分別是 D3207(上海虹橋 11:05 — 廈門北19:58) 接續(xù)D6256(廈門北 21:13—福州22:55)、D3203(上海虹橋10:22—廈門19:19) 接續(xù) D6252(廈門19:47—福州21:55) 和 D3209(上海虹橋 10:27—廈門北19:40) 接續(xù) D6250(廈門北20:00—福州21:45)，造成該狀況的主要原因是沒有從整個路網(wǎng)的角度考慮動車組的運用問題。由于動車組的配屬問題導致其跨局服務頻率較低，而過早入段或過晚出段也極大地影響了動車組的運用效率。建議從全路動車組運用的角度進行優(yōu)化，將上海虹橋站早上 10 點后的動車組發(fā)車時間提前 2～3h，這樣下午到達廈門的車底還可以套跑南昌鐵路局管內的短交路，而晚上 20 點前到達上海虹橋站的車底也可以繼續(xù)套跑上海鐵路局管內的短交路，從而能夠最大程度優(yōu)化動車組使用效率。

6 研究結論

動車組交路計劃是典型的非確定多項式 NP 問題，獲得其最優(yōu)解比較困難。通過提出在編制動車組交路計劃時區(qū)分考慮動車段所在站和非所在站，采用裝箱問題進行建模及采用遺傳算法進行求解。由于現(xiàn)場數(shù)據(jù)規(guī)模有限，以杭深線上的福州南動車段交路為例進行了計算機模擬計算，如果求解對象是覆蓋若干條線路及地區(qū)樞紐站的小規(guī)模路網(wǎng)，則其動車組的運用條件會更加復雜，求解空間的維度也會更大，從而對算法的求解效率和收斂速度提出更高的要求。因此，如何加入更多的實際限制條件對模型進行完善并求解還有待進一步研究。

[1]趙 鵬，富井規(guī)雄. 動車組運用計劃及其編制算法[J]. 鐵道學報，2003，25(6)：1-7.

[2]趙 鵬，富井規(guī)雄. 基于路段交換的多基地動車組運用計劃的編制算法[J]. 鐵道學報，2004，26(2)：7-11.

[3]吳莊勝，趙 清，王伯銘. 高速列車運用檢修及動車段的設計研究[J]. 西南交通大學學報：自然科學版，1997，32(2)：277-282.