周文梁,姜 敏,薛利娟
中南大學(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).
考慮由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 本節(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為解編碼示意圖,每個(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ù). 對(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> 算法一旦滿足以下任一條件便終止迭代. 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. 考慮由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)行. 本研究以最小化列車總旅行時(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∶002 算法設(shè)計(jì)
2.1 解編碼及其生成法
2.2 基于給定解編碼的多節(jié)拍列車時(shí)刻表生成算法
2.3 算法終止條件
3 算例分析
結(jié) 語(yǔ)