劉文韜，牛青坡，李天翼，宋 陽

（中國鐵道科學(xué)研究院集團(tuán)有限公司 電子計(jì)算技術(shù)研究所，北京 100081)

0 引言

截至2020年12月底，我國鐵路運(yùn)營里程達(dá)14.63萬km，規(guī)模居世界第二，其中高速鐵路里程3.8萬km，占世界高速鐵路總里程近70%，多年穩(wěn)居世界第一?！八臋M四縱”高速鐵路網(wǎng)絡(luò)已經(jīng)建成，“八橫八縱”的高速鐵路網(wǎng)絡(luò)正在逐步建設(shè)，在京津冀、長三角、珠三角等經(jīng)濟(jì)發(fā)達(dá)和人口稠密地區(qū)的城際網(wǎng)絡(luò)日益完善?！缎聲r(shí)代交通強(qiáng)國鐵路先行規(guī)劃綱要》提出，到2035年，全國鐵路運(yùn)營里程達(dá)20萬km左右，高速鐵路達(dá)7萬km左右，鐵路網(wǎng)內(nèi)外互聯(lián)互通、區(qū)際多路暢通、省會(huì)高效連通、地市快速通達(dá)、縣域基本覆蓋、樞紐銜接順暢。鐵路快速發(fā)展在便利旅客出行的同時(shí)，也對(duì)鐵路客運(yùn)運(yùn)營管理工作提出了更高的要求。

鐵路客運(yùn)運(yùn)營條件是指鐵路線路、車站組織旅客運(yùn)輸生產(chǎn)活動(dòng)的營業(yè)辦理?xiàng)l件，主要業(yè)務(wù)類型包括：線路開通、車站命名(更名)、車站開辦、停辦或變更客運(yùn)業(yè)務(wù)等，是鐵路業(yè)務(wù)部門管理路網(wǎng)信息的重要工作。長期以來鐵路客運(yùn)運(yùn)營條件信息管理采用人工管理為主、簡(jiǎn)單電子化表格為輔的管理模式。伴隨鐵路網(wǎng)規(guī)模擴(kuò)大，結(jié)構(gòu)日益復(fù)雜，現(xiàn)有管理模式已不能與管理需求相匹配，亟需實(shí)現(xiàn)鐵路客運(yùn)運(yùn)營條件的信息化管理，提高鐵路客運(yùn)運(yùn)營條件管理的效率和水平。

查找計(jì)算2個(gè)車站之間的合理可達(dá)徑路及里程，是鐵路客運(yùn)運(yùn)營條件管理的日常工作，以鐵路客運(yùn)運(yùn)營條件信息為基礎(chǔ)，研究經(jīng)典圖論中的徑路算法[1]，構(gòu)建指定起始站、終到站條件下可達(dá)徑路的搜索模型，改變依賴人工經(jīng)驗(yàn)或紙質(zhì)地圖查找計(jì)算的工作模式，為鐵路客運(yùn)運(yùn)營條件管理人員提供高效實(shí)用的信息化工具[2]。

1 徑路搜索算法適應(yīng)性分析

通過分析比對(duì)，在諸多圖論徑路搜索算法中，選取深度優(yōu)先搜索算法(DFS算法)、狄克斯特拉算法(Dijkstra算法)和A*(A-Star)算法進(jìn)行重點(diǎn)研究，用Java語言實(shí)現(xiàn)算法，在相同的數(shù)據(jù)基礎(chǔ)上進(jìn)行模擬驗(yàn)證，并結(jié)合需求特點(diǎn)對(duì)不同算法進(jìn)行適用性分析。

1.1 DFS算法

DFS算法用于遍歷或搜索樹和圖，其基本思路是從圖中1個(gè)節(jié)點(diǎn)出發(fā)，每次遍歷當(dāng)前訪問節(jié)點(diǎn)的1個(gè)相鄰可達(dá)節(jié)點(diǎn)，一直到訪問的節(jié)點(diǎn)沒有未被訪問過的相鄰可達(dá)節(jié)點(diǎn)為止。然后采用依次回退的方式，查看遍歷路徑上的每一個(gè)節(jié)點(diǎn)是否有其他未被訪問的相鄰可達(dá)節(jié)點(diǎn)[3]。上述訪問過程完成后，全部連通圖中的所有節(jié)點(diǎn)都已經(jīng)遍歷完成，通過此算法可以搜索指定2點(diǎn)間所有可達(dá)徑路。DFS算法是一個(gè)不斷遍歷回溯的過程，采用了遞歸的思想實(shí)現(xiàn)搜索目標(biāo)結(jié)果集。

1.2 Dijkstra算法

Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959 年提出的，是經(jīng)典最短徑路算法之一，是能夠獲取圖中的指定節(jié)點(diǎn)到其余各節(jié)點(diǎn)的單源最短徑路算法[4]，其核心思想是以起點(diǎn)為中心向外層擴(kuò)展，求出該節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑，即從 1個(gè)點(diǎn)開始到其他所有點(diǎn)的路徑[5]。Dijkstra算法應(yīng)用貪心算法的策略[6]，每次遍歷到指定節(jié)點(diǎn)距離最近且未訪問過的頂點(diǎn)的鄰接節(jié)點(diǎn)，直到擴(kuò)展到終點(diǎn)為止。

1.3 A*算法

A*算法又稱A-Star算法，是基于啟發(fā)式的最短徑路算法，每次利用一個(gè)確定的評(píng)價(jià)函數(shù)對(duì)所有沒展開的節(jié)點(diǎn)進(jìn)行評(píng)價(jià)，從而找到最符合評(píng)價(jià)標(biāo)準(zhǔn)的節(jié)點(diǎn)[7]。A*算法中的距離估算值與實(shí)際值越接近，最終搜索速度越快，通常用曼哈頓距離作為評(píng)價(jià)函數(shù)預(yù)估距離代價(jià)，搜索過程取決于A*算法采用的評(píng)價(jià)函數(shù)，搜索效率受限[8]。

1.4 算法比對(duì)

為綜合分析不同算法的適用性，采用構(gòu)建靜態(tài)站點(diǎn)模型方式進(jìn)行執(zhí)行情況分析，節(jié)點(diǎn)模型示意圖如圖1所示。圖1中圓圈代表節(jié)點(diǎn)，圓圈中的字母代表節(jié)點(diǎn)名稱，數(shù)字代表節(jié)點(diǎn)序號(hào)，圓圈之間的線段表示節(jié)點(diǎn)之間存在可達(dá)徑路，徑路旁邊的數(shù)字代表徑路長度。用Java語言實(shí)現(xiàn)上述3種算法，驗(yàn)證內(nèi)容為：①求A點(diǎn)到U點(diǎn)的最短徑路及其距離；②求A點(diǎn)到U點(diǎn)的所有可達(dá)徑路；③計(jì)算算法的執(zhí)行時(shí)間。3種算法對(duì)比結(jié)果如表1所示。

通過對(duì)DFS算法、Dijkstra算法、A*算法特點(diǎn)和執(zhí)行結(jié)果的分析可知，Dijkstra算法是一種尋找單源到其他所有節(jié)點(diǎn)的最短路徑搜索算法，需要指定起點(diǎn)，可以計(jì)算出起點(diǎn)到圖中其他所有可達(dá)點(diǎn)的最短路徑；A*算法是一種尋找指定2點(diǎn)間最短路徑的算法，搜索過程取決于A*算法采用的評(píng)價(jià)函數(shù)；DFS算法在問題求解過程中對(duì)圖進(jìn)行遍歷，能夠搜索指定2點(diǎn)間所有可達(dá)路徑的算法，適用鐵路客運(yùn)運(yùn)營條件信息中求解給定始發(fā)、終到站之間所有可達(dá)路徑的需求。雖然利用靜態(tài)站點(diǎn)計(jì)算DFS算法在開發(fā)環(huán)境下優(yōu)化前的指標(biāo)并不是最優(yōu)，綜合分析業(yè)務(wù)應(yīng)用場(chǎng)景，該算法符合鐵路客運(yùn)運(yùn)營條件業(yè)務(wù)管理需求，因而選擇DFS算法作為鐵路客運(yùn)運(yùn)營條件徑路搜索算法的基礎(chǔ)。

圖1 節(jié)點(diǎn)模型示意圖Fig.1 Diagram of node model

表1 3種算法對(duì)比結(jié)果表Tab.1 Comparison among three algorithms

2 基于鐵路客運(yùn)運(yùn)營條件信息的徑路算法

將Java實(shí)現(xiàn)DFS算法應(yīng)用于經(jīng)過規(guī)范化整理的鐵路客運(yùn)運(yùn)營條件數(shù)據(jù)后，由于車站眾多、線路之間交叉關(guān)系復(fù)雜等原因，導(dǎo)致算法遞歸調(diào)用層次過多，搜索出大量不合理的繞行徑路，時(shí)間開銷劇增，在實(shí)際業(yè)務(wù)中不可用。因此，應(yīng)基于鐵路客運(yùn)運(yùn)營條件信息特點(diǎn)，從簡(jiǎn)化搜索節(jié)點(diǎn)、限定搜索區(qū)域、結(jié)合列車開行、控制遞歸深度等方面對(duì)DFS算法進(jìn)行優(yōu)化，以提升計(jì)算效率。

2.1 簡(jiǎn)化搜索節(jié)點(diǎn)

鐵路客運(yùn)運(yùn)營條件信息中辦理客運(yùn)業(yè)務(wù)、乘降所、結(jié)算站等各類車站近5 000個(gè)，全部車站都作為路網(wǎng)圖模型節(jié)點(diǎn)，將大大增加算法的搜索深度，消耗大量?jī)?nèi)存和計(jì)算資源，嚴(yán)重影響徑路搜索效率。依據(jù)鐵路客運(yùn)運(yùn)營條件信息中線路、車站及線站關(guān)系等特點(diǎn)，選取有2條及以上線路經(jīng)過的結(jié)算站作為構(gòu)建遞歸搜索的基本節(jié)點(diǎn)，再結(jié)合始發(fā)、經(jīng)由和終到車站信息，形成完整的徑路搜索圖。經(jīng)上述優(yōu)化篩選后，搜索節(jié)點(diǎn)數(shù)量得到有效控制，數(shù)量降為800個(gè)左右，不到全部車站的1/6，算法占用資源降低，搜索效率有了較大的提升。

算法實(shí)現(xiàn)將鐵路網(wǎng)定義為圖G= (V，E)，V是圖G中各節(jié)點(diǎn)車站集合，V= {vi|i= 1，2，…，n}，其中vi代表第i個(gè)車站，vi= {(xi，yi) |i= 1，2，…，n}，n為車站的數(shù)量，其中xi為vi車站的經(jīng)度，yi為vi車站的緯度；E為連接站點(diǎn)的線路作為圖中的邊，其值為線路端點(diǎn)站間的里程，E= {(u，v) |u，v∈V} = {e1，e2，…，ej，…，em}，其中ej代表第j條線路，m為線路的條數(shù)。

結(jié)算站優(yōu)化前后節(jié)點(diǎn)示意圖如圖2所示。優(yōu)化前包含全路范圍車站，其中遼寧朝陽、沙城、忻州、楊村等站并不是結(jié)算站，去除這些車站不影響路網(wǎng)的通達(dá)性，通過篩選結(jié)算站方式可以大量減少節(jié)點(diǎn)數(shù)量。

2.2 限定搜索區(qū)域

由于路網(wǎng)結(jié)構(gòu)復(fù)雜，在始發(fā)、終到站之間存在多條可達(dá)徑路，其中有些徑路會(huì)有較大的繞行現(xiàn)象，此部分搜索結(jié)果除了通達(dá)性之外，沒有實(shí)際應(yīng)用意義，應(yīng)予以舍棄，進(jìn)一步降低無效搜索數(shù)量，提升算法效率。

算法改進(jìn)應(yīng)結(jié)合始發(fā)站、終到站的實(shí)際情況對(duì)搜索區(qū)域進(jìn)行限定，以始發(fā)站、終到站的經(jīng)緯度信息為基礎(chǔ)，按照始發(fā)站、終到站所在經(jīng)緯度位置，設(shè)置一定范圍內(nèi)的經(jīng)緯度偏移量閥值(如1°，2°等)，確定新的始發(fā)、終到位置，以兩者之間的連線做對(duì)角線確定四邊形的搜索區(qū)域，在區(qū)域內(nèi)的車站為合理搜索的節(jié)點(diǎn)。經(jīng)緯度偏移量系數(shù)設(shè)置為p1= {z|z= 1，2，…，5}。其中z代表偏移度。通過搜索區(qū)域限定，算法的搜索范圍大為降低，既能節(jié)省無效搜索的開銷，又能搜索出合理的徑路。

以北京到廣州為例，優(yōu)化前后的限定搜索區(qū)域變化如圖3所示，將偏離北京和廣州較遠(yuǎn)的沈陽、長春、哈爾濱、通遼、西安、青島和上海等方向的線路車站做了有效的排除。

圖3 優(yōu)化前后的限定搜索區(qū)域變化Fig.3 Change in limited search area before and after optimization

2.3 結(jié)合列車開行

算法模型中按照路網(wǎng)基本信息進(jìn)行關(guān)聯(lián)，會(huì)形成較為復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，存在較多不合理的可達(dá)徑路。為進(jìn)一步提升可達(dá)徑路的合理性，搜索過程中與實(shí)際列車運(yùn)行情況相結(jié)合，加入列車徑路因素，將有效開行列車運(yùn)行線路作為徑路搜索的重要依據(jù)，簡(jiǎn)化節(jié)點(diǎn)間的連接關(guān)系，縮小搜索范圍，提升算法效率。

列車開行徑路因素由p2表示，p2=φ(A，B)，A∈VK，B∈EK，其中A代表變線站因素；VK代表列車運(yùn)行徑路中變線站集合；B代表徑路因素；EK是列車運(yùn)行徑路中行經(jīng)線路集合。

以北京到廣州的徑路為例，結(jié)合列車開行優(yōu)化后搜索徑路簡(jiǎn)化示意圖如圖4所示。將北京至廣州區(qū)間不會(huì)行經(jīng)的北京—張家口—原平—太原、北京—天津—濟(jì)南—鄭州、鄭州—十堰—襄陽—黔江—長沙南等繞行區(qū)間排除。

圖4 列車開行優(yōu)化后搜索徑路簡(jiǎn)化示意圖Fig.4 Simplified diagram of search paths optimized by train plans

2.4 控制遞歸深度

為使算法的時(shí)間效率可控，對(duì)遞歸條件進(jìn)行優(yōu)化，采用遞歸深度和累計(jì)里程2種機(jī)制控制算法是否結(jié)束，結(jié)合對(duì)鐵路客運(yùn)運(yùn)營條件信息的綜合分析，設(shè)置遞歸深度閥值及最大累計(jì)里程閥值，超過閥值的徑路視為不合理徑路，有效控制算法遞歸深度，確保時(shí)間效率。

用T代表節(jié)點(diǎn)深度控制閥值，超過閥值的搜索將被終止。X代表里程控制閥值，第一條徑路計(jì)算完成后的里程閥值X1依據(jù)首次計(jì)算得到的徑路里程S(p1)和經(jīng)緯度偏移量p1系數(shù)計(jì)算得到

式中：X1為第一條徑路計(jì)算完成后的里程閥值；Z1為2個(gè)站間連線與低經(jīng)度站緯線間形成的角度；X ′為校對(duì)里程，設(shè)置范圍為業(yè)務(wù)可接受的里程偏差，驗(yàn)證中取X ′∈[0，50]。依次按照最短里程進(jìn)行閥值修正，則當(dāng)前徑路里程可以表示為

式中：Xi為當(dāng)前徑路里程；Xi-1為前序徑路里程。

3 基于鐵路客運(yùn)運(yùn)營條件信息的徑路算法優(yōu)化流程及效果

3.1 算法優(yōu)化流程

基于鐵路客運(yùn)運(yùn)營條件信息的徑路算法優(yōu)化以保留核心關(guān)鍵節(jié)點(diǎn)、降低鐵路客運(yùn)運(yùn)營條件信息復(fù)雜度為基礎(chǔ)，通過簡(jiǎn)化搜索節(jié)點(diǎn)、經(jīng)緯度限定搜索范圍、結(jié)合列車開行、設(shè)置遞歸深度和里程閥值等優(yōu)化，有效提升求解效率，得到符合業(yè)務(wù)需求的最優(yōu)徑路。經(jīng)過優(yōu)化后的基于鐵路客運(yùn)運(yùn)營條件信息的徑路算法搜索可達(dá)徑路時(shí)，在鐵路客運(yùn)運(yùn)營條件路網(wǎng)信息中指定始發(fā)站vs經(jīng)由vv站至終到站ve的最優(yōu)可達(dá)徑路里程表示為

式中：vs代表始發(fā)站；vv代表經(jīng)由站；ve代表終到站；ei代表vi站到vi+1站的最優(yōu)徑路；α(p1，V)為按照結(jié)算站及經(jīng)緯度偏移量篩選的節(jié)點(diǎn)集合；β(p2，V，E)為按照列車開行徑路優(yōu)化后的車站及站間可達(dá)線路關(guān)系；γ(X，T，V，E)為按照節(jié)點(diǎn)深度及里程進(jìn)行的線站搜索控制范圍；di為vi，vi+1之間經(jīng)過α，β，γ綜合判定后的優(yōu)選徑路里程。

基于鐵路客運(yùn)運(yùn)營條件信息的徑路算法優(yōu)化流程如圖5所示。

圖5 算法優(yōu)化流程圖Fig.5 Flow chart of algorithm optimization

3.2 算法優(yōu)化效果

以北京—廣州區(qū)間為例，優(yōu)化之前全部線站加載至模型中參與經(jīng)由運(yùn)算，結(jié)果集中會(huì)出現(xiàn)與始發(fā)站、終到站偏離較遠(yuǎn)的車站節(jié)點(diǎn)，經(jīng)過線路、車站節(jié)點(diǎn)較多，未進(jìn)行遞歸深度控制，不僅運(yùn)算時(shí)間長，執(zhí)行結(jié)果產(chǎn)生了大量不合理的徑路。優(yōu)化前后徑路如圖6所示。

圖6 優(yōu)化前后徑路圖Fig.6 Path charts before and after optimization

算法優(yōu)化前后的效果對(duì)比如表2所示。

表2 算法優(yōu)化前后的效果對(duì)比Tab.2 Comparison between optimization algorithms

經(jīng)過節(jié)點(diǎn)、經(jīng)緯度、列車開行、遞歸深度的優(yōu)化后，節(jié)點(diǎn)規(guī)模大幅度減少，排除了偏離始發(fā)站、終到站較遠(yuǎn)的徑路，不會(huì)繞行距離較遠(yuǎn)的車站，會(huì)與列車開行緊密結(jié)合，徑路合理性明顯優(yōu)于原始算法，與實(shí)際業(yè)務(wù)要求相符，同時(shí)時(shí)間效率有較大提升，算法用時(shí)由百秒級(jí)降至毫秒級(jí)。

4 結(jié)束語

在我國鐵路路網(wǎng)建設(shè)規(guī)模逐步擴(kuò)大，結(jié)構(gòu)日益復(fù)雜的情況下，圍繞路網(wǎng)信息的業(yè)務(wù)特點(diǎn)，對(duì)線路、車站進(jìn)行關(guān)聯(lián)，設(shè)計(jì)路網(wǎng)模型，以DFS算法為基礎(chǔ)進(jìn)行研究改進(jìn)，能夠解決搜索深度過大情況下的合理徑路高效求解難題，快速全面地搜索出符合業(yè)務(wù)需求的站間合理徑路，有效提升鐵路客運(yùn)運(yùn)營條件的信息化管理水平。未來可根據(jù)實(shí)際應(yīng)用情況綜合考慮客流分布、旅客偏好等因素對(duì)模型進(jìn)一步優(yōu)化，為旅客互聯(lián)化、智慧化的美好出行服務(wù)提供技術(shù)支撐，為網(wǎng)狀綜合交通的互聯(lián)互通管理提供新的思路。