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

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

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

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

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

1 問題分析

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

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

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

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

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

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

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

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

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

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

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

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

(1)

s.t.

(2)

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

(3)

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

式(1)可以改寫為

(4)

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

(2)當(dāng)a1

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

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

3 基于開行方案搜索的客流分配算法

3.1 算法思路

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

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

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

圖2 算法流程圖

3.2 符號定義

表1 符號定義

3.3 算法設(shè)計

o,d∈Ht

(6)

若t滿足

(7)

若t滿足

(8)

若t滿足

(9)

(10)

(11)

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

m={0,1,2}時的o,d之間的備選乘車方案搜索過程見圖3。

圖3 備選乘車方案搜索過程

(12)

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

(13)

(14)

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

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

算法步驟如下：

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

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

(15)

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

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

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

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

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

4 算例驗證

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

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

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

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

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

4.2 算法測試

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

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

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

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

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

5 結(jié)論

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

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

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

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