王宇強(qiáng)，魏玉光，林 楓

(1.中國鐵道科學(xué)研究院集團(tuán)有限公司 運(yùn)輸及經(jīng)濟(jì)研究所， 北京 100081；2.北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044)

近年來，我國高速鐵路(以下簡稱“高鐵”)迅猛發(fā)展，客運(yùn)需求逐年攀升，形成了以“四縱四橫”為基礎(chǔ)的高鐵路網(wǎng)，且我國高鐵運(yùn)營情況復(fù)雜，不同速度等級的本線及跨線列車混合運(yùn)行，如何準(zhǔn)確計(jì)算高鐵通過能力且在有限的時(shí)空資源內(nèi)開行更多的列車成為亟需解決的問題。

目前關(guān)于高鐵通過能力計(jì)算的研究主要為扣除系數(shù)法[1]、平均最小列車間隔時(shí)間法[2]、計(jì)算機(jī)模擬法[3-4]和基于UIC 406的運(yùn)行圖壓縮及加密法[5]，但現(xiàn)有研究或沿用既有線通過能力計(jì)算方法，或采用國外的通過能力計(jì)算法，或在計(jì)算過程中沒有考慮占比較大的跨線列車，從而可能導(dǎo)致計(jì)算結(jié)果不夠精確。高鐵運(yùn)行圖鋪畫問題，可視為多商品流問題，列車作為商品占用高鐵有限的時(shí)空資源，目標(biāo)函數(shù)一般為最小化列車運(yùn)行(等待)時(shí)間，最小化重新鋪畫后列車運(yùn)行圖與現(xiàn)有運(yùn)行圖的差異，最大化運(yùn)營收益和最大化列車開行數(shù)。在解決運(yùn)行圖鋪畫問題的小規(guī)模案例時(shí)，可采用商業(yè)求解器(如CPLEX)得到精確解，但當(dāng)處理大規(guī)模案例時(shí)，必須使用啟發(fā)式算法或分解算法來求解模型，目前使用較多的分解算法包括：拉格朗日松弛法、ADMM、列生成法、D-W分解法等。文獻(xiàn)[6-7]基于累計(jì)流變量模型鋪畫列車運(yùn)行圖，使用拉格朗日松弛算法求解；文獻(xiàn)[8]構(gòu)建擴(kuò)展時(shí)空網(wǎng)絡(luò)以解決周期運(yùn)行圖問題，采用ADMM分解算法求解；文獻(xiàn)[9]構(gòu)建整數(shù)規(guī)劃模型，在鋪畫列車運(yùn)行圖的同時(shí)考慮客流需求，最后采用列生成算法求解；文獻(xiàn)[10]提出一種整數(shù)規(guī)劃模型來鋪畫列車運(yùn)行圖，旨在最大化運(yùn)營收益，設(shè)計(jì)了啟發(fā)式算法求解；文獻(xiàn)[11]以最大化列車開行數(shù)為目標(biāo)鋪畫列車運(yùn)行圖，構(gòu)建整數(shù)規(guī)劃模型，采用D-W分解法求解。

以上研究對車站因素的影響仍采用傳統(tǒng)的簡化處理方法，尤其是繁忙干線上銜接多方向的高鐵樞紐，本線列車與跨線列車混合運(yùn)行沖突干擾產(chǎn)生的影響未能得到深入研究，導(dǎo)致高鐵列車運(yùn)行圖編制質(zhì)量難以突破樞紐瓶頸的制約。文獻(xiàn)[12]注意到這一問題的重要性，但未能提出具體有效的量化解決方法。文獻(xiàn)[13]將車站設(shè)定為虛擬區(qū)間，提出基于點(diǎn)線一體化的高鐵通過能力計(jì)算方法，在此基礎(chǔ)上，本文研究將高鐵樞紐這一虛擬區(qū)間內(nèi)的通過能力利用細(xì)化為被各種列車弧占用的描述方法，以站場實(shí)際布局和列車徑路疏解方式為基本依據(jù)，將不同方向列車在跨線樞紐站的沖突用車站最小列車間隔時(shí)間來表示，構(gòu)建目標(biāo)函數(shù)為最大化列車開行數(shù)量的整數(shù)規(guī)劃模型，采用ADMM將復(fù)雜的列車組合優(yōu)化問題分解為尋找單個(gè)列車的最短路問題，從而獲得各方向列車在跨線樞紐接發(fā)和通過的最佳配合方式，最后得到更符合實(shí)際情況的運(yùn)行圖鋪畫結(jié)果。

1 問題描述

符號及其定義見表1。

表1 符號說明

本文進(jìn)一步從優(yōu)化高鐵樞紐跨線列車運(yùn)行組織的角度研究高鐵運(yùn)行圖鋪畫問題，力求在有限的高鐵時(shí)空資源中開行更多列車，進(jìn)而計(jì)算高鐵通過能力。高鐵物理網(wǎng)(N,L)見圖1(a)，包括車站集合N和運(yùn)行區(qū)段集合L。為方便表示列車在物理網(wǎng)中的各種作業(yè)過程，采用文獻(xiàn)[13]提出的方法構(gòu)建虛擬區(qū)間，將一個(gè)車站拆分為若干物理點(diǎn)，將物理網(wǎng)擴(kuò)展為服務(wù)網(wǎng)(N′,A)，擴(kuò)展后的高鐵服務(wù)網(wǎng)見圖1(b)，包括物理點(diǎn)集合N′和物理弧集合A，列車在服務(wù)網(wǎng)中的作業(yè)過程(列車停站、列車運(yùn)行和列車跨線等)為弧(i,j)∈A，表示列車從物理點(diǎn)i∈N′到物理點(diǎn)j∈N′。將起點(diǎn)站拆分為列車虛擬起點(diǎn)、列車到達(dá)點(diǎn)和列車出發(fā)點(diǎn)；將終點(diǎn)站拆分為列車到達(dá)點(diǎn)、列車出發(fā)點(diǎn)和列車虛擬終點(diǎn)；將其他車站拆分為列車虛擬起點(diǎn)、列車到達(dá)點(diǎn)、列車出發(fā)點(diǎn)和列車虛擬終點(diǎn)。車站的拆分過程及各類弧的構(gòu)建見圖1(b)，列車生成弧、列車到達(dá)弧、列車停站弧、列車跨線弧以及列車運(yùn)行弧分別表示列車生成、列車消失、列車停站作業(yè)、列車跨線作業(yè)以及列車運(yùn)行?？缇€列車在跨線站2只能通過跨線弧到達(dá)車站4。

圖1 高鐵物理網(wǎng)與服務(wù)網(wǎng)的構(gòu)建

時(shí)空網(wǎng)可以很好地反映列車在路網(wǎng)中的時(shí)空路徑，被廣泛應(yīng)用于列車運(yùn)行圖鋪畫研究中。本文在高鐵服務(wù)網(wǎng)的基礎(chǔ)上，引入時(shí)間維度，構(gòu)建高鐵時(shí)空網(wǎng)(V,A′)，其中V由物理點(diǎn)i∈N′擴(kuò)展為時(shí)空頂點(diǎn)(i,t)∈V，表示列車在t時(shí)刻位于物理點(diǎn)i，A′由物理弧(i,j)∈A擴(kuò)展為時(shí)空弧(i,j,t,s)∈A′，表示列車由頂點(diǎn)(i,t)移動到頂點(diǎn)(j,s)，作業(yè)時(shí)間為s-t。服務(wù)網(wǎng)中各類物理弧可以擴(kuò)展為以下5種時(shí)空?。?/p>

為了更好地描述列車運(yùn)行過程且保證模型的可行性，構(gòu)建以下2種?。?/p>

時(shí)空網(wǎng)中列車停站弧，列車跨線弧和列車運(yùn)行弧的費(fèi)用ci,j,t,s為實(shí)際作業(yè)時(shí)間，列車生成弧及列車到達(dá)弧的費(fèi)用ci,j,t,s為0，列車虛擬運(yùn)行弧的費(fèi)用為無限大?；趫D1(b)的高鐵時(shí)空網(wǎng)中各類時(shí)空弧的構(gòu)建以及不同速度等級的本線及跨線列車在時(shí)空網(wǎng)中的路徑選擇見圖2，同理可構(gòu)建另一方向的時(shí)空弧。

圖2 時(shí)空網(wǎng)的構(gòu)建及列車的路徑選擇

圖3 沖突弧集的構(gòu)建

圖4 跨線站站場布局及列車進(jìn)路

表2 列車在跨線站的最小列車間隔時(shí)間

2 模型構(gòu)建

本節(jié)基于高鐵時(shí)空網(wǎng)構(gòu)建鋪畫列車運(yùn)行圖的整數(shù)規(guī)劃模型，模型的輸入為：①高鐵物理網(wǎng)；②列車開行方案；③基礎(chǔ)數(shù)據(jù)：如列車最大最小停站時(shí)間、各種最小列車間隔時(shí)間、列車在各區(qū)間的運(yùn)行時(shí)間等。模型的輸出為：列車運(yùn)行圖、通過能力。

模型的目標(biāo)函數(shù)為最大化列車選擇運(yùn)行弧的數(shù)量，即最大化列車開行數(shù)，即

( 1 )

為提高模型解的質(zhì)量且方便算法求解，將式( 1 )轉(zhuǎn)換為

( 2 )

通過阻止列車選擇虛擬運(yùn)行弧(即最小化列車選擇時(shí)空弧的總費(fèi)用)來最大化列車開行數(shù)，同時(shí)還可以最小化列車運(yùn)行費(fèi)用。模型的約束條件為

( 3 )

( 4 )

Depmin(k)≤DT(k)≤Depmax(k)

( 5 )

( 6 )

( 7 )

本文提出的模型為典型的NP-hard模型，復(fù)雜度較高。為直觀地展示模型規(guī)模，模型中變量和各約束的數(shù)量見表3，由于式( 3 )～式( 5 )可以歸并到式( 6 )中，因此式( 6 )和式( 7 )的數(shù)量見表3。

表3 模型規(guī)模

3 基于ADMM的分解算法

本文研究的列車運(yùn)行圖鋪畫問題實(shí)質(zhì)上是將有限的時(shí)空資源分配給不同列車的多商品流問題，當(dāng)案例規(guī)模較小時(shí)，可以使用商業(yè)求解器，如CPLEX，直接求得精確解。但當(dāng)研究案例很大時(shí)，商業(yè)求解器不能在有效時(shí)間內(nèi)求得最優(yōu)解，所以提出使用分解算法將原問題分解為若干獨(dú)立子問題進(jìn)行求解。本文使用的ADMM分解算法是增廣拉格朗日松弛算法與塊坐標(biāo)下降法的結(jié)合。其中，增廣拉格朗日松弛算法是在拉格朗日松弛算法的基礎(chǔ)上引入困難約束的二次懲罰項(xiàng)，可以提高模型的魯棒性，但是二次項(xiàng)的引入會使模型非線性化，需要結(jié)合使用塊坐標(biāo)下降法處理該二次項(xiàng)，將運(yùn)行圖鋪畫問題分解為單個(gè)列車的最短路問題。

模型中安全約束式( 7 )會引起列車的大規(guī)模組合，其他約束都只針對單個(gè)列車。將式( 7 )作為懲罰項(xiàng)放入目標(biāo)函數(shù)式( 2 )中，新的目標(biāo)函數(shù)為

( 8 )

式中：q為弧(i,j,t,s)；ρ為二次項(xiàng)懲罰乘子；μq為拉格朗日懲罰乘子，其迭代方法為次梯度法，即

( 9 )

(10)

(11)

則二次懲罰項(xiàng)轉(zhuǎn)化為

(12)

其中當(dāng)πk≥1時(shí)，二次懲罰項(xiàng)的推導(dǎo)過程為

(13)

代入目標(biāo)函數(shù)式( 8 )中，通過合并同類項(xiàng)得到

(14)

式中：Q為一個(gè)常數(shù)。

新的費(fèi)用更新為

(15)

最后，經(jīng)過ADMM分解的模型變?yōu)椋耗繕?biāo)函數(shù)式(14)，約束條件式( 6 )?？梢娦履Ｐ椭懈髁熊囅嗷オ?dú)立，原問題可被分解為若干獨(dú)立的最短路子問題，各子問題可通過動態(tài)規(guī)劃求解。在每次迭代求解過程中依次為列車集合K={1,2,3,…，k,…，n}中的列車尋找最短路，n為k中列車的數(shù)量，當(dāng)鋪畫列車k的運(yùn)行線時(shí)，固定其他列車的決策變量解，以此循環(huán)。

基于ADMM分解算法的步驟為：

Step2通過動態(tài)規(guī)劃算法為每列車尋找最短路徑，用式(15)計(jì)算弧的費(fèi)用，得到?jīng)Q策變量解集{xg}。

Step5使用式( 9 )更新拉格朗日乘子。

Step6如果迭代次數(shù)達(dá)到預(yù)先設(shè)定的最大迭代次數(shù)，結(jié)束算法，否則，返回Step2，g=g+1。

4 案例分析

以我國太原—德州高鐵和鄭州—北京高鐵路網(wǎng)為例，同時(shí)鋪畫生成兩條線路的本線及跨線列車運(yùn)行圖，驗(yàn)證模型及算法的可行性。提出的算法在Python平臺上實(shí)現(xiàn)，算法運(yùn)行環(huán)境為一臺內(nèi)存16 GB，CPU：i7-770HQ 2.80 GHz的臺式計(jì)算機(jī)。

太原—德州及鄭州—北京高鐵共設(shè)23個(gè)車站，兩條線路的交匯車站石家莊站為跨線站，10個(gè)方向的列車(太原—德州、德州—太原、鄭州—北京、北京—鄭州、太原—北京、北京—太原、太原—鄭州、鄭州—太原、鄭州—德州、德州—鄭州)在石家莊站可能會產(chǎn)生進(jìn)路沖突，石家莊站的站場圖及各方向列車在石家莊站的列車徑路見圖5，不同方向列車在石家莊站的最小列車間隔時(shí)間見表4。根據(jù)現(xiàn)有列車運(yùn)行圖，只有太原—德州、德州—太原、太原—北京、北京—太原方向有“D”字頭列車，其他方向列車均為“G”字頭列車，列車在各運(yùn)行區(qū)段的運(yùn)行時(shí)間見表5。設(shè)置案例的總時(shí)長為600 min，即時(shí)空網(wǎng)的時(shí)間跨度為600 min，離散化后的單位時(shí)間刻度為1 min。本文將跨線列車列入研究對象，為突出跨線列車的影響且精確量化跨線列車的開行比例，假設(shè)各列車的起點(diǎn)站和終點(diǎn)站都為太原、德州、北京和鄭州，所以各方向列車數(shù)量根據(jù)現(xiàn)有運(yùn)行圖比例輸入為：太原—德州7列，德州—太原7列，太原—北京18列，北京—太原18列，太原—鄭州5列，鄭州—太原5列，鄭州—德州6列，德州—鄭州6列，鄭州—北京40列，北京—鄭州40列。設(shè)置各最小列車間隔時(shí)間ha=3 min，hd=3 min，had=2 min，hda=2 min。

圖5 石家莊站站場圖及各方向列車徑路

表4 不同方向列車在石家莊站的最小列車間隔時(shí)間

表5 列車在各運(yùn)行區(qū)段的運(yùn)行時(shí)間 min

4.1 計(jì)算結(jié)果與分析計(jì)算法的對比分析

文獻(xiàn)[13]提出的通過能力計(jì)算方法是在已知列車開行方案和運(yùn)行圖的前提下用來評估當(dāng)下通過能力利用情況的一種方法，計(jì)算過程較本節(jié)更為簡單；而本文提出的通過能力計(jì)算方法則可根據(jù)需要，鋪畫出具有特定要求(如列車出發(fā)時(shí)間窗，跨線列車開行比例等)的飽和列車運(yùn)行圖，根據(jù)在研究時(shí)段內(nèi)最多可鋪畫的列車數(shù)量計(jì)算通過能力，是一種可視化的通過能力計(jì)算方法，兩種方法可根據(jù)需要互為補(bǔ)充。

圖6 使用本文方法生成的高鐵運(yùn)行圖

4.2 跨線列車比例對高鐵通過能力影響分析

為了更直觀的體現(xiàn)跨線列車對高鐵通過能力及運(yùn)行圖的影響，研究不同跨線列車比例下不同的列車開行數(shù)量。輸入列車總數(shù)固定為152列，由圖6(b)可知，鄭州—北京能力已趨于飽和，所以通過刪除鄭州—北京方向與北京—鄭州方向列車，增加相應(yīng)數(shù)量的跨線列車來調(diào)整跨線列車比例。圖7統(tǒng)計(jì)了當(dāng)跨線列車占分別為38%、46%、54%、62%時(shí)，600 min內(nèi)可鋪畫的列車總數(shù)為144、138、134、132列。由于跨線列車的增加，列車在跨線站的停站時(shí)間增加，且各方向列車在跨線站的互相干擾也隨之增多，造成了大量的能力消耗，可鋪畫列車數(shù)量降低。但從圖7也可以看出可鋪畫列車數(shù)量減小的速度在慢慢降低，其原因是隨著跨線列車的增多，具有相同屬性的列車也隨之增多，從而緩解了能力占用。由于跨線高鐵列車一般運(yùn)程較長，較運(yùn)程較短的本線列車可實(shí)現(xiàn)更高的經(jīng)濟(jì)效益，因此在通過能力允許范圍內(nèi)，通過合理調(diào)整列車結(jié)構(gòu)，適當(dāng)提高跨線列車比重，可以收到更優(yōu)的運(yùn)營效果。

圖7 不同跨線列車比例下列車開行數(shù)量

4.3 車站站場布局對高鐵通過能力影響分析

本文提出的方法也可以評價(jià)高鐵站站場布局,見圖5，將圖中紅色道岔取消，鄭州—德州方向列車直接改用立交形式由站場1到達(dá)站場2，那么該方向列車與太原—鄭州、北京—太原、北京—鄭州，德州—鄭州和鄭州—太原方向的列車沒有沖突，計(jì)算結(jié)果見圖8，600 min內(nèi)太原—德州和鄭州—北京高鐵可鋪畫列車數(shù)為150列，較圖6可多鋪畫6列列車，表明在跨線列車運(yùn)行需求較大的繁忙高鐵干線，合理的高鐵站站場布局可減少列車進(jìn)路沖突，從而提高高速鐵路通過能力。

圖8 站場優(yōu)化后的高鐵運(yùn)行圖

5 結(jié)論

本文深入研究了高鐵樞紐內(nèi)跨線列車運(yùn)行對高鐵通過能力和運(yùn)行圖鋪畫的影響機(jī)理。提出在跨線站不同方向列車之間的進(jìn)路沖突可用最小列車間隔時(shí)間標(biāo)準(zhǔn)為判據(jù)，建立基于時(shí)空網(wǎng)絡(luò)的整數(shù)規(guī)劃模型，設(shè)計(jì)了ADMM分解算法將原問題分解為若干尋找單個(gè)列車的最短路徑問題，獲得了各方向列車運(yùn)行線在跨線樞紐的最佳配合方案。并以太原—德州及鄭州—北京高鐵為例，驗(yàn)證了方法的可行性。論文分析、評估了跨線列車占比變化和高鐵站站場布局優(yōu)化對高速鐵路通過能力影響，為進(jìn)一步提高高鐵運(yùn)營效能提供了科學(xué)依據(jù)。