基于網(wǎng)絡(luò)最短路徑的鐵路購票智能推薦算法研究

劉勝來，李瑞敏

（清華大學(xué) 土木工程系，北京 100084）

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

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

通過換乘實(shí)現(xiàn)出行并可能減少出行時(shí)間的實(shí)施需要有合理計(jì)算方法的支持。本文基于鐵路網(wǎng)絡(luò)的路徑優(yōu)化問題，根據(jù)已有鐵路列車時(shí)刻表，給出了一種行之有效的最優(yōu)路徑求解的解決方案。

本方案基于現(xiàn)行鐵道部門實(shí)際擁有的線路信息，通過計(jì)算優(yōu)化，提供給用戶智能化的線路推薦服務(wù)。可以自動(dòng)生成兩地間到達(dá)速度最快和花費(fèi)費(fèi)用最少的兩種方案，幫助用戶達(dá)到省錢和省時(shí)的目的。

1 研究現(xiàn)狀

為用戶提供換乘策略并給出旅行路線指導(dǎo)方案，這個(gè)功能已經(jīng)有不少網(wǎng)站正在嘗試，但卻能發(fā)現(xiàn)不少可改進(jìn)的地方。

1.1 12306網(wǎng)站

鐵道部門購票唯一官方網(wǎng)站12306提供了一項(xiàng)鐵路旅程規(guī)劃功能，如圖1所示，但卻沒有達(dá)到相應(yīng)的旅程規(guī)劃的實(shí)用性。

圖1 12306網(wǎng)站鐵路旅程規(guī)劃功能界面截圖（2013.7.10）

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

1.2 火車網(wǎng)（www.huoche.com.cn）

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

在提供的多種方案中，給出了一個(gè)總用時(shí)的指標(biāo)，但根據(jù)12306網(wǎng)站提供的列車信息核查，這個(gè)總時(shí)間實(shí)際指的是兩列列車運(yùn)行時(shí)間的和，換乘中間的時(shí)間差并沒有考慮。因此該網(wǎng)站給出的推薦出行方案參考價(jià)值不大。另外，該網(wǎng)站與12306網(wǎng)站還存在數(shù)據(jù)誤差，其實(shí)用性有限。

針對上述不足，本文結(jié)合網(wǎng)絡(luò)最短路徑算法，研究開發(fā)了一種更為合理、實(shí)用并且準(zhǔn)確的路線規(guī)劃方法，并通過計(jì)算機(jī)程序予以實(shí)現(xiàn)。

2 核心算法

2.1 站點(diǎn)與列車線路網(wǎng)絡(luò)化

以城市站點(diǎn)為網(wǎng)絡(luò)中的節(jié)點(diǎn)，列車為兩站間的線段，每條線屬性包含車次名稱、出發(fā)及到達(dá)時(shí)間、運(yùn)行時(shí)間和票價(jià)，這樣便形成了基本的網(wǎng)絡(luò)。

2.2 不同座位等級區(qū)分

硬座票、硬臥票分別對應(yīng)動(dòng)車的二等座和一等座，在選擇票價(jià)最優(yōu)時(shí)需先選擇座位等級，即硬座（二等座）級或硬臥（一等座）級，其他如軟臥等座位級別本文暫不考慮。根據(jù)每條線路的票價(jià)屬性，座位等級用于票價(jià)最低的線路優(yōu)化。

2.3 得到票價(jià)最低線路或票價(jià)最低排名前N的路線

根據(jù)每條線路賦給的票價(jià)屬性，根據(jù)選擇的座位等級，直接使用網(wǎng)絡(luò)最短路徑算法（Dijkstra算法[3]）可立即得到票價(jià)最低的路線圖。另外，考慮到實(shí)際要求，通過對Dijkstra算法改進(jìn)，用一個(gè)數(shù)組記錄算法過程中每一個(gè)節(jié)點(diǎn)所得的“權(quán)重和”最低的N個(gè)數(shù)字。這樣計(jì)算得到排名前N的最低票價(jià)及對應(yīng)的列車線路。

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

算法 Dijkstra（G，s）

//單起點(diǎn)最短路徑的Dijkstra算法

//輸入：具有非負(fù)權(quán)重的加權(quán)圖G=以及頂點(diǎn)s

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

Initialize(Q) //將頂點(diǎn)優(yōu)先隊(duì)列初始化為空

for V中每一個(gè)頂點(diǎn)v do

dv←0；pv←null //pv是最短路徑上倒數(shù)第2個(gè)頂點(diǎn)

Insert(Q,v,dv) //初始化優(yōu)先隊(duì)列中頂點(diǎn)的優(yōu)先級

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

VT←?

for i←0 to |V|-1 do

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

改進(jìn)的Dijkstra算法可以得到前N名的最短路徑，此時(shí)需要建一個(gè)副表，將每次提取出來的前N名最短路徑ds用數(shù)組保存下來，得到需要的路徑長度后反推該長度對應(yīng)的路徑。

2.4 得到用時(shí)最短線路

用時(shí)最短路線與最少費(fèi)用計(jì)算稍有不同，轉(zhuǎn)車換乘中間環(huán)節(jié)的用時(shí)必須考慮，需要在上述列車線路網(wǎng)絡(luò)基礎(chǔ)上，考慮在換乘時(shí)間的處理。因此需要單獨(dú)對每個(gè)車站進(jìn)行網(wǎng)絡(luò)賦權(quán)優(yōu)化處理。

2.4.1 考慮換乘銜接時(shí)間的中轉(zhuǎn)方案

在基本網(wǎng)絡(luò)中，兩城市之間使用的車次信息完全與12306官網(wǎng)顯示的信息一致。對于一列列車同時(shí)穿過多個(gè)城市的，只是將連接的站點(diǎn)兩兩之間建立互通的所有列車信息，每條線賦給車次屬性（票價(jià)、出發(fā)時(shí)間、到達(dá)時(shí)間、運(yùn)行時(shí)間）。

圖2 某中轉(zhuǎn)火車站點(diǎn)

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

2.4.2 考慮同城多站的情況

以北京為例，北京市區(qū)內(nèi)有北京站、北京南站、北京西站以及北京北站共4個(gè)客運(yùn)車站，車站之間的換乘就必須考慮一個(gè)最小換乘時(shí)間，處理方法就是連接4站之間的C屬性點(diǎn)到D屬性點(diǎn)，并且按照城市內(nèi)部交通方式附上一個(gè)值（此數(shù)據(jù)可以很容易地在百度地圖上獲取），同時(shí)將此4站匯總到一個(gè)公共點(diǎn)O點(diǎn)作為北京的代表，連接線權(quán)重賦為0，如圖3所示。

圖3 同城多站點(diǎn)連接處理示意圖

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

2.5 路線可靠性評價(jià)

不僅是中轉(zhuǎn)換乘，列車晚點(diǎn)導(dǎo)致的延誤損失也值得關(guān)注。為此，方案中可以開辟空間，根據(jù)統(tǒng)計(jì)數(shù)據(jù)對路線進(jìn)行可靠性評價(jià)，計(jì)算出線路晚點(diǎn)時(shí)間期望值與方差，同時(shí)可以通過網(wǎng)絡(luò)連接調(diào)出該線路最近一周的晚點(diǎn)分布圖。

3 算法實(shí)現(xiàn)

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

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

算法實(shí)現(xiàn)流程如圖4所示。

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

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

圖4 推薦算法實(shí)現(xiàn)流程

4 計(jì)算實(shí)例

以2013年9月4日的數(shù)據(jù)為例。

4.1 有直達(dá)車的兩站點(diǎn)通行

延安去太原兩列車時(shí)間和價(jià)格如表1。

表1 兩列車時(shí)間和價(jià)格表

這是典型的價(jià)格一致時(shí)間不同的。在同時(shí)能購到兩種票的前提下本算法會自動(dòng)選擇前者。

4.2 需要中轉(zhuǎn)換乘的兩站點(diǎn)通行

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

5 結(jié)束語

上述方案利用高效算法，同時(shí)考慮換乘時(shí)間、晚點(diǎn)、同城多站等因素，能夠?yàn)橛脩籼峁┣袑?shí)可行的鐵路出行購票策略。

基于網(wǎng)絡(luò)分析的鐵路路徑優(yōu)化及購票推薦算法，可以為出行者提供更智能更方便的鐵路出行選擇。目前，各種交通工具相對獨(dú)立，不能及時(shí)有效調(diào)配資源，造成資源的浪費(fèi)，建立綜合交通運(yùn)輸體系的協(xié)調(diào)機(jī)制很有必要。基于本文所提出的方法，可以將鐵路、公路乃至航空進(jìn)行整合，形成覆蓋全方式的出行路徑選擇及優(yōu)化系統(tǒng)。本文提供的方案有助于綜合智能交通協(xié)同機(jī)制的建立，并輔助用戶快捷地挑選最優(yōu)出行方案。

[1] 2013年春運(yùn)落幕，全國出行人次突破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] 胡運(yùn)全. 運(yùn)籌學(xué)教程[M]. 4版. 北京：清華大學(xué)出版社，2012，11：242-245.

[4] 柴登峰，張登榮. 前N條最短路徑問題的算法及應(yīng)用[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2002，36（5）.

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

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

[7] Anany Levitin. 算法設(shè)計(jì)與分析基礎(chǔ)[M]. 潘 彥，譯. 北京：清華大學(xué)出版社，2007，1：246-249.