檢修條件下動車組運(yùn)用計(jì)劃編制研究

安 琪，王建英

（1.中國鐵道科學(xué)研究院 研究生部，北京 100081；2.中國鐵道科學(xué)研究院 通信信號研究所，北京 100081）

動車組檢修是保障列車運(yùn)行安全的重要手段，優(yōu)化動車組的運(yùn)用和檢修計(jì)劃對于提高客運(yùn)專線運(yùn)輸生產(chǎn)效益具有重要意義。目前，提高動車組使用效率是各國學(xué)者普遍關(guān)注的問題，我國也對動車組運(yùn)用問題進(jìn)行了大量研究，如各種條件下動車組運(yùn)用計(jì)劃編制的優(yōu)化模型[1-3]，模擬退火算法在解決 TSP問題中的具體應(yīng)用[4]。還有學(xué)者在研究解決商旅問題幾種算法的比較中，分析了蟻群算法、遺傳算法和模擬退火算法在解決問題時的優(yōu)缺點(diǎn)[5]。因此，在考慮這3種算法的不同適用范圍的情況下，通過采用模擬退火算法結(jié)合有向圖的方法，研究檢修條件下根據(jù)接續(xù)時間和接續(xù)地點(diǎn)的優(yōu)化模型，從而實(shí)現(xiàn)動車組運(yùn)用計(jì)劃的編制。

1 模型的建立

1.1 問題的描述

采用有向圖 G＝(C，L) 表示動車組的運(yùn)用網(wǎng)絡(luò)，如圖1所示。

圖1 有向圖 G＝(C，L)表示動車組的運(yùn)用網(wǎng)絡(luò)

C＝{cis∣cis＝(tif，ξif，tid，ξid)}∪{ckr∣ckr＝(τkf，ζk，τkd)}是點(diǎn)的集合，包含cis和ckr兩部分。其中，點(diǎn)cis對應(yīng)給定運(yùn)行圖中的運(yùn)行線 i，包括運(yùn)行線的始發(fā)時刻 tif、終到時刻tid、始發(fā)車站 ξif和終到車站 ξid；點(diǎn)ckr對應(yīng)動車組的一項(xiàng)檢修作業(yè) k，包括檢修點(diǎn) ζk、從車站去檢修點(diǎn)的離站時刻τkf和檢修完畢后從檢修點(diǎn)返回車站的到站時刻τkd。

式中：τid＝tid＋T作業(yè)＋T走行，T作業(yè)為擔(dān)當(dāng)運(yùn)行線i任務(wù)后在車站必要的作業(yè)時間；τif＝τid＋τ標(biāo)＋T走行，T走行為出入檢修點(diǎn)的走行時間。

1.2 約束條件

1.2.1 檢修條件

一級修條件 X1：

二級修條件 X2：

三級修條件 X3：

如果動車組 i 滿足上述檢修條件 X2或X3，說明動車組應(yīng)該檢修，如果當(dāng)時正處在具有二、三級檢修能力的車站，則應(yīng)立即進(jìn)行檢修；否則，下次運(yùn)行的終點(diǎn)站必須為具有二、三級檢修能力的車站。如果動車組i滿足條件 X1，則應(yīng)在動車組當(dāng)前所處車站進(jìn)行檢修。3種檢修能力的判斷順序依次為X3、X2、X1。

1.2.2 接續(xù)條件

運(yùn)行接續(xù)條件 X4：

式中：t標(biāo)表示動車組連續(xù)運(yùn)行的標(biāo)準(zhǔn)接續(xù)時間；tjf表示運(yùn)行線j 下一次可接續(xù)運(yùn)行的最早時刻；tid表示運(yùn)行線 i的終到時刻。

檢修接續(xù)條件 X5：

式中：τ標(biāo)表示進(jìn)行第 k 級動車組檢修的標(biāo)準(zhǔn)持續(xù)時間。

1.2.3 運(yùn)用條件

始發(fā)車站運(yùn)用條件 X6：

式中：ξid表示動車組 i 當(dāng)前所位于的車站；ξjf表示運(yùn)行圖中第j條運(yùn)行線的始發(fā)車站。

1.3 模型優(yōu)化

在保證完成列車運(yùn)行計(jì)劃規(guī)定的運(yùn)輸任務(wù)和進(jìn)行必要檢修作業(yè)的情況下，以投入動車組數(shù)量最少為目標(biāo)，建立動車組周轉(zhuǎn)優(yōu)化數(shù)學(xué)模型。在一個編制周期內(nèi)，動車組數(shù)量最少可以用動車組周轉(zhuǎn)接續(xù)時間總和最小來表達(dá)，因此，考慮檢修條件下的動車組周轉(zhuǎn)優(yōu)化模型可表示為：

式中：T 為動車組周轉(zhuǎn)接續(xù)時間總和，包含動車組擔(dān)當(dāng)運(yùn)行線的接續(xù)時間和必要的檢修作業(yè)時間；Nd為給定運(yùn)輸任務(wù)中到達(dá)的動車組總數(shù)；Nf為給定運(yùn)輸任務(wù)中出發(fā)的動車組總數(shù)；M 為可能的檢修作業(yè)數(shù)。

該約束表示對一條未被擔(dān)當(dāng)?shù)倪\(yùn)行線j，或者由擔(dān)當(dāng)運(yùn)行線 i 的動車組擔(dān)當(dāng)，或者由檢修后返回車站的動車組擔(dān)當(dāng)。

該約束表示擔(dān)當(dāng)運(yùn)行線 i 的動車組，或者繼續(xù)擔(dān)當(dāng)運(yùn)行線j 的任務(wù)，或者去檢修地進(jìn)行檢修作業(yè)。

該約束表示對于檢修作業(yè) k，只能安排一組動車組，也可以不安排動車組，因此，檢修弧屬于非強(qiáng)制性的。

該約束表示完成檢修作業(yè) k 的動車組，只能擔(dān)當(dāng)一條運(yùn)行線任務(wù)，也可以暫不擔(dān)當(dāng)運(yùn)行線任務(wù)。

xik為動車組擔(dān)當(dāng)運(yùn)行線 i 后是否進(jìn)行檢修作業(yè) k的控制變量，其值為：當(dāng)滿足約束條件 X1、 X2、X3或同時滿足X1、 X2、X3時，xik＝1；否則，xik＝0。

xij為動車組擔(dān)當(dāng)運(yùn)行線 i 后是否接續(xù)運(yùn)行線j 的控制變量，其值為：當(dāng)不滿足約束條件 X1、 X2、X3，且滿足 X4、 X6時，xij＝1；否則，xij＝0。

xkj為動車組完成檢修作業(yè) k 是否接續(xù)運(yùn)行線j的控制變量，其值為：當(dāng)滿足約束條件 X5時，xkj＝1；否則，xkj＝0。

2 算法求解

模擬退火算法 (Simulated Annealing，SA) 是基于所求解問題的求解過程與熔化物體退火過程的相似性進(jìn)行的，其中 Metropolis 準(zhǔn)則是 SA 算法收斂于全局最優(yōu)解的關(guān)鍵，該準(zhǔn)則以一定的概率接受惡化解，這樣就使算法跳離局部最優(yōu)的陷阱。將固體內(nèi)能 E 模擬為動車組周轉(zhuǎn)接續(xù)總時間 T，溫度 t 演化成動車組數(shù)量 N，運(yùn)行線之間的接續(xù)關(guān)系用 Metropolis 準(zhǔn)則來描述。模擬退火算法的詳細(xì)步驟如下。

步驟 1：初始化。①輸入列車運(yùn)行計(jì)劃，包括動車組始發(fā)時刻 tif、始發(fā)車站 ξif、終到時刻 tid、終到車站 ξid。②輸入檢修作業(yè)時間標(biāo)準(zhǔn)，包括往返走行時間T走行、在車站必要的作業(yè)時間 T作業(yè)。③輸入基本參數(shù)，如 L1、L2、L3、t標(biāo)、τ標(biāo)等。④根據(jù)運(yùn)行接續(xù)條件 X4和始發(fā)車站運(yùn)用條件 X6，得到所有具有接續(xù)可能的交路數(shù)量 JN。⑤設(shè)置動車組下降量 η，動車組最少數(shù)量ZN 和評價值 δ。

步驟 2：生成初始解。初始動車組周轉(zhuǎn)接續(xù)總時間 T(0)＝T0，動車組初始數(shù)量為 N。

步驟 3：根據(jù)檢修條件X1、X2和 X3開啟或關(guān)閉控制變量 xik。

步驟 4：根據(jù)接續(xù)條件和運(yùn)用條件 X4、X5和 X6開啟或關(guān)閉控制變量 xij和xkj，并根據(jù)控制變量狀態(tài)，調(diào)用 Metropolis 抽樣算法。返回狀態(tài) T 作為本算法的當(dāng)前解，Ti＝T。

步驟 5：按照下降量 η 減少動車組的數(shù)量，即 N＝Ni+1＝Ni－η，其中 Ni+1＜Ni，i＝i＋1。

步驟 6：判斷是否 N＞ZN，如果是，轉(zhuǎn)至步驟2，繼續(xù)進(jìn)行任務(wù)；否則，得到不同動車組數(shù)量下最優(yōu)的周轉(zhuǎn)接續(xù)時間的目標(biāo)值 T。

步驟 7：對得到的不同動車組數(shù)量下周轉(zhuǎn)接續(xù)時間進(jìn)行統(tǒng)計(jì)和比較。

Metropolis 抽樣算法描述如下。

（1）令 k＝0 時，當(dāng)前解 T(0)＝T，在一定動車組數(shù)量 N下，進(jìn)行以下各步操作。

（2）按照運(yùn)行圖采用2-opt運(yùn)算得到 L種不同接續(xù)方案下的周轉(zhuǎn)接續(xù)時間，并把這些時間作為當(dāng)前解 T (k) 的所處狀態(tài) T的一個臨域子集 N (T(k))＋T，從中隨機(jī)得到一個新狀態(tài)T (k＋1) 作為下一個候選解，計(jì)算時間之差Δt＝|1－T (k) / T (k＋1)|。

（3）如果Δt＜δ，則接受 T (k) 作為下一個當(dāng)前解，否則，以概率 exp (－Δt/N) 接受 T (k＋1) 作為下一個當(dāng)前解。

（4）k＝k＋1，如果 k＜L，則轉(zhuǎn)到（2）繼續(xù)進(jìn)行；否則，繼續(xù)下一步。

（5）返回得到的一定動車組數(shù)量下的周轉(zhuǎn)接續(xù)時間 T(i)，結(jié)束。

3 仿真應(yīng)用

以目前已有武廣高速鐵路資料為基礎(chǔ)，編制相應(yīng)的列車運(yùn)行圖，采用本文建立的優(yōu)化模型和求解算法對所編制的運(yùn)行圖進(jìn)行動車組運(yùn)用計(jì)劃優(yōu)化。動車組檢修條件[6]為每走行 30 000 km 進(jìn)行一次一級修，需耗時 4 h，最短立刻折返時間為 24 min。利用高速鐵路國家工程實(shí)驗(yàn)室——運(yùn)營調(diào)度仿真實(shí)驗(yàn)室進(jìn)行模擬仿真，在仿真過程中，通過改變動車組的運(yùn)用數(shù)量，得到動車組平均利用率。其仿真結(jié)果如表1和圖2所示。

由表1可知，方案4為最優(yōu)方案，說明在給定列車運(yùn)行圖后，采用該模型和求解算法，通過不斷減少動車組的使用數(shù)量能夠得到優(yōu)化的動車組運(yùn)用計(jì)劃。由圖2可知，隨著動車組運(yùn)用數(shù)量的等額減少，動車組平均利用率的提高幅度變小。

表1 不同動車組數(shù)量和接續(xù)方案下的動車組平均利用率

圖2 動車組平均在線運(yùn)行時間和運(yùn)用數(shù)量之間的關(guān)系

4 結(jié)束語

通過研究高速鐵路動車組運(yùn)用的一般方法，重點(diǎn)了討論動車組運(yùn)用計(jì)劃編制理論。以動車組接續(xù)時間、接續(xù)地點(diǎn)、動車組定檢里程為約束條件，以需要動車組數(shù)量最少和總的動車組周轉(zhuǎn)接續(xù)時間最短為目標(biāo)函數(shù)，建立動車組運(yùn)用計(jì)劃的數(shù)學(xué)模型，采用模擬退火算法進(jìn)行求解，給出了動車組運(yùn)用計(jì)劃編制算法流程，為實(shí)現(xiàn)動車組運(yùn)用計(jì)劃的自動編制提供一種可供選擇的技術(shù)。

[1]張才春，花 偉，陳建華. 雙修制下的動車組運(yùn)用計(jì)劃編制研究[J]. 鐵道學(xué)報(bào)，2010，32(3)：16-19.

[2]耿敬春. 客運(yùn)專線動車組運(yùn)用計(jì)劃編制優(yōu)化研究[J]. 西華大學(xué)學(xué)報(bào)(自然科學(xué)版)，2008，27(6)：83-86.

[3]張才春，陳建華，花 偉. 基于不同檢修能力的動車組運(yùn)用計(jì)劃研究[J]. 中國鐵道科學(xué)，2010，31(5)：130-133.

[4]馮 劍，岳 琪. 模擬退火算法求解TSP問題[J]. 深林工程，2008，24(1)：94-96.

[5]李 敏，吳 浪，張開碧. 求解旅行商問題的幾種算法的比較研究[J]. 重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版)，2008，20(5)：624-626.

[6]中華人民共和國鐵道部. 新建時速300～350公里客運(yùn)專線鐵路設(shè)計(jì)暫行規(guī)定[Z]. 北京：中國鐵道出版社，2007.