周文梁，姜 敏，薛利娟

中南大學(xué)交通運輸工程學(xué)院，湖南長沙 410075

節(jié)拍式列車運行圖具有規(guī)律性強、使用靈活及方便旅客出行與車站工作組織等優(yōu)點，在日本、歐洲的一些國家得到廣泛應(yīng)用．PEETERS[1]提出周期事件規(guī)劃問題(periodic event scheduling problem，PESP)模型和周期性列車運行圖編制(cycle periodicity formulation，CPF)模型；CAIMI等[2]在此基礎(chǔ)上提出周期運行圖的彈性PESP模型；汪波等[3-4]借助網(wǎng)絡(luò)約束圖及周期勢差模型，以列車停站時間最少為目標(biāo)，建立城際鐵路與城軌周期運行圖優(yōu)化方法；謝美全等[5]考慮列車周期性運行約束，建立基于定序的周期性運行圖優(yōu)化方法；賈曉秋等[6]構(gòu)建了高速鐵路周期列車運行圖的多目標(biāo)模型，并設(shè)計基于job-shop的遺傳算法；李傳賓[7]基于矩陣表示和極大代數(shù)法設(shè)計高速鐵路(即高鐵)周期列車運行圖優(yōu)化方法．

周期列車運行圖雖能提供旅客規(guī)律化的運行列車以方便旅客出行，然而在其編制過程中，通常是基于高峰期出行需求確定該時段列車時刻表，通過進(jìn)一步復(fù)制和刪除非高峰時段部分列車而獲得全天列車運行圖．如此一來，列車原本嚴(yán)格的等時間間隔周期運行規(guī)律將在一定程度上被破壞．為使列車運行具有嚴(yán)格的等間隔運行規(guī)律，能夠使不同時段列車運行數(shù)量與出行需求量相適應(yīng)，本研究基于列車多節(jié)拍協(xié)同運行方式，將具有相同起點、終點、停站方案以及速度等級的列車歸為一個節(jié)拍單元．同節(jié)拍單元列車以嚴(yán)格的等時間間隔周期運行，而不同節(jié)拍單元列車可具有不同的運行時間間隔，進(jìn)而協(xié)調(diào)優(yōu)化各節(jié)拍單元列車運行的時間間隔及其車站到達(dá)與出發(fā)時間，由此獲得的列車時刻表，不僅具有嚴(yán)格的等時間間隔運行規(guī)律，還能使不同時段的列車運行數(shù)量與出行需求量相適應(yīng)．

1 優(yōu)化模型

考慮由K個車站與K-1個復(fù)線區(qū)間構(gòu)成的高鐵線路L=(S,E)上多節(jié)拍單元列車運行圖優(yōu)化問題，其中，S為線路車站序列；E為線路區(qū)間集．為簡便起見，該問題研究基于以下假設(shè)．

假設(shè)1車站簡化為具有停車能力屬性的節(jié)點，不考慮列車在車站運行路徑，但要求車站同一時間內(nèi)的停留列車數(shù)量不能超過該站停車能力．

假設(shè)2線路僅運營多個節(jié)拍式運行列車，不包含非節(jié)拍運行列車．

假設(shè)3同節(jié)拍單元列車采用相同的車底或動車組，所有同節(jié)拍列車具有相同定員．

這種多節(jié)拍組合運行方式能夠使得各節(jié)拍單元列車嚴(yán)格按某固定時間間隔周期性運行，以方便旅客乘車出行，而且能夠通過協(xié)調(diào)各節(jié)拍單元首列車始發(fā)時刻及其運行時間間隔，使得客流高峰期組織運行更多列車，而在客流低峰期運行少量列車以適應(yīng)不同時期客流需求的變化．

圖1 由2個運行節(jié)拍單元構(gòu)成的列車運行圖Fig.1 A train schedule with two period-types of trains

多節(jié)拍單元列車運行圖優(yōu)化旨在優(yōu)化各節(jié)拍單元列車運行時間間隔、以及各節(jié)拍單元列車在車站的到達(dá)與出發(fā)時刻，使其在滿足各類運營與行車時間標(biāo)準(zhǔn)條件下，所有節(jié)拍單元列車總旅行時間達(dá)到最小．該優(yōu)化問題所涉及到的相關(guān)參數(shù)符號定義如表1，決策變量與輔助變量的定義如表2．

以最小化所有節(jié)拍單元列車旅行時間之和為目標(biāo)，實現(xiàn)多節(jié)拍列車組合運行時刻表優(yōu)化，其具體模型為

(1)

該模型滿足以下7組約束條件：

1)同節(jié)拍單元列車等間隔運行約束.

aw, f+1(i,j)=aw, f(i,j)+Tw, ?w;f=1,2,…,mw-1; (i,j)∈Ew

(2)

表1 符號定義

dw, f+1(i,j)=dw, f(i,j)+Tw,?w;

f=1,2,…,(mw-1); (i,j)∈Ew

(3)

約束式(2)和(3)確保節(jié)拍單元w兩相鄰列車的到達(dá)(出發(fā))時刻的時間間隔長度為Tw．

2)列車發(fā)車達(dá)到最低客座率約束.

(4)

表2 決策變量與輔助變量的符號定義

aw, f+1(rw,j)-aw, f(rw,j)≥RTw(aw, f(rw,j)),

?w;f=1,2,…,mw-1; (rw,j)∈Ew

(5)

3)區(qū)間運行時分標(biāo)準(zhǔn)與最小停站時間約束.

(i,j)∈Ew

(6)

(i,j),(j,i′)∈Ew

(7)

約束式(6)與(7)分別確保節(jié)拍單元w首列列車區(qū)間運行時間與車站停站時間分別不低于其相應(yīng)的最小值．

4)列車間最小安全到達(dá)與出發(fā)時間間隔約束.

aw′, f′(i,j)+ATi, j，

?[w,f]≠[w′,f′]; (i,j)∈Ew∩Ew′

(8)

dw′, f′(i,j)+DTi, j，

?[w,f]≠[w′,f′]; (i,j)∈Ew∩Ew′

(9)

約束式(8)保證節(jié)拍單元w第f列列車與節(jié)拍單元w′第f′列列車進(jìn)入?yún)^(qū)間(i,j)的時間間隔不小于最小安全間隔ATi, j，離開區(qū)間(i,j)的時間間隔不小于最小安全間隔DTi, j．

同理，約束式(9)確保節(jié)拍單元w第f列列車與節(jié)拍單元w′第f′列列車離開區(qū)間的時間間隔不小于最小安全間隔DTi, j．

5)車站最大同時停留列車數(shù)約束，即車站停車能力約束.

?j∈S;t=1,2,…,T

(10)

約束式(10)保證了車站j在任意時刻t停留的列車總數(shù)不會超過其停車能力capj．

6)列車到發(fā)時間取值范圍約束.

1≤aw,f(i,j)≤T, ?w;

f=1,2,…,mw; (i,j)∈Ew

(11)

1≤dw,f(i,j)≤T, ?w;

f=1,2,…,mw; (i,j)∈Ew

(12)

約束式(11)和(12)分別使得列車進(jìn)入和離開區(qū)間的時間均在列車運營時間1～T以內(nèi)．

7)決策變量間一致性約束.

?[w,f]≠[w′,f′]; (i,j)∈Ew∩Ew′

(13)

f=1,2,…,mw;t=1,2,…,T; (i,j)∈Ew

(14)

[1-ρw, f(i,j,t)]×M，?w;

f=1,2,…,mw;t=1,2,…,T;

(i,j),(j,i′)∈Ew

(15)

θw, f(j,t)≤ρw, f(i,j,t)， ?w;

f=1,2,…,mw;t=1,2,…,T; (i,j)∈Ew

(16)

約束式(15)和(16)共同確保僅當(dāng)列車[w,f]在車站j的到發(fā)時間滿足dw, f(i,j)≤t

2 算法設(shè)計

本節(jié)設(shè)計交叉元啟發(fā)算法求解模型．首先，基于初始化的概率參數(shù)隨機生成多個解編碼，基于每個解編碼采用多路徑搜索算法生成一個多節(jié)拍運行時刻表；其次，衡量各個體解對應(yīng)列車時刻表質(zhì)量，按一定比例挑選其中的精英解；最后，根據(jù)挑選出來的精英解更新概率參數(shù)，并以此概率隨機生成新的個體解編碼．通過如此反復(fù)改進(jìn)概率參數(shù)，使較高質(zhì)量個體解編碼能以更高概率生成，而較差質(zhì)量個體解編碼因其生成概率較低而逐將淘汰．

2.1 解編碼及其生成法

圖2為解編碼示意圖，每個節(jié)拍單元包含優(yōu)先權(quán)值、以整數(shù)表示的始發(fā)時刻與運行間隔3個基因位．其中，優(yōu)先權(quán)值決定了節(jié)拍單元列車鋪畫的先后順序；始發(fā)時刻與運行間隔分別確定了首列車發(fā)車時刻與運行時間間隔．

圖2 解編碼示意圖Fig.2 The schematic diagram of solution encoding

每個節(jié)拍單元列車基因值通過離散概率分布函數(shù)生成．記αw,r,n為第n次迭代中節(jié)拍單元w列車選擇優(yōu)先權(quán)Qw=r的概率，此時，r=1,2,…,W；βw,r,n與γw,r,n分別為第n次迭代中節(jié)拍單元w列車選擇始發(fā)時刻dw=t與運行時間間隔Tw=Δt的概率．

初始化時，各節(jié)拍單元列車基因所有取值的選擇概率相同，然后基于精英解更新，使精英解中基因值能以較高概率進(jìn)入后續(xù)個體解編碼，具體方法(以參數(shù)βw,r,n為例，其他參數(shù)類似)為

(1-ρ)·βw,r,n-1

(17)

其中，GS為每次迭代種群中個體數(shù)量；σ為選擇精英解的比例；ES為當(dāng)前迭代選中的精英解集合；Tw(n,k)表示第n次迭代中第k個解中節(jié)拍單元w參數(shù)Tw的取值；參數(shù)ρ為權(quán)衡系數(shù)．

2.2 基于給定解編碼的多節(jié)拍列車時刻表生成算法

對每個節(jié)拍單元，定義其首列列車運行路徑為主路徑，其余列車運行路徑為從路徑，主路徑與從路徑起點時刻間隔稱為路徑間隔，如圖3．

圖3 節(jié)拍單元列車運行的主路徑、從路徑及路徑間隔示意圖Fig.3 Headways between primary path and subordinate path of a period-type

算法開始時，僅初始化所有備選起始節(jié)點的標(biāo)號集，而其余節(jié)點標(biāo)號在之后的路徑搜索過程中根據(jù)需要添加．當(dāng)搜索節(jié)拍單元w列車路徑時，起始節(jié)點標(biāo)號初始化如下

(18)

tn+(mw-1)×Γ+Rw≤T

(19)

其中， Rw表示節(jié)拍單元w列車按區(qū)間最小運行、車站最小停站時間運行所花費的總旅行時間．

接下來，算法需通過不斷生成新標(biāo)號，更新既有標(biāo)號值搜索從起點到各節(jié)點總費用最少的主路徑與間隔值，具體過程為

步驟1逐一選擇標(biāo)號集Bnew中標(biāo)號，對于當(dāng)前標(biāo)號b， 根據(jù)其與前序標(biāo)號的對應(yīng)車站及停站時間，更新其后續(xù)節(jié)點標(biāo)號如下：

步驟2令Bnew=Bupdate， 從Bupdate中選擇標(biāo)號值最小的標(biāo)號b*， 令ηb*=1、Bupdate=?． 若標(biāo)號對應(yīng)節(jié)點車站為列車終點站，則停止算法計算；否則，重復(fù)以上步驟更新節(jié)點標(biāo)號．

在以上路徑搜索中，為避免當(dāng)前節(jié)拍單元列車路徑與已確定列車路徑產(chǎn)生作業(yè)沖突，任何搜索到的主路徑與從路徑均不可包含：① 之前已確定節(jié)拍單元列車路徑所含有向?。虎?若被使用將與第1類有向弧違背最小安全到達(dá)時間間隔或最小安全出發(fā)時間間隔約束的有向?。?/p>

2.3 算法終止條件

算法一旦滿足以下任一條件便終止迭代．

1)對任意節(jié)拍單元列車，βw,r,n與γw,r,n>(1-ω)或<ω． 同樣，εw,r,n與εw,r,n>(1-ω)或<ω， 其中，ω為一很小正數(shù)值， 通常取ω=0.01；

2)從算法開始所獲得的最優(yōu)個體解對應(yīng)的目標(biāo)函數(shù)值連續(xù)μ次迭代未發(fā)生改進(jìn)；

3)當(dāng)前迭代次數(shù)達(dá)到給定最大迭代次數(shù)nmax．

3 算例分析

考慮由6個車站、5個復(fù)線區(qū)間線路，運營時間為[1,180] min，且各區(qū)間最小安全出發(fā)、到達(dá)間隔為3 min．所有列車均從線路端點站出發(fā)到達(dá)另一端點站，停車隨機確定，且最小停車時間為1 min．

圖4 算法計算時間CT與Gap隨節(jié)拍單元數(shù)量的變化關(guān)系Fig.4 The change relation of CT and Gap with the number of period-types

圖4(a)與(b)分別給出當(dāng)節(jié)拍單元平均列車數(shù)為3～7列時，算法計算時間(CT)與目標(biāo)函數(shù)與最優(yōu)值相對差距(Gap)隨節(jié)拍數(shù)量增加的變化．顯然，CT呈先慢后快增長趨勢．如在平均列車數(shù)為4時，節(jié)拍單元數(shù)量從2增至4，計算時間增幅較小，但之后卻大幅增加．另外，節(jié)拍單元平均列車數(shù)越少，計算時間增速反而較大，主要原因是在平均列車數(shù)量較少時，每個節(jié)拍單元列車可搜索的路徑范圍與時間間隔值均較多，導(dǎo)致更多的計算時間．由圖4(b)可知，隨節(jié)拍單元數(shù)量增加，算法基本能搜索到最優(yōu)解，僅在平均列車數(shù)為7列、節(jié)拍單元為4時，沒有搜索到最優(yōu)解，此時Gap約為10%．

圖5 算法計算時間CT與Gap隨節(jié)拍單元平均列車的變化關(guān)系Fig.5 The change relation of CT and Gap with the increase of average train number of period-types

圖5(a)與(b)分別給出不同節(jié)拍單元數(shù)量時，CT與Gap隨著節(jié)拍單元平均列車數(shù)增加的變化關(guān)系．由圖5(a)可知，隨著節(jié)拍單元平均列車數(shù)量的增加，CT反而下降．主要原因是算法并不需要為同節(jié)拍單元列車逐列搜索路徑，而只需尋找具有開行間隔屬性的出行路徑，反而節(jié)拍單元平均列車數(shù)越少，首列列車路徑的搜索時間范圍與對應(yīng)的列車運行間隔范圍越大，計算時間越多．由圖5(b)可知，在節(jié)拍單元平均列車數(shù)較少時，Gap均為0，但當(dāng)繼續(xù)增加至6以后，Gap具有一定的波動性，最大值接近18.0%．

圖6(a)與(b)分別給出當(dāng)節(jié)拍單元平均列車數(shù)為3～6列時，CT與Gap隨高、中速節(jié)拍單元數(shù)量之比增加的變化關(guān)系．由圖6(a)可知，在節(jié)拍單元平均列車數(shù)為5列或6列時，高、中速節(jié)拍單元數(shù)量之比變化對計算時間影響較大，但當(dāng)節(jié)拍單元平均列車數(shù)為3列或4列時，算法計算時間變化范圍相對較?。蓤D6(b)可知，在節(jié)拍單元平均列車數(shù)較少時，Gap一直保持為0；而當(dāng)節(jié)拍單元平均列車數(shù)為6列時，Gap達(dá)到最大值29.6%、最小值1.4%．由此可見，在節(jié)拍平均開行列車數(shù)量較少時，高、中速節(jié)拍單元列車混行對CT與Gap影響均較??；但當(dāng)節(jié)拍平均列車數(shù)量較大時，將導(dǎo)致CT與Gap增加．

圖6 算法計算時間CT與Gap隨高、中速節(jié)拍單元數(shù)量比的變化關(guān)系Fig.6 The change relation of CT and Gap with the rate increase of high-speed to middle-speed period-type

以京滬高鐵線路為例，僅考慮北京南至上海虹橋的節(jié)拍列車，暫不考慮其他非節(jié)拍列車．假定共有5個節(jié)拍單元列車，其列車數(shù)量及停站序列見表3，運營時間為07∶00—24∶00，且在各區(qū)間的最小安全出發(fā)、到達(dá)時間間隔分別為5 min和6 min．

表3 各運行節(jié)拍單元列車停站序列以及運行數(shù)量Table 3 The number of trains and stop sequences of each period-type train

為方便記憶列車運行時刻，以10 min的整倍數(shù)作為列車運行時間間隔的可能取值．經(jīng)4.31 h的計算后，獲得列車運行圖如圖7，此時，Gap為6.8%．

由圖7可知，每個節(jié)拍單元列車均按所確定的時間間隔等間隔運行，通過協(xié)調(diào)各節(jié)拍單元列車最早發(fā)車時間與時間間隔使得全天不同時段具有不同數(shù)量的列車，以滿足不同時段旅客需求．經(jīng)比較發(fā)現(xiàn)，具有較多數(shù)量列車節(jié)拍單元的運行時間間隔相對較小，反之相對較大，從而使列車盡可能分散到全天運營時間范圍內(nèi)，避免列車集中運行．

結(jié) 語

本研究以最小化列車總旅行時間為目標(biāo)，構(gòu)建多節(jié)拍單元列車協(xié)同運行時刻表優(yōu)化模型．在定義主路徑、從路徑及路徑間隔等概念的基礎(chǔ)上，將交互熵原理與多路徑組合搜索算法相結(jié)合，設(shè)計了時刻表優(yōu)化的元啟發(fā)式算法．

本模型與算法暫未考慮客流因素，今后研究需進(jìn)一步將客流因素反映到模型與算法中．此外，關(guān)于車站到發(fā)數(shù)量、車站路徑選擇限制的考慮、以及將本方法推廣到小規(guī)模軌道網(wǎng)絡(luò)同樣是需要進(jìn)一步研究的內(nèi)容．

圖7 07∶00—24∶00以10 min的整數(shù)倍為運行間隔的多節(jié)拍列車運行圖Fig.7 The multi-periodic train timetable based on setting train operation period as the integer multiples of 10 min during 07∶00 to 24∶00