安 琪，王建英

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

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

1 模型的建立

1.1 問(wèn)題的描述

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

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

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

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

1.2 約束條件

1.2.1 檢修條件

一級(jí)修條件 X1：

二級(jí)修條件 X2：

三級(jí)修條件 X3：

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

1.2.2 接續(xù)條件

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

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

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

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

1.2.3 運(yùn)用條件

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

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

1.3 模型優(yōu)化

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

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

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

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

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

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

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

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

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

2 算法求解

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

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

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

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

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

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

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

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

Metropolis 抽樣算法描述如下。

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

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

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

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

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

3 仿真應(yīng)用

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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