基于深度優先搜索的鐵路中轉路線規劃研究

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

關鍵詞：鐵路中轉方案；深度優先算法；剪枝優化；軟件系統設計

一、引言

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

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

二、算法設計

算法主要分為兩部分，一部分是根據鐵路數據構建出圖，另一部分是在圖上進行搜索。

（一）構建圖

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

采用鄰接表數據結構存儲圖，即對于每個站點Station，存儲離開它的所有線路，圖的數據結構如圖1：

為了方便剪枝和輸出最終方案，創建方案的數據結構如下，即維護花費、到達時間、總用時、與期望時間差異程度等各項評價參數：

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

（二）圖的搜索

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

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

// 嘗試從當前站乘車

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; // 防止跨天

// 更新換乘次數

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（）;

}

（三）剪枝優化

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

（四）方案評價與復雜度分析

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

三、系統設計

本文所設計的系統是一個后端系統，為前端提供查詢服務接口，主要借助Spring平臺。

系統分為四個模塊：數據獲取模塊、核心算法處理模塊、數據庫交互模塊、WEB模塊。各模塊之間的依賴關系如圖3。

WEB模塊負責處理前端發送的請求，將請求傳遞給算法處理模塊，并將處理結果返回給前端。

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

數據庫交互模塊使用Mybatis框架，負責將數據庫數據映射成Java對象。

數據獲取模塊使用并發優秀的WebMagic框架，負責訪問接口獲取鐵路信息，并將信息存入數據庫。同時使用Spring Task做定時任務框架，每日定時更新鐵路信息。

同時系統采用分布式架構，各個服務之間使用Dubbo進行通信。整個系統的部署圖如圖4。

四、結論

基本實現了預期功能。

五、解決方案持有的問題

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

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

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

六、后續研究方向

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

②加強對數據獲取的控制，爭取達到更高的數據完整性和更快的獲取速度。

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

參? 考? 文? 獻

[1]林開欽，白羽，王倩，柴強. 一種改進的星間鏈路深度優先路由搜索算法[C]//第十二屆中國衛星導航年會論文集——S06 時間基準與精密授時.[出版者不詳]，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]