基于鐵路客運運營條件信息的 徑路算法研究

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

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

0 引言

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

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

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

1 徑路搜索算法適應性分析

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

1.1 DFS算法

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

1.2 Dijkstra算法

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

1.3 A*算法

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

1.4 算法比對

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

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

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

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

2 基于鐵路客運運營條件信息的徑路算法

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

2.1 簡化搜索節(jié)點

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

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

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

2.2 限定搜索區(qū)域

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

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

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

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

2.3 結(jié)合列車開行

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

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

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

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

2.4 控制遞歸深度

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

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

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

式中：Xi為當前徑路里程；Xi-1為前序徑路里程。

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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