蔣沐弘,鄭屹桐,李 帥,孫國鋒
(蘭州交通大學(xué) 交通運輸學(xué)院,甘肅 蘭州 730070)
受天氣、設(shè)備等因素影響,普速鐵路列車運行時容易出現(xiàn)晚點情況。列車間運行秩序可能受到晚點擾亂,且由于列車運行線之間的關(guān)聯(lián)性及整體性,列車晚點往往會向后傳播[1],因而調(diào)度人員需要根據(jù)具體情況進行晚點恢復(fù)調(diào)整。在編制列車運行圖時,編圖人員往往會預(yù)留緩沖時間,以備列車運行調(diào)整及晚點恢復(fù)。設(shè)置合理的緩沖時間既可以有效抑制晚點傳播,還可以有效避免冗余浪費。
在列車運行圖實際編制過程中,緩沖時間的設(shè)置具有重點取向,設(shè)置的優(yōu)劣主要取決于編圖人員的經(jīng)驗和技術(shù)水平[2-3]。國內(nèi)外既有文獻對緩沖時間的研究主要基于晚點延誤、晚點恢復(fù)等指標(biāo),運用概率論,采用計算機仿真技術(shù)進行研究,從隨機模擬的結(jié)果來推導(dǎo)必要的緩沖時間[4-7],但因?qū)嶋H情況下晚點延誤的復(fù)雜性與不可控性,估計結(jié)果可能會出現(xiàn)偏差[8]。國內(nèi)學(xué)者對列車運行圖緩沖時間的研究多集中在高速鐵路[9-10],對普速鐵路列車運行圖緩沖時間優(yōu)化分配的研究較少。相比高速鐵路,普速鐵路受天氣和設(shè)備因素影響產(chǎn)生晚點的可能性更大,同時由于普速鐵路線路實行“客貨混跑”,開行多速度等級列車,結(jié)合我國國情、路情,普速鐵路列車運行圖緩沖時間優(yōu)化分配是亟待研究的問題。
針對普速鐵路緩沖時間優(yōu)化分配問題,首先利用壓縮列車運行圖思想,建立列車運行圖壓縮模型,獲取列車運行圖中可利用的總緩沖時間容量。然后,基于列車運行線協(xié)同優(yōu)化思想,建立列車運行圖緩沖時間優(yōu)化分配模型,優(yōu)化列車運行圖緩沖時間分配和布局。最后,重點分析緩沖時間價值計算方法,設(shè)計貪心算法求解緩沖時間優(yōu)化模型,并結(jié)合案例進行驗證。
列車運行圖緩沖時間分為列車區(qū)間運行緩沖時間、車站作業(yè)緩沖時間和其他緩沖時間。由于各部分作業(yè)之間存在內(nèi)在相互依賴性,對單個作業(yè)時間進行緩沖可能與其他作業(yè)時間產(chǎn)生沖突。因此,從列車運行圖的整體結(jié)構(gòu)出發(fā),將緩沖時間定義為在列車運行圖中列車圖定作業(yè)時分與標(biāo)準(zhǔn)作業(yè)時分之間的差值[11]。
通過以下例子說明緩沖時間分配的作用。設(shè)計由A,B,C,D,E共5個車站組成的列車運行圖簡圖,未分配緩沖時間情形簡單案例如圖1所示,相鄰列車在滿足追蹤間隔時間的條件下運行。當(dāng)10001次貨物列車在E站發(fā)生初始晚點后,考慮后方高等級列車的準(zhǔn)時性與正點率條件下,在D站進行越行作業(yè),最終導(dǎo)致10001次貨物列車在A站晚點抵達(dá)。為預(yù)防該晚點發(fā)生或是減輕后續(xù)晚點傳播現(xiàn)象,在10001次貨物列車與Z3次旅客列車間適當(dāng)插入緩沖時間,以提高列車運行圖抗干擾能力,分配緩沖時間情形簡單案例如圖2所示。
圖1 未分配緩沖時間情形簡單案例Fig.1 Simple case without buffer time allocation
圖2 分配緩沖時間情形簡單案例Fig.2 Simple case with buffer time allocation
普速鐵路列車運行圖緩沖時間優(yōu)化分配問題研究為在已知列車定序運行,列車種類、數(shù)量、圖定運行速度與實際運行速度條件下,綜合列車運行線間安全運行因素,采用協(xié)同優(yōu)化思想,確定最佳緩沖時間分配方案。
根據(jù)普速鐵路列車運行圖鋪畫實踐,提出以下假設(shè):①不考慮列車越行情況,即列車運行圖中列車順序保持不變。②不考慮列車起停附加時分對緩沖時間分配的影響。③不考慮天窗對列車運行圖緩沖時間分配的影響。④不考慮閉塞方式對緩沖時間分配的影響。
在列車運行圖緩沖時間優(yōu)化分配時,首先建立列車運行圖壓縮模型,通過壓縮既有列車運行圖,得到每個區(qū)間緩沖時間總?cè)萘?。然后建立緩沖時間優(yōu)化分配模型,確定列車運行圖中各區(qū)間緩沖時間優(yōu)化分配的位置及數(shù)量。
通常用事件—活動網(wǎng)絡(luò)圖G=(E,A)來表示列車運行圖中列車的各項作業(yè)及相互之間關(guān)系,在整體層面上對列車運行圖建模。其中,節(jié)點E表示事件為列車車站作業(yè)的集合,弧線(有向弧)A表示過程為列車運行過程,模型中只包括在車站中發(fā)生的事件。令A(yù)run,Adwell,Ahead,Acon分別為列車在區(qū)間運行、列車停站、列車追蹤間隔、列車接續(xù)時間集合。令ai,j表示事件—活動網(wǎng)絡(luò)圖G中任一列車活動,ai,j∈A。ai,j由2個列車車站作業(yè)i,j構(gòu)成,i,j∈E,其中ti,j為列車圖定活動時間,為列車最小活動時間[9]。通過壓縮列車運行圖的方法,得到每個區(qū)間的總緩沖時間容量,壓縮列車運行圖簡單示例如圖3所示。
圖3所示簡例表示在滿足列車在運行圖中各項作業(yè)安全完成的情況下,通過壓縮車站作業(yè)時間、列車追蹤間隔時間與列車區(qū)間運行時間,得到壓縮的列車運行圖。根據(jù)上述緩沖時間定義可以計算運行圖中每列車的緩沖時間,得出列車運行圖每個區(qū)間緩沖時間容量。
圖3 壓縮列車運行圖簡單示例Fig.3 Simple example for a compressed train timetable
為充分利用列車運行圖能力,以得出列車運行圖中緩沖時間容量最大為目標(biāo),建立列車運行圖壓縮模型,目標(biāo)函數(shù)如公式(1)所示,約束條件如公式(2)至公式(5)所示。模型中,公式(2)、公式(3)表示列車運行線定序約束,即作業(yè)時間范圍約束,公式(4)表示列車區(qū)間最小運行時分與車站最小作業(yè)時間約束,公式(5)表示列車之間的最小發(fā)車間隔時間約束。
列車運行圖壓縮模型可以壓縮得到列車運行圖中各區(qū)間緩沖時間容量,可將壓縮后相鄰列車運行線間的作業(yè)間隔時間區(qū)域視為可分配緩沖時間的候選位置,然后使緩沖時間優(yōu)化分配至此候選位置中。將整個事件—活動網(wǎng)絡(luò)圖G =(E,A)中緩沖時間分配問題建模轉(zhuǎn)化為背包問題模型。定義在可分配緩沖時間位置的緩沖時間容量為wn,對應(yīng)的價值為Pn。背包問題模型如公式(6)和公式(7)所示,公式(6)為目標(biāo)函數(shù),公式(7)為背包容量限制約束。
式中:xn為0-1變量,如果第n個容量背包被選擇,則xn等于1,否則等于0;S表示列車運行圖中區(qū)間的集合;wn,s為各個區(qū)間分配緩沖時間位置的緩沖時間容量。
緩沖時間的設(shè)置目的是預(yù)防晚點發(fā)生或降低晚點傳播,在同一位置多次分配緩沖時間的效用呈現(xiàn)遞減規(guī)律,即當(dāng)首次分配緩沖時間后,再分配給該位置緩沖時間時,緩沖時間的作用價值應(yīng)降低,故引入效用函數(shù)。既有研究表明,指數(shù)分布可以很好地擬合列車晚點時間的概率分布,因而在目標(biāo)函數(shù)中引入指數(shù)分布函數(shù)作為效用函數(shù),表示緩沖時間可作用于初始晚點產(chǎn)生或晚點傳播的概率[10]。同時,為在緩沖時間分配時充分體現(xiàn)效用函數(shù)的作用,以1min為間隔將緩沖時間離散化處理,引入變量m表示緩沖時間的等分間隔,即運行圖中設(shè)置的緩沖時間總?cè)萘康扔趍min內(nèi)的緩沖時間之和。對緩沖時間離散化處理如公式(8)至公式(10)所示,效用函數(shù)如公式(11)所示。
式中:λ為大于1的常數(shù),其值與線路中相鄰列車之間的區(qū)間總運行時分之比成正相關(guān)。
綜上,以緩沖時間的效用最大化為目標(biāo)函數(shù),建立緩沖時間優(yōu)化分配模型如公式(12)至公式(14)所示。公式(12)為緩沖時間分配優(yōu)化模型的目標(biāo)函數(shù),公式(13)為每個維度區(qū)間緩沖時間優(yōu)化分配不超過該區(qū)間緩沖時間的總量約束,公式(14)為分配第(m+1)min時,前mmin必須被分配約束。
式中:xn,m為0-1變量,表示第n個緩沖時間選擇區(qū)域里的第mmin被分配,被分配則為1,否則為0。
此外,還要考慮列車運行圖中運行線間隔約束及停站時間約束,停站時間約束如公式(15)所示,列車運行線間隔約束如公式(16)和公式(17)所示。
在求解緩沖時間優(yōu)化分配模型前,需要先明確各個候選位置緩沖時間對應(yīng)的價值,用以確定該位置需要設(shè)置緩沖時間的重要程度。由于我國普速鐵路采用不同速度等級列車共線運行的模式,發(fā)生列車晚點后,不同速度等級或相同速度等級但運行范圍不同的列車受到的影響程度存在差異。因此,有必要結(jié)合不同等級列車在不同候選位置設(shè)置緩沖時間的重要程度,對緩沖時間對應(yīng)的價值Pn,m的計算進行研究。
對各次列車分配緩沖時間的重要程度進行換算統(tǒng)一處理,以體現(xiàn)相鄰列車間設(shè)置緩沖時間造成的影響。不僅需要考慮每一列車在運行中產(chǎn)生晚點可能影響后續(xù)列車,同時還應(yīng)考慮該列車的前行車發(fā)生晚點對其可能產(chǎn)生的影響。可能的權(quán)重情況分析如下。
(1)列車等級權(quán)重系數(shù)。將普速鐵路列車等級分為直達(dá)特快旅客列車、直通特快旅客列車、跨局快速旅客列車、普快旅客列車、普客列車、普慢列車與貨物列車等5個等級[2]。由于實際運行中高等級列車應(yīng)優(yōu)先分配緩沖時間,定義T為不同列車等級的權(quán)重,取直達(dá)特快旅客列車等級為5,依此類推,則貨物列車等級為1。即T∈ {1,2,3,4,5}。
(2)相鄰列車間開行方式權(quán)重系數(shù)。由于相鄰2列車之間存在運行速差,因而相鄰2列車的開行方式具有較大的區(qū)別,不同的列車開行方式導(dǎo)致列車運行圖結(jié)構(gòu)不同,將會產(chǎn)生列車運行圖冗余時間,相鄰列車在不同情況下影響示意圖如圖4所示,圖中b表示緩沖時間。
分析列車運行圖相鄰列車在速差不同情況下對緩沖時間分配的影響,圖4a中后行列車與前行列車存在速差形成的“冗余”時間為Δb,當(dāng)前行列車在該區(qū)間發(fā)生晚點后,可利用該時間進行晚點恢復(fù)調(diào)整,因而此“緩沖”可起到預(yù)防或降低列車在區(qū)間運行晚點的效果;圖4b中前行列車和后行列車運行速度相同,不會產(chǎn)生由前后行列車速差形成的該類緩沖時間Δb;圖4c中由前行列車與后行列車速差形成的“冗余”時間Δb,當(dāng)前行列車在區(qū)間發(fā)生晚點時,該“冗余”時間Δb在沒有起到緩沖作用的同時,還會造成無效浪費。因此相較圖4a和圖4b的列車運行情況,圖4c情況對列車運行晚點恢復(fù)的影響最嚴(yán)重。
圖4 相鄰列車在不同情況下影響示意圖Fig.4 Influence of adjacent trains in different situations
考慮相鄰列車開行方式對晚點的影響,定義α為前后行列車不同等級下緩沖時間的分配權(quán)重,根據(jù)前行列車晚點對后行列車的影響程度,取α∈ {1, 2,3}分別為前后行列車不同開行方式下的緩沖時間權(quán)重。
(3)相鄰列車間的間隔時間權(quán)重系數(shù)。相鄰列車運行受晚點影響的程度,除上述不同速差情況下的影響外,還與列車之間的間隔時間有關(guān)。例如:相鄰列車間追蹤間隔時間越短,發(fā)生晚點后,產(chǎn)生的延誤影響越大。定義列車之間緩沖時間相互影響關(guān)系如公式(18)所示。
式中:R為影響系數(shù);λ為大于1的常數(shù),其值與線路中相鄰列車間的區(qū)間運行時分之比成正相關(guān);λT后-T前 為后行列車對該列車影響大于前行列車對該列車影響;λT前-T后 為前行列車對該列車影響大于后行列車對該列車影響;T前為前行列車等級,T前∈ {1,2,3,4,5};T后為后行列車等級,T后∈ {1, 2,3,4,5}。
指數(shù)分布可以良好地擬合列車晚點時間的概率分布[9]。理想情況下,優(yōu)化分配的緩沖時間可以恰好抵消晚點延誤時間,利用該分布可計算列車運行圖中每個位置分配緩沖時間的期望。概率函數(shù)如公式(19)所示。
式中:Q為每個位置分配緩沖時間的期望。
綜上,設(shè)置緩沖時間的價值Pn,m的計算方法如公式(20)所示。
式中:Q為每個位置分配緩沖時間的期望;R為影響系數(shù);α為前后行列車不同開行方式下的緩沖時間權(quán)重。
針對建立的列車運行圖緩沖時間優(yōu)化分配模型,采用貪心算法求解。首先求解列車運行圖壓縮模型作為該問題的初始解,再運用貪心算法對緩沖時間優(yōu)化分配模型求解得到優(yōu)化后列車運行圖。貪心算法的核心思想是找出整體當(dāng)中每個局部的最優(yōu)解,并且將所有的局部最優(yōu)解合起來形成整體上的最優(yōu)解。主要計算步驟如下。
步驟1:把求解的問題分成若干子問題。將列車運行圖中總體緩沖時間優(yōu)化分配問題分解為各區(qū)間緩沖時間優(yōu)化分配問題。
步驟2:尋找初始解。利用列車運行圖壓縮模型求解各區(qū)間緩沖時間分配的初始數(shù)值作為初始解。通過鐵路列車運行圖編制系統(tǒng)求解列車運行圖壓縮模型,求得各區(qū)間緩沖時間初始數(shù)值。
步驟3:計算局部最優(yōu)解。利用緩沖時間優(yōu)化分配模型對問題進行求解,得到各區(qū)間緩沖時間優(yōu)化分配局部最優(yōu)解后,將局部最優(yōu)解整合為全局最優(yōu)解;當(dāng)多個位置同時出現(xiàn)價值Pn,m最大時,設(shè)計將緩沖時間分配到最后位置,并將多個位置同時利用效用函數(shù)進行迭代,即可滿足緩沖時間在列車運行線群的分配情況,也可防止緩沖時間分配時可能造成過多分配緩沖時間的情況。
步驟4:對計算結(jié)果進行判斷。將計算得到的緩沖時間放入列車運行圖中,判斷是否滿足停站時間約束、列車運行線間安全約束等,滿足各項約束情況下的最優(yōu)解即為最終解。否則,需對計算得到的解進行調(diào)整,直到滿足各項約束條件。
以隴海線隴西—蘭州東區(qū)段下行方向列車運行圖為例進行案例分析,選取2020年第4季度列車運行圖9 : 00—14 : 00為研究時段。根據(jù)列車運行圖壓縮模型計算緩沖時間容量,根據(jù)圖定作業(yè)取相鄰列車追蹤間隔時間為6min;直達(dá)特快旅客列車、直通特快旅客列車速度為120 km/h,跨局快速旅客列車速度為110 km/h,普快旅客列車速度為100 km/h,普慢旅客列車與貨物列車速度為90 km/h;列車在特等、一等、二等、三等、四等及中間站的最短作業(yè)時間分別為8min,6min, 4min,2min,2min和1min;λ取1.3。既有列車運行圖如圖5所示。
圖5 既有列車運行圖Fig.5 Existing train timetable
運用鐵路列車運行圖編制系統(tǒng)計算列車運行圖壓縮模型得到緩沖時間初始分配情況,各區(qū)間緩沖時間分配表如表1所示。表1中定西站車站緩沖時間包含在景家店—定西區(qū)間,從表1中可得出緩沖時間分配數(shù)值與列車等級成正比,通過壓縮列車運行圖模型計算出緩沖時間的總量為258min。
表1 各區(qū)間緩沖時間分配表 minTab.1 Buffer time allocation for each interval
根據(jù)緩沖時間初始價值計算方法,得到選取研究時段內(nèi)列車運行圖中各列車的初始價值,緩沖時間初始價值表如表2所示。X8015/6/5次和X8155次列車在定西—蘭州東區(qū)段的各區(qū)間中價值均為1.10400,表示所分配緩沖時間的重要程度最大;最小為T112/3次列車在定西—梁家坪區(qū)間權(quán)重0.00020。
表2 緩沖時間初始價值表Tab.2 Initial value of buffer time
運用貪心算法計算緩沖時間優(yōu)化分配模型得到每個位置優(yōu)化后的緩沖時間,優(yōu)化后新生成列車運行圖的緩沖時間總量為 227min,總價值約為32。緩沖時間分配后的列車運行圖如圖6所示。由表1可知,每列車在各區(qū)間所設(shè)置的緩沖時間與列車等級相關(guān),高等級列車在各區(qū)間緩沖時間較多,當(dāng)列車發(fā)生晚點延誤時,可有效地進行晚點延誤恢復(fù),低等級列車在發(fā)生晚點延誤時,較易產(chǎn)生晚點傳播情況。優(yōu)化后緩沖時間分配表如表3所示。比較表1與表3中的數(shù)據(jù)可知,每列車所需緩沖時間并不絕對與列車等級相關(guān)。在實際列車運行圖執(zhí)行過程中,先需確保高等級列車正點運行,但同樣也不能忽視低等級列車的正點率,且緩沖時間并不絕對與列車等級成正比關(guān)系,而是與相鄰列車運行線的時空布置有關(guān)。例如表1中Z292/3次、X8015/6/5次、X8155次列車在各區(qū)間所擁有緩沖時間與表3有明顯變化。結(jié)合圖5與圖6可知,此相鄰列車之間通過重新分配緩沖時間后,列車運行線時空分布發(fā)生變化,可以提升預(yù)防晚點延誤的能力。各區(qū)間緩沖時間容量優(yōu)化前后對比表如表4所示。
表3 優(yōu)化后緩沖時間分配表 minTab.3 Buffer time allocation after optimization
圖6 緩沖時間分配后的列車運行圖 Fig.6 Train timetable after buffer time allocation
在表4中,優(yōu)化前的緩沖時間是通過列車運行圖壓縮模型得到的各區(qū)間總的緩沖時間容量,優(yōu)化后的緩沖時間是通過緩沖時間優(yōu)化分配模型得到的實際分配到各個區(qū)間的緩沖時間容量。例如許家臺—夏官營區(qū)間通過列車運行圖壓縮模型得到總緩沖時間為26min,運用緩沖時間優(yōu)化分配模型實際分配緩沖時間為18min。對比優(yōu)化前后緩沖時間總?cè)萘?,?yōu)化后緩沖時間總?cè)萘繛?27min,較優(yōu)化前減少31min,且滿足緩沖時間優(yōu)化分配模型約束,可有效避免分配緩沖時間造成的列車運行圖能力浪費。優(yōu)化前后各列車緩沖時間分配表如表5所示,優(yōu)化前后各列車緩沖時間分配趨勢對比圖如圖7所示。
表4 各區(qū)間緩沖時間容量優(yōu)化前后對比表minTab.4 Comparison of buffer time capacity at each interval before and after optimization
由表5和圖7可知,優(yōu)化前既有列車運行圖中Z126/7次—Z292/3次列車之間的列車發(fā)生晚點時,具有較充足的緩沖時間進行晚點恢復(fù),而X8015/6/5次—X208/5次列車之間的列車可利用緩沖時間較少,當(dāng)列車按照優(yōu)化前列車運行圖運行時,若在Z126/7次—Z292/3次列車之間不發(fā)生晚點,在X8015/6/5次—X208/5次列車之間發(fā)生晚點時,將會使Z126/7次—Z292/3次列車之間設(shè)置的緩沖時間大量浪費,并且在X8015/6/5次—X208/5次列車之間可能會出現(xiàn)緩沖時間不充足的情況。優(yōu)化后對該時段所有列車來說,可用緩沖時間整體呈現(xiàn)增長趨勢,當(dāng)前行列車發(fā)生晚點時,后行列車可用緩沖時間增多,能夠增加列車運行圖的魯棒性,可避免在列車發(fā)生晚點延誤時向后大規(guī)模傳播,同時有效地防止在列車運行圖前端過多鋪設(shè)緩沖時間造成浪費。結(jié)合圖6與表5可知,通過緩沖時間優(yōu)化分配模型求解,充分利用了列車運行圖結(jié)構(gòu)產(chǎn)生的冗余時間,如:Z126/7次列車運行線在圖中與后行列車間本身存在冗余時間,繼續(xù)對該列車設(shè)置緩沖時間會造成冗余浪費。
圖7 優(yōu)化前后各列車緩沖時間分配趨勢對比圖Fig.7 Comparison of buffer time allocation trend for each train before and after optimization
表5 優(yōu)化前后各列車緩沖時間分配表minTab.5 Buffer time allocation for each train before and after optimization
對比優(yōu)化前后列車運行圖,優(yōu)化前后列車開行方式發(fā)生改變,如Z292/3次與X8015/6/5次列車在隴西—云田鄉(xiāng)的開行方式,優(yōu)化前Z292/3次與X8015/6/5次列車的關(guān)系為前行小于后行(如圖4 c),優(yōu)化后通過重新分配緩沖時間,Z292/3次與X8015/6/5次列車的關(guān)系在隴西—云田鄉(xiāng)區(qū)間為前行等于后行(如圖4 b),在云田鄉(xiāng)—夏官營區(qū)間變?yōu)榍靶写笥诤笮?如圖4 a),列車運行圖結(jié)構(gòu)產(chǎn)生的空費時間減少。優(yōu)化前X8015/6/5次與X8155次列車在定西—梁家坪區(qū)間的追蹤間隔時間為7min 30 s,列車極易在該區(qū)間發(fā)生晚點,且當(dāng)前行X8015/6/5次列車發(fā)生晚點后,直接會將晚點延誤傳播至后行X8155次列車。優(yōu)化后2列車在該區(qū)間的追蹤間隔時間為10min,提高了該相鄰列車運行線之間的抗干擾能力。
為提高列車運行圖的抗干擾能力,基于緩沖時間優(yōu)化分配的思想,在列車運行圖壓縮模型基礎(chǔ)上,提出緩沖時間優(yōu)化分配模型。相比于傳統(tǒng)列車運行圖緩沖時間優(yōu)化方法,引入效用函數(shù),達(dá)到避免過多分配緩沖時間造成能力浪費的目的,同時分析不同情況下設(shè)置緩沖時間的重要程度,設(shè)計緩沖時間價值和模型求解方法。案例分析結(jié)果表明,在優(yōu)化后的列車運行圖中,緩沖時間的分布較優(yōu)化前更為合理,呈現(xiàn)在圖中列車運行線的時空分布更趨于均衡,且列車運行圖本身結(jié)構(gòu)導(dǎo)致的空費時間減少,有效提高了列車運行圖的抗干擾能力。但是,該方法僅考慮了列車定序運行的情況,沒有考慮列車越行對緩沖時間分配的影響,還應(yīng)進一步研究考慮列車越行情況的緩沖時間優(yōu)化方法。