高速鐵路多節(jié)拍組合運(yùn)行圖優(yōu)化模型與算法

周文梁，姜 敏，薛利娟

中南大學(xué)交通運(yùn)輸工程學(xué)院，湖南長(zhǎng)沙 410075

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

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

1 優(yōu)化模型

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

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

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

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

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

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

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

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

(1)

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

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

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

(2)

表1 符號(hào)定義

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ā))時(shí)刻的時(shí)間間隔長(zhǎng)度為Tw．

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

(4)

表2 決策變量與輔助變量的符號(hào)定義

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ū)間運(yùn)行時(shí)分標(biāo)準(zhǔn)與最小停站時(shí)間約束.

(i,j)∈Ew

(6)

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

(7)

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

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

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)的時(shí)間間隔不小于最小安全間隔ATi, j，離開區(qū)間(i,j)的時(shí)間間隔不小于最小安全間隔DTi, j．

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

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

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

(10)

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

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

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ū)間的時(shí)間均在列車運(yùn)營(yíng)時(shí)間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ā)時(shí)間滿足dw, f(i,j)≤t

2 算法設(shè)計(jì)

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

2.1 解編碼及其生成法

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

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

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

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

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

(17)

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

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

對(duì)每個(gè)節(jié)拍單元，定義其首列列車運(yùn)行路徑為主路徑，其余列車運(yùn)行路徑為從路徑，主路徑與從路徑起點(diǎn)時(shí)刻間隔稱為路徑間隔，如圖3．

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

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

(18)

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

(19)

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

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

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

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

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

2.3 算法終止條件

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

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

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

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

3 算例分析

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

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

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

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

圖6 算法計(jì)算時(shí)間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個(gè)節(jié)拍單元列車，其列車數(shù)量及停站序列見表3，運(yùn)營(yíng)時(shí)間為07∶00—24∶00，且在各區(qū)間的最小安全出發(fā)、到達(dá)時(shí)間間隔分別為5 min和6 min．

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

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

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

結(jié) 語(yǔ)

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