冬奧會京張高鐵列車時刻表優(yōu)化研究

任雪晴，趙浩淋，張馨月

(北方工業(yè)大學(xué)城市智能交通控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100144)

0 引言

軌道交通越來越成為人們出行主要方式[1-2].本文研究的主要問題是軌道交通中冬奧會背景下對京張高鐵列車時刻表加入新增列車以滿足冬奧客流出行需求并在此基礎(chǔ)上對列車時刻表進(jìn)行調(diào)整優(yōu)化，最大化滿足冬奧會乘客出行需求和最小化新增列車總旅行時間以及對原有列車時刻表的影響最小為目標(biāo)，提出了基于跳站運(yùn)行模式列車運(yùn)行圖優(yōu)化方法,實(shí)現(xiàn)列車跳站運(yùn)行方案與實(shí)時大客流的精準(zhǔn)匹配.本文前提是已知客流預(yù)測分配結(jié)果，主要關(guān)注新增客流對京張高鐵列車時刻表影響及調(diào)整優(yōu)化方案.

近年來，有關(guān)列車運(yùn)行線問題，需要安排新增列車插入現(xiàn)有列車時刻表來滿足新增需求.Wang等[6]基于列生成的啟發(fā)式算法考慮旅客服務(wù)需求和列車調(diào)度，利用拉格朗日松弛法構(gòu)建線性規(guī)劃問題來尋找列車時刻表最優(yōu)解.Gao等[7]研究在現(xiàn)有列車時刻表中增加新列車以新增列車運(yùn)營時間最小和最小化的總旅行時間的雙目標(biāo)混合整數(shù)線性規(guī)劃模型，提出3階段優(yōu)化方法求解模型滿足乘客需求.Zhang等[8]考慮了鐵路網(wǎng)維護(hù)時需要在固定的列車時刻表插入額外的列車，以旅客總出行時間和維修費(fèi)用最小化為雙目標(biāo)利用啟發(fā)式算法進(jìn)行優(yōu)化，驗(yàn)證了模型有效性.Niu等[9]研究了高峰時段擁擠條件下，以乘客等待時間最小為優(yōu)化目標(biāo)建立了1個非線性優(yōu)化模型求解最優(yōu)時刻表，用遺傳算法給出了載客量與列車到發(fā)時間之間的關(guān)系.Yang等[10]考慮了列車?？亢土熊囌{(diào)度問題，以所有列車的總停留時間和實(shí)際出發(fā)時間與期望出發(fā)時間之間的總延誤的最小化為目標(biāo)函數(shù)的多目標(biāo)混合整數(shù)線性規(guī)劃模型.但上述研究中，大都考慮乘客總出行時間且乘客對到達(dá)時間沒有時間要求，對時間有要求的特殊乘客研究較少，造成對到達(dá)時間有要求的乘客無法提供運(yùn)力實(shí)現(xiàn)列車時刻表最優(yōu).

針對以上研究，本文基于京張高鐵線路日常出行動態(tài)OD數(shù)據(jù)，面對冬奧會乘客出行需求構(gòu)建列車時刻表優(yōu)化模型，通過引入乘客上下車站點(diǎn)客流數(shù)據(jù)來分解列車提供的運(yùn)力剩余容量，將原有列車時刻表用模擬退火算法進(jìn)行迭代加入新增列車生成符合安全約束的新列車時刻表，提高冬奧客流在有效到達(dá)時間范圍內(nèi)的乘客需求滿足率，從而實(shí)現(xiàn)找到最優(yōu)列車時刻表生成基于冬奧會的京張高鐵列車運(yùn)行圖.本文主要在以下3個方面進(jìn)行了擴(kuò)展研究：①不同于以往大多數(shù)研究，新增的部分乘客對到達(dá)時間有要求，因此需要考慮新的列車時刻表滿足乘客對到達(dá)時間的要求；②面向大型體育賽事，在原有列車時刻表中新增列車盡量減小對原有列車時刻表影響；③基于冬奧會期間超大客流數(shù)據(jù)和列車停站方案，精確刻畫站臺乘客數(shù)量、上/下車乘客數(shù)量、列車空座位數(shù)等變量之間的關(guān)系.

1 問題描述與模型設(shè)計

1.1 集合

Ke：計劃時間范圍內(nèi)發(fā)出的原有列車數(shù)量；

Ka：計劃時間范圍內(nèi)新增列車數(shù)量；

K：列車的總數(shù)量，K=Ke+Ka；

S：模型中車站數(shù)量.

1.2 決策變量

1.3 參數(shù)

1)列車相關(guān)符號和定義

k,l,u：火車上標(biāo)，k,l,u∈Ka∪Ke;

k′ik：停靠i站的k車上一輛?？寇嚧?

i,j：車站下標(biāo),i,j∈S;

r：軌道上標(biāo)；

i′ik：列車k在i站后下一個?？空军c(diǎn);

Sk：列車k經(jīng)過的車站集，Sk?S,k,l∈Ka∪Ke;

n：列車的加車數(shù)量;

f：列車線路，f=0為張家口以遠(yuǎn)線路，f=1為太子城線路，f=2為延慶線路；

Ck：k列車最大載客數(shù);

tij：i站到j(luò)站的運(yùn)行時間;

2)客流相關(guān)符號和定義

δ：離散時間間隔

Pif(t):f線路截止到t時刻i站站臺數(shù);

P′if(t):f線路截止到t時刻i站站臺原有客流數(shù);

Wijf(t)：f線路截止到t時刻站臺i站的滯留乘客;

W′ijf(t)：f線路截止到t時刻在i站到j(luò)站臺的站臺新增客流等待數(shù);

pijf(t)：f線路在t時刻乘客到達(dá)i站且終點(diǎn)站為j站原始乘客流入率;

ATij:新增乘客從i站到j(luò)站的期望到達(dá)時間

1.4 約束條件

1.4.1 列車安全約束

約束(1)為停車模式約束:假設(shè)原有k車在i站停車，那么k車在新的列車時刻表中也必須停車.約束(2)表示如果k車在原時刻表中停車，則新時刻表也停車.

(1)

(2)

約束(3)為列車運(yùn)行時間約束.列車j站到達(dá)時間減i站出發(fā)時間，可表示為:

(3)

(4)

(5)

約束(6)根據(jù)發(fā)車時距約束，每對列車同一車站離開時間必須大于一個安全約束.

(6)

約束(7)表示每對列車同一車站到達(dá)時間必須大于一個安全約束.

(7)

約束(8)確保不相鄰列車離開同一站臺時符合安全間隔.

(8)

約束(9)表示列車只能被分配到車站的一條軌道中.

(9)

約束(10)表示先到站的列車在站內(nèi)等待相鄰列車超車時離站時間約束.

(10)

約束(11)保證任意時刻k車車內(nèi)人數(shù)不大于車輛的最大容量.

ck(t)≤Ck,k∈Ka,f=0,1,2.

(11)

1.4.2 列車位席及客流約束

約束(12)表示k車?？縤站時，所有以i站為終點(diǎn)站的乘客均在該站下車.

(12)

約束(13)表示k車在i站的出發(fā)時刻且沒有登上k車的站臺新增乘客等待人數(shù)，約束(14)表示k車在i站的出發(fā)時刻且沒有登上k車的站臺等待人數(shù)是由k車在i站到達(dá)時刻站臺和停站時間內(nèi)乘客到達(dá)人數(shù)兩部分組合而成.

(13)

(14)

約束(15)表示在i站的到達(dá)時刻站臺等待從i站到j(luò)站的新增乘客人數(shù)，約束(16)表示在i站的到達(dá)時刻站臺等待從i站到j(luò)站的乘客人數(shù)，這部分人數(shù)由上一輛?？縤站的k′車出發(fā)時的站臺人數(shù)和k′車的出發(fā)時刻到k車的到達(dá)時刻到達(dá)i站的人數(shù)構(gòu)成.

(15)

(16)

約束(17)表示k車在i站到達(dá)時站臺等待人數(shù).

(17)

約束(18)表示列車在離開始發(fā)站時車內(nèi)剩余座位數(shù).剩余座位是由列車最大載客量減去i站之前上車的旅客和，約束(19)為列車離開i站時剩余座位由列車到達(dá)i站時剩余座位加上以i站為目的地的下車乘客加上在i站上車的乘客.

(18)

(19)

(20)

當(dāng)列車到達(dá)i站，乘客面臨2種情況①乘坐k車，在比賽開始前列車到達(dá)終點(diǎn)站；②等待后續(xù)到站車輛.式(21)表示乘客將選擇從i站到j(luò)站車內(nèi)時間最短的列車進(jìn)行乘坐.式(22)表示選擇k車從i站到j(luò)站的旅行時間由k車從i站的出發(fā)時間減j站的出發(fā)時間.

(21)

(22)

約束(23)表示新增乘客選擇k車到達(dá)最后一站時必須小于比賽開始時間.

(23)

約束(24)表示可乘坐f線路k車從i站到j(luò)站的站臺等待乘客

(24)

約束(25)表示i站臺所有等待乘客中可坐上f方向k車的總?cè)藬?shù)

(25)

約束(26)表示t時k車到達(dá)i站時可上f方向車的人數(shù)=min{車內(nèi)剩余座位，站臺人數(shù)}

(26)

約束(27)表示截止到t時刻乘客乘坐f方向k車從i站到j(luò)站的上車人數(shù)新增客流的占比

如果列車空座位大于站臺等待從f方向i站到j(luò)站的乘客數(shù)，則站臺等待乘客數(shù)全部上車，否則本著先到先上車的原則，前t個時間段內(nèi)到達(dá)的乘客均可上車，在第t+1個時間段內(nèi)到達(dá)的乘客中隨機(jī)選擇乘客來滿足剩余容量.

(27)

約束(28)表示最終在i站上k車的人數(shù).

(28)

約束(29)表示k車在i站出發(fā)時站臺上從i站到j(luò)站的剩余乘客.等于站臺從i站到j(luò)站沒上車的乘客減去上車的乘客.

(29)

約束(30)表示k車在i站離開時的站臺等待人數(shù).

(30)

約束(31)是k車在i站出發(fā)時車內(nèi)人數(shù)，由k車在i站到達(dá)時的車內(nèi)人數(shù)減i站下車人數(shù)加i站上車人數(shù).

(31)

約束(32)表示k車在i站到達(dá)時人數(shù)等于k車在下一個?？空緄′的人數(shù).

(32)

1.5 模型建立

目標(biāo)函數(shù)由3部分構(gòu)成：

1)新增列車總運(yùn)行時間

(33)

2)新列車發(fā)車時刻表與原列車發(fā)車時刻表偏差時長

(34)

3)新增乘客實(shí)際出行與需求偏差大小

(35)

Z=min (α1F1+α2F2+α3F3).

(49)

2 求解算法

該模型采用的模擬退火算法步驟如下：

步驟1初始化.設(shè)定初始溫度T0,終止溫度Tf，初始化內(nèi)循環(huán)迭代次數(shù)k，首先令T=T0,k=0；

步驟2編碼并生成新列車時刻表.每個停車方案是隨機(jī)生成一個新列車時刻表X′，采用0～1編碼形式，每個方案由K×S個編碼組成，每行代表一列車，每列代表一車站，1代表停站，0代表跳站.迭代代數(shù)ngen=1.

步驟3計算客流參數(shù).按照約束條件(1)～(11)判斷是否符合安全約束，將不安全約的停車方案，判斷是否符合列車安全約束.如果不滿足安全約束，調(diào)整至符合安全約束.下面計算客流相關(guān)指標(biāo)，乘客上下車過程中車內(nèi)人數(shù)均需滿足約束約束(11)，具體步驟如下.

步驟4計算目標(biāo)函數(shù)值.按照式(33)～(35)計算.

步驟5隨機(jī)調(diào)整列車發(fā)車時刻形成新的列車時刻表.重復(fù)步驟3和步驟4，ngen=ngen+1.

步驟6對比兩個列車時刻表方案，Δf=f(X)-f(X0),進(jìn)行模擬退火過程.如果Δf<0以一定概率p∈(0,1)接受新解，如果Δf>0則令X=X0更新最優(yōu)解.即接受路徑X為新的列車時刻表；若Δf>0,計算p=exp (-Δf/T),若p大于(0，1)之間的隨機(jī)數(shù)，仍然接受路徑X為新的列車時刻表；

步驟7判斷終止條件，若滿足條件則輸出最優(yōu)解，結(jié)束程序，否則更新ngen=ngen+1，轉(zhuǎn)步驟5繼續(xù)迭代.

圖1 算法流程圖

3 數(shù)值算例

京張高鐵全長174 km，設(shè)10個車站，最高設(shè)計速度350 km/h.圖2是目前京張高鐵線路示意圖，京張高鐵起點(diǎn)為北京北、清河，終點(diǎn)站有延慶站、太子城站.使用f={0,1,2}分別標(biāo)記.列車從北京北站或清河站發(fā)車，分別開往延慶站、太子城站.研究時段為07：00—21：00，天窗時間為21：00—次日7：00，表1列出了每段高鐵上下行純運(yùn)行時間.站點(diǎn)額外加、減速時間設(shè)置為1 min.若i站為起始站和終點(diǎn)站，則設(shè)置停留時間為5 min，即Si=5，反之Si=3.對于最小到達(dá)車頭時距設(shè)為2 min，最小出發(fā)車頭時距設(shè)為3 min.最小出發(fā)間隔為5 min.同一站軌上最小離抵車頭時距設(shè)為2 min.

表1 京張高鐵列車站停時間和運(yùn)營時間

圖2 京張高鐵線路圖(部分)

圖3 表示研究周期內(nèi)客流OD圖

乘客從北京北出行至太子城和延慶的時間段選擇情況調(diào)查結(jié)果見圖4、圖5.根據(jù)結(jié)果可知，乘客在以延慶和太子城為終點(diǎn)的出行選擇在上午08：00—12：00比例最高，其次12：00—16：00、08：00以前，而選擇其他時段出行的乘客比較均衡.

圖4 乘客在北京北至延慶出行時間段

圖5 乘客在北京北至太子城出行時間段

根據(jù)現(xiàn)有的列車時刻表畫出列車運(yùn)行圖，在根據(jù)預(yù)測出來的新增客流和模型中的安全約束進(jìn)行加車.表2是我們使用過的原始時刻表2020-10-01實(shí)際發(fā)車時刻表.

將客流情況和優(yōu)化模型參數(shù)取值帶入程序進(jìn)行求解京張高鐵列車優(yōu)化模型，可得到求解后的列車發(fā)車情況，更好地與京張高鐵實(shí)際列車時刻表進(jìn)行對比，給出優(yōu)化前的列車時刻表圖6，優(yōu)化后時刻表圖7.優(yōu)化之后京張高鐵旅客列車時刻表更加貼合冬奧會乘客出行需求.例如，根據(jù)調(diào)查結(jié)果可知，上午07：00—09：00太子城方向以及13：00—16：00延慶方向冬奧會乘客有較大的出行需求，且延慶方向13：00—16：00時間間隔中，列車發(fā)車出現(xiàn)了斷層，列車發(fā)車間隔較大，不符合實(shí)際的客流需求，應(yīng)該新增列車并縮短列車的發(fā)車間隔，快速發(fā)送旅客.在上午客流高峰后，下午16：00以后的客流需求較小，應(yīng)該是新增較少的列車，使用較大的列車發(fā)車間隔，同時在一定程度上可有效地提高列車的客座率.

圖6 京張高鐵原有列車運(yùn)行圖

圖7 京張高鐵優(yōu)化后列車運(yùn)行圖

對列車時刻表進(jìn)行分析，求解得到優(yōu)化后的列車時刻表新增列車總運(yùn)營時間為1 921 min，新增列車23輛其中延慶方向7輛車，太子城方向16輛車，優(yōu)化的列車時刻表與原有列車時刻表中的原有列車發(fā)車時間總偏差為2 min，到達(dá)時間總偏差為34 min.新增乘客出行需求滿足率為100%.結(jié)果表明基于冬奧會新增乘客出行需求的京張高鐵列車時刻表優(yōu)化模型是有效的，更大程度的實(shí)現(xiàn)旅客的快速、便捷的出行需求.

4 結(jié)束語

為了在冬奧會期間提供充足的運(yùn)力滿足冬奧會乘客出行需求，解決難以精準(zhǔn)匹配列車運(yùn)力與乘客需求的局限性，本文描述了在高鐵走廊上安排新增列車的問題，提出了一種整數(shù)規(guī)劃方法來求解優(yōu)化模型，分解為一些規(guī)模較小的子問題.本文以新增列車運(yùn)營時間、新列車時刻表與原時刻表的偏差和新增奧運(yùn)客流需求為目標(biāo)，構(gòu)建高速鐵路系統(tǒng)列車跳站整數(shù)規(guī)劃并設(shè)計了模擬退火算法，通過京張高鐵利用京張高鐵的真實(shí)數(shù)據(jù)，我們進(jìn)行了計算實(shí)驗(yàn)，結(jié)果驗(yàn)證了該模型的有效性和適用性.結(jié)果表明：①列車通過跳站明顯降低了乘客的總旅行時間；②滿足新增奧運(yùn)客流的出行需求；③雖然在繁忙的列車時刻表中新增了列車，但是新列車時刻表對原有列車時刻的影響較小，對原有承德出行習(xí)慣改動較??；④新增列車以運(yùn)營時間最小的條件下保證了新增奧運(yùn)客流的出行需求.

另外，本文僅僅從乘客的角度優(yōu)化列車運(yùn)行圖，將來可進(jìn)一步考慮列車能耗，成本，碳排放、車輛周轉(zhuǎn)率等指標(biāo)，從鐵路運(yùn)營公司角度優(yōu)化列車跳站運(yùn)行方案.在未來的研究中，我們可能會在以下方面進(jìn)行擴(kuò)展.在本文中，僅處理了可安排所有列車的情況.實(shí)際上，某些列車可能無法安排.這都是未來的研究的方向.