鐵路客票快速經由算法的研究與實現

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

（中國鐵道科學研究院集團有限公司 電子計算技術研究所，北京 100081）

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

在此背景下，本文中的鐵路客票經由算法是指，在給定列車發站X和到站Y的情況下，基于中轉次數、運行里程、時間、總票價和中轉代價等因素，向旅客提供推薦列車中轉線路的算法。

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

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

1 簡單的圖論算法

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

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

簡單經由算法只能找到路徑最短的經由通路[3]，對于實際客票經由問題，還需考慮列車票價、中轉次數等，顯然不是客票經由算法的最佳選擇[4]。客票經由不是簡單的徑路問題，需要考慮車次實際開行情況[5]。本文基于傳統的經典圖論算法并結合鐵路實際業務，提出快速經由算法。

2 經由傳遞閉包

2.1 傳遞閉包

在數學概念中，在集合X上的二元關系R的傳遞閉包是指包含R的X上的最小的傳遞關系。從定義上很容易看出，對于經由算法來說，集合X就是所有停靠站的集合，關系R就是任意兩個停靠站之間是否有列車直達，即可用鄰接矩陣表示，那么R的傳遞閉包（簡稱：經由傳遞閉包）就是任意兩個停靠站間是否最終可達。

引入經由傳遞閉包是為了檢驗給定的兩個停靠站是否最終可達。在快速經由算法中，根據經由傳遞閉包中兩個停靠站的可達狀態，決定是否繼續計算相關中轉站，它是減少無效節點計算的有力方法。

2.2 弗洛伊德算法

計算傳遞閉包的經典算法是弗洛伊德算法（Floyd-Warshall algorithm）[6]，其原理是動態規劃：設路網圖為D，其中，i點為發站、j點為到站，k為路網中的其他站點，Di,j,k為發站至到站且途徑k中某個節點的最短路徑的代價，i、j、k為1, 2, …, n。

（1）如果最短（最優）路徑經過點k，則Di,j,k=Di,k,k-1+Dk,j,k-1。

（2）如果最短（最優）路徑不經過點k，則Di,j,k=Di,j,k-1。

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

Di,j指發站i到達目的地j時的總代價，即車票、耗時、里程等綜合代價值，當Di,j為∞，代表i、j兩站點之間是不可到達的。

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

3 快速經由算法

快速經由算法需要解決如下旅客需求：

（1）接受旅客提出的中轉次數的要求；

（2）在（1）的基礎上，還需要接受旅客對換乘車次的里程，票價，中轉時間差的要求。

3.1 中轉次數

根據旅客提出的中轉次數來選擇鐵路經由路線時，需要使用鄰接矩陣的特性。

設路網圖為G，具有N個乘車站的鄰接矩陣A，使用二維數組N×N存放各乘車站之間關系數據，ai,j=1 表示i, j之間互通，否則 ai,j=0，表示i、j之間不可達。

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

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);

}

}

}

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

3.2 附加需求

將旅客提出的里程、時間、票價等附加要求加入到查詢條件中，需要通過鄰接矩陣中附加信息來過濾。在構建鄰接矩陣時，除了標注點到點的連通性外，還可以增加類似車次數據。

這些記錄著車次信息的矩陣元素，均可為算法描述時間、費用提供依據。

4 優化及改進設計

快速經由算法可以通過程序具體實現方法來優化性能，改進用戶體驗。

4.1 數據預處理

數據提前處理生成，并在程序啟動時就載入內存。這里的數據包括車次信息，停靠站信息，里程信息，票價信息等[7]。數據提前處理包括為停靠站編號，將列車相關信息組織成容易訪問和獲取的結構（其中，可以將全車次哈希成唯一數字ID，提升比較效率），通過將全車次數據排序預處理操作，提升后續計算的查詢操作；根據停靠站信息構建經由鄰接矩陣時，將站到站的直達列車信息附加到經由鄰接矩陣元素結構中，在這過程中，可以根據預設的條件把一些列車過濾。

4.2 中轉次數限定

提供合理的中轉次數選擇。快速經由算法在理論上支持旅客輸入任意中轉次數，但每個Ak的計算需要O(Nk)，比較合適的做法是假設一個中轉次數的最高合理數k，然后提前生成A2, …, Ak，比如認為要求中轉7次以上基本不可能，那么可以提前生成A2,…, A7。這樣，可以很大程度上節省運算時間。

4.3 測試效果

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

測試樣本數據包括既有的鐵路路網數據、全國辦理客運業務所有車站，及1 000個換乘站樣本集，將火車站及開行車的樣本數據初始化為路網圖，如圖1所示。

圖 1 數據初始化

測試評價標準包括：換乘車站是否合理；接續方案是否可靠；綜合評價是否易于接受。換乘方案的測試用例如表1所示。

表1 換乘方案測試用例

如圖2所示，出發城市為北京，到達城市為穆棱，兩地之間經過算法計算獲得9個建議的一次換乘城市的列表（其中，濱江與哈爾濱東、哈爾濱西為同城車站，長春與長春西為同城車站，高花與沈陽、沈陽北、沈陽南為同城車站等），與余票數據結合后，旅客獲得聯程產品如圖3所示。

圖2 簡單展現一次換乘里程權重優先的方案圖

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

圖3 一次換乘結果展示

5 結束語

鐵路經由算法根據旅客的個性化需求，計算出的接續方案擁有不同的側重點和靈活性。本文所研究的快速經由算法可以很好地解決根據旅客經由次數需求，以及附加的里程、票價、中轉時間差要求的鐵路經由問題。通過實際原型系統測試，該算法性能高效，運行平穩，證明了算法的正確性。