摘要：目前，許多長距離鐵路出行沒有直達(dá)列車，或直達(dá)列車?yán)@路，導(dǎo)致額外的時間和金錢花費(fèi)。本文針對這一現(xiàn)象，將復(fù)雜的鐵路路線數(shù)據(jù)抽象成計算機(jī)方便處理的圖，使用帶有剪枝優(yōu)化的深度優(yōu)先搜索算法，對可能的乘車中轉(zhuǎn)方案進(jìn)行遍歷，根據(jù)不同目標(biāo)（如花費(fèi)最少、耗時最短、到達(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ī)劃出一條花費(fèi)最少，或者到達(dá)時間最早，又或者是換乘次數(shù)最少的乘車方案愈發(fā)顯得重要。12306 官方網(wǎng)站提供的各種換乘方案無法讓用戶自己設(shè)定最早出發(fā)時間，最晚到達(dá)時間，以及最小換乘時間的限制，而且最多只能換乘一次，靈活性受限。提供的換乘方案又多又雜，用戶體驗不好。
本文以開發(fā)一個能夠幫助用戶更加靈活地規(guī)劃乘車方案的系統(tǒng)為目標(biāo)，彌補(bǔ) 12306 官網(wǎng)提供的服務(wù)的缺點，支持用戶自己定制各種條件，包括最早出發(fā)時間、最晚到達(dá)時間、最小換乘時間、最大換乘次數(shù)。為用戶規(guī)劃出行路線提供一定參考。
二、算法設(shè)計
算法主要分為兩部分，一部分是根據(jù)鐵路數(shù)據(jù)構(gòu)建出圖，另一部分是在圖上進(jìn)行搜索。
（一）構(gòu)建圖
將每個站點抽象成點，兩個站點之間的鐵路線路抽象成邊。設(shè)計站點的數(shù)據(jù)結(jié)構(gòu)如下，后期可以方便地進(jìn)行屬性的添加。設(shè)計路線的數(shù)據(jù)結(jié)構(gòu)如下，維護(hù)了始發(fā)站、終點站、始發(fā)時間、到達(dá)時間、座位類型（二等座/硬座）、價格、編號等信息。
采用鄰接表數(shù)據(jù)結(jié)構(gòu)存儲圖，即對于每個站點Station，存儲離開它的所有線路，圖的數(shù)據(jù)結(jié)構(gòu)如圖1：
為了方便剪枝和輸出最終方案，創(chuàng)建方案的數(shù)據(jù)結(jié)構(gòu)如下，即維護(hù)花費(fèi)、到達(dá)時間、總用時、與期望時間差異程度等各項評價參數(shù)：
方法：betterInAllAspects和atLeastBetterInOneAspect，分別用于對其他方案進(jìn)行剪枝和決定是否對當(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)前時間所有可以乘坐的車次，依次嘗試各個可以乘坐的車次，同時更新花費(fèi)和到達(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)化
為了縮短用戶查詢時間，需要對上述算法進(jìn)行優(yōu)化。通過之前定義的Scheme數(shù)據(jù)結(jié)構(gòu)可以方便地對搜索過程進(jìn)行剪枝。剪枝可以分為兩部分，一部分根據(jù)用戶的限制條件進(jìn)行剪枝，例如當(dāng)前時間已經(jīng)超出用戶設(shè)置的可以接受的最晚到達(dá)時間，則沒有必要繼續(xù)擴(kuò)展當(dāng)前搜索子樹。另一種是通過和歷史經(jīng)過該站點的方案進(jìn)行比較，如果當(dāng)前方案在所有方面均比歷史方案差，則沒有必要在此方案的基礎(chǔ)上繼續(xù)嘗試。
（四）方案評價與復(fù)雜度分析
曾考慮過效率更高的動態(tài)規(guī)劃算法，但為了更高的靈活性和可擴(kuò)展性以及易實現(xiàn)性選用了搜索算法。搜索算法在最壞情況下時間復(fù)雜度將是指數(shù)級別。但由于乘車問題具有時間限制其復(fù)雜度遠(yuǎn)遠(yuǎn)低于指數(shù)。在最初測試時對于用戶查詢大概可以在幾分鐘內(nèi)返回結(jié)果。這樣的表現(xiàn)顯然不盡如人意。于是采用“剪枝”對算法進(jì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ù)庫中將鐵路路線信息加載進(jìn)內(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進(jìn)行通信。整個系統(tǒng)的部署圖如圖4。
四、結(jié)論
基本實現(xiàn)了預(yù)期功能。
五、解決方案持有的問題
①暫時無法提供跨天乘車方案，一是因為數(shù)據(jù)不充足，二是算法處理時間較長，無法在5s內(nèi)返回用戶想要的方案。
②雖然在爬蟲系統(tǒng)方面采取種種措施保證數(shù)據(jù)完整性，但還會丟失0.2%的數(shù)據(jù)。難以在數(shù)據(jù)完整性和爬取速度方面達(dá)到平衡。
③由于采用將整條路線拆分成一段段的路徑類和求花費(fèi)，使用這種方案計算出的價格和實際價格可能有0.5元或者1元的誤差。
六、后續(xù)研究方向
①增加跨天乘車方案的功能。
②加強(qiáng)對數(shù)據(jù)獲取的控制，爭取達(dá)到更高的數(shù)據(jù)完整性和更快的獲取速度。
作者單位：郭怡然 重慶市重慶郵電大學(xué)2019級軟件工程學(xué)院
參 考 文 獻(xiàn)
[1]林開欽，白羽，王倩，柴強(qiáng). 一種改進(jìn)的星間鏈路深度優(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]
