基于網絡最短路徑的鐵路購票智能推薦算法研究

劉勝來，李瑞敏

（清華大學 土木工程系，北京 100084）

2013年春運期間，全國鐵路部門共發送2.4億人次[1]，如此龐大的出行量也讓買票成了一個難題。自網上售票以來，車站買票排隊問題已經大為緩解，但是無票可買的問題仍然大量存在。而另一方面，部分鐵路路段卻出現了大量空座現象。由此，可以考慮通過換乘的方式，變直達為換乘，實現相應的出行。

事實上，目前已有個別出行者針對春運期間一票難求的問題，通過換乘來解決長途出行，而最終可能在多支付一定費用的情況下，不僅解決了出行的問題，而且還可能縮短行程時間[2]。在當前我國高速鐵路網基本覆蓋主要干線的情況下，部分二、三線城市之間的出行通過普速鐵路與高速鐵路的結合，可能實現更短的出行時間。

通過換乘實現出行并可能減少出行時間的實施需要有合理計算方法的支持。本文基于鐵路網絡的路徑優化問題，根據已有鐵路列車時刻表，給出了一種行之有效的最優路徑求解的解決方案。

本方案基于現行鐵道部門實際擁有的線路信息，通過計算優化，提供給用戶智能化的線路推薦服務。可以自動生成兩地間到達速度最快和花費費用最少的兩種方案，幫助用戶達到省錢和省時的目的。

1 研究現狀

為用戶提供換乘策略并給出旅行路線指導方案，這個功能已經有不少網站正在嘗試，但卻能發現不少可改進的地方。

1.1 12306網站

鐵道部門購票唯一官方網站12306提供了一項鐵路旅程規劃功能，如圖1所示，但卻沒有達到相應的旅程規劃的實用性。

圖1 12306網站鐵路旅程規劃功能界面截圖（2013.7.10）

從輸入界面中可以看到，它需要用戶手動輸入換乘城市，甚至需要換乘日期，而且只能換乘一次。其實質僅相當于在余票查詢窗口的兩次搜索功能放在一個窗口顯示，并沒有實現真正的旅途規劃，更不可能設計出多次換乘的乘車路線。除了它能及時根據網站數據查出現在是否有票外，沒有太多實際參考價值。

1.2 火車網（www.huoche.com.cn）

火車網的車次查詢功能通過輸入起始與終止站點即可查詢到需要的車次，對沒有直達車次的則提供一系列中轉方案。

在提供的多種方案中，給出了一個總用時的指標，但根據12306網站提供的列車信息核查，這個總時間實際指的是兩列列車運行時間的和，換乘中間的時間差并沒有考慮。因此該網站給出的推薦出行方案參考價值不大。另外，該網站與12306網站還存在數據誤差，其實用性有限。

針對上述不足，本文結合網絡最短路徑算法，研究開發了一種更為合理、實用并且準確的路線規劃方法，并通過計算機程序予以實現。

2 核心算法

2.1 站點與列車線路網絡化

以城市站點為網絡中的節點，列車為兩站間的線段，每條線屬性包含車次名稱、出發及到達時間、運行時間和票價，這樣便形成了基本的網絡。

2.2 不同座位等級區分

硬座票、硬臥票分別對應動車的二等座和一等座，在選擇票價最優時需先選擇座位等級，即硬座（二等座）級或硬臥（一等座）級，其他如軟臥等座位級別本文暫不考慮。根據每條線路的票價屬性，座位等級用于票價最低的線路優化。

2.3 得到票價最低線路或票價最低排名前N的路線

根據每條線路賦給的票價屬性，根據選擇的座位等級，直接使用網絡最短路徑算法（Dijkstra算法[3]）可立即得到票價最低的路線圖。另外，考慮到實際要求，通過對Dijkstra算法改進，用一個數組記錄算法過程中每一個節點所得的“權重和”最低的N個數字。這樣計算得到排名前N的最低票價及對應的列車線路。

Dijkstra 算法的偽代碼如下[4～5，7]：

算法 Dijkstra（G，s）

//單起點最短路徑的Dijkstra算法

//輸入：具有非負權重的加權圖G=以及頂點s

//輸出：對于V中的每個頂點v來說，從s到v的最短路徑長度dv以及路徑上的各頂點

Initialize(Q) //將頂點優先隊列初始化為空

for V中每一個頂點v do

dv←0；pv←null //pv是最短路徑上倒數第2個頂點

Insert(Q,v,dv) //初始化優先隊列中頂點的優先級

ds←0;Decrease(Q,s,ds) //將s的優先級更新為ds

VT←?

for i←0 to |V|-1 do

u*←DeleteMin(Q) //刪除優先級最小的元素

改進的Dijkstra算法可以得到前N名的最短路徑，此時需要建一個副表，將每次提取出來的前N名最短路徑ds用數組保存下來，得到需要的路徑長度后反推該長度對應的路徑。

2.4 得到用時最短線路

用時最短路線與最少費用計算稍有不同，轉車換乘中間環節的用時必須考慮，需要在上述列車線路網絡基礎上，考慮在換乘時間的處理。因此需要單獨對每個車站進行網絡賦權優化處理。

2.4.1 考慮換乘銜接時間的中轉方案

在基本網絡中，兩城市之間使用的車次信息完全與12306官網顯示的信息一致。對于一列列車同時穿過多個城市的，只是將連接的站點兩兩之間建立互通的所有列車信息，每條線賦給車次屬性（票價、出發時間、到達時間、運行時間）。

圖2 某中轉火車站點

與票價最優比選不同的是，時間最短的優化需將網絡中每個節點（即車站）做相應的處理。如圖2中所示，每個站點到達的列車與在其到站后從該站出發的所有列車之間增加一條“中轉時差線”，它的屬性為到達列車轉到另一輛出發列車的時間差。對于某個站點，到達的列車終點記作該站的A特性點，出站的列車起點記作B特性點。所有A特性點再匯總至一個虛擬結點C，代表作為終點時的該站，A、C之間線段賦值為0；所有B特性點匯總至另一虛擬結點D，代表作為起點時的該站，B、D之間線段賦值為0。當選中站點1和站點2為起止點時，實際是站點1的D點到站點2的C點之間的最短路徑問題，此時再用Dijkstra算法或改進的Dijkstra算法獲得最短路徑或排名前N的最短路徑結果。這就充分考慮了中轉帶來的時間延誤。這樣得到的用時最短路徑也是最合理的。

2.4.2 考慮同城多站的情況

以北京為例，北京市區內有北京站、北京南站、北京西站以及北京北站共4個客運車站，車站之間的換乘就必須考慮一個最小換乘時間，處理方法就是連接4站之間的C屬性點到D屬性點，并且按照城市內部交通方式附上一個值（此數據可以很容易地在百度地圖上獲?。瑫r將此4站匯總到一個公共點O點作為北京的代表，連接線權重賦為0，如圖3所示。

圖3 同城多站點連接處理示意圖

通過以上對站點的簡化處理，采用改進的Dijkstra算法[3～6]即可計算出用時最短路徑和排名前N的最短路徑。當路徑選擇確定后，只需按選中的車次信息購票。

2.5 路線可靠性評價

不僅是中轉換乘，列車晚點導致的延誤損失也值得關注。為此，方案中可以開辟空間，根據統計數據對路線進行可靠性評價，計算出線路晚點時間期望值與方差，同時可以通過網絡連接調出該線路最近一周的晚點分布圖。

3 算法實現

本算法主要提供旅程規劃與列車中轉方案推薦，面向的出行工具是列車，采用Java語言編寫。通過采集鐵路系統的相關數據，再根據用戶的出行需求，為用戶提供最合適的旅行路線。

推薦的旅行路線會根據用戶不同需求而不同。比如，用戶可以根據自己的需要，選擇最短時間為目的、或者最少花費為目的，或者在春運等比較繁忙時，一些路線會比較擁擠甚至無票，可以選擇擁擠程度較低而且有票的路線。

算法實現流程如圖4所示。

核心程序通過獲取用戶提出的需求和限制條件，依據鐵路系統數據進行計算，給出智能購票推薦方案。使用方法如下。

由用戶確定自己的需求：出發地、目的地以及限制條件，限制條件是指希望的票價等級、花費的時間、是否需要在出發地與目的地之間途徑某個地方、希望繞開的某條路線等，完成需求輸入后，程序自動把規劃好的旅途路線反饋給用戶，如果用戶不滿意，還可以更改限制條件重新計算。程序在處理后顯示方案時，既用高亮線畫出線路圖，又給出文字注解，包含車次、用時和車票價格等信息。

圖4 推薦算法實現流程

4 計算實例

以2013年9月4日的數據為例。

4.1 有直達車的兩站點通行

延安去太原兩列車時間和價格如表1。

表1 兩列車時間和價格表

這是典型的價格一致時間不同的。在同時能購到兩種票的前提下本算法會自動選擇前者。

4.2 需要中轉換乘的兩站點通行

唐山到膠州，有K704（03:56-14:09，歷時10:13）和 K1394（19:01-06:29，歷時 11:28），硬座票價均為105元，硬臥中鋪為190元，如果在鐵路官網12306上查詢也只能得到這一個結果。但通過本文方案計算，可以發現另一條更加優越的線路——唐山到天津再到膠州，從唐山乘坐T238到天津（05:50-07:04，歷時01:14）轉D331到達膠州（07:46-11:42），總歷時05:52（含中轉延誤時間），票價合計硬座（二等座）213.5元，硬臥中鋪（一等座）324.5元。如果趕時間，無疑后面的方案更有價值。

5 結束語

上述方案利用高效算法，同時考慮換乘時間、晚點、同城多站等因素，能夠為用戶提供切實可行的鐵路出行購票策略。

基于網絡分析的鐵路路徑優化及購票推薦算法，可以為出行者提供更智能更方便的鐵路出行選擇。目前，各種交通工具相對獨立，不能及時有效調配資源，造成資源的浪費，建立綜合交通運輸體系的協調機制很有必要?；诒疚乃岢龅姆椒ǎ梢詫㈣F路、公路乃至航空進行整合，形成覆蓋全方式的出行路徑選擇及優化系統。本文提供的方案有助于綜合智能交通協同機制的建立，并輔助用戶快捷地挑選最優出行方案。

[1] 2013年春運落幕，全國出行人次突破34億[EB/OL].http://news.xinhuanet.com/local/2013-03/06/c_114917679.htm，2013-03-06.

[2]上海到德陽8張票換乘7次‘換乘哥’[EB/OL].http://china.cnr.cn/yaowen/201302/t20130206_511931498.shtml，2013-02-06.

[3] 胡運全. 運籌學教程[M]. 4版. 北京：清華大學出版社，2012，11：242-245.

[4] 柴登峰，張登榮. 前N條最短路徑問題的算法及應用[J].浙江大學學報：工學版，2002，36（5）.

[5] 王 峰，游志勝，曼麗春，等. Dijkstra及基于 Dijkstra的前 N條最短路徑算法在智能交通系統中的應用[J]. 計算機應用研究，2006（9）.

[6] Steven M.LaValle. 規劃算法[M]. 張慶雅，孫 東，譯.北京：清華大學出版社，2011，1：37-38.

[7] Anany Levitin. 算法設計與分析基礎[M]. 潘 彥，譯. 北京：清華大學出版社，2007，1：246-249.