柳 健，聶 磊

（北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044）

鐵路客運(yùn)服務(wù)網(wǎng)絡(luò)路徑搜索算法的研究與實(shí)現(xiàn)

柳 健，聶 磊

（北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044）

基于反映旅客出行鏈的有向換乘服務(wù)網(wǎng)，采用一種拼接和去冗相結(jié)合的K最短路算法，設(shè)計(jì)并實(shí)現(xiàn)客運(yùn)服務(wù)網(wǎng)絡(luò)路徑搜索系統(tǒng)。該系統(tǒng)可根據(jù)客流計(jì)劃和列車開(kāi)行方案，以多種路徑搜索模式得到合理的乘車方案。以某高速鐵路及相關(guān)路網(wǎng)的列車開(kāi)行方案和相應(yīng)的客流計(jì)劃為例，對(duì)客運(yùn)服務(wù)網(wǎng)絡(luò)路徑搜索算法進(jìn)行測(cè)試，取得了預(yù)期的結(jié)果，但需在乘車效用的豐富和優(yōu)化方面進(jìn)行深入研究。

鐵路客運(yùn)；路徑搜索；服務(wù)網(wǎng)絡(luò)；K 最短路

我國(guó)鐵路路網(wǎng)規(guī)模大、線路運(yùn)營(yíng)條件不同，列車不僅可能跨不同的高速線運(yùn)行，而且還可能跨高速線和既有線開(kāi)行。龐大的鐵路物理網(wǎng)絡(luò)、眾多的客流起訖點(diǎn)，導(dǎo)致鐵路客運(yùn)服務(wù)網(wǎng)相對(duì)于物理網(wǎng)更為龐大和復(fù)雜。復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)給鐵路部門(mén)的業(yè)務(wù)決策帶來(lái)諸多難題。

1 研究背景

近年來(lái)，國(guó)內(nèi)外學(xué)者在服務(wù)網(wǎng)和物理網(wǎng)的構(gòu)建優(yōu)化方面做了大量的研究。張彥提出了由鐵路客運(yùn)站和區(qū)間構(gòu)成的網(wǎng)絡(luò)，稱為區(qū)間網(wǎng)絡(luò)[1]。史峰、鄧連波詳細(xì)討論了另一種用于優(yōu)化乘車費(fèi)用和換乘次數(shù)的基于列車開(kāi)行方案的換乘網(wǎng)絡(luò)[2]。路徑搜索問(wèn)題很多學(xué)科都有涉及。M.Ridwan 建立了基于出行者偏好的模糊徑路選擇模型，提出了出行者由于認(rèn)識(shí)的不足，不一定能夠選擇最短路出行[3]。楊群等指出基于單一標(biāo)準(zhǔn)如行駛時(shí)間最優(yōu)而選擇的路徑并不能完全滿足需求，即并不是實(shí)際的最優(yōu)[4]。Noto.M等人提出了一種改進(jìn)的Dijkstra 算法，并運(yùn)用該算法進(jìn)行了汽車導(dǎo)航的模擬[5]。

從有關(guān)研究結(jié)果看，關(guān)于換乘網(wǎng)絡(luò)結(jié)構(gòu)的理論研究已經(jīng)比較完善，路徑搜索問(wèn)題在多個(gè)領(lǐng)域有廣泛的研究成果。德國(guó)、丹麥等國(guó)家已有較完備、囊括多種運(yùn)輸方式的運(yùn)輸出行規(guī)劃系統(tǒng)。但是，在列車開(kāi)行方案的優(yōu)化過(guò)程中，不僅要考慮旅客對(duì)出行路徑的滿意度，還需將鐵路部門(mén)的運(yùn)營(yíng)成本考慮在內(nèi)，對(duì)這方面的研究尚有待完善。因此，以滿足鐵路列車開(kāi)行方案編制的需要為目標(biāo)，應(yīng)針對(duì)服務(wù)網(wǎng)路徑搜索研究一種有效的算法并開(kāi)發(fā)相應(yīng)的系統(tǒng)。

2 客運(yùn)服務(wù)網(wǎng)絡(luò)的構(gòu)建

在服務(wù)網(wǎng)絡(luò)構(gòu)建方面，有關(guān)研究成果采用了一種改進(jìn)的有向換乘服務(wù)網(wǎng)[6]，該服務(wù)網(wǎng)結(jié)構(gòu)如圖1 所示。

圖1 服務(wù)網(wǎng)結(jié)構(gòu)示意圖

客運(yùn)服務(wù)網(wǎng)的結(jié)構(gòu)主要由包含特定意義的“點(diǎn)”和“弧”構(gòu)成。其中，F(xiàn) 為車站節(jié)點(diǎn)；S 為列車發(fā)車節(jié)點(diǎn)；T 為列車停車節(jié)點(diǎn)?；〉母鞣N類型分別表示旅客在出行過(guò)程中的各種行為：弧 1 是上車弧段，描述旅客上車前進(jìn)站、購(gòu)票、候車及排隊(duì)上車的過(guò)程，其起訖點(diǎn)類型為 S→F；弧 2 是下車弧段，描述旅客到達(dá)終點(diǎn)站后排隊(duì)下車及步行出站的過(guò)程，其起訖點(diǎn)類型為 T→S；弧 3 是乘車弧段，描述列車在兩個(gè)車站之間的運(yùn)行過(guò)程，其起訖點(diǎn)類型為 F→T；弧 4 是停車弧段，描述由于辦理客運(yùn)作業(yè)使車上旅客必須經(jīng)歷的停車等待過(guò)程，其起訖點(diǎn)類型為 T→ 同次列車的F；弧 5 是換乘弧段，描述旅客從某次列車下車，經(jīng)歷候車，然后乘坐上另外一趟列車的出行過(guò)程，其起訖點(diǎn)類型為 T→ 非同次列車的F。

選用這種改進(jìn)的有向換乘服務(wù)網(wǎng)，是因?yàn)槠漭^好地表現(xiàn)了各種影響旅客出行的列車屬性及乘客的旅行行為。例如，圖1 中各虛線表示的弧反映了“旅客 A 站上車→乘車至B 站 →B 站換乘→乘車至C 站 →C 站停站→乘車至D 站 →D 站下車”的全過(guò)程。一個(gè)可以詳盡描述旅客行為的服務(wù)網(wǎng)結(jié)構(gòu)是客流分配及開(kāi)行方案優(yōu)化的基礎(chǔ)。

3 基于客運(yùn)服務(wù)網(wǎng)的路徑搜索

客運(yùn)服務(wù)網(wǎng)下的路徑搜索，就是一個(gè)根據(jù)客運(yùn)服務(wù)網(wǎng)絡(luò)和旅客出行需求得到數(shù)個(gè)旅客乘車方案的過(guò)程，一條服務(wù)路徑也就是一個(gè)乘車方案。搜索過(guò)程中用到的算法稱為 K 最短路算法。若客運(yùn)服務(wù)網(wǎng)絡(luò)中的每條邊都有一個(gè)數(shù)值(長(zhǎng)度、成本、時(shí)間等)，則找出兩節(jié)點(diǎn)(通常是源節(jié)點(diǎn)和阱節(jié)點(diǎn))之間總權(quán)和最小的k條路徑就是 K 最短路問(wèn)題。

我國(guó)鐵路客運(yùn)服務(wù)網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜、規(guī)模龐大，各種列車開(kāi)行方案的停站方式迥異，因此對(duì)路徑搜索算法的效率要求很高。根據(jù)鐵路客運(yùn)換乘次數(shù)較少(一般不會(huì)超過(guò) 3 次)的特點(diǎn)，在此采用了一種拼接和去冗相結(jié)合的路徑搜索算法。該算法的特點(diǎn)是能適應(yīng)鐵路客運(yùn)服務(wù)網(wǎng)的龐大規(guī)模；效率較高，可以滿足不同使用群體的計(jì)算速度要求；具有可擴(kuò)展性，對(duì)于混合服務(wù)網(wǎng)下的分層路徑搜索同樣適用。

3.1 算法描述

算法的主要流程為：簡(jiǎn)化站點(diǎn)并生成直達(dá)弧，判斷當(dāng)前弧是否能產(chǎn)生k條路徑。能夠則輸出結(jié)果，不能則進(jìn)行一次弧的拼接，完成后再次進(jìn)行判斷，直至達(dá)到拼接次數(shù)上限或找到k條路徑為止。各步驟詳述如下。

3.1.1 簡(jiǎn)化站點(diǎn)

假設(shè)一條簡(jiǎn)易的單向(從左到右)列車開(kāi)行方案線 Plan1，如圖2 所示。線上各點(diǎn)表示列車途經(jīng)的所有車站。其中，大圓點(diǎn)表示的是停站的車站(A、B、C、D)，小圓點(diǎn)表示的是途經(jīng)不停站的車站(a、b、c、d、e)。

圖2 一條簡(jiǎn)易列車開(kāi)行方案線 Plan1

對(duì)于旅客而言，不停站即表示不能到達(dá)，因此可保留停站的車站，將圖2 簡(jiǎn)化為如圖3 所示的列車開(kāi)行方案線。

圖3 簡(jiǎn)化后的列車開(kāi)行方案線 Plan1

3.1.2 建立直達(dá)弧

根據(jù)圖3 畫(huà)出旅客在這條列車開(kāi)行方案線中可以直達(dá)的乘車弧，如圖4 所示。

圖4 標(biāo)記弧后的列車開(kāi)行方案線 Plan1

3.1.3 弧的拼接

引入一個(gè)新的簡(jiǎn)化列車開(kāi)行方案線 Plan2，標(biāo)記弧后如圖5 所示。兩個(gè)列車開(kāi)行方案線 Plan1和 Plan2 的弧集合如表1 所示。

圖5 標(biāo)記弧后的列車開(kāi)行方案線 Plan2

表1 Plan1和 Plan2 的直達(dá)弧記錄

選取直達(dá)弧集合中的兩弧進(jìn)行拼接?；〉幕酒唇訔l件為：若弧 1 的終點(diǎn)與弧 2 的起點(diǎn)相同，則選取弧 1 的起點(diǎn)與弧 2 的終點(diǎn)組成一個(gè)新的弧，加入到一次換乘弧的集合中。本例中拼接一次的結(jié)果如圖6 所示。

圖6 一次拼接過(guò)程及結(jié)果

如圖6 所示，在兩個(gè)列車開(kāi)行方案線中，都沒(méi)有 A→E 的直達(dá)弧。但通過(guò)一次拼接后，在一次換乘弧中產(chǎn)生了 A→E。表明旅客可以通過(guò)一次換乘從 A 站到達(dá) E 站。依次類推，如將一次換乘弧再與直達(dá)弧進(jìn)行拼接，則可得到一個(gè)二次換乘弧的集合。N次換乘的結(jié)果可以由N－1 次換乘弧與直達(dá)弧拼接得到。因此，兩站間只要存在可以到達(dá)的乘車方案，就可通過(guò)N次換乘弧的構(gòu)建得到合理結(jié)果。

3.1.4 不同模式的路徑搜索

經(jīng)過(guò)拼接之后，需要的k條路徑全部包含在多次拼接弧的集合中。為了從中篩選出旅客所需的有效路徑，在此采用“效用函數(shù)”這一定義來(lái)表現(xiàn)旅客對(duì)某乘車方案的滿意程度，并通過(guò)效用函數(shù)對(duì)已篩選出的k個(gè)乘車方案進(jìn)行對(duì)比排序。主要定義以下 4 種效用函數(shù)。

（1）時(shí)間。時(shí)間函數(shù)表示為：

式中：T為旅客旅行時(shí)間；Tk為列車純運(yùn)行時(shí)分；ti為第i個(gè)車站的起停附加時(shí)分；wi為第i個(gè)車站的停站時(shí)分；n為列車沿途停站的車站數(shù)。

（2）路程。路程是列車在物理網(wǎng)線路上所經(jīng)過(guò)路徑的總長(zhǎng)度。

（3）換乘次數(shù)。換乘次數(shù)是指一次旅行中旅客換乘的總次數(shù)。

（4）費(fèi)用支出。費(fèi)用支出是旅客在出行過(guò)程中購(gòu)票、換乘等方面產(chǎn)生的經(jīng)濟(jì)支出。

由于目前在列車開(kāi)行方案中對(duì)于經(jīng)濟(jì)因素尚未考慮，因此在系統(tǒng)設(shè)計(jì)實(shí)現(xiàn)過(guò)程中只考慮前 3 種效用函數(shù)。根據(jù)效用函數(shù)將合理路徑提取、處理后就完成了一次路徑搜索的過(guò)程。

3.2 算法優(yōu)化

并不是所有符合以上條件的兩個(gè)弧都可以進(jìn)行拼接，如果不對(duì)拼接過(guò)程進(jìn)行優(yōu)化，則會(huì)導(dǎo)致運(yùn)行效率降低和路徑結(jié)果不合理等問(wèn)題。因此，每一次拼接時(shí)都會(huì)進(jìn)行以下兩種優(yōu)化。

3.2.1 數(shù)據(jù)冗余處理

從上述拼接例子中可以發(fā)現(xiàn)，拼接時(shí)換乘弧集合里會(huì)保留所有可行的弧信息。但在實(shí)際應(yīng)用中，這些信息并不都會(huì)被用到。例如，A→C 的最優(yōu)換乘方案，可由 A→B 與 B→C 拼接獲得，其中 A→B也是由拼接獲得的弧。如果只想獲取兩條 A→C 的最優(yōu)方案，那么 A→B 只需要保留兩條最優(yōu)弧即可，其他弧都屬于冗余信息。當(dāng)列車開(kāi)行方案和停站數(shù)量較多或拼接次數(shù)很大時(shí)，冗余信息會(huì)極大地影響程序的運(yùn)行效率。

因此，每次拼接完成后，都對(duì)新生成的換乘弧集合進(jìn)行檢索。如果發(fā)現(xiàn)兩點(diǎn)間弧的數(shù)量大于k條最短路的k值，則將兩點(diǎn)間的弧按照效用函數(shù)進(jìn)行排序，保留最優(yōu)的k個(gè)弧，而將其他弧刪除。

3.2.2 防止環(huán)路的生成

列車開(kāi)行方案集合中必定存在雙向的記錄。在路徑搜索系統(tǒng)設(shè)計(jì)中，雙向開(kāi)行方案會(huì)被拆分成兩個(gè)獨(dú)立的單向開(kāi)行方案來(lái)處理。因此，可能要對(duì)A→B、B→A 或 A→B、B→C、C→A 的換乘弧進(jìn)行拼接，導(dǎo)致 A→A 的環(huán)形弧出現(xiàn)。

環(huán)形弧是沒(méi)有實(shí)際意義的，有環(huán)形弧存在的方案顯然是不合理的，并且環(huán)形弧的出現(xiàn)會(huì)降低程序運(yùn)行效率，所以采取一些處理方法杜絕環(huán)形弧的出現(xiàn)。假如要對(duì)弧 A 和弧 B 進(jìn)行拼接，拼接之前必須加入一次環(huán)形弧檢查。若弧 A 的子弧集中存在一個(gè)子弧的起始站等于弧 B 的到達(dá)站，則放棄此次拼接。

4 系統(tǒng)實(shí)現(xiàn)

服務(wù)網(wǎng)絡(luò)路徑搜索系統(tǒng)主要面向鐵路部門(mén)和旅客兩類用戶。鐵路部門(mén)要求系統(tǒng)在實(shí)現(xiàn)時(shí)，首先保證與其他子系統(tǒng)之間具有良好的功能接口，使服務(wù)網(wǎng)絡(luò)路徑搜索系統(tǒng)能為其他子系統(tǒng)提供服務(wù)；同時(shí)還要求系統(tǒng)加入分析對(duì)比模塊，以幫助鐵路部門(mén)合理決策。當(dāng)面向旅客時(shí)，要求系統(tǒng)具有靈活、易操作性；系統(tǒng)得到的搜索結(jié)果應(yīng)清晰、易懂，使整個(gè)系統(tǒng)擁有良好的用戶體驗(yàn)。本著以上設(shè)計(jì)原則，結(jié)合前述有關(guān)服務(wù)網(wǎng)絡(luò)和路徑搜索的理論基礎(chǔ)，設(shè)計(jì)并實(shí)現(xiàn)客運(yùn)服務(wù)網(wǎng)路徑搜索系統(tǒng)。該系統(tǒng)在 NET 平臺(tái)下運(yùn)用 C# 語(yǔ)言開(kāi)發(fā)而成。

4.1 系統(tǒng)界面

客運(yùn)服務(wù)網(wǎng)路徑搜索系統(tǒng)是“列車開(kāi)行方案生成優(yōu)化與決策支持系統(tǒng)”的一個(gè)子系統(tǒng)，進(jìn)入本系統(tǒng)后，主界面如圖7所示。

4.2 系統(tǒng)功能模塊

系統(tǒng)的各種功能圍繞服務(wù)路徑搜索算法進(jìn)行設(shè)計(jì)，可以實(shí)現(xiàn)以車站、城市和客流小區(qū)作為起訖點(diǎn)的服務(wù)路徑搜索，進(jìn)一步可以根據(jù)是否存在服務(wù)路徑將 OD 客流進(jìn)行分類。該系統(tǒng)還可以對(duì)k條服務(wù)路徑進(jìn)行排序處理，并能顯示服務(wù)路徑所屬的物理路徑。在圖7 中，A 為車站輸入模塊，B 為城市輸入模塊，C 為小區(qū)分類模塊，D 為參數(shù)輸入模塊，E 為導(dǎo)出處理模塊，F(xiàn) 為服務(wù)路徑顯示模塊，G 為物理路徑模塊。

5 案例分析

對(duì)設(shè)計(jì)完成的系統(tǒng)導(dǎo)入一個(gè)列車開(kāi)行方案和其對(duì)應(yīng)的客流計(jì)劃，進(jìn)行客運(yùn)服務(wù)網(wǎng)絡(luò)路徑搜索系統(tǒng)測(cè)試。列車開(kāi)行方案以某高速鐵路為基礎(chǔ)，并包含適量的跨線列車開(kāi)行方案。

圖7 客運(yùn)服務(wù)網(wǎng)絡(luò)搜索系統(tǒng)主界面

5.1 輸入信息

輸入方案中包含 27 條開(kāi)行方案線和 19 個(gè)可停站的車站，共開(kāi)行 141 對(duì)列車。該服務(wù)網(wǎng)絡(luò)中形成的直達(dá)弧為 1 106 個(gè)。底層物理路網(wǎng)包括 5 條線路和59 個(gè)車站；客流方案包括 40 個(gè)客流小區(qū)及小區(qū)間的237 個(gè)客流 OD 對(duì)。

5.2 輸出結(jié)果

根據(jù)用戶的不同目的設(shè)置搜索參數(shù)，進(jìn)行服務(wù)路徑搜索。本案例設(shè)置允許最大換乘次數(shù)為 1，所求 K 最短路的K值為 6；效用不超過(guò)最短路的倍數(shù)值為 2，即所有路徑的距離、時(shí)間效用值小于最短路距離、時(shí)間效用值的2 倍；效用函數(shù)為“換乘次數(shù)優(yōu)先”。以蚌埠—杭州的客流 OD 對(duì)為例，換乘次數(shù)優(yōu)先的路徑搜索結(jié)果的前 3 條路徑信息如表2 所示。

若將效用函數(shù)改為“時(shí)間優(yōu)先”(即搜索乘車時(shí)間最短的服務(wù)路徑)，則路徑搜索結(jié)果產(chǎn)生了變化。時(shí)間優(yōu)先的路徑搜索結(jié)果的前 3 條路徑信息如表3 所示。

由此可見(jiàn)，效用函數(shù)選擇不同，用戶會(huì)得到不同的服務(wù)路徑。在算例的服務(wù)網(wǎng)絡(luò)規(guī)模下，該 OD 路徑搜索的平均計(jì)算時(shí)間小于 0.1 s。服務(wù)網(wǎng)路徑搜索系統(tǒng)在合理的計(jì)算時(shí)間內(nèi)，生成了合理的乘車方案，可以滿足 OD 配流和出行規(guī)劃的要求。本次實(shí)驗(yàn)結(jié)果證明，該服務(wù)網(wǎng)絡(luò)路徑搜索系統(tǒng)實(shí)用、有效，能夠適應(yīng)鐵路客運(yùn)服務(wù)網(wǎng)絡(luò)的結(jié)構(gòu)特征，滿足客流分配和列車開(kāi)行方案優(yōu)化的需要。

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

結(jié)合國(guó)內(nèi)外現(xiàn)有研究，選取一種可以完整描述旅客乘車過(guò)程的服務(wù)網(wǎng)絡(luò)結(jié)構(gòu)。分析鐵路列車開(kāi)行方案、乘車方案等數(shù)據(jù)結(jié)構(gòu)，建立一種適合客運(yùn)服務(wù)網(wǎng)絡(luò)的路徑搜索算法，并且實(shí)現(xiàn)了可與 OD客流信息相結(jié)合的服務(wù)網(wǎng)絡(luò)路徑搜索系統(tǒng)。最后，根據(jù)某高速鐵路的列車開(kāi)行方案對(duì)服務(wù)網(wǎng)絡(luò)路徑搜索系統(tǒng)進(jìn)行測(cè)試，取得了預(yù)期的結(jié)果。但在乘車效用的豐富、優(yōu)化方面尚有不足，需要進(jìn)行更深入的研究。

表2 換乘次數(shù)優(yōu)先的路徑搜索結(jié)果

表3 時(shí)間優(yōu)先的路徑搜索結(jié)果

：

[1] 張 彥. 鐵路客票中轉(zhuǎn)換乘多徑路選擇問(wèn)題研究[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，1997(8)：11-13.

[2] 史 峰，鄧連波. 旅客換乘網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)[J]. 鐵道科學(xué)與工程學(xué)報(bào)，2004，1(1)：78-82.

[3] M.Ridwan. Fuzzy Preference based Traffic Assignment Problem[J]. Transportation Research Part C，2004，12(3-4)：209-233.

[4] 楊 群，關(guān) 偉，張國(guó)伍. 基于合理多路徑的路徑選擇方法的研究[J]. 管理工程，2002，16(4)：42-45.

[5] Noto.M,Sato.H. A Method for the Shortest Path Search by Extended Dijkstra Algorithm[J]. Systems,Man,and Cybernetics,2000 IEEE International Conference，2000(3)：2316-2320.

[6] 楊同慶. 基于彈性需求的客運(yùn)專線開(kāi)行方案優(yōu)化設(shè)計(jì)研究[D]. 北京：北京交通大學(xué)，2009.

Research and Realization of Route Search Algorithm of Railway Passenger Traffic Service Network

LIU Jian,NIE Lei

(School of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China)

Based on directed transfer service network which reflecting passenger travelling chain,a K shortest route algorithm combined with joining and redundancy eliminating is applied,and a route search system of passenger traffic service network is designed and realized. By using the system and according to passenger flow plan and train operation diagram,the reasonable transfer scheme with the mode of multi-route search could be achieved. By taking a certain high-speed railway and train operation diagram of relative railway network as well as corresponding passenger flow plan as examples,the route search algorithm is tested and achieved prospective result,but the enrichment and optimization of riding avail are need to be studied.

Railway Passenger Transportation; Route Search; Service Network; K Shortest Route

1003-1421(2012)12-0058-06

O157.5:U293.3

A

2012-09-14

國(guó)家自然科學(xué)基金(60870012)；鐵道部科技研究開(kāi)發(fā)計(jì)劃項(xiàng)目(2008X027-A)；科技部、鐵道部聯(lián)合支撐計(jì)劃項(xiàng)目(2009BAG12A10)；軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室(北京交通大學(xué))自主研究課題資助(RCS2009ZT008)

何 瑩