楊文韜，周 強(qiáng)

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

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

1 既有算法概述

目前對(duì)動(dòng)車組交路計(jì)劃的研究主要基于以下 2種算法，分析其特點(diǎn)如下。

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

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

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

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

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

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

3 模型建立

3.1 問題描述

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

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

圖1 動(dòng)車組交路計(jì)劃編制問題向裝箱問題轉(zhuǎn)化

（1）將動(dòng)車組交路計(jì)劃視為箱子，列車運(yùn)行線視為待裝箱的片狀物品(設(shè)物品形狀與箱子的截面相同)。

（2）列車運(yùn)行線之間的接續(xù)時(shí)間視為物品之間的保護(hù)層，保護(hù)層的最小厚度即為列車接續(xù)時(shí)間標(biāo)準(zhǔn)。

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

3.2 定義函數(shù)

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

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

3.3 建立模型

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

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

4 遺傳算法設(shè)計(jì)

4.1 遺傳表示

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

圖2 列車交路序列

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

4.2 遺傳算子

4.2.1 雜交

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

Step 1：隨機(jī)選擇 2個(gè)雜交位置，對(duì)每個(gè)父代選定雜交部分。

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

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

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

Step 5：改變 2個(gè)父代的角色并重新應(yīng)用Step 1 — Step 4 生成第二個(gè)子代。

雜交過程圖如圖3 所示。

4.2.2 變異

圖3 雜交過程圖

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

4.2.3 適應(yīng)值函數(shù)

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

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

4.2.4 初始解的構(gòu)造

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

5 實(shí)例分析

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

5.1 杭深線福州南動(dòng)車所設(shè)備及運(yùn)用情況

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

5.2 裝箱模型計(jì)算

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

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

表1 實(shí)際交路與模擬交路對(duì)比表

表2 動(dòng)車組模擬交路運(yùn)用效率指標(biāo)分析表

通過計(jì)算機(jī)模擬，得出動(dòng)車組運(yùn)行距離總計(jì)為31 102km，平均單組動(dòng)車組運(yùn)行距離為 1 636km，計(jì)算機(jī)模擬動(dòng)車組的運(yùn)行效率略高。從與實(shí)際交路完全相同的動(dòng)車組計(jì)算機(jī)模擬運(yùn)用效率指標(biāo)來看，部分動(dòng)車組利用效率較低，非生產(chǎn)時(shí)間超過 500min，等待服務(wù)和檢修的時(shí)間也都接近400min，其中運(yùn)用效率指標(biāo)最差的 3 組動(dòng)車組分別是 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)，造成該狀況的主要原因是沒有從整個(gè)路網(wǎng)的角度考慮動(dòng)車組的運(yùn)用問題。由于動(dòng)車組的配屬問題導(dǎo)致其跨局服務(wù)頻率較低，而過早入段或過晚出段也極大地影響了動(dòng)車組的運(yùn)用效率。建議從全路動(dòng)車組運(yùn)用的角度進(jìn)行優(yōu)化，將上海虹橋站早上 10 點(diǎn)后的動(dòng)車組發(fā)車時(shí)間提前 2～3h，這樣下午到達(dá)廈門的車底還可以套跑南昌鐵路局管內(nèi)的短交路，而晚上 20 點(diǎn)前到達(dá)上海虹橋站的車底也可以繼續(xù)套跑上海鐵路局管內(nèi)的短交路，從而能夠最大程度優(yōu)化動(dòng)車組使用效率。

6 研究結(jié)論

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

[1]趙 鵬，富井規(guī)雄. 動(dòng)車組運(yùn)用計(jì)劃及其編制算法[J]. 鐵道學(xué)報(bào)，2003，25(6)：1-7.

[2]趙 鵬，富井規(guī)雄. 基于路段交換的多基地動(dòng)車組運(yùn)用計(jì)劃的編制算法[J]. 鐵道學(xué)報(bào)，2004，26(2)：7-11.

[3]吳莊勝，趙 清，王伯銘. 高速列車運(yùn)用檢修及動(dòng)車段的設(shè)計(jì)研究[J]. 西南交通大學(xué)學(xué)報(bào)：自然科學(xué)版，1997，32(2)：277-282.