基于開(kāi)行方案的高速鐵路客流分配方法研究

李文卿，倪少權(quán),2,3，楊渝華，文 迪

(1.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031；2.西南交通大學(xué) 全國(guó)鐵路列車(chē)運(yùn)行圖編制研發(fā)培訓(xùn)中心，四川 成都 610031；3.西南交通大學(xué) 綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，四川 成都 610031)

基于開(kāi)行方案的客流分配方法用以在給定開(kāi)行方案下估計(jì)客流在各條列車(chē)服務(wù)路徑上的分配情況，進(jìn)而評(píng)估票價(jià)收入和所有旅客的廣義出行費(fèi)用，是開(kāi)行方案評(píng)估反饋循環(huán)的重要組成部分。

國(guó)內(nèi)外學(xué)者對(duì)客流分配方法進(jìn)行了大量研究。最早的客流分配方法是在制定開(kāi)行方案之前，將旅客按照一定的規(guī)則預(yù)分配至物理路徑上[1-2]，此類(lèi)方法忽略了旅客的自由選擇和列車(chē)服務(wù)對(duì)旅客的影響。隨著研究者逐漸重視旅客的效用，以及旅客出行選擇行為研究的深入，基于列車(chē)開(kāi)行方案的客流分配方法研究受到了更多關(guān)注。此類(lèi)研究多采用基于圖論的尋路算法和配流算法結(jié)合的求解框架，為描述旅客基于列車(chē)服務(wù)的旅行過(guò)程，需建立一個(gè)由節(jié)點(diǎn)和加權(quán)弧組成的服務(wù)網(wǎng)絡(luò)，節(jié)點(diǎn)表示旅客在旅行過(guò)程中的不同狀態(tài)，弧段表示旅客的不同旅行過(guò)程，弧的權(quán)重表示相應(yīng)旅行過(guò)程的廣義費(fèi)用，通過(guò)尋路算法求解各點(diǎn)對(duì)之間旅客廣義出行費(fèi)用最小的路徑，最后通過(guò)配流算法按一定規(guī)則將客流量加載到路徑上。研究考慮了哪些旅行過(guò)程決定了服務(wù)網(wǎng)絡(luò)的結(jié)構(gòu)，進(jìn)而決定了節(jié)點(diǎn)和弧段的數(shù)量，最終影響尋路算法的求解效率。文獻(xiàn)[3]從適用問(wèn)題、節(jié)點(diǎn)和弧段數(shù)量等角度對(duì)不同結(jié)構(gòu)的服務(wù)網(wǎng)絡(luò)進(jìn)行了分析，文獻(xiàn)[4-8]建立了不同結(jié)構(gòu)的服務(wù)網(wǎng)絡(luò)進(jìn)行客流分配。上述研究假設(shè)旅客能完全知悉網(wǎng)絡(luò)中各條路徑的阻抗且一定選擇廣義費(fèi)用最小的路徑，屬于單路徑確定性配流。文獻(xiàn)[9-10]認(rèn)為旅客對(duì)路徑阻抗的認(rèn)知可能有偏差且個(gè)人選擇行為帶有一定的隨機(jī)性，因此基于廣義費(fèi)用按概率將客流分配至多條備選路徑上更加合理。根據(jù)是否基于用戶均衡定理，配流算法可以分為用戶均衡配流和非用戶均衡配流兩個(gè)范疇。基于用戶均衡定理的研究認(rèn)為，列車(chē)上旅客數(shù)增加會(huì)使列車(chē)的擁擠度即路徑的阻抗增加，因此高速鐵路(以下簡(jiǎn)稱(chēng)高鐵)客流分配和公路交通流分配具有相似性，應(yīng)滿足用戶均衡定理；文獻(xiàn)[11-12]認(rèn)為高速列車(chē)不存在擁擠，并且高鐵的旅客出行選擇過(guò)程并不是實(shí)時(shí)占用列車(chē)能力，而是在購(gòu)票的一瞬間占用列車(chē)能力，因此不滿足用戶均衡定理的適用條件。是否引入用戶均衡定理對(duì)配流結(jié)果有較大影響，因此有待于進(jìn)一步研究。

在上述研究的基礎(chǔ)上，本文以提高客流分配方法的準(zhǔn)確性和求解效率為目的，從尋路算法和配流算法兩個(gè)維度展開(kāi)研究。在高鐵系統(tǒng)中，路徑搜索建立在開(kāi)行方案即列車(chē)服務(wù)的基礎(chǔ)上，因此本文提出一種直接基于開(kāi)行方案搜索的兩階段尋路算法，與既有研究相比，避免了建立復(fù)雜的服務(wù)網(wǎng)絡(luò)與冗余的節(jié)點(diǎn)搜索，算法的求解效率得到了顯著提升。由于列車(chē)定員與列車(chē)運(yùn)行圖的限制，高鐵系統(tǒng)中乘車(chē)路徑的容量和阻抗通常是確定的，因此用戶均衡定理不適用于高鐵客流分配，本文對(duì)此進(jìn)行了分析與證明。最后使用成渝地區(qū)高鐵網(wǎng)絡(luò)客流分配案例驗(yàn)證了方法的有效性。

1 問(wèn)題分析

客流分配方法的本質(zhì)是模擬旅客為了實(shí)現(xiàn)位移選擇乘車(chē)方案的過(guò)程，要求準(zhǔn)確地描述旅客出行選擇行為。

現(xiàn)實(shí)中，旅客的出行選擇分為兩個(gè)階段，第一階段為根據(jù)公布的列車(chē)運(yùn)營(yíng)計(jì)劃尋找所有可行的乘車(chē)方案。如果某一列車(chē)的停站包括旅客出行起訖點(diǎn)，則該列車(chē)為一個(gè)可行的直達(dá)乘車(chē)方案，如果不存在直達(dá)乘車(chē)方案，則需要尋找由至少2列車(chē)組成的換乘方案。由于換乘不僅會(huì)給旅客帶來(lái)額外的廣義費(fèi)用，還會(huì)增加旅途的不確定性，旅客會(huì)優(yōu)先考慮中轉(zhuǎn)換乘次數(shù)最少的乘車(chē)方案；第二階段為根據(jù)各個(gè)備選乘車(chē)方案的廣義費(fèi)用確定最佳乘車(chē)方案，最后通過(guò)購(gòu)票預(yù)訂相關(guān)的列車(chē)服務(wù)。上述過(guò)程和現(xiàn)有的客流分配方法存在一定的差異，主要體現(xiàn)在以下2個(gè)方面。

1.1 與現(xiàn)有尋路算法的差異

現(xiàn)實(shí)中旅客的“尋路”是先根據(jù)列車(chē)運(yùn)營(yíng)計(jì)劃尋找可行的乘車(chē)方案，最終選擇廣義費(fèi)用最小的方案。而現(xiàn)有的基于圖論的尋路算法是在搜索過(guò)程中考慮最小化廣義費(fèi)用，即依據(jù)旅行過(guò)程的廣義費(fèi)用尋找最佳方案。為了全面地考慮旅行過(guò)程，后者需要根據(jù)開(kāi)行方案設(shè)置大量的虛擬列車(chē)節(jié)點(diǎn)，在每次搜索過(guò)程中獲取單個(gè)源點(diǎn)到所有其他節(jié)點(diǎn)的最短路，但最終僅有OD節(jié)點(diǎn)之間的最短路被利用了。換言之，大量的節(jié)點(diǎn)搜索是冗余的，因?yàn)楸举|(zhì)上只有關(guān)于OD節(jié)點(diǎn)間可行的乘車(chē)方案的節(jié)點(diǎn)是有意義的，而開(kāi)行方案本身已充分包含尋找可行的乘車(chē)方案的所有信息。由于開(kāi)行方案問(wèn)題不涉及時(shí)間窗，根據(jù)區(qū)間運(yùn)行時(shí)間標(biāo)準(zhǔn)，車(chē)站乘降、停站、換乘時(shí)間標(biāo)準(zhǔn)和票價(jià)標(biāo)準(zhǔn)等已知信息即可確定廣義費(fèi)用最小的乘車(chē)方案。

1.2 與現(xiàn)有配流算法的差異

現(xiàn)有高鐵客流分配方法的核心思想大多為用戶均衡理論，該理論的適用環(huán)境須滿足以下假設(shè)：①出行者可以最大限度獲知起訖點(diǎn)間各條路徑的阻抗信息；②出行者可以在任意情況下自由選擇路徑；③大多數(shù)出行者是理性的，一般會(huì)選擇阻抗最低的路徑；④在一定范圍內(nèi)，路徑的阻抗會(huì)受到其使用者人數(shù)的影響，二者一般呈正比例關(guān)系。

與完全滿足上述條件的公路系統(tǒng)不同，盡管鐵路系統(tǒng)滿足條件①和條件③，但顯然并不滿足條件②和條件④。條件②意味著即使某條路徑發(fā)生擁堵，但只要該條路徑的阻抗低于其他路徑，出行者依然可以選擇。但在鐵路系統(tǒng)中，出行者選擇路徑體現(xiàn)為通過(guò)購(gòu)票預(yù)訂列車(chē)席位，會(huì)受到列車(chē)定員和售票策略的制約。為了保證高鐵良好的服務(wù)質(zhì)量，一般不允許超員或僅發(fā)售少量無(wú)座票，因此當(dāng)某條路徑涉及的相關(guān)列車(chē)的席位售罄時(shí)，便不再允許出行者進(jìn)入；針對(duì)條件④，路徑阻抗通常表示為使用該路徑需支出的廣義費(fèi)用，主要由時(shí)間和票價(jià)組成，在大多數(shù)公共交通系統(tǒng)中，運(yùn)輸工具內(nèi)部的擁擠度也是考慮因素之一。但在鐵路系統(tǒng)中，路徑由一列或多列高速列車(chē)構(gòu)成，其時(shí)間由列車(chē)運(yùn)行圖決定，票價(jià)由票價(jià)率和運(yùn)輸距離決定，二者基本固定不變，且由于不允許超員，車(chē)廂內(nèi)的擁擠度亦不需考慮，因此，各條路徑的廣義費(fèi)用不會(huì)受到使用人數(shù)變化的影響。

綜上所述，由于高鐵系統(tǒng)不完全滿足用戶均衡定理的適用條件，所以高鐵客流分配不會(huì)達(dá)到用戶均衡狀態(tài)，第2節(jié)對(duì)此推論進(jìn)行數(shù)學(xué)證明。

2 關(guān)于用戶均衡定理不適用于高鐵客流分配的證明

鐵路系統(tǒng)路徑示意見(jiàn)圖1：o、d為一對(duì)起訖點(diǎn)；l1、l2為o、d之間的兩條路徑；t1、t2為阻抗函數(shù)，A1、A2分別為l1和l2中席位數(shù)最少列車(chē)的定員；q1、q2為各條路徑負(fù)載客流量，q1、q2未知；q為總客流需求量，q已知且q1+q2=q。

圖1 鐵路系統(tǒng)路徑示意圖

由用戶均衡定理可知，在滿足所有假設(shè)的情況下，當(dāng)所有出行者均選定自己的路徑不做改變時(shí)，所有被使用路徑的阻抗相同且為最小值，任意出行者改變其選擇都會(huì)使自身的廣義出行費(fèi)用增加，此時(shí)系統(tǒng)達(dá)到用戶均衡狀態(tài)。路徑流量q1、q2與下列優(yōu)化問(wèn)題的最優(yōu)解等價(jià)

(1)

s.t.

(2)

0≤qi≤Ai?i∈{1,2}

(3)

由于高鐵系統(tǒng)的路徑阻抗不受出行者選擇的影響，阻抗函數(shù)t1和t2為常量，由a1和a2表示。

式(1)可以改寫(xiě)為

(4)

將式(2)等價(jià)變換為q2=q-q1代入式(4)中，得到新的目標(biāo)函數(shù)

min[(a1-a2)q1+a2q]

(5)

式中：a1、a2、q為已知量且均為正數(shù)，若要得到最優(yōu)解，分為以下3種情況討論：

(1)當(dāng)a1>a2時(shí)，a1-a2>0，只有當(dāng)q1取最小值時(shí)得到最優(yōu)解，最優(yōu)解為q2=min{A2,q},q1=max{0,q-q2}。所有旅客會(huì)優(yōu)先選擇阻抗較低的路徑l2直至滿載，未能成功預(yù)訂l2列車(chē)席位的剩余客流只能選擇路徑l1。在該狀態(tài)下，所有旅客均無(wú)法通過(guò)改變其出行選擇降低自身的廣義出行費(fèi)用，但t1和t2顯然不相等，且t1>t2恒成立，不滿足用戶均衡狀態(tài)。

(2)當(dāng)a1

(3)當(dāng)a1=a2時(shí)，式(5)等價(jià)為常數(shù)函數(shù)，無(wú)論q1取任何值，目標(biāo)函數(shù)均不發(fā)生變化，任何滿足約束條件式(2)和式(3)的解均可作為最優(yōu)解。在該狀態(tài)下，盡管t1=t2恒成立，但任意旅客改變其出行路徑均不會(huì)使自身的廣義出行費(fèi)用發(fā)生變化，不滿足用戶均衡狀態(tài)。

綜上所述，用戶均衡定理并不適用于高鐵客流分配。

3 基于開(kāi)行方案搜索的客流分配算法

3.1 算法思路

算法分為基于開(kāi)行方案搜索的兩階段k短路算法和全有全無(wú)配流算法兩部分。

旅客選擇高鐵出行的必要條件為起訖點(diǎn)間有列車(chē)服務(wù)，分為直達(dá)與換乘兩種情況，直達(dá)要求至少有一列車(chē)的停站序列同時(shí)包含起訖點(diǎn)，換乘要求至少有兩列車(chē)的停站序列中分別包含起點(diǎn)和訖點(diǎn)且相關(guān)列車(chē)可以組成完整的出行鏈。將開(kāi)行方案中的列車(chē)集合分為4個(gè)子集：a. 同時(shí)包含起訖點(diǎn)的列車(chē)；b. 包含起點(diǎn)但不包含訖點(diǎn)的列車(chē)；c. 不包含起點(diǎn)但包含訖點(diǎn)的列車(chē)；d. 不包含起訖點(diǎn)的列車(chē)，子集a中的列車(chē)可以滿足旅客直達(dá)的需要，若不存在直達(dá)列車(chē)，以預(yù)期換乘次數(shù)遞增的規(guī)則搜索子集b、 c、 d以尋找可以組成完整出行鏈的列車(chē)集合。搜索出行鏈的思路為：若預(yù)期換乘一次，則在子集b和子集c中各選出一列列車(chē)，選取規(guī)則為兩列車(chē)的停站序列的交集非空，代表存在換乘站可使旅客完成換乘出行；若預(yù)期換乘兩次，則在子集b、c、d中各選取一列列車(chē)，選取規(guī)則為子集b、c中兩列車(chē)的停站序列交集為空，子集b、d中兩列車(chē)和子集c、d中兩列車(chē)的停站序列交集非空，代表旅客可以從子集b中的列車(chē)換乘到子集d中的列車(chē)，再換乘到子集c中的列車(chē)完成出行；若預(yù)期換乘次數(shù)大于兩次，則需要再?gòu)淖蛹痙中選擇一列車(chē)，選取規(guī)則與前一情境類(lèi)似，關(guān)鍵是組成起訖點(diǎn)間的完整出行鏈。由于換乘會(huì)給旅客帶來(lái)較大不便，一般旅客會(huì)偏好換乘次數(shù)少的路徑。因此在配流過(guò)程中，按換乘次數(shù)遞增的規(guī)則，逐步搜索可行的路徑集合，根據(jù)各時(shí)間標(biāo)準(zhǔn)、票價(jià)率和站間距等已知信息計(jì)算各條路徑的廣義出行費(fèi)用。隨后對(duì)可行路徑集中的所有路徑按廣義出行費(fèi)用進(jìn)行排序，利用全有全無(wú)法將客流按廣義費(fèi)用從低到高的順序逐次加載到相應(yīng)的路徑上。

當(dāng)客流量較大時(shí)，需要考慮長(zhǎng)途與短途、直達(dá)與換乘的旅客出行選擇沖突。根據(jù)鐵路售票策略，本文采用先長(zhǎng)途后短途、先直達(dá)后換乘的規(guī)則。具體思路為：按旅途距離從高到低的順序，對(duì)所有OD對(duì)按旅客預(yù)期換乘次數(shù)遞增的順序優(yōu)先分配長(zhǎng)途和直達(dá)旅客的列車(chē)席位，再分配短途和換乘旅客的列車(chē)席位，每次分配后需要扣除已加載客流列車(chē)的可供分配席位，直至配流完畢。完整算法流程見(jiàn)圖2。

圖2 算法流程圖

3.2 符號(hào)定義

表1 符號(hào)定義

3.3 算法設(shè)計(jì)

o,d∈Ht

(6)

若t滿足

(7)

若t滿足

(8)

若t滿足

(9)

(10)

(11)

由于高鐵成網(wǎng)后直達(dá)率較高且旅客一般不考慮換乘次數(shù)較高的路徑，為了簡(jiǎn)化表述，在此不考慮m>2的情況。

m={0,1,2}時(shí)的o,d之間的備選乘車(chē)方案搜索過(guò)程見(jiàn)圖3。

圖3 備選乘車(chē)方案搜索過(guò)程

(12)

式中：δ和η分別為時(shí)間因素和費(fèi)用因素的權(quán)重，δ,μ≥0且δ+μ=1。

(13)

(14)

將所有備選乘車(chē)方案按Co,d的升序排列，即可快速枚舉出o,d之間k取任意值的k短路。

最后，在滿足列車(chē)容量約束的條件下將客流依次加載到最優(yōu)乘車(chē)方案中的相關(guān)列車(chē)上，直至o,d間的總客流加載完畢或席位耗盡。

算法步驟如下：

Step1將所有OD按旅途距離的降序進(jìn)行排列，設(shè)OD總數(shù)為N，序號(hào)為n，令n=0。

3.4 算法時(shí)間復(fù)雜度分析與比較

(15)

式中：α,β,γ分別為所有起訖點(diǎn)中可不換乘到達(dá)，需換乘1次到達(dá)和需換乘2次到達(dá)的比例，α+β+γ=1且α,β,γ∈[0,1]。

不同算法時(shí)間復(fù)雜度的對(duì)比結(jié)果見(jiàn)表2。

表2 不同算法時(shí)間復(fù)雜度的對(duì)比結(jié)果

圖4 不同算法的時(shí)間復(fù)雜度變化對(duì)比圖

圖5 不同參數(shù)的算法1時(shí)間復(fù)雜度變化對(duì)比圖

4 算例驗(yàn)證

采用2018年4月10日起執(zhí)行的成渝地區(qū)部分高鐵網(wǎng)絡(luò)及列車(chē)開(kāi)行方案進(jìn)行驗(yàn)算，見(jiàn)圖6。包含4種不同速度等級(jí)的線路和46個(gè)車(chē)站，其中包括4個(gè)省會(huì)始發(fā)站、20個(gè)非省會(huì)始發(fā)站和24個(gè)普通站，日開(kāi)行超過(guò)250對(duì)不同等級(jí)的高速列車(chē)，為1 035個(gè)OD對(duì)提供優(yōu)質(zhì)的列車(chē)服務(wù)。經(jīng)測(cè)算，在既有物理網(wǎng)絡(luò)和開(kāi)行方案條件下，約72%OD對(duì)可以直達(dá)，約28%的OD對(duì)可經(jīng)1次換乘到達(dá)(α≈0.72，β≈0.28，γ=0)。

圖6 成渝地區(qū)部分高鐵網(wǎng)絡(luò)拓?fù)鋱D

4.1 參數(shù)設(shè)置

按全國(guó)平均收入水平設(shè)置旅客平均單位時(shí)間價(jià)值為30元/h。票價(jià)按區(qū)間距離乘以票價(jià)率計(jì)算。δ和η分別設(shè)為0.6、0.4。G、D字頭的高速列車(chē)票價(jià)率分別設(shè)為0.45、0.4元/km。區(qū)間運(yùn)行時(shí)間標(biāo)準(zhǔn)為區(qū)間距離和列車(chē)運(yùn)營(yíng)速度之比。車(chē)站乘降、停站和換乘時(shí)間標(biāo)準(zhǔn)按不同的車(chē)站規(guī)模確定，見(jiàn)表3。所有算法使用Matlab R2015a優(yōu)化器進(jìn)行測(cè)試，運(yùn)行環(huán)境為Intel core i7-7700HQ四核處理器、8 GB內(nèi)存的計(jì)算機(jī)。

表3 車(chē)站時(shí)間標(biāo)準(zhǔn)參數(shù)設(shè)置

4.2 算法測(cè)試

分別使用算法1、算法2和算法3求解所有OD對(duì)的最短路或k短路(k=3)，結(jié)果見(jiàn)表4。

表4 尋路算法運(yùn)算時(shí)間對(duì)比

算法2和算法3的運(yùn)算時(shí)間分為2部分：構(gòu)建服務(wù)網(wǎng)絡(luò)時(shí)間和尋路時(shí)間。構(gòu)建服務(wù)網(wǎng)絡(luò)需要遍歷1次開(kāi)行方案，當(dāng)所有OD對(duì)均可直達(dá)時(shí)，算法1同樣只需遍歷1次開(kāi)行方案，因此算法1的運(yùn)算時(shí)間與算法2、3的構(gòu)圖時(shí)間相近。由于需要搜索大量節(jié)點(diǎn)，算法2的運(yùn)算時(shí)間是算法1的3倍以上。由于算法3需要重復(fù)進(jìn)行k次搜索，所以運(yùn)算時(shí)間遠(yuǎn)長(zhǎng)于算法1和算法2。

按包含車(chē)站規(guī)模和區(qū)間里程對(duì)所有OD對(duì)進(jìn)行降序排序，按順序基于算法1求得各OD對(duì)的k短路及其廣義出行費(fèi)用，使用全有全無(wú)配流法將客流需求量一次性分配到對(duì)應(yīng)路徑上。運(yùn)算時(shí)間約4.5 s，客流分配統(tǒng)計(jì)結(jié)果見(jiàn)表5。

表5 客流分配結(jié)果統(tǒng)計(jì)

5 結(jié)論

客流分配方法作為鐵路運(yùn)輸計(jì)劃評(píng)估反饋循環(huán)中的重要組成部分，在開(kāi)行方案優(yōu)化過(guò)程中需要多次調(diào)用，其運(yùn)算效率和合理性對(duì)開(kāi)行方案優(yōu)化的速度和質(zhì)量有重要影響?；诟哞F客流分配的特點(diǎn)，本文從尋路算法和配流算法兩個(gè)維度對(duì)高鐵客流分配方法進(jìn)行了研究。

同基于圖論的尋路算法相比，本文提出的算法會(huì)產(chǎn)生2種時(shí)間結(jié)余：①無(wú)需構(gòu)建服務(wù)網(wǎng)絡(luò)所節(jié)約的時(shí)間；②基于開(kāi)行方案針對(duì)OD進(jìn)行精確搜索而無(wú)需搜索冗余節(jié)點(diǎn)所節(jié)約的時(shí)間。此外，當(dāng)高鐵網(wǎng)絡(luò)的連通性提升時(shí)，算法的運(yùn)算時(shí)間會(huì)進(jìn)一步降低。

由于高鐵不存在擁擠現(xiàn)象，將適用于公路交通流分配的用戶均衡定理直接引入高鐵客流分配是不合理的。本文對(duì)用戶均衡定理不適用于高鐵客流分配進(jìn)行了證明。高鐵客流分配實(shí)際上是旅客購(gòu)票的過(guò)程，因此全有全無(wú)配流更符合實(shí)際，且由于避免了為實(shí)現(xiàn)均衡而反復(fù)迭代，顯著提高了算法的運(yùn)算效率。

通過(guò)考慮每列車(chē)的時(shí)間窗或在售票周期內(nèi)根據(jù)售票策略動(dòng)態(tài)改變列車(chē)停站序列，本文提出的算法可以拓展到基于列車(chē)運(yùn)行圖的客流分配問(wèn)題或考慮售票策略的客流分配問(wèn)題，能否在上述問(wèn)題中取得較好結(jié)果有待進(jìn)一步研究。