鐵路客票快速經(jīng)由算法的研究與實(shí)現(xiàn)

張 霞，單杏花，戴琳琳，尹伊伊

（中國鐵道科學(xué)研究院集團(tuán)有限公司 電子計(jì)算技術(shù)研究所，北京 100081）

近年來，中國交通運(yùn)輸行業(yè)高速發(fā)展，特別是高鐵成網(wǎng)后，高速列車和動(dòng)車組列車開行密度逐漸增大，為廣大旅客的出行提供了很大的便利。但是，隨著旅客出行數(shù)量的增長，有些問題也日益突出。其中，站點(diǎn)與站點(diǎn)之間的可達(dá)性問題成為困擾旅客出行的主要因素，具體來說，旅客在通過網(wǎng)絡(luò)進(jìn)行購票時(shí)，經(jīng)常會遇到始發(fā)站與終點(diǎn)站間沒有直達(dá)車次或直達(dá)車次沒有余票的情況，此時(shí)，旅客往往只能自行選擇換乘站，再查詢是否有始發(fā)站到換乘站以及換乘站到終點(diǎn)站的車次，這一過程操作復(fù)雜，耗時(shí)巨大，且旅客單靠人力根本無法全面掌握始發(fā)站與終點(diǎn)站間的多個(gè)換乘線路，進(jìn)而往往無法選擇合適的換乘站。并且，在春運(yùn)等時(shí)間段，還很有可能遭遇所選的換乘站也沒有余票的情形，這導(dǎo)致旅客的出行極為不便。車站發(fā)售通票的功能也僅限于路徑規(guī)劃[1]。因此，如何自動(dòng)為旅客提供有效的換乘方案，成為目前亟待解決的技術(shù)問題。

在此背景下，本文中的鐵路客票經(jīng)由算法是指，在給定列車發(fā)站X和到站Y的情況下，基于中轉(zhuǎn)次數(shù)、運(yùn)行里程、時(shí)間、總票價(jià)和中轉(zhuǎn)代價(jià)等因素，向旅客提供推薦列車中轉(zhuǎn)線路的算法。

如果將一趟列車從起始站到終點(diǎn)站看作一個(gè)有向直線，沿途各站為該有向直線的各點(diǎn)，那么經(jīng)由算法可以轉(zhuǎn)化為有向圖的最短路徑算法。同時(shí)，所有停靠站都可以很容易地轉(zhuǎn)化為某種唯一編號，鐵路的經(jīng)由算法就轉(zhuǎn)化為基于N個(gè)節(jié)點(diǎn)的有向圖，計(jì)算兩個(gè)節(jié)點(diǎn)之間的最短（最優(yōu)）路徑的問題[2]。這里，N為沿途的車站數(shù)。

文中所述的基于經(jīng)由算法的最短路徑算法，是指換乘次數(shù)最少條件下的最短（最優(yōu)）路徑，再輔以考慮里程、時(shí)間和票價(jià)等綜合評分因素，為旅客提供最合理的出行的接續(xù)方案。因此簡單的圖論最短路徑算法不能滿足經(jīng)由算法的實(shí)際應(yīng)用需求。

1 簡單的圖論算法

簡單的圖論算法就是通過有向圖廣度搜索（BFS）或深度搜索（DFS），把出發(fā)點(diǎn)i至到達(dá)點(diǎn)j的所有路徑找出，然后列出最短路徑。在搜索過程中，需要排除回路，即經(jīng)過出發(fā)點(diǎn)之后不能再回溯到i，且達(dá)到終點(diǎn)j則停止并返回。

簡單的圖論算法中，線路信息即為有向圖，有向圖可以通過鄰接表（Adjacency List）或鄰接矩陣（Adjacency Matrix）來描述圖中各個(gè)節(jié)點(diǎn)之間的連通屬性，其中，鄰接表使用頂點(diǎn)及其所鄰接的邊來表示，而鄰接矩陣使用N×N的數(shù)組來表示各點(diǎn)間的連通性。圖論算法的效率問題直接取決于數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)及方式，使用鄰接表，時(shí)間復(fù)雜度為O(N+e)，e為常量；而使用鄰接矩陣，時(shí)間復(fù)雜度為O(N2)。

簡單經(jīng)由算法只能找到路徑最短的經(jīng)由通路[3]，對于實(shí)際客票經(jīng)由問題，還需考慮列車票價(jià)、中轉(zhuǎn)次數(shù)等，顯然不是客票經(jīng)由算法的最佳選擇[4]?？推苯?jīng)由不是簡單的徑路問題，需要考慮車次實(shí)際開行情況[5]。本文基于傳統(tǒng)的經(jīng)典圖論算法并結(jié)合鐵路實(shí)際業(yè)務(wù)，提出快速經(jīng)由算法。

2 經(jīng)由傳遞閉包

2.1 傳遞閉包

在數(shù)學(xué)概念中，在集合X上的二元關(guān)系R的傳遞閉包是指包含R的X上的最小的傳遞關(guān)系。從定義上很容易看出，對于經(jīng)由算法來說，集合X就是所有?？空镜募?，關(guān)系R就是任意兩個(gè)?？空局g是否有列車直達(dá)，即可用鄰接矩陣表示，那么R的傳遞閉包（簡稱：經(jīng)由傳遞閉包）就是任意兩個(gè)?？空鹃g是否最終可達(dá)。

引入經(jīng)由傳遞閉包是為了檢驗(yàn)給定的兩個(gè)?？空臼欠褡罱K可達(dá)。在快速經(jīng)由算法中，根據(jù)經(jīng)由傳遞閉包中兩個(gè)?？空镜目蛇_(dá)狀態(tài)，決定是否繼續(xù)計(jì)算相關(guān)中轉(zhuǎn)站，它是減少無效節(jié)點(diǎn)計(jì)算的有力方法。

2.2 弗洛伊德算法

計(jì)算傳遞閉包的經(jīng)典算法是弗洛伊德算法（Floyd-Warshall algorithm）[6]，其原理是動(dòng)態(tài)規(guī)劃：設(shè)路網(wǎng)圖為D，其中，i點(diǎn)為發(fā)站、j點(diǎn)為到站，k為路網(wǎng)中的其他站點(diǎn)，Di,j,k為發(fā)站至到站且途徑k中某個(gè)節(jié)點(diǎn)的最短路徑的代價(jià)，i、j、k為1, 2, …, n。

（1）如果最短（最優(yōu)）路徑經(jīng)過點(diǎn)k，則Di,j,k=Di,k,k-1+Dk,j,k-1。

（2）如果最短（最優(yōu)）路徑不經(jīng)過點(diǎn)k，則Di,j,k=Di,j,k-1。

在實(shí)際運(yùn)算中，算法成本需要考慮空間成本及時(shí)間成本，為節(jié)約空間，可以在原基礎(chǔ)上通過迭代處理做降維操作，將空間降至為二維，如下所示：

Di,j指發(fā)站i到達(dá)目的地j時(shí)的總代價(jià)，即車票、耗時(shí)、里程等綜合代價(jià)值，當(dāng)Di,j為∞，代表i、j兩站點(diǎn)之間是不可到達(dá)的。

弗洛伊德算法的空間復(fù)雜度為O(N2)，時(shí)間復(fù)雜度為O(N3)。這個(gè)算法除了可以計(jì)算出傳遞閉包外，還可以算出每兩個(gè)頂點(diǎn)間的最短路徑。當(dāng)然這個(gè)最短路徑中的點(diǎn)到點(diǎn)的代價(jià)，可以是中轉(zhuǎn)次數(shù)、里程、運(yùn)行時(shí)間以及票價(jià)的加權(quán)值。由于該算法的時(shí)間復(fù)雜度較高，一個(gè)性能優(yōu)化的做法是提前根據(jù)預(yù)設(shè)權(quán)值計(jì)算出經(jīng)由傳遞閉包矩陣，那么實(shí)際應(yīng)用中，需要查詢時(shí)，時(shí)間消耗僅有O(1)。這個(gè)算法可以基本滿足經(jīng)由算法的要求，但是還具有局限性，比如，旅客希望自己選擇中轉(zhuǎn)次數(shù)，然后設(shè)定票價(jià)區(qū)間或中轉(zhuǎn)時(shí)間差，那么這個(gè)算法需要重新計(jì)算點(diǎn)到點(diǎn)的代價(jià)，運(yùn)行時(shí)間較長，而且僅能有一條最短路徑的推薦，不符合旅客購票心理。

3 快速經(jīng)由算法

快速經(jīng)由算法需要解決如下旅客需求：

（1）接受旅客提出的中轉(zhuǎn)次數(shù)的要求；

（2）在（1）的基礎(chǔ)上，還需要接受旅客對換乘車次的里程，票價(jià)，中轉(zhuǎn)時(shí)間差的要求。

3.1 中轉(zhuǎn)次數(shù)

根據(jù)旅客提出的中轉(zhuǎn)次數(shù)來選擇鐵路經(jīng)由路線時(shí)，需要使用鄰接矩陣的特性。

設(shè)路網(wǎng)圖為G，具有N個(gè)乘車站的鄰接矩陣A，使用二維數(shù)組N×N存放各乘車站之間關(guān)系數(shù)據(jù)，ai,j=1 表示i, j之間互通，否則 ai,j=0，表示i、j之間不可達(dá)。

也就是說，可以通過Ak來判斷停靠站i到j(luò)是否存在中轉(zhuǎn)次數(shù)為k-1的路線，如果存在，可以根據(jù)以下算法得到所有中轉(zhuǎn)站：

function find Route Node(start Node, end Node, k){

if(k＜=1){

stack.push(#);//end of one route

return;

}

if(Ak== 1){

stack.push(end Node);

}

byte [] B = Astart Node,(1,…,n)k-1& A(1,…,n),end Node

for( index=0; index ＜=n; index++){

if(Bindex == 1){

find Route Node(start Node, index,k-1);

}

}

}

該算法的時(shí)間復(fù)雜度為O(Nk)，但前提是A2,…,Ak都已算好，Ak一次計(jì)算的時(shí)間復(fù)雜度為O(N3)。

3.2 附加需求

將旅客提出的里程、時(shí)間、票價(jià)等附加要求加入到查詢條件中，需要通過鄰接矩陣中附加信息來過濾。在構(gòu)建鄰接矩陣時(shí)，除了標(biāo)注點(diǎn)到點(diǎn)的連通性外，還可以增加類似車次數(shù)據(jù)。

這些記錄著車次信息的矩陣元素，均可為算法描述時(shí)間、費(fèi)用提供依據(jù)。

4 優(yōu)化及改進(jìn)設(shè)計(jì)

快速經(jīng)由算法可以通過程序具體實(shí)現(xiàn)方法來優(yōu)化性能，改進(jìn)用戶體驗(yàn)。

4.1 數(shù)據(jù)預(yù)處理

數(shù)據(jù)提前處理生成，并在程序啟動(dòng)時(shí)就載入內(nèi)存。這里的數(shù)據(jù)包括車次信息，?？空拘畔ⅲ锍绦畔?，票價(jià)信息等[7]。數(shù)據(jù)提前處理包括為?？空揪幪?，將列車相關(guān)信息組織成容易訪問和獲取的結(jié)構(gòu)（其中，可以將全車次哈希成唯一數(shù)字ID，提升比較效率），通過將全車次數(shù)據(jù)排序預(yù)處理操作，提升后續(xù)計(jì)算的查詢操作；根據(jù)停靠站信息構(gòu)建經(jīng)由鄰接矩陣時(shí)，將站到站的直達(dá)列車信息附加到經(jīng)由鄰接矩陣元素結(jié)構(gòu)中，在這過程中，可以根據(jù)預(yù)設(shè)的條件把一些列車過濾。

4.2 中轉(zhuǎn)次數(shù)限定

提供合理的中轉(zhuǎn)次數(shù)選擇?？焖俳?jīng)由算法在理論上支持旅客輸入任意中轉(zhuǎn)次數(shù)，但每個(gè)Ak的計(jì)算需要O(Nk)，比較合適的做法是假設(shè)一個(gè)中轉(zhuǎn)次數(shù)的最高合理數(shù)k，然后提前生成A2, …, Ak，比如認(rèn)為要求中轉(zhuǎn)7次以上基本不可能，那么可以提前生成A2,…, A7。這樣，可以很大程度上節(jié)省運(yùn)算時(shí)間。

4.3 測試效果

將經(jīng)由算法根據(jù)鐵路的業(yè)務(wù)進(jìn)行優(yōu)化后，基于分布式內(nèi)存數(shù)據(jù)庫集群GemFire[8]的硬件環(huán)境下搭建了鐵路旅程規(guī)劃原型系統(tǒng)，并進(jìn)行了實(shí)例測試。測試流程為模擬旅客輸入基本的查詢條件：乘車站、到站，乘車日期，算法根據(jù)旅客對時(shí)間、票價(jià)、換乘概率的要求對接續(xù)方案綜合評分，高效計(jì)算出滿足需求的接續(xù)方案。

測試樣本數(shù)據(jù)包括既有的鐵路路網(wǎng)數(shù)據(jù)、全國辦理客運(yùn)業(yè)務(wù)所有車站，及1 000個(gè)換乘站樣本集，將火車站及開行車的樣本數(shù)據(jù)初始化為路網(wǎng)圖，如圖1所示。

圖 1 數(shù)據(jù)初始化

測試評價(jià)標(biāo)準(zhǔn)包括：換乘車站是否合理；接續(xù)方案是否可靠；綜合評價(jià)是否易于接受。換乘方案的測試用例如表1所示。

表1 換乘方案測試用例

如圖2所示，出發(fā)城市為北京，到達(dá)城市為穆棱，兩地之間經(jīng)過算法計(jì)算獲得9個(gè)建議的一次換乘城市的列表（其中，濱江與哈爾濱東、哈爾濱西為同城車站，長春與長春西為同城車站，高花與沈陽、沈陽北、沈陽南為同城車站等），與余票數(shù)據(jù)結(jié)合后，旅客獲得聯(lián)程產(chǎn)品如圖3所示。

圖2 簡單展現(xiàn)一次換乘里程權(quán)重優(yōu)先的方案圖

測試過程中，設(shè)計(jì)了總體測試方案，每輪測試又設(shè)計(jì)了重點(diǎn)需要解決的方案，選擇了具有代表性的城鎮(zhèn)，涵蓋了省會、大多數(shù)大中型城市、部分末梢車站、全部鐵路樞紐車站。從測試結(jié)果看，測試方案涵蓋面廣，測試內(nèi)容較為合理，對修正錯(cuò)誤，調(diào)整、優(yōu)化系統(tǒng)內(nèi)容起到了較好的作用。測試結(jié)果表明，算法基于預(yù)處理數(shù)據(jù)方式，計(jì)算效率高效，換乘的方案比較合理、實(shí)用，初步達(dá)到了可以進(jìn)行公測的條件。

圖3 一次換乘結(jié)果展示

5 結(jié)束語

鐵路經(jīng)由算法根據(jù)旅客的個(gè)性化需求，計(jì)算出的接續(xù)方案擁有不同的側(cè)重點(diǎn)和靈活性。本文所研究的快速經(jīng)由算法可以很好地解決根據(jù)旅客經(jīng)由次數(shù)需求，以及附加的里程、票價(jià)、中轉(zhuǎn)時(shí)間差要求的鐵路經(jīng)由問題。通過實(shí)際原型系統(tǒng)測試，該算法性能高效，運(yùn)行平穩(wěn)，證明了算法的正確性。