基于深度優(yōu)先搜索的鐵路中轉(zhuǎn)路線規(guī)劃研究

摘要：目前，許多長距離鐵路出行沒有直達(dá)列車，或直達(dá)列車?yán)@路，導(dǎo)致額外的時間和金錢花費。本文針對這一現(xiàn)象，將復(fù)雜的鐵路路線數(shù)據(jù)抽象成計算機方便處理的圖，使用帶有剪枝優(yōu)化的深度優(yōu)先搜索算法，對可能的乘車中轉(zhuǎn)方案進行遍歷，根據(jù)不同目標(biāo)（如花費最少、耗時最短、到達(dá)時間最早等）挑選出不同中轉(zhuǎn)方案，供用戶出行參考。根據(jù)軟件設(shè)計的原則和方法，給出了使用實現(xiàn)該算法的系統(tǒng)的設(shè)計。

關(guān)鍵詞：鐵路中轉(zhuǎn)方案；深度優(yōu)先算法；剪枝優(yōu)化；軟件系統(tǒng)設(shè)計

一、引言

隨著我國鐵路行業(yè)的飛速發(fā)展，鐵路出行已經(jīng)成為很多人出行的首選。隨著高鐵、動車的車次越來越多，鐵路網(wǎng)變得愈加復(fù)雜。如何在錯綜復(fù)雜的鐵路線路中規(guī)劃出一條花費最少，或者到達(dá)時間最早，又或者是換乘次數(shù)最少的乘車方案愈發(fā)顯得重要。12306 官方網(wǎng)站提供的各種換乘方案無法讓用戶自己設(shè)定最早出發(fā)時間，最晚到達(dá)時間，以及最小換乘時間的限制，而且最多只能換乘一次，靈活性受限。提供的換乘方案又多又雜，用戶體驗不好。

本文以開發(fā)一個能夠幫助用戶更加靈活地規(guī)劃乘車方案的系統(tǒng)為目標(biāo)，彌補 12306 官網(wǎng)提供的服務(wù)的缺點，支持用戶自己定制各種條件，包括最早出發(fā)時間、最晚到達(dá)時間、最小換乘時間、最大換乘次數(shù)。為用戶規(guī)劃出行路線提供一定參考。

二、算法設(shè)計

算法主要分為兩部分，一部分是根據(jù)鐵路數(shù)據(jù)構(gòu)建出圖，另一部分是在圖上進行搜索。

（一）構(gòu)建圖

將每個站點抽象成點，兩個站點之間的鐵路線路抽象成邊。設(shè)計站點的數(shù)據(jù)結(jié)構(gòu)如下，后期可以方便地進行屬性的添加。設(shè)計路線的數(shù)據(jù)結(jié)構(gòu)如下，維護了始發(fā)站、終點站、始發(fā)時間、到達(dá)時間、座位類型（二等座/硬座）、價格、編號等信息。

采用鄰接表數(shù)據(jù)結(jié)構(gòu)存儲圖，即對于每個站點Station，存儲離開它的所有線路，圖的數(shù)據(jù)結(jié)構(gòu)如圖1：

為了方便剪枝和輸出最終方案，創(chuàng)建方案的數(shù)據(jù)結(jié)構(gòu)如下，即維護花費、到達(dá)時間、總用時、與期望時間差異程度等各項評價參數(shù)：

方法：betterInAllAspects和atLeastBetterInOneAspect，分別用于對其他方案進行剪枝和決定是否對當(dāng)前方案剪枝。

（二）圖的搜索

常用的搜索算法主要有兩類，深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先可以保證第一次搜索到站時可以保證在某方面最優(yōu)，但空間復(fù)雜度較大。由于本系統(tǒng)是需要提供多個不同指標(biāo)最優(yōu)化的方案，因此廣度優(yōu)先的這個性質(zhì)并不能很好地被利用。同時考慮到圖的點數(shù)和邊數(shù)較多，因此選用空間復(fù)雜度較小的深度優(yōu)先搜索算法來實現(xiàn)。

算法核心流程：構(gòu)建一個Traveler對象模擬各種乘車方案，具體來講，當(dāng)traveler到達(dá)某個站點后，看一下在當(dāng)前時間所有可以乘坐的車次，依次嘗試各個可以乘坐的車次，同時更新花費和到達(dá)時間，到達(dá)下一個車站后重復(fù)上述過程。當(dāng)?shù)竭_(dá)一個車站發(fā)現(xiàn)沒有任何一輛車次可以乘坐，則回退到上一個車站嘗試其他車次，具體實現(xiàn)如下：

// 嘗試從當(dāng)前站乘車

for （Line line ： graph.map.get（currentStation.id）） {

if （！path.empty（） && ！path.peek（）.id.equals（line.id） &&

（line.startTime.getTime（） - currentDate.getTime（）） <

（long） minMinutesForSameStationTransfer * 60 * 1000）

continue;

if （line.startTime.compareTo（currentDate） < 0） continue; // 防止跨天

// 更新?lián)Q乘次數(shù)

int newTransferTimes = transferTimes;

if （！path.isEmpty（） && ！（path.peek（）.id）.equals（line.id）） newTransferTimes++;

if （newTransferTimes > maxTransferTimes） continue;

path.push（line）;

travel（line.endStation， line.endTime， currentCost + line.price， newTransferTimes）;

path.pop（）;

}

（三）剪枝優(yōu)化

為了縮短用戶查詢時間，需要對上述算法進行優(yōu)化。通過之前定義的Scheme數(shù)據(jù)結(jié)構(gòu)可以方便地對搜索過程進行剪枝。剪枝可以分為兩部分，一部分根據(jù)用戶的限制條件進行剪枝，例如當(dāng)前時間已經(jīng)超出用戶設(shè)置的可以接受的最晚到達(dá)時間，則沒有必要繼續(xù)擴展當(dāng)前搜索子樹。另一種是通過和歷史經(jīng)過該站點的方案進行比較，如果當(dāng)前方案在所有方面均比歷史方案差，則沒有必要在此方案的基礎(chǔ)上繼續(xù)嘗試。

（四）方案評價與復(fù)雜度分析

曾考慮過效率更高的動態(tài)規(guī)劃算法，但為了更高的靈活性和可擴展性以及易實現(xiàn)性選用了搜索算法。搜索算法在最壞情況下時間復(fù)雜度將是指數(shù)級別。但由于乘車問題具有時間限制其復(fù)雜度遠(yuǎn)遠(yuǎn)低于指數(shù)。在最初測試時對于用戶查詢大概可以在幾分鐘內(nèi)返回結(jié)果。這樣的表現(xiàn)顯然不盡如人意。于是采用“剪枝”對算法進行優(yōu)化，優(yōu)化之后，通過測試，平均可以在5s內(nèi)可以返回查詢結(jié)果。

三、系統(tǒng)設(shè)計

本文所設(shè)計的系統(tǒng)是一個后端系統(tǒng)，為前端提供查詢服務(wù)接口，主要借助Spring平臺。

系統(tǒng)分為四個模塊：數(shù)據(jù)獲取模塊、核心算法處理模塊、數(shù)據(jù)庫交互模塊、WEB模塊。各模塊之間的依賴關(guān)系如圖3。

WEB模塊負(fù)責(zé)處理前端發(fā)送的請求，將請求傳遞給算法處理模塊，并將處理結(jié)果返回給前端。

核心算法模塊在初始化時從數(shù)據(jù)庫中將鐵路路線信息加載進內(nèi)存，接受請求，通過搜索，將結(jié)果返回給WEB模塊。

數(shù)據(jù)庫交互模塊使用Mybatis框架，負(fù)責(zé)將數(shù)據(jù)庫數(shù)據(jù)映射成Java對象。

數(shù)據(jù)獲取模塊使用并發(fā)優(yōu)秀的WebMagic框架，負(fù)責(zé)訪問接口獲取鐵路信息，并將信息存入數(shù)據(jù)庫。同時使用Spring Task做定時任務(wù)框架，每日定時更新鐵路信息。

同時系統(tǒng)采用分布式架構(gòu)，各個服務(wù)之間使用Dubbo進行通信。整個系統(tǒng)的部署圖如圖4。

四、結(jié)論

基本實現(xiàn)了預(yù)期功能。

五、解決方案持有的問題

①暫時無法提供跨天乘車方案，一是因為數(shù)據(jù)不充足，二是算法處理時間較長，無法在5s內(nèi)返回用戶想要的方案。

②雖然在爬蟲系統(tǒng)方面采取種種措施保證數(shù)據(jù)完整性，但還會丟失0.2%的數(shù)據(jù)。難以在數(shù)據(jù)完整性和爬取速度方面達(dá)到平衡。

③由于采用將整條路線拆分成一段段的路徑類和求花費，使用這種方案計算出的價格和實際價格可能有0.5元或者1元的誤差。

六、后續(xù)研究方向

①增加跨天乘車方案的功能。

②加強對數(shù)據(jù)獲取的控制，爭取達(dá)到更高的數(shù)據(jù)完整性和更快的獲取速度。

作者單位：郭怡然 重慶市重慶郵電大學(xué)2019級軟件工程學(xué)院

參? 考? 文? 獻

[1]林開欽，白羽，王倩，柴強. 一種改進的星間鏈路深度優(yōu)先路由搜索算法[C]//第十二屆中國衛(wèi)星導(dǎo)航年會論文集——S06 時間基準(zhǔn)與精密授時.[出版者不詳]，2021：98-101.DOI：10.26914/c.cnkihy.2021.002192.

[2]https：//redis.io/documentation [2021.10.2]

[3]https：//www.rabbitmq.com/getstarted.html [2021.10.3]

[4]https：//dubbo.apache.org/zh/docs/ [2021.10.5]

[5]http：//webmagic.io/docs/zh/ [2021.10.1]