任雪晴，趙浩淋，張馨月

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

0 引言

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

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

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

1 問(wèn)題描述與模型設(shè)計(jì)

1.1 集合

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

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

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

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

1.2 決策變量

1.3 參數(shù)

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

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

k′ik：?？縤站的k車上一輛?？寇嚧?

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

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

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

Sk：列車k經(jīng)過(guò)的車站集，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)行時(shí)間;

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

δ：離散時(shí)間間隔

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

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

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

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

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

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

1.4 約束條件

1.4.1 列車安全約束

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

(1)

(2)

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

(3)

(4)

(5)

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

(6)

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

(7)

約束(8)確保不相鄰列車離開(kāi)同一站臺(tái)時(shí)符合安全間隔.

(8)

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

(9)

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

(10)

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

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

(11)

1.4.2 列車位席及客流約束

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

(12)

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

(13)

(14)

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

(15)

(16)

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

(17)

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

(18)

(19)

(20)

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

(21)

(22)

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

(23)

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

(24)

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

(25)

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

(26)

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

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

(27)

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

(28)

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

(29)

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

(30)

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

(31)

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

(32)

1.5 模型建立

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

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

(33)

2)新列車發(fā)車時(shí)刻表與原列車發(fā)車時(shí)刻表偏差時(shí)長(zhǎng)

(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編碼并生成新列車時(shí)刻表.每個(gè)停車方案是隨機(jī)生成一個(gè)新列車時(shí)刻表X′，采用0～1編碼形式，每個(gè)方案由K×S個(gè)編碼組成，每行代表一列車，每列代表一車站，1代表停站，0代表跳站.迭代代數(shù)ngen=1.

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

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

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

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

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

圖1 算法流程圖

3 數(shù)值算例

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

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

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

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

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

圖4 乘客在北京北至延慶出行時(shí)間段

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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