李　健，王　瑩，李海鷹，張哲銘

(1. 北京交通大學(xué) 交通運輸學(xué)院，北京 100044；2. 北京交通大學(xué) 軌道交通控制與安全國家重點實驗室，北京 100044)

至2016年9月我國已建成并運行包括京津、滬寧、滬杭城際等在內(nèi)共 20條城際鐵路，據(jù)十三五規(guī)劃綱要中的《中長期鐵路網(wǎng)規(guī)劃》，未來我國城際鐵路系統(tǒng)建設(shè)規(guī)模將繼續(xù)擴(kuò)大。為了降低鐵路部門的運營成本，動車組作為高速鐵路和城際鐵路的主要運載工具，其運用優(yōu)化一直是國內(nèi)外學(xué)者不斷研究的問題。目前，國外學(xué)者對動車組交路計劃的研究主要集中在考慮多車種、列車摘解與重聯(lián)等不同的約束條件和不同的優(yōu)化目標(biāo)建立數(shù)學(xué)優(yōu)化模型，多采用CPLEX等商業(yè)化軟件、分支定界等確定性算法進(jìn)行求解。其中，以Arianna等[1?4]為代表對此展開了大量的研究[1-4]。國內(nèi)學(xué)者主要將動車組運用問題轉(zhuǎn)化成指派和(多)旅行商 2類問題。前者均不考慮檢修約束，后者主要考慮動車組一級檢修約束，個別學(xué)者還考慮了二級檢修約束。由于我國路網(wǎng)和列車開行數(shù)量規(guī)模較大，因此在求解時常采用啟發(fā)式算法，包括基于概率的局域搜索算法、蟻群算法、模擬退火算法、遺傳算法以及大規(guī)模鄰域搜索算法[5?8]，也有學(xué)者采用列生成法等精確算法求解[9]。其中，接續(xù)網(wǎng)絡(luò)[10?12]被廣泛用于刻畫運行線間的關(guān)系，并基于此進(jìn)行建模和求解。然而，由于城際鐵路列車開行密度大的特點，列車間可行接續(xù)關(guān)系多而復(fù)雜，基于接續(xù)網(wǎng)構(gòu)建的優(yōu)化模型可能因其規(guī)模較大而出現(xiàn)求解效率低下的情況。因此，本文引入時間軸線網(wǎng)絡(luò)[13]建立城際鐵路動車組交路計劃的優(yōu)化模型，以期更為快速、高效地求解該問題。在構(gòu)建動車組運用網(wǎng)絡(luò)時，接續(xù)網(wǎng)將運輸任務(wù)即列車運行線以一個超節(jié)點表示，在時間和空間上均滿足接續(xù)條件的任意兩運輸任務(wù)節(jié)點間均建立一條可行接續(xù)弧，而時間軸線網(wǎng)則是將列車運行線以一個始發(fā)節(jié)點和一個終到節(jié)點表示，在同一站點的相鄰節(jié)點間建立時間軸線連線。圖1(a)和圖1(b)分別為接續(xù)網(wǎng)絡(luò)和時間軸線網(wǎng)絡(luò) 2種表示方法的簡單示意圖，2圖中均包含3對即6條列車運行線1，2，3，…，6。圖1(a)接續(xù)網(wǎng)絡(luò)中a，b，c…，i為滿足列車間可行接續(xù)的接續(xù)弧，而圖 1(b)時間軸線網(wǎng)絡(luò)中a，b…，e為同一站點相鄰節(jié)點間建立的時間軸線連接弧, 弧的規(guī)模有所降低。此外，在動車組車底接續(xù)關(guān)系表示方法上兩者也存在差異，接續(xù)網(wǎng)中單獨的一條接續(xù)弧即可表示動車組車底的接續(xù)關(guān)系, 而時間軸線網(wǎng)中的動車組車底接續(xù)關(guān)系一般需要多條連接弧組合在一起才能表示。

圖1　接續(xù)網(wǎng)絡(luò)和時間軸線網(wǎng)絡(luò)示意圖對比Fig.1　Comparison of schematic diagrams between connection network and time-line network

1　城際鐵路的列車開行模式和特點

作為我國鐵路快速客運網(wǎng)的重要組成部分，城際鐵路主要服務(wù)于經(jīng)濟(jì)發(fā)達(dá)、人口稠密的都市圈和城市帶之間，承擔(dān)區(qū)域內(nèi)或2個城市間的短途客流?？偨Y(jié)我國實際運營的城際鐵路列車開行模式及特點主要有：

1) 城際鐵路上通常只開行本線運輸?shù)母咚賱榆嚱M列車；

2) 列車開行具有高頻率、短運距、短發(fā)車間隔的公交化運營特點，列車開行密度大。

這種列車開行模式不僅提高了城際鐵路線路能力的利用率，也使得旅客出行有了更多的選擇，使旅客的出行更為方便、快捷。以京津城際為例，北京南?天津的全程直達(dá)運行時間為30 min左右，實際平日開行列車達(dá) 172列，最小發(fā)車間隔僅 5 min，其他時段間隔不超過25 min，公交化運營特點明顯。

針對城際鐵路的列車開行模式和特點，時間軸線網(wǎng)因其建弧和建網(wǎng)方法的不同，能夠有效降低弧的數(shù)量和網(wǎng)絡(luò)規(guī)模，更易于求解，因此本文建立了基于時間軸線網(wǎng)絡(luò)的城際鐵路動車組交路計劃優(yōu)化模型。

2　動車組交路計劃優(yōu)化模型

假設(shè)列車運行圖已給定，且各動車段所的檢修能力充足，以動車組使用數(shù)量最少為優(yōu)化目標(biāo)，考慮運行圖和一級檢修等約束，建立基于時間軸線網(wǎng)絡(luò)的動車組交路計劃優(yōu)化模型。

2.1　時間軸線網(wǎng)絡(luò)的構(gòu)建

基于給定的列車運行圖構(gòu)建動車組運用的時間軸線網(wǎng)絡(luò)G(V,A)，V為所有運行線始發(fā)、終到節(jié)點和檢修基地節(jié)點的集合，A為網(wǎng)絡(luò)中所有類型弧的集合。時間軸線網(wǎng)絡(luò)圖中橫軸表示時間，縱軸表示空間即車站(包括檢修基地所在站或連接站在內(nèi))，運行圖中的任一列車運行線r∈R均具有 4個屬性，分別表示各列車的始發(fā)車站、終到車站、始發(fā)時刻和終到時刻，時間以分鐘為單位。由于列車運行圖上的列車開行周期為 1 d，因此建立 1 d的時間軸線網(wǎng)，具體的網(wǎng)絡(luò)構(gòu)建方法如下：

1) 設(shè) R = { r|r = 1 ,2,· · ·,m } 為所有列車運行線的集合，m為列車運行線總數(shù)，對任一列車運行線r∈R，在其始發(fā)站的始發(fā)時刻處建立始發(fā)節(jié)點，在其終到站的時刻建立終到節(jié)點，其中tc表示列車間的最小接續(xù)時間，將其取值為15 min，并建立列車弧()，定義弧的權(quán)重。記所有列車弧集合為AR，所有列od車運行線的始發(fā)、終到節(jié)點的集合為VR。

2) 對每一車站所在的時間橫軸上任何相鄰的2個節(jié)點i和j(i和j均可能為運行線的始發(fā)或終到節(jié)點)之間建立一條日連接弧，記弧的權(quán)重，同時建立一條從該車站末節(jié)點指向始節(jié)點的夜連接弧，弧的權(quán)重記為 t始+ 1 440-t末，其中t始和t末分別表示該車站所在時間橫軸上的始節(jié)點時刻和末節(jié)點時刻。特別地，如果在某一時刻存在某一列車運行線的終到節(jié)點與另一列車運行線的始發(fā)節(jié)點重合，仍在該兩點間建立一條連接弧，弧的方向為終到節(jié)點指向始發(fā)節(jié)點且記弧的權(quán)重為 0。記所有日連接弧集合為，所有夜連接弧集合為，所有連接弧集合。

3) 設(shè)所有檢修基地集合為K，對每一個檢修基地 k∈K，建立一對虛擬檢修出、入節(jié)點 ok和 dk來代替該檢修基地，所有虛擬檢修出節(jié)點集合和虛擬檢修入節(jié)點集合分別記為VO和VD，則所有節(jié)點集合。對任意始發(fā)車站為檢修基地k所在站或連接站的列車運行線r建立檢修出段弧()，表示某個動車組從檢修基地k檢修完出來即將上線擔(dān)當(dāng)運輸任務(wù)。類似地，對任意終到車站為檢修基地k所在站或連接站的列車運行線r′建立檢修入段弧()，表示某個動車組擔(dān)當(dāng)完某一運輸任務(wù)后回檢修基地k進(jìn)行檢修，虛擬檢修出、入段弧的建立可以將動車組回檢修基地進(jìn)行檢修和在檢修基地進(jìn)行夜間駐留進(jìn)行區(qū)分。記檢修出、入段弧的權(quán)重均為0，所有檢修出段弧集合為AO，所有檢修入段弧集合為 AD，則所有弧集合。

圖2為動車組運用時間軸線網(wǎng)絡(luò)示意圖，圖中有8條列車運行線、3個車站和1個動車所/段，其中站A為動車所/段所在或所連接的車站，對該動車所/段我們建立一對虛擬檢修出入節(jié)點 ok和 dk，并用不同線條、粗細(xì)的有向箭頭來表示不同類型的弧，如圖2所示。

圖 2 動車組運用時間軸線網(wǎng)絡(luò)示意圖Fig.2　Schematic diagram of time-line network of train-set utilization

2.2　數(shù)學(xué)優(yōu)化模型

基于2.1節(jié)構(gòu)建的時間軸線網(wǎng)絡(luò)G(V,A)，建立動車組交路計劃的數(shù)學(xué)優(yōu)化模型。

2.2.1符號定義

基于動車組運用時間軸線網(wǎng)絡(luò)，定義如下符號：

P為所有交路的集合，交路數(shù)作為未知參數(shù)求解前需給其設(shè)定初值；p為P中任一條交路；為以j為起點的所有出邊弧的集合；為以j為終點的所有入邊弧的集合；為動車段/所 k的所有檢修出段弧集合；為動車段/所 k的所有檢修入段弧集合；為決策變量，表示最優(yōu)解中弧(i,j)被交路p選中的次數(shù)；lij和tij分別為弧(i,j)的運行距離和運行時間；為動車組一級檢修的累計運行里程標(biāo)準(zhǔn)和累計運行時間標(biāo)準(zhǔn)。

2.2.2目標(biāo)函數(shù)

選取動車組交路計劃優(yōu)化問題中最直觀常見的動車組數(shù)最少作為目標(biāo)函數(shù)。由于運用動車組數(shù)等于交路段的數(shù)量，交路數(shù)等于檢修出段弧數(shù)，而交路段的數(shù)量又等于交路數(shù)和夜連接弧數(shù)之和，因此將檢修出段弧數(shù)與夜連接弧數(shù)之和最少作為動車組數(shù)最少的等價目標(biāo)函數(shù)，如式(1)所示。

2.2.3約束條件

需考慮的約束條件如式(2)～(8)所示。

其中：式(2)為覆蓋約束，表示任何一條列車弧必須被某個交路選中且只能選中一次；式(3)為守恒約束，表示對任一交路p而言，任一列車節(jié)點的出邊弧數(shù)均等于其入邊弧數(shù)；式(4)和(5)分別表示動車組一級檢修累計運行里程和運行時間約束；式(6)和(7)為回所檢修約束，表示對每個交路來說動車組只能從一個動車段/所出發(fā)，最后回到同一動車段/所進(jìn)行檢修；式(8)為決策變量取值約束。

3　模型求解

3.1　動車組交路數(shù)下界值的確定

模型中，列車運行線、車站與檢修基地等相關(guān)參數(shù)均可根據(jù)實際案例的數(shù)據(jù)輸入，而交路數(shù)作為未知參數(shù)且決策變量是一個與弧和交路均有關(guān)的二維變量，因此需預(yù)先給交路數(shù)設(shè)定一個初值，而該初值設(shè)定的合適與否將直接影響求解的結(jié)果，若值偏大則所求解不是最優(yōu)解，相反若值偏小則會出現(xiàn)無可行解。因此，在參照式(9)動車組數(shù)量計算方法[10]基礎(chǔ)上給交路數(shù)設(shè)定一初始下界值。

對于一個給定的列車運行圖，總列車旅行時間和運行圖周期是定值，將任意2列列車間的接續(xù)時間均按緊接續(xù)即最小動車組運用接續(xù)時間標(biāo)準(zhǔn) 15 min進(jìn)行計算，向上取整后則可得動車組數(shù)量的下界值，另外考慮到一個交路大多由1個交路段或2個交路段組成，而交路段的數(shù)量即等于動車組數(shù)量，因此交路數(shù)的下界初值可按式(10)計算得出。

3.2　求解步驟

首先初始化動車組運用時間軸線網(wǎng)絡(luò)，在計算確定動車組交路下界值后即可進(jìn)行模型求解，通過反復(fù)調(diào)用CPLEX求解引擎和迭代不斷調(diào)整參數(shù)交路數(shù)規(guī)模，直至模型第一次成功求解為止，則所得解即為最優(yōu)解，具體步驟如下。

Step 1: 輸入運行線、車站、動車段/所等數(shù)據(jù)，初始化動車組運用時間軸線網(wǎng)絡(luò)；

Step 2: 計算并初始化交路規(guī)模，記交路數(shù)初始下界值為n0，調(diào)用CPLEX求解引擎求解模型；

Step 3：若模型成功求解，則所求解即為最優(yōu)解，轉(zhuǎn)Step 5；若求解結(jié)果為無可行解，轉(zhuǎn)Step 4；

Step 4：調(diào)整交路數(shù)參數(shù)值，將該參數(shù)值增加1并重新開始求解；

Step 5：若成功求解，則所求解即為最優(yōu)解，轉(zhuǎn)Step 5；若仍無可行解，則轉(zhuǎn)Step 4，直至模型第一次成功求解為止；

Step 6：輸出最優(yōu)解，算法結(jié)束。

4　算例分析

選取 4條國內(nèi)已實現(xiàn)運營的城際鐵路在 2017年3月平日的列車運行圖作為算例，并基于這些算例對比分析時間軸線網(wǎng)模型和接續(xù)網(wǎng)模型[14]的求解性能。時間軸線網(wǎng)的構(gòu)建是在Visual Studio 2013平臺上使用C#編程語言實現(xiàn)的，求解引擎調(diào)用的是ILOG CPLEX V12.3軟件，求解環(huán)境為一臺CPU為Intel(R) Core(TM) i7-4770，3.40GHZ×2，4GB內(nèi)存的臺式計算機(jī)。

實際選作算例的各城際鐵路的動車段/所、列車及車站數(shù)基本信息如表1所示。根據(jù)我國《鐵路動車組運用維修規(guī)程》，動車組一級檢修的累計里程標(biāo)準(zhǔn)為4 000 km，一級檢修的累計運行時間標(biāo)準(zhǔn)為48 h。

針對同一案例數(shù)據(jù)，首先對比分析2種動車組運用網(wǎng)絡(luò)模型的求解性能，見表2；圖3是利用時間軸線網(wǎng)模型的求解結(jié)果在城際鐵路1運行圖基礎(chǔ)上所勾畫出的交路圖，圖中的交路1(1)和交路1(2)表示交路1為2 d的交路，這里的(1)和(2)分別表示交路1的第1 d交路段和第2 d交路段，其他的2 d交路類似。之后再進(jìn)一步對比分析2種不同的建網(wǎng)方法下的弧和決策變量數(shù)以及它們隨列車數(shù)量的變化關(guān)系，見圖4。

表1　各城際鐵路動車段/所、運行線及車站基本信息Table1　General information of corresponding depot,train path, station of each intercity railway

表2　求解性能分析Table2　Analysis of solving performance

圖3　列車運行圖及動車組交路圖Fig.3　Train diagram and rolling stock circulation diagram

從表2和圖4可得出以下結(jié)論：

1) 基于 2種動車組運用網(wǎng)絡(luò)構(gòu)建的模型在求解城際鐵路動車組交路計劃問題時求解效率存在較大差異。同一算例數(shù)據(jù)下，時間軸線網(wǎng)求解時間更短、求解效率更高，說明時間軸線網(wǎng)模型和求解方法可快速有效地求解城際鐵路動車組交路計劃。

2) 隨著運行線數(shù)的增加，接續(xù)網(wǎng)中弧數(shù)量呈指數(shù)上升，而時間軸線網(wǎng)中弧數(shù)量呈線性上升。實際

上，接續(xù)網(wǎng)絡(luò)模型中決策變量數(shù)即等于弧數(shù)，而時間軸線網(wǎng)模型中決策變量數(shù)為弧數(shù)與交路數(shù)的乘積，由于城際鐵路運距較短，一條交路可覆蓋多條列車運行線，因此在運行線規(guī)模較大時，時間軸線網(wǎng)絡(luò)模型由于所需交路數(shù)較少而不會導(dǎo)致對應(yīng)數(shù)學(xué)模型規(guī)?？焖僭黾?，仍能保持較高效的求解效率。

圖4　弧規(guī)模和決策變量數(shù)隨運行線數(shù)量變化關(guān)系Fig.4　Performance of arc size and the number of decision variables with the change of the number of train paths

5　結(jié)論

1) 基于城際鐵路列車開行特點，本文通過構(gòu)建動車組運用時間軸線網(wǎng)絡(luò)建立了動車組交路計劃優(yōu)化模型，通過設(shè)計嵌入CPLEX求解引擎的迭代求解方法，成功實現(xiàn)了模型的快速求解。

2) 對比分析時間軸線網(wǎng)和接續(xù)網(wǎng) 2種動車組運用網(wǎng)絡(luò)優(yōu)化模型，算例求解結(jié)果表明：2種優(yōu)化模型均能求得問題的最優(yōu)解，但時間軸線網(wǎng)模型的求解規(guī)模較小，求解快速、求解效率較高。且隨著運行線數(shù)的增加，其求解優(yōu)勢更加明顯，成功驗證了時間軸線網(wǎng)建網(wǎng)方法更適用于城際鐵路這類列車開行密度大、運距短的動車組交路計劃的編制和求解。

3) 隨著如今我國高速鐵路成網(wǎng)規(guī)模的擴(kuò)大，作為一類典型的大規(guī)模NP-hard組合優(yōu)化問題，動車組交路計劃的求解變得更加復(fù)雜，鑒于能夠有效降低數(shù)學(xué)規(guī)模的優(yōu)點，時間軸線網(wǎng)仍具有較大適用性，但實際大多需要結(jié)合一些優(yōu)化算法才能實現(xiàn)快速求解。