霍雷剛 鐘雅婷 李永玉
摘 要:為改善鐵路乘客購(gòu)票及出行體驗(yàn),針對(duì)售票系統(tǒng)換乘站推薦功能不全的缺陷,設(shè)計(jì)和實(shí)現(xiàn)基于Matlab的鐵路中轉(zhuǎn)換乘站推薦系統(tǒng),實(shí)現(xiàn)數(shù)據(jù)采集、整理、換乘站點(diǎn)推薦等功能。采用Matlab語(yǔ)言編程,利用爬蟲(chóng)技術(shù)獲取各鐵路站點(diǎn)信息和車(chē)次信息,將獲取的信息進(jìn)行整理和網(wǎng)絡(luò)化建模,確定模型各條邊的權(quán)值,最后采用最短路徑算法得到換乘站。實(shí)驗(yàn)結(jié)果表明,結(jié)合列車(chē)信息和最短路徑算法可為乘客推薦有效的換乘站。
關(guān)鍵詞:鐵路中轉(zhuǎn)換乘;最短路徑算法;Matlab
DOI:10. 11907/rjdk. 181939
中圖分類(lèi)號(hào):TP319 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1672-7800(2019)005-0142-04
Abstract:To improve rail passengers' ticket purchase and travel experience, a recommendation system for railway interchange stations based on MATLAB is designed and implemented in allusion to the deficiency of the existing ticket selling system, so that the functions of data collection, sorting and transfer station recommendation can be realised. This system mainly uses the MATLAB programming language and the crawler technology to obtain the information of each railway station and train number, collates the information obtained and establishes the network model, determines the weight of each edge of the model, and finally uses the shortest path algorithm to get the transfer station. The experimental results on the railway data in Guangxi area show that the combination of train information and shortest path algorithm can recommend effective transfer stations for passengers.
Key Words:railway transfer; shortest path algorithm; Matlab
0 引言
中國(guó)鐵路線(xiàn)路密集,鐵路交通四通八達(dá)。鐵路出行因其覆蓋面廣、車(chē)次多、價(jià)格實(shí)惠、訂票方便、安全性高等特點(diǎn),成為人們選擇最多的中遠(yuǎn)途出行方式,也是交通行業(yè)發(fā)展的重點(diǎn)。中國(guó)鐵路客戶(hù)服務(wù)中心12306網(wǎng)站、支付寶、去哪兒網(wǎng)、攜程網(wǎng)等為旅客提供訂票、查詢(xún)、車(chē)站引導(dǎo)等服務(wù),大大提高了鐵路旅客的出行體驗(yàn)。雖然鐵路線(xiàn)路的開(kāi)通和開(kāi)行方案充分考慮了經(jīng)濟(jì)、地域和客流時(shí)變性等因素,但仍存在部分旅客出行不能通過(guò)直達(dá)方式滿(mǎn)足的情況,為此眾多學(xué)者進(jìn)行了研究。鐵路換乘研究集中在以下3個(gè)方面:
(1)站內(nèi)換乘空間和流線(xiàn)優(yōu)化。通過(guò)旅客出入站路線(xiàn)和建筑結(jié)構(gòu)設(shè)計(jì),提高換乘空間利用率,減少中轉(zhuǎn)旅客重復(fù)進(jìn)出站次數(shù),提高鐵路樞紐換乘和轉(zhuǎn)乘其它交通系統(tǒng)的便利性。周覃龍等[1]提出應(yīng)高度重視換乘問(wèn)題,建立站內(nèi)換乘的合理流線(xiàn),以最短行程、最少時(shí)間完成換乘,從優(yōu)化客運(yùn)站總平面布置圖、完善客運(yùn)建筑規(guī)劃設(shè)計(jì)、既有客運(yùn)站優(yōu)化補(bǔ)強(qiáng)以及運(yùn)營(yíng)管理等方面初步提出應(yīng)對(duì)措施。劉振華等[2]提出同站臺(tái)換乘、站廳換乘以及通道換乘等方式,科學(xué)分析了鐵路運(yùn)輸與城市軌道交通的換乘方式。何相聚等[3]以廈門(mén)北站為例,對(duì)鐵路客運(yùn)站換乘空間綜合設(shè)計(jì)提出建議。馬述等[4] 針對(duì)市域鐵路與城市軌道交通換乘問(wèn)題,提出通道換乘方案。李亞茹等[5] 探討了武漢市城際鐵路站前換乘空間設(shè)計(jì)方案。施諾等[6]設(shè)計(jì)和實(shí)現(xiàn)了鐵路樞紐旅客精細(xì)化換乘服務(wù)系統(tǒng),增加了鐵路車(chē)站內(nèi)部設(shè)施設(shè)備查詢(xún)及走行路徑搜索功能。程璐等[7]以鐵路與常規(guī)公交的換乘銜接為主要對(duì)象,研究二者之間運(yùn)營(yíng)時(shí)間銜接與站點(diǎn)布局銜接的優(yōu)化。
(2)鐵路運(yùn)行圖優(yōu)化。通過(guò)客流量等數(shù)據(jù)分析,優(yōu)化鐵路運(yùn)行路線(xiàn)和客運(yùn)站點(diǎn)選址和布局以及列車(chē)運(yùn)行時(shí)間等,提高旅客出行體驗(yàn)。張旭等[8]利用隨機(jī)期望值模型和遺傳算法,提出高鐵冗余時(shí)間整體布局優(yōu)化方案。張睿[9] 提出大站旅客換乘接續(xù)的高鐵運(yùn)行調(diào)整方法。李元?jiǎng)P等[10]提出高鐵列車(chē)接續(xù)安排等可行性建議。李智等[11]基于周期事件規(guī)劃理論,提出基于換乘最優(yōu)的城際鐵路周期運(yùn)行圖編制模型。劉廣武等[12] 通過(guò)分析跨線(xiàn)客流組織模式提出部分換乘模式。
(3)鐵路樞紐內(nèi)換乘站點(diǎn)推薦。主要針對(duì)旅客出發(fā)地與目的地之間無(wú)直達(dá)列車(chē)或直達(dá)列車(chē)車(chē)票售罄情況,為旅客提供中轉(zhuǎn)換乘建議。蘇煥銀等[13]提出基于鐵路有效路徑的換乘方案快速搜索方法。尹伊伊等[14] 選取具有始發(fā)車(chē)次、具備客運(yùn)組織換乘能力的大站作為換乘車(chē)站,對(duì)比分析了常用的Dijkstra算法及啟發(fā)式A*算法,擇優(yōu)選取啟發(fā)式A*算法改進(jìn)換乘策略。李秦陽(yáng)等[15] 利用網(wǎng)絡(luò)等價(jià)變換方法,建立了最短時(shí)間網(wǎng)絡(luò)優(yōu)化模型。張琦等[16] 引入旅行時(shí)間和服務(wù)頻率兩種權(quán)重計(jì)算介數(shù),實(shí)現(xiàn)對(duì)鐵路車(chē)站樞紐影響力的量化評(píng)估。利用SpaceP方式構(gòu)建局部網(wǎng)絡(luò),針對(duì)列車(chē)接續(xù)關(guān)系及其特征提出修正表達(dá)及網(wǎng)絡(luò)構(gòu)建方法。李麗輝等[17] 提出一種比較OD最短路徑距離的統(tǒng)計(jì)算法用于換乘需求統(tǒng)計(jì),保留了詳細(xì)的車(chē)次換乘信息。
12306網(wǎng)站近期開(kāi)通了接續(xù)換乘功能,例如,2018年5月29日通過(guò)12306網(wǎng)站可查詢(xún)到北京到南京有60趟直達(dá)車(chē),乘客可通過(guò)頁(yè)面上的“車(chē)票預(yù)訂”購(gòu)買(mǎi)車(chē)票,該網(wǎng)站會(huì)自動(dòng)顯示換乘站的若干方案。但研究發(fā)現(xiàn),該功能僅適用于客流量較大的中等以上城市,僅提供換乘一次的部分列車(chē)余票信息。雖然該網(wǎng)站可手動(dòng)輸入中轉(zhuǎn)站,但并不能提供一個(gè)中轉(zhuǎn)站選擇方案。大多數(shù)市縣級(jí)火車(chē)站之間的中轉(zhuǎn)換乘仍需人工經(jīng)驗(yàn)或查看地圖。如通過(guò)12306查詢(xún)不到賀州到百色列車(chē)信息,使用“接續(xù)換乘”也未查詢(xún)到接續(xù)換乘方案。但賀州到百色至少存在一條經(jīng)由廣西南寧的中轉(zhuǎn)路線(xiàn),對(duì)于不熟悉的旅客很難知道這一方案。因此,改善鐵路換乘系統(tǒng)成為我們的研究重點(diǎn)。
最短路徑問(wèn)題是圖論研究中一個(gè)經(jīng)典的算法問(wèn)題,旨在尋找圖(由節(jié)點(diǎn)和路徑組成的)中兩節(jié)點(diǎn)之間的最短路徑。鐵路中轉(zhuǎn)換乘站點(diǎn)推薦可看作是確定起點(diǎn)和終點(diǎn)的最短路徑問(wèn)題。
Matlab是美國(guó)MathWorks公司出品的商業(yè)數(shù)學(xué)軟件,用于算法開(kāi)發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計(jì)算的高級(jí)計(jì)算語(yǔ)言,并提供界面編程工具,該軟件以工具箱的形式提供常用算法函數(shù)。
本文提出一種鐵路換乘中轉(zhuǎn)站推薦算法。利用爬蟲(chóng)技術(shù)、最短路徑算法,設(shè)計(jì)和實(shí)現(xiàn)了基于Matlab的鐵路換乘中轉(zhuǎn)站推薦系統(tǒng),針對(duì)小型城市也能給出很好的換乘方案。
1 系統(tǒng)設(shè)計(jì)
1.1 系統(tǒng)總體設(shè)計(jì)
本文首先利用爬蟲(chóng)技術(shù)獲取各鐵路站點(diǎn)信息和車(chē)次信息,然后將獲取的信息進(jìn)行整理和網(wǎng)絡(luò)化建模,最后采用最短路徑算法推薦換乘站。最短路徑算法有很多種,最常用的是Dijkstra算法,考慮到網(wǎng)絡(luò)特征,需要對(duì)算法進(jìn)行優(yōu)化[18-19]。系統(tǒng)采用Matlab語(yǔ)言編程實(shí)現(xiàn),通過(guò)GUI界面與用戶(hù)交互,并可跳轉(zhuǎn)到12306網(wǎng)站。中轉(zhuǎn)換乘方案總體設(shè)計(jì)如圖1所示。
1.2 詳細(xì)功能設(shè)計(jì)
(1)系統(tǒng)主要功能。本系統(tǒng)核心部分包括數(shù)據(jù)獲取、數(shù)據(jù)整理、站點(diǎn)推薦和可視化。數(shù)據(jù)獲取采用Matlab網(wǎng)絡(luò)爬蟲(chóng)技術(shù)和地理信息API,獲取各站點(diǎn)名稱(chēng)、位置以及列車(chē)時(shí)刻表。數(shù)據(jù)整理包括兩部分:①將站點(diǎn)篩選和地理位置經(jīng)緯度轉(zhuǎn)換為平面坐標(biāo);②根據(jù)列車(chē)運(yùn)行信息構(gòu)建圖模型。站點(diǎn)推薦即將Matlab最短路徑算法應(yīng)用于構(gòu)建的圖模型??梢暬奖阌脩?hù)和系統(tǒng)交互以及展示站點(diǎn)位置和列車(chē)運(yùn)行路線(xiàn)。
(2)系統(tǒng)模塊設(shè)計(jì)。系統(tǒng)設(shè)計(jì)為數(shù)據(jù)獲取與整理模塊、站點(diǎn)推薦模塊和可視化模塊。將這幾個(gè)模塊整合后的用戶(hù)界面設(shè)計(jì)如圖2所示。
(3)數(shù)據(jù)庫(kù)設(shè)計(jì)。系統(tǒng)采用應(yīng)用較為廣泛的Excel表格存放站點(diǎn)和車(chē)次等信息,方便用戶(hù)自行設(shè)計(jì)數(shù)據(jù)和對(duì)獲取數(shù)據(jù)進(jìn)行操作。Matlab提供的系統(tǒng)函數(shù)xlsread和xlswrite分別用于讀、寫(xiě)這種文件格式。
2 系統(tǒng)功能實(shí)現(xiàn)
2.1 數(shù)據(jù)獲取
(1)列車(chē)運(yùn)行信息獲取。以IP138網(wǎng)站為例,采用Matlab網(wǎng)絡(luò)爬蟲(chóng)技術(shù)獲取各車(chē)站的站點(diǎn)名稱(chēng)及列車(chē)時(shí)刻表等。函數(shù)webread用于獲取網(wǎng)頁(yè)源碼,以regexp和正則表達(dá)式[20]提取內(nèi)容,用xlswrite將獲取的內(nèi)容存入Excel文件。
獲取廣西區(qū)內(nèi)站點(diǎn)名稱(chēng)代碼如下:
url_GX_station='http://qq.ip138.com/train/guangxi/';
sourcefile=webread(url_GX_station);
expr1='
[stationfile, station_tokens]= regexp(sourcefile, expr1, 'match', 'tokens');
獲取經(jīng)過(guò)某個(gè)站點(diǎn)(station_tokens{idx}{1})的所有車(chē)次信息:
tmp_url=[url_GX_station,station_tokens{idx}{1},'.htm'];
sourcefile=webread(tmp_url);
expr2 = '
[nofile, no_tokens] = regexp(sourcefile, expr2, 'match', 'tokens');
獲取經(jīng)過(guò)某個(gè)站點(diǎn)的某個(gè)車(chē)次運(yùn)行信息({‘車(chē)次‘當(dāng)前車(chē)次車(chē)站編號(hào) ‘車(chē)站 ‘到達(dá)時(shí)間‘發(fā)車(chē)時(shí)間‘走行時(shí)間(小時(shí))‘里程(公里)}):
sourcefile=webread(['http://qq.ip138.com/train/',no_tokens{i}{1},'.htm']);
expr3=['
[detailfile, detail_tokens] = regexp(sourcefile, expr3, 'match', 'tokens');
for it=1:length(detail_tokens)
i_final=i_final+1; final_detail(i_final,1:7)=cellstr({no_tokens{i}{2},detail_tokens{it}{:}});
end
獲取的數(shù)據(jù)存儲(chǔ)到Excel后效果如圖 3所示。
(2)站點(diǎn)位置信息獲取。該步驟主要獲取站點(diǎn)的經(jīng)緯度信息以方便展示。該數(shù)據(jù)可通過(guò)百度地圖API查詢(xún),為了方便本文直接采用其它網(wǎng)站提供的批量查詢(xún)功能,對(duì)部分查詢(xún)不到的站點(diǎn)再進(jìn)行精細(xì)查詢(xún),根據(jù)之后的可視化模塊顯示結(jié)果人工校正。
2.2 數(shù)據(jù)整理
(1)將經(jīng)緯度轉(zhuǎn)化為平面坐標(biāo)的核心代碼如下:
% 定義投影結(jié)構(gòu),這里對(duì)mercator投影結(jié)構(gòu)進(jìn)行定義,然后對(duì)mstruct進(jìn)行補(bǔ)全
mstruct=defaultm('mercator');
%定義橢球體長(zhǎng)軸,橢率,坐標(biāo)原點(diǎn)
mstruct.geoid=[ 6378137,0.0818191908426215];
mstruct.origin=[0,0,0];
mstruct=defaultm(mstruct);
% 進(jìn)行投影和數(shù)據(jù)轉(zhuǎn)換:地理坐標(biāo)投影到直角坐標(biāo):
[XData,YData] =projfwd(mstruct,data(2,:),data(1,:));
(2)將列車(chē)運(yùn)行信息轉(zhuǎn)化為圖模型。去除廣西區(qū)外的站點(diǎn),簡(jiǎn)化每個(gè)車(chē)次對(duì)應(yīng)的數(shù)據(jù),例如對(duì)圖3中的2011次列車(chē)簡(jiǎn)化后的數(shù)據(jù)如圖4所示。
其中,第1列為車(chē)次,第二列表示該車(chē)次經(jīng)過(guò)廣西區(qū)內(nèi)的站點(diǎn)數(shù)量,其它列為經(jīng)過(guò)的每個(gè)站點(diǎn)名稱(chēng)。為使用Matlab提供的構(gòu)造有向圖函數(shù)digraph,需要提供起點(diǎn)、終點(diǎn)、權(quán)重和節(jié)點(diǎn)名稱(chēng)信息。對(duì)于2011次列車(chē),起點(diǎn)向量為S=[‘三江縣,‘融安,‘融水,‘柳江,‘來(lái)賓,‘黎塘],終點(diǎn)向量為T(mén)=[‘融安,‘融水,‘柳江,‘來(lái)賓,‘黎塘,南寧],向量的構(gòu)建可采用循環(huán)拼接方式實(shí)現(xiàn)。權(quán)重w可以是對(duì)應(yīng)起點(diǎn)和終點(diǎn)的運(yùn)行時(shí)間、里程、經(jīng)歷的站點(diǎn)個(gè)數(shù)等,同樣采用循環(huán)拼接的方式得出。names指無(wú)重復(fù)的所有廣西區(qū)站點(diǎn)名稱(chēng)。
構(gòu)建圖模型核心代碼即Matlab函數(shù)調(diào)用:G=digraph(S,T,W,names)。
2.3 站點(diǎn)推薦
由構(gòu)建的圖模型調(diào)用Matlab函數(shù)的shortestpath求出最短距離,即得到中轉(zhuǎn)換乘站點(diǎn),核心代碼為:[PATH,D,EDGEPATH]=shortestpath(G,'賀州','桂林')。PATH中包含起點(diǎn)、中轉(zhuǎn)站和終點(diǎn)站名稱(chēng),EDGEPATH包含車(chē)次信息。
2.4 可視化
可視化包括站點(diǎn)位置、最短路徑和用戶(hù)界面。
結(jié)合站點(diǎn)的平面坐標(biāo),利用Matlab提供的plot、line、text、figure函數(shù)得到站點(diǎn)的位置和簡(jiǎn)化的列車(chē)線(xiàn)路,如圖 5所示。
為方便用戶(hù)驗(yàn)證推薦方案,采用Matlab提供的函數(shù)highlight高亮顯示推薦的路徑,顯示效果如圖6所示。
3 結(jié)果分析
為了驗(yàn)證實(shí)驗(yàn)系統(tǒng)的有效性,通過(guò)隨機(jī)挑選廣西區(qū)內(nèi)站點(diǎn)作為出發(fā)站和到達(dá)站,將本文設(shè)計(jì)的系統(tǒng)與12306網(wǎng)站的接續(xù)換乘和中轉(zhuǎn)查詢(xún)進(jìn)行對(duì)比,如表1所示。在任意兩站點(diǎn)之間,本系統(tǒng)均可判斷是否有直達(dá)車(chē)次。如果不存在直達(dá)車(chē)次則推薦滿(mǎn)足最短路徑的換乘站。
由實(shí)驗(yàn)結(jié)果可知,通過(guò)構(gòu)建圖模型,利用Matlab最短路徑算法建立鐵路客運(yùn)換乘網(wǎng)絡(luò)以實(shí)現(xiàn)推薦中轉(zhuǎn)站功能是可行的。
4 結(jié)語(yǔ)
本文利用網(wǎng)絡(luò)爬蟲(chóng)技術(shù)和最短路徑算法,設(shè)計(jì)并實(shí)現(xiàn)了基于Matlab的鐵路換乘站點(diǎn)推薦系統(tǒng)。系統(tǒng)實(shí)現(xiàn)了數(shù)據(jù)采集、數(shù)據(jù)整理、換乘站點(diǎn)推薦、數(shù)據(jù)可視化等功能。實(shí)驗(yàn)表明,系統(tǒng)功能模塊運(yùn)行正常,基本滿(mǎn)足旅客需求,可為旅客提供購(gòu)票參考,具有一定的實(shí)用價(jià)值。后續(xù)將進(jìn)行擴(kuò)大站點(diǎn)涵蓋范圍、實(shí)時(shí)獲取車(chē)票信息以及降低模型復(fù)雜度研究。
參考文獻(xiàn):
[1] 周覃龍. 解決鐵路中轉(zhuǎn)旅客站內(nèi)換乘問(wèn)題的探討[J]. 高速鐵路技術(shù),2016 (3):16-18.
[2] 劉振華. 鐵路運(yùn)輸與城市軌道交通的換乘研究[J]. 智能城市, 2017(2):164-169.
[3] 何相聚. 鐵路客運(yùn)站換乘空間淺析——以廈門(mén)北站為例[J]. 中外建筑,2017(8):172-174.
[4] 馬述. 市域鐵路與城市軌道交通換乘方案探討[C]. 中國(guó)鐵道學(xué)會(huì)工程分會(huì),中國(guó)鐵道學(xué)會(huì)工程分會(huì)第7屆線(xiàn)路專(zhuān)委會(huì)第二次會(huì)議論文集, 2017.
[5] 李亞茹. 武漢市城際鐵路站前換乘空間設(shè)計(jì)研究[D]. 武漢:湖北工業(yè)大學(xué),2017.
[6] 施諾. 鐵路樞紐旅客精細(xì)化換乘服務(wù)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D]. 北京:北京交通大學(xué),2017.
[7] 程璐. 鐵路客運(yùn)樞紐與常規(guī)公交換乘銜接問(wèn)題研究[D]. 蘭州:蘭州交通大學(xué),2017.
[8] 張旭. 高速鐵路換乘銜接下運(yùn)行圖冗余時(shí)間優(yōu)化[J]. 物流科技,2017(2):107-110.
[9] 張睿. 考慮大站旅客換乘接續(xù)的高速鐵路列車(chē)運(yùn)行調(diào)整方案研究[D]. 北京交通大學(xué),2016.
[10] 李元?jiǎng)P,李海鷹,王瑩,等. 換乘模式下的京滬高速鐵路運(yùn)輸組織研究[J]. 鐵道運(yùn)輸與經(jīng)濟(jì),2017(1):46-50.
[11] 李智,張琦,袁志明. 基于換乘最優(yōu)的城市圈城際鐵路運(yùn)行圖研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息,2015(3):114-119,139.
[12] 劉廣武,連義平,張凱. 旅游軌道交通運(yùn)輸組織模式研究[J]. 鐵道運(yùn)輸與經(jīng)濟(jì), 2018(1):106-110.
[13] 蘇煥銀,史峰,張佩,等. 基于鐵路有效路徑的換乘方案快速搜索方法[J]. 鐵道科學(xué)與工程學(xué)報(bào),2016(12):2496-2502.
[14] 尹伊伊,王富章,單杏花,等. 啟發(fā)式算法在鐵路換乘的應(yīng)用[J]. 鐵路計(jì)算機(jī)應(yīng)用,2016(1):20-23,40.
[15] 李秦陽(yáng),李宗平. 一類(lèi)鐵路旅客換乘問(wèn)題的網(wǎng)絡(luò)優(yōu)化模型[J]. 蘭州交通大學(xué)學(xué)報(bào),2012(3):61-64.
[16] 張琦,馬艷. 基于復(fù)雜網(wǎng)絡(luò)的高速鐵路列車(chē)服務(wù)網(wǎng)絡(luò)特征[J]. 鐵道科學(xué)與工程學(xué)報(bào),2018(3):29-33.
[17] 李麗輝,朱建平,史峰,等. 高速鐵路換乘需求統(tǒng)計(jì)算法研究[J]. 鐵道科學(xué)與工程學(xué)報(bào),2018(5):251-255
[18] 張渭軍,王華. 城市道路最短路徑的Dijkstra算法優(yōu)化[J]. 長(zhǎng)安大學(xué)學(xué)報(bào):自然科學(xué)版,2005(6):89-92.
[19] 王樹(shù)西,吳政學(xué). 改進(jìn)的Dijkstra最短路徑算法極其應(yīng)用研究[J]. 計(jì)算機(jī)科學(xué),2012(5):1201-1208.
[20] 胡軍偉,秦弈青,張偉. 正則表達(dá)式在Web信息抽取中的作用[J]. 北京信息科技大學(xué)學(xué)報(bào):自然科學(xué)版,2011(6):321-329.
(責(zé)任編輯:杜能鋼)