基于專家系統(tǒng)的網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃的編制

陳　然，周磊山，樂逸祥，路　超，周　宇

(北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京　100044)

隨著高速鐵路新線的開通，動(dòng)車組的使用數(shù)量逐漸增大，但動(dòng)車組的成本高昂，如何安全、經(jīng)濟(jì)地運(yùn)用動(dòng)車組越來越受到人們的關(guān)注。

國外學(xué)者對(duì)動(dòng)車組或機(jī)車運(yùn)用進(jìn)行了研究[1-6]，主要關(guān)注在為旅客提供足夠多的客車座席以及保證列車足夠牽引動(dòng)力情況下，盡量減少客車和機(jī)車的使用數(shù)量。但國外鐵路線路里程短、客流量較少、運(yùn)行線結(jié)構(gòu)規(guī)律性明顯，而且旅客列車非固定編組，可以通過重聯(lián)、分解、連掛、無動(dòng)力回送等方式增減編組輛數(shù)或機(jī)車數(shù)以適應(yīng)客流變化，動(dòng)車組運(yùn)用情況與國內(nèi)有較大不同，因此借鑒性較少。

國內(nèi)專家重點(diǎn)研究動(dòng)車組的交路計(jì)劃、檢修計(jì)劃和分配計(jì)劃，目的是減少動(dòng)車組使用數(shù)量或提高動(dòng)車組使用效率。王瑩等研究二級(jí)修以上的動(dòng)車組檢修計(jì)劃，以檢修前累計(jì)運(yùn)行里程最大為目標(biāo)，通過構(gòu)建接續(xù)網(wǎng)絡(luò)建立數(shù)學(xué)模型，以廣深線為例運(yùn)用列生成算法求解[7]；在后續(xù)的研究[8]中，將動(dòng)車組周轉(zhuǎn)計(jì)劃編制問題在列車運(yùn)行圖可作微調(diào)的前提下進(jìn)一步優(yōu)化，實(shí)現(xiàn)動(dòng)車組運(yùn)用計(jì)劃與運(yùn)行圖編制優(yōu)化的協(xié)調(diào)。趙鵬等以京滬高鐵為實(shí)例，利用局域搜索產(chǎn)生單個(gè)動(dòng)車基地的運(yùn)用計(jì)劃初始解，再通過列車分組、路段交換形成多動(dòng)車基地下的動(dòng)車組運(yùn)用計(jì)劃[9]。王忠凱等以動(dòng)車組運(yùn)用交路與檢修規(guī)程為約束，以減少動(dòng)車組數(shù)和檢修成本為目標(biāo)，設(shè)計(jì)了運(yùn)用計(jì)劃與檢修計(jì)劃一體化編制的整數(shù)規(guī)劃模型，先求解約束條件生成可行的運(yùn)用路徑集合，再以此為基礎(chǔ)設(shè)計(jì)模擬退火算法[10]。史峰等為描述動(dòng)車組運(yùn)用均勻性，以環(huán)形排列為動(dòng)車交路建立模型，將檢修約束以罰值函數(shù)代入目標(biāo)函數(shù)用基于三交換法的模擬退火算法求解[11]；在后續(xù)的研究中[12]，建立以車站作業(yè)時(shí)間、動(dòng)車組接續(xù)時(shí)間和到發(fā)線數(shù)為約束條件,以列車旅行時(shí)間和動(dòng)車組接續(xù)時(shí)間最小化為目標(biāo)函數(shù)的綜合優(yōu)化模型，將動(dòng)車組周轉(zhuǎn)、到發(fā)線運(yùn)用與運(yùn)行圖整體優(yōu)化。林柏梁等研究了固定區(qū)段和不固定區(qū)段動(dòng)車組二級(jí)檢修特點(diǎn)，建立了相關(guān)模型[13]。李華等以設(shè)計(jì)接續(xù)邊的累計(jì)時(shí)間和里程為約束建立整數(shù)規(guī)劃模型，以武廣線為例引入動(dòng)車組運(yùn)用最優(yōu)接續(xù)網(wǎng)絡(luò)為粒子飛行參考，運(yùn)用粒子群算法求解[14]。張才春提出了基于簇式運(yùn)用方式和動(dòng)態(tài)備用方式編制動(dòng)車組運(yùn)用計(jì)劃，將動(dòng)車組運(yùn)用計(jì)劃優(yōu)化問題轉(zhuǎn)化為多個(gè)小周期內(nèi)的優(yōu)化問題并使用蟻群算法求解[15]。這些研究多數(shù)使用智能算法求解單條線路的動(dòng)車組運(yùn)用計(jì)劃，在列車網(wǎng)絡(luò)化運(yùn)行背景下可能會(huì)出現(xiàn)不適應(yīng)的情況。

本文借鑒鐵路現(xiàn)場(chǎng)使用的機(jī)車周轉(zhuǎn)圖，突出網(wǎng)絡(luò)化運(yùn)行下動(dòng)車的累計(jì)運(yùn)行里程和時(shí)間，以及需要擔(dān)當(dāng)?shù)母鳁l運(yùn)行線的里程和時(shí)間，提出網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃圖。以動(dòng)車組累計(jì)運(yùn)行里程和時(shí)間、動(dòng)車段(所)檢修能力、接續(xù)作業(yè)時(shí)間與檢修作業(yè)時(shí)間為約束條件，以動(dòng)車組運(yùn)用數(shù)量最少為最優(yōu)目標(biāo)、檢修次數(shù)最少為次優(yōu)目標(biāo)，建立動(dòng)車組運(yùn)用計(jì)劃雙目標(biāo)規(guī)劃優(yōu)化模型；設(shè)計(jì)基于專家系統(tǒng)的最大最小蟻群算法進(jìn)行求解。以含有6條高速鐵路線的路網(wǎng)為例，求解動(dòng)車組運(yùn)用計(jì)劃。

1　問題描述

1.1　網(wǎng)絡(luò)化運(yùn)行下動(dòng)車組運(yùn)用計(jì)劃的編制

隨著高速鐵路新線的開通，高速鐵路線路逐漸形成網(wǎng)絡(luò)布局，動(dòng)車組在網(wǎng)狀線路間運(yùn)行，大量跨線列車開行導(dǎo)致運(yùn)行圖結(jié)構(gòu)更復(fù)雜，更多不同類型的動(dòng)車組運(yùn)行在同一路網(wǎng)上而導(dǎo)致動(dòng)車組運(yùn)用計(jì)劃編制也更困難。然而，動(dòng)車組運(yùn)用問題的可優(yōu)化范圍也變得更大。主要表現(xiàn)在：動(dòng)車組不固定區(qū)段運(yùn)行，將有更多的運(yùn)行線接續(xù)組合，適當(dāng)選擇接續(xù)運(yùn)行線(如采用大小交路套跑模式)可以充分運(yùn)用動(dòng)車組；適當(dāng)選擇檢修地點(diǎn)和檢修時(shí)機(jī)，讓動(dòng)車組盡量運(yùn)行到檢修里程的上界，在檢修次數(shù)不變的前提下多擔(dān)當(dāng)運(yùn)行任務(wù)。例如圖1所示，按線路分別編制動(dòng)車組運(yùn)用計(jì)劃需要4列動(dòng)車組，若按圖2網(wǎng)絡(luò)化方式編制動(dòng)車組運(yùn)用計(jì)劃，可以讓動(dòng)車組擔(dān)當(dāng)更多線路的運(yùn)輸任務(wù)，雖增加了動(dòng)車組運(yùn)行里程，但可節(jié)省2列動(dòng)車組；由圖3(圖中數(shù)字表示運(yùn)行線里程)也可知，適當(dāng)選擇檢修作業(yè)的時(shí)間和地點(diǎn)，同樣能夠達(dá)到充分運(yùn)用動(dòng)車組、減少檢修次數(shù)的目的?？傊?，從路網(wǎng)角度求解動(dòng)車組運(yùn)用計(jì)劃，可以得到更多初始解空間，搜索到更優(yōu)解，最終使全局優(yōu)化效果大于各線優(yōu)化效果之和[16]。

圖1　按線路分別編制動(dòng)車組運(yùn)用計(jì)劃

圖2　按路網(wǎng)編制動(dòng)車組運(yùn)用計(jì)劃

圖3　適當(dāng)選擇檢修時(shí)機(jī)和地點(diǎn)節(jié)省用車

1.2　專家系統(tǒng)及其基于專家系統(tǒng)的改進(jìn)蟻群算法

專家系統(tǒng)擁有某專業(yè)領(lǐng)域內(nèi)大量的專家級(jí)知識(shí)，通過運(yùn)用這些知識(shí)進(jìn)行判斷及推理，可以解決該領(lǐng)域內(nèi)的復(fù)雜問題。專家系統(tǒng)主要包含知識(shí)庫和推理機(jī)兩部分，其中，知識(shí)庫存儲(chǔ)專家的經(jīng)驗(yàn)知識(shí)，推理機(jī)負(fù)責(zé)響應(yīng)用戶的查詢[17]。

成網(wǎng)條件下動(dòng)車組運(yùn)用計(jì)劃編制優(yōu)化模型的求解較復(fù)雜，智能算法已經(jīng)不能滿足模型求解的質(zhì)量和速度，因此引入專家系統(tǒng)，設(shè)計(jì)基于專家系統(tǒng)的改進(jìn)蟻群算法。該算法的原理為：若專家系統(tǒng)的知識(shí)庫中存在相應(yīng)的經(jīng)驗(yàn)知識(shí)，則采用專家系統(tǒng)求解，否則采用蟻群算法求解；在編制完成動(dòng)車組運(yùn)用計(jì)劃后，對(duì)編制過程進(jìn)行總結(jié)，得到新的知識(shí)經(jīng)驗(yàn)，并將其加入知識(shí)庫，以豐富知識(shí)庫。該算法的流程如圖4所示。

圖4　基于專家系統(tǒng)的改進(jìn)蟻群算法的流程圖

2　網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃圖的提出

既有動(dòng)車組交路計(jì)劃圖的結(jié)構(gòu)與運(yùn)行圖結(jié)構(gòu)較為相似，展示了單條線路的列車運(yùn)行線信息，以及運(yùn)行線的接續(xù)關(guān)系?？紤]到在編制動(dòng)車組運(yùn)用計(jì)劃過程中，編制人員更加關(guān)注整個(gè)路網(wǎng)上動(dòng)車組運(yùn)行里程或時(shí)間是否超過檢修規(guī)定，能否繼續(xù)擔(dān)當(dāng)下次運(yùn)行線任務(wù)。因此，基于既有的動(dòng)車組運(yùn)用計(jì)劃圖，提出網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃圖。網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃圖包括：運(yùn)行線車次、擔(dān)當(dāng)該車次的動(dòng)車組車號(hào)、到發(fā)時(shí)刻、到發(fā)站、運(yùn)行里程、運(yùn)行時(shí)間和運(yùn)行線間的接續(xù)關(guān)系，以及車站、動(dòng)車段(所)在物理路網(wǎng)中的相對(duì)位置。網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃圖避免了傳統(tǒng)繪制多線路動(dòng)車周轉(zhuǎn)圖時(shí)需分塊鋪畫的情況，突出了動(dòng)車組運(yùn)行的里程、時(shí)間，以及累計(jì)運(yùn)行的里程、時(shí)間等信息。

圖5為含有4座車站(S1，S2，S3和S4)、4條線路和1個(gè)動(dòng)車運(yùn)用所的路網(wǎng)結(jié)構(gòu)圖。圖6為該路網(wǎng)圖的網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃圖，圖中兩圓相連的折線表示接續(xù)對(duì)應(yīng)的運(yùn)行線，若折線是虛線則表示為檢修接續(xù)。圖7為圖6中數(shù)字含義的解釋示意圖。圖7中：圓內(nèi)字符代表車次/擔(dān)當(dāng)此次運(yùn)行線的動(dòng)車組車號(hào)；與圓相連的箭頭代表運(yùn)行方向，指向圓為到達(dá)該車站，背離圓為離開該車站；箭頭線上下的4組字符中，靠近圓一側(cè)上方的字符代表該運(yùn)行線的里程，靠近圓一側(cè)下方的為運(yùn)行線的運(yùn)行時(shí)間，遠(yuǎn)離圓一側(cè)上方的為出發(fā)或到達(dá)時(shí)刻，遠(yuǎn)離圓一側(cè)下方的為出發(fā)或到達(dá)車站站名；在指向圓的箭頭線的另一邊，線上方的表示動(dòng)車組累計(jì)運(yùn)行里程，線下方的表示動(dòng)車組累計(jì)運(yùn)行時(shí)間。

圖5　路網(wǎng)結(jié)構(gòu)圖(單位：km)

圖6　網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃圖

圖7　針對(duì)圖6中數(shù)字的含義解釋圖

圖8為圖6虛線框內(nèi)箭頭線的解釋示意圖，圖8中各箭頭線線段的長(zhǎng)短表示對(duì)應(yīng)運(yùn)行線運(yùn)行里程的長(zhǎng)短，箭頭指在豎線上的位置是按照對(duì)應(yīng)運(yùn)行線在該站到達(dá)或從該站出發(fā)時(shí)間順序等比例排布的。圖9為圖6中粗箭頭線所表示的動(dòng)車交路段信息解釋圖。

圖8　針對(duì)圖6中虛線框內(nèi)箭頭線的解釋示意圖

圖9　對(duì)應(yīng)圖6中粗箭頭線所包含的動(dòng)車組交路段信息(以001號(hào)動(dòng)車組為例)

3　動(dòng)車組運(yùn)用計(jì)劃雙目標(biāo)規(guī)劃優(yōu)化模型

3.1　前提假設(shè)

首先做如下假設(shè)：動(dòng)車組車型不可以混用；2列短編組的動(dòng)車組重聯(lián)后不分解，按1列動(dòng)車組考慮；在每個(gè)車站始發(fā)的列車數(shù)等于終到的列車數(shù)，只考慮列車在本站進(jìn)行接續(xù)；在動(dòng)車段(所)不計(jì)調(diào)車所用的時(shí)間；動(dòng)車組只在每天的6:00—23:30之間開行；動(dòng)車組運(yùn)用采用不固定區(qū)段的運(yùn)行方式。

3.2　集合定義

3.3　參數(shù)定義

(1)

(2)

(3)

(4)

3.4　變量說明

(2)決策變量xe,i(e∈E，i∈A)。若動(dòng)車組e擔(dān)當(dāng)運(yùn)行線i的運(yùn)輸任務(wù)，則xe,i=1，否則xe,i=0。

(3)變量xi,j(i,j∈A)。若運(yùn)行線i為運(yùn)行線j的緊前接續(xù)線，則xi,j=1，否則xi,j=0。

3.5　數(shù)學(xué)模型

以動(dòng)車組使用數(shù)量最少為最優(yōu)目標(biāo)、動(dòng)車組入段(所)檢修次數(shù)最少為次優(yōu)目標(biāo)，構(gòu)建動(dòng)車組運(yùn)用計(jì)劃雙目標(biāo)規(guī)劃優(yōu)化模型，即

e∈E，i∈A

(5)

i∈A，j∈A，d∈D，e∈E

(6)

s.t.

(7)

(8)

(9)

(10)

(11)

(12)

約束條件中：式(7)表示對(duì)任意1條運(yùn)行線，有且只有1列動(dòng)車組擔(dān)當(dāng)；式(8)和式(9)表示動(dòng)車組最大運(yùn)行時(shí)間和運(yùn)行里程不允許超過《鐵路動(dòng)車組運(yùn)用維修規(guī)程》的規(guī)定；式(10)表示在動(dòng)車段(所)d進(jìn)行M檢修作業(yè)的動(dòng)車組數(shù)量不能大于動(dòng)車段(所)的檢修能力；式(11)表示運(yùn)行線i和運(yùn)行線j進(jìn)行非檢修接續(xù)時(shí)，接續(xù)時(shí)間必須大于TR；式(12)表示運(yùn)行線i和運(yùn)行線j進(jìn)行檢修接續(xù)時(shí)，接續(xù)時(shí)間必須大于從車站到動(dòng)車段(所)往返運(yùn)行時(shí)間與在動(dòng)車段(所)檢修所需的時(shí)間之和。

4　求解算法

因?yàn)榻⒌膭?dòng)車組運(yùn)用計(jì)劃雙目標(biāo)規(guī)劃優(yōu)化模型具有解空間龐大的特點(diǎn)，因此設(shè)計(jì)基于專家系統(tǒng)的改進(jìn)蟻群算法對(duì)模型求解。

4.1　知識(shí)庫內(nèi)經(jīng)驗(yàn)知識(shí)的豐富

在編制完成動(dòng)車組運(yùn)用計(jì)劃后，總結(jié)得到如下5條經(jīng)驗(yàn)知識(shí)。

(1)在選擇后續(xù)運(yùn)行線時(shí)，避免選擇節(jié)省用車選擇范圍之外的運(yùn)行線。

圖10　節(jié)省用車選擇范圍示意圖

(2)經(jīng)驗(yàn)知識(shí)只考慮動(dòng)車組的累計(jì)運(yùn)行里程。當(dāng)選取的動(dòng)車組的最大檢修里程較小時(shí)，只考慮緊湊接續(xù)，即將滿足接續(xù)時(shí)間要求和檢修里程最小的運(yùn)行線接續(xù)。

(3)在節(jié)省用車選擇范圍之內(nèi)，對(duì)于最大檢修里程較短的運(yùn)行線，應(yīng)優(yōu)先選擇最大檢修里程較長(zhǎng)的運(yùn)行線接續(xù)；對(duì)于最大檢修里程較長(zhǎng)的運(yùn)行線，應(yīng)優(yōu)先選擇最大檢修里程較短的運(yùn)行線接續(xù)。

(4)若動(dòng)車組需入段進(jìn)行某項(xiàng)檢修作業(yè)，則判斷其他檢修作業(yè)里程或時(shí)間是否也同時(shí)達(dá)到檢修要求，若達(dá)到則同時(shí)進(jìn)行檢修。

(5)在夜間非行車期間，對(duì)到達(dá)動(dòng)車組按最大檢修里程從大到小排序，在不超過動(dòng)車段所檢修能力情況下，按照此順序?qū)?dòng)車組進(jìn)行檢修。

4.2　最大最小蟻群算法原理

參照文獻(xiàn)[19—20]中的最大最小蟻群算法，將運(yùn)行線類比為城市，運(yùn)行線接續(xù)時(shí)間類比為城市之間的距離，求解所有螞蟻遍歷所有城市后行走總距離最小的問題。該算法的轉(zhuǎn)移概率準(zhǔn)則和信息素更新準(zhǔn)則如下。

1)轉(zhuǎn)移概率準(zhǔn)則

(13)

2)全局信息素更新規(guī)則(信息素遺留規(guī)則)

(14)

(15)

(16)

3)局部信息素更新規(guī)則(信息素?fù)]發(fā)規(guī)則)

τij=(1-ζ)τij+ζτ0

(17)

(18)

式中：n為運(yùn)行線的條數(shù)；tnn為在滿足接續(xù)作業(yè)時(shí)間要求前提下最短的接續(xù)時(shí)間；ζ為權(quán)重參數(shù)，滿足0<ζ<1。

增加如下2條防止算法過早收斂或停滯的規(guī)則。

(2)當(dāng)系統(tǒng)接近停滯狀態(tài)(通過對(duì)各條邊的信息素大小的統(tǒng)計(jì)來測(cè)定)，或者在一定數(shù)量的迭代過程中不再有更優(yōu)的路徑出現(xiàn)，則所有的信息素都被重新初始化。

4.3　基于專家系統(tǒng)指導(dǎo)的最大最小蟻群算法

動(dòng)車組運(yùn)用計(jì)劃雙目標(biāo)規(guī)劃優(yōu)化模型有動(dòng)車組運(yùn)用數(shù)量最少和檢修次數(shù)最少2個(gè)目標(biāo)函數(shù)，考慮到1列動(dòng)車組的購置成本遠(yuǎn)大于其檢修成本，因此在求解時(shí)首先求解滿足動(dòng)車組使用數(shù)量最少的解，多次求解后，若存在相同運(yùn)用數(shù)量的解則比較檢修次數(shù)，取檢修次數(shù)較少的解為最優(yōu)解，若不存在相同的解，則直接取動(dòng)車組使用數(shù)量最少的解。

算法輸入：列車運(yùn)行線的到發(fā)時(shí)刻、到發(fā)站、車次、運(yùn)行里程和運(yùn)行時(shí)間；動(dòng)車組的初始運(yùn)行里程和運(yùn)行時(shí)間。

算法輸出：動(dòng)車組運(yùn)用計(jì)劃。

算法參數(shù)：可以接續(xù)運(yùn)行線i的后續(xù)運(yùn)行線集合Aallow，螞蟻數(shù)pmax，最大循環(huán)次數(shù)Kmax；經(jīng)驗(yàn)知識(shí)權(quán)重系數(shù)λ(一般0.55<λ<1.00)。循環(huán)次數(shù)K的初始值為0。

算法原理：在確定1條運(yùn)行線的后續(xù)運(yùn)行線時(shí)，先產(chǎn)生1個(gè)隨機(jī)數(shù)λ′，若λ′≤λ，則檢索知識(shí)庫中是否有滿足條件的經(jīng)驗(yàn)知識(shí)，如果有則按照經(jīng)驗(yàn)確定接續(xù)關(guān)系，否則按照智能算法確定接續(xù)關(guān)系；若λ′>λ，則采用最大最小蟻群算法確定接續(xù)關(guān)系；直到所有運(yùn)行線都已確定后續(xù)運(yùn)行線。在算法初期，λ應(yīng)賦以較大值，以產(chǎn)生較優(yōu)初始解，后期則應(yīng)賦以較小值，同時(shí)配以較大ρ，以充分利用啟發(fā)式信息搜索。

具體算法步驟如下。

步驟2：p=p+1，取車站集合S中的1個(gè)元素s作為當(dāng)前車站，取s站第1條到達(dá)運(yùn)行線i為當(dāng)前運(yùn)行線。

步驟4：在(0,1)中產(chǎn)生隨機(jī)數(shù)λ′，若λ′≤λ，則采用知識(shí)庫的經(jīng)驗(yàn)知識(shí)求解，轉(zhuǎn)步驟5；否則采用最大最小蟻群算法求解，轉(zhuǎn)步驟6。

步驟5：檢測(cè)是否有符合下述經(jīng)驗(yàn)知識(shí)的情況。

(5)將24:00之后到達(dá)s站的動(dòng)車組按最大檢修里程從大到小排序，若達(dá)到檢修里程下限的動(dòng)車組有nlow個(gè)，則取前min{Cd,nlow}個(gè)動(dòng)車組進(jìn)行檢修作業(yè)。轉(zhuǎn)步驟6。

步驟7：按式(1)更新動(dòng)車組各檢修的實(shí)際運(yùn)行里程。若后續(xù)運(yùn)行線j的Aallow為空集，則轉(zhuǎn)步驟8，否則轉(zhuǎn)步驟4。

步驟8：若仍存在沒有搜索過的車站，則選取下一個(gè)未被搜索的車站，記為s，取s站第1條未被接續(xù)的到達(dá)運(yùn)行線i，轉(zhuǎn)步驟3；否則，若p

步驟9：按照全局信息素更新規(guī)則，對(duì)兩兩接續(xù)的運(yùn)行線進(jìn)行更新，若存在信息素大于τmax的，則將其修改為τmax；按照局部信息更新規(guī)則，對(duì)兩兩能夠接續(xù)的運(yùn)行線接續(xù)信息素進(jìn)行信息素?fù)]發(fā)，若存在信息素小于τmin的，將其修改為τmin。

步驟10：記錄此次循環(huán)中的最優(yōu)解，將當(dāng)前最優(yōu)解的動(dòng)車組使用數(shù)量與歷史最優(yōu)解的進(jìn)行比較。若比歷史最優(yōu)解的少，則將當(dāng)前最優(yōu)解賦給歷史最優(yōu)解；若比歷史最優(yōu)解的多，則保留當(dāng)前歷史最優(yōu)解；若與歷史最優(yōu)解的相等，則再比較檢修次數(shù)，若比歷史最優(yōu)解的少，則將當(dāng)前最優(yōu)解賦給歷史最優(yōu)解，否則保留當(dāng)前歷史最優(yōu)解。

步驟11：若K=Kmax，則轉(zhuǎn)步驟12；否則K=K+1，轉(zhuǎn)步驟1。

步驟12：總結(jié)編制過程，得到新的知識(shí)經(jīng)驗(yàn)，并將其加入知識(shí)庫。

步驟13：輸出歷史最優(yōu)解的動(dòng)車組運(yùn)用計(jì)劃，算法結(jié)束。

5　算例分析

本文以京滬、滬杭、寧杭、京津、滬寧、膠濟(jì)線組成實(shí)例路網(wǎng)，以北京、天津、濟(jì)南、青島、南京、上海、杭州為始發(fā)終到站，各站配備動(dòng)車段或動(dòng)車運(yùn)用所。該路網(wǎng)中有432條列車運(yùn)行線，始發(fā)終到信息見表1。其中北京和上海動(dòng)車運(yùn)用段(所)的檢修能力均為100列·d-1，南京和天津動(dòng)車運(yùn)用段(所)的檢修能力為30列·d-1，其余的均為20列·天-1。

表1　車站間始發(fā)終到運(yùn)行線數(shù)表

由于動(dòng)車組車型不可混用，不同車型動(dòng)車組運(yùn)用計(jì)劃需要分別制定，因此本實(shí)例只考慮其中的1種車型?？紤]到二級(jí)檢修的大部分作業(yè)檢修里程較長(zhǎng)，因此本實(shí)例只考慮二級(jí)檢修中檢修里程相對(duì)較短的M1作業(yè)，規(guī)定的其檢修作業(yè)里程[21-23]見表2。

表2　動(dòng)車組檢修作業(yè)里程表

參數(shù)取值：螞蟻個(gè)數(shù)pmax=100只，循環(huán)次數(shù)Kmax=20次，經(jīng)驗(yàn)知識(shí)權(quán)重系數(shù)λ=0.70， 重要性參數(shù)α=1.1，β=1.1，信息素?fù)]發(fā)因子ρ=0.2。

計(jì)算環(huán)境為：64位Win7系統(tǒng)，CPU主頻2.80 GHz，開發(fā)工具為Visual Studio 2010，開發(fā)語言為C#。用基于專家系統(tǒng)的最大最小蟻群算法求解，對(duì)模型重復(fù)進(jìn)行5次求解，得到結(jié)果分別見表3。表3中動(dòng)車?yán)寐实挠?jì)算公式為

(19)

優(yōu)先選擇動(dòng)車組數(shù)最少的解，若存在相同動(dòng)車組使用數(shù)量的解。則再選擇檢修次數(shù)少的解，綜合以上2點(diǎn)，選擇第1次解或第4次解作為最終算法的解。

為了對(duì)比分析本文方法的有效性，僅使用蟻群算法對(duì)動(dòng)車組運(yùn)用計(jì)劃雙目標(biāo)規(guī)劃優(yōu)化模型求解，結(jié)果見表4。

對(duì)比表3和表4可知，采用基于專家系統(tǒng)的最大最小蟻群算法可以得到更優(yōu)的解，并且計(jì)算的收斂速度更快。

再按線路分別編制動(dòng)車組運(yùn)用計(jì)劃。將杭州站(寧杭線和滬杭線上到達(dá)杭州站的除外)和青島站的到發(fā)的列車分別單獨(dú)作為1條線路處理，南京與上海間的列車計(jì)入滬寧線，北京與天津之間的計(jì)入京津線。結(jié)果見表5。由表5可知，按照線路分別編制動(dòng)車組運(yùn)用計(jì)劃，則全路網(wǎng)共需要?jiǎng)榆嚱M132列，多于網(wǎng)絡(luò)化編制的113列。

表4　僅使用蟻群算法的求解結(jié)果

表5　按線路分別編制動(dòng)車組運(yùn)用計(jì)劃的結(jié)果

6　結(jié)　語

在動(dòng)車組網(wǎng)絡(luò)化運(yùn)行背景下，提出了強(qiáng)化動(dòng)車組運(yùn)用信息的、更直觀的“網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃圖”，為編制人員提供一個(gè)網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃編制更便捷的界面。建立動(dòng)車組運(yùn)用計(jì)劃雙目標(biāo)規(guī)劃優(yōu)化模型，設(shè)計(jì)基于專家系統(tǒng)的最大最小蟻群算法對(duì)模型求解，編制出網(wǎng)絡(luò)化條件下動(dòng)車組使用數(shù)和檢修次數(shù)均較少的網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃。案例求解結(jié)果證明：采用本文模型和算法比僅采用最大最小蟻群算法結(jié)果更優(yōu)；采用網(wǎng)絡(luò)化編制動(dòng)車運(yùn)用計(jì)劃比分別編制各線路動(dòng)車組運(yùn)用計(jì)劃更優(yōu)。文中提出的網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃圖和基于專家系統(tǒng)的最大最小蟻群算法可用于開發(fā)人機(jī)界面更加友好、更加智能化的網(wǎng)絡(luò)化動(dòng)車組運(yùn)用計(jì)劃編制系統(tǒng)，方便編制人員編制高質(zhì)量的動(dòng)車組運(yùn)用計(jì)劃。

[1]RAVINDRA K Ahuja, JIAN Liu, JAMES B Orlin, et al. Solving Real-Life Locomotive-Scheduling Problems[J]. Transportation Science, 2005, 39(4)：503-517.

[2]PIETER-JAN Fioole, LEO Kroon, GABOR Maroti, et al. A Rolling Stock Circulation Model for Combining and Splitting of Passenger Trains[J]. European Journal of Operational Research, 2006, 174: 1281-1297.

[3]MARC Peeters, LEO Kroon. Circulation of Railway Rolling Stock: a Brach-and-Price Approach[J]. Computers & Operations Research, 2008, 35:538-556.

[4]ERWIN Abbink, BIANCA van den Berg, LEO Kroon, et al. Allocation of Railway Rolling Stock for Passenger Trains[J]. Transportation Science, 2004, 38(1): 33-41.

[5]TOMOSHI Otsuki, HIDEYUKI Aisu, TOSHIAKI Tanaka. A Search-Based Approach to Railway Rolling Stock Allocation Problems[J]. Discrete Math Algorithm, 2011(3):443-456.

[6]ARIANNA Alfieri, RUTGER Groot, LEO Kroon, et al. Efficient Circulation of Railway Rolling Stock[J]. Transportation Science, 2006, 40(3)：378-391.

[7]王瑩，劉軍，苗建瑞. 基于列生成算法的動(dòng)車組檢修計(jì)劃優(yōu)化[J].中國鐵道科學(xué)，2010，31(2)：115-120.

(WANG Ying, LIU Jun, MIAO Jianrui. Column Generation Algorithms Based Optimization Method for Maintenance Scheduling of Multiple Units[J]. China Railway Science, 2010, 31(2):115-120. in Chinese)

[8]王瑩，劉軍，苗建瑞. 基于運(yùn)行線可調(diào)的動(dòng)車組周轉(zhuǎn)計(jì)劃優(yōu)化研究[J].中國鐵道科學(xué)，2012，33(4)：112-119.

(WANG Ying, LIU Jun, MIAO Jianrui. Optimization of the Circulation Plan for Multiple Units Based on Adjustable Train Path[J]. China Railway Science, 2012, 33(4):112-119. in Chinese)

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

(ZHAO Peng, TOMII Norio. An Algorithm for Multiple-Bases Train-Set Scheduling Based on Path-Exchange[J]. Journal of the China Railway Society, 2004, 26(1):7-11. in Chinese)

[10]王忠凱，史天運(yùn)，張惟皎，等. 動(dòng)車組運(yùn)用計(jì)劃和檢修計(jì)劃一體化編制模型及算法[J].中國鐵道科學(xué)，2012，33(3)：102-108.

(WANG Zhongkai, SHI Tianyun, ZHANG Weijiao, et al.Model and Algorithm for the Integrative Scheduling of EMU Utilization Plan and Maintenance Plan[J].China Railway Science, 2012, 33(3):102-108. in Chinese)

[11]史峰，周文梁，郁宇衛(wèi)，等.客運(yùn)專線動(dòng)車組運(yùn)用計(jì)劃優(yōu)化模型與算法[J].鐵道學(xué)報(bào)，2011，33(1)：8-13.

(SHI Feng, ZHOU Wenliang, YU Yuwei, et al. Optimized Model and Algorithm of Motor Train-Sets Scheduling for Dedicated Passenger Lines[J]. Journal of the China Railway Society,2011,33(1):8-13.in Chinese)

[12]史峰，魏堂建，周文梁，等. 考慮動(dòng)車組周轉(zhuǎn)和到發(fā)線運(yùn)用的高速鐵路列車運(yùn)行圖優(yōu)化方法[J].中國鐵道科學(xué)，2012，33(2)：107-114.

(SHI Feng, WEI Tangjian, ZHOU Wenliang, et al.Optimization Method for Train Diagram of High-Speed Railway Considering the Turnover of Multiple Units and the Utilization of Arrival-Departure Tracks[J].China Railway Science, 2012, 33(2):107-114. in Chinese)

[13]林柏梁，陳雷，孫卿，等. 動(dòng)車組二級(jí)檢修計(jì)劃優(yōu)化模型[J/OL].中國科技論文在線， http://www.paper.edu.cn/html/releasepaper/2013/12/470/.

(LIN Boliang, CHEN Lei, SUN Qing, et al.Study on Optimization Model of EMU Grade 2 Maintenance Plan[J/OL].Science Paper Online，http://www.paper.edu.cn/html/releasepaper/2013/12/470/. in Chinese)

[14]李華，韓寶明，張琦，等. 動(dòng)車組交路計(jì)劃優(yōu)化模型與算法研究[J].鐵道學(xué)報(bào)，2013，35(3)：1-8.

(LI Hua, HAN Baoming, ZHANG Qi, et al. Research on Optimization Model and Algorithm of EMU Circulation Plan[J]. Journal of the China Railway Society, 2013, 35(3):1-8. in Chinese)

[15]張才春. 成網(wǎng)條件下客運(yùn)專線動(dòng)車組運(yùn)用的研究[D].北京：北京交通大學(xué)，2010.

(ZHANG Caichun. Study on the Train Units Operation Problems of Passenger Dedicated Rail Network[D]. Beijing:Beijing Jiaotong University, 2010. in Chinese)

[16]鄭鋰，宋瑞，肖赟，等. 網(wǎng)絡(luò)化運(yùn)營下城市軌道交通列車車底運(yùn)用計(jì)劃編制的優(yōu)化方法[J].中國鐵道科學(xué)，2014，35(2)：104-110.

(ZHENG Li, SONG Rui, XIAO Yun, et al. Optimization Method for Working out Vehicle Scheduling Plan of Urban Rail Transit under Network Operation[J]. China Railway Science, 2014, 35(2):104-110. in Chinese)

[17]李焱. 應(yīng)用軟件工程和專家系統(tǒng)的列控中心仿真研究[D].北京：北京交通大學(xué)，2012.

(LI Yan. Simulation of Train Control Center Applying Software Engineering and Expert System[D].Beijing:Beijing Jiaotong University, 2012. in Chinese)

[18]中國鐵路總公司. TG/CL 127—2013 鐵路動(dòng)車組運(yùn)用維修規(guī)程[S]. 北京：中國鐵道出版社，2013.

[19]梁旭，黃明. 現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M].北京：電子工業(yè)出版社，2011.

[20]趙玉新,Xin-She Yang,劉利強(qiáng). 新興元啟發(fā)式優(yōu)化方法[M].北京：科學(xué)出版社，2013.

[21]焦風(fēng)川，王斌杰. 動(dòng)車組運(yùn)用與維修[M]. 北京：北京交通大學(xué)出版社，2012.

[22]王連森，連蘇寧. 動(dòng)車組維護(hù)與檢修[M]. 成都：西南交通大學(xué)出版社，2010.

[23]李華，韓寶明，趙鵬. 面向我國鐵路實(shí)際的動(dòng)車組運(yùn)用計(jì)劃編制問題[J].北京交通大學(xué)學(xué)報(bào)，2012，36(6)：8-14.

(LI Hua, HAN Baoming, ZHAO Peng. Train-Set Scheduling Problem Geared to Practical Production Process of Railway in China[J]. Journal of Beijing Jiaotong University, 2012, 36(6)：8-14.in Chinese)

[24]張惟皎,史天運(yùn),陳彥. 動(dòng)車運(yùn)用所存車線運(yùn)用方案優(yōu)化模型與算法[J].中國鐵道科學(xué)，2013，34(1)：121-125.

(ZHANG Weijiao, SHI Tianyun, CHEN Yan. Optimization Model and Algorithm for the Operation Plan of the Stabling Track at EMU Running Shed[J].China Railway Science, 2013, 34(1):121-125. in Chinese)