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

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

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

一、引言

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

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

二、算法設(shè)計(jì)

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

（一）構(gòu)建圖

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

采用鄰接表數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)圖，即對(duì)于每個(gè)站點(diǎn)Station，存儲(chǔ)離開(kāi)它的所有線路，圖的數(shù)據(jù)結(jié)構(gòu)如圖1：

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

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

（二）圖的搜索

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

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

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

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（） && ?。╬ath.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)化

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

（四）方案評(píng)價(jià)與復(fù)雜度分析

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

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

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

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

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

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

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

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

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

四、結(jié)論

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

五、解決方案持有的問(wèn)題

①暫時(shí)無(wú)法提供跨天乘車(chē)方案，一是因?yàn)閿?shù)據(jù)不充足，二是算法處理時(shí)間較長(zhǎng)，無(wú)法在5s內(nèi)返回用戶想要的方案。

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

③由于采用將整條路線拆分成一段段的路徑類(lèi)和求花費(fèi)，使用這種方案計(jì)算出的價(jià)格和實(shí)際價(jià)格可能有0.5元或者1元的誤差。

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

①增加跨天乘車(chē)方案的功能。

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

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

參? 考? 文? 獻(xiàn)

[1]林開(kāi)欽，白羽，王倩，柴強(qiáng). 一種改進(jìn)的星間鏈路深度優(yōu)先路由搜索算法[C]//第十二屆中國(guó)衛(wèi)星導(dǎo)航年會(huì)論文集——S06 時(shí)間基準(zhǔn)與精密授時(shí).[出版者不詳]，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]