高速鐵路網列車運行徑路精細化搜索算法研究

李 靖，王 濤，李 博，劉明瑋

（1.中國鐵道科學研究院集團有限公司 中國鐵路列車運行圖技術中心，北京 100081；2.中國鐵道科學研究院集團有限公司 運輸及經濟研究所，北京 100081；3.中國國家鐵路集團有限公司運輸部，北京 100844）

0 引言

隨著我國鐵路行業快速而穩步的發展，大量高速鐵路線路、車站建成并投入使用，路網規模愈發龐大，結構也愈發復雜，截至2022 年底全國高速鐵路營業里程共計4.2 萬余km，是德國的6 倍、法國的9 倍、日本的12 倍，同時路網內樞紐越來越多，樞紐內車站不同方向之間徑路的連通關系復雜，如石家莊至沈陽高速列車徑路分析如表1 所示。石家莊至沈陽的徑路在北京樞紐不連通，可知在徑路搜索時考慮樞紐內部的連通性具有必要性；我國高速鐵路點多、線長、面廣且跨線列車多，大規模成網運營已成為不同于國外高速鐵路的突出特點(例如日本多為本線運行，法國多為小規?？缇€運行)，在實際上增大了列車運行徑路搜索的難度。

表1 石家莊至沈陽高速列車徑路分析Tab.1 Analysis of high speed railway train routes from Shijiazhuang to Shenyang

客流需求等因素是列車運行組織、計劃編制、應急指揮工作中的重要基礎，而根據客流需求的列車徑路是否具有可行性需要精細化的徑路搜索來支撐，徑路搜索可為運輸組織工作提供技術支持，實現降本增效的目的。目前國內外學者在網絡構建、路徑求解等方面進行了大量研究。張蘭霞[1]、賀俊源[2]對我國高速鐵路網特點進行分析；胡心磊等[3]對高速鐵路列車徑路進行了分類與分析；張羽成等[4]研究鐵路網絡結構存儲及路徑構造；畢明凱等[5]建立場站網絡拓撲圖并對樞紐場站分工優化求解。路徑搜索算法方面，最短路求解有Dijkstra 算法[6]，K 短路求解有YEN 算法[7]、雙向掃除算法[8]等；啟發式算法求解有A*算法[9]、B*算法[10]等。高速路網徑路搜索方面，胡必松[11]利用動態規劃思想采用逆序解法求解K短路問題；王喆等[12]從遺傳學角度探討兩點間K 條最優路徑；習子文[13]結合Dijkstra算法和雙向掃除算法求解OD間的合理徑路集；柳鍵等[14]采用一種拼接和去冗結合的K最短路算法設計客運服務網絡路徑搜索；范家銘等[15]采用向量限定等優化策略實現列車徑路快速搜索等。

上述研究聚焦路網構建、徑路搜索等方面，主要以車站或車場為路網節點，未考慮車站的結構和進路信息，在樞紐等連通關系復雜的地區徑路搜索更容易產生誤差，徑路搜索精細化程度有待提升。本研究針對大規模復雜的高速鐵路網，重點考慮詳細的車站站場結構，并構建區間屬性信息，提出全國高速鐵路網的多徑路精細化搜索算法。

1 精細化高速鐵路拓撲網構建方法

高速鐵路網指有動車組列車開行的高速鐵路、城際鐵路、高普混行線路。高速鐵路拓撲網根據構建精細程度的不同，可分為宏觀、中觀、微觀3 個層級，其復雜程度有較大差距，不同精度層級下鐵路網構建涉及數據如圖1 所示。宏觀和中觀層面下通過車站節點的線路默認連通，車站節點內線路連通關系精度不足；微觀路網層面下可真實反映路網站間、站內實際連通拓撲結構。

圖1 不同精度層級下鐵路網構建涉及數據Fig.1 Railway network construction at different precision levels

為支持列車走行徑路的全過程、精細化研究，研究建立基于車站進出口的多維度路徑信息表示方法，包括車站內進路關系及區間連通關系：在車站物理網絡拓撲的基礎上，構建車站進路數據，并以車站進路數據為基礎構建車站內進站信號節點(車站進出口)間的連通關系，以線路區間數據為基礎構建不同車站間進出口的連通關系，最后實現路網層的連通拓撲構建。上述路徑信息對基礎路網數據的準確性和規范性有很高要求，下面從車站、線路區間實際物理拓撲結構出發，研究高速鐵路網拓撲構建和徑路數據表達。

1.1 車站層級連通拓撲構建

1.1.1 車站物理網絡拓撲構建方法

車站的物理網絡拓撲是車站進路的數據支撐，構建車站拓撲時應以車場為一個獨立的車站單元，使得進路只涉及相應車場。高速鐵路車站站場結構主要由道岔、信號機、軌道區段等設備構成，車站站型示意圖如圖2 所示，各類設備關鍵位置坐標由圖元控制點確定(圖中紅點)，可通過對比關鍵位置坐標確定各設備的左側和右側相鄰的設備類型及名稱[16]。

圖2 車站站型示意圖Fig.2 Railway station yard structure

通過對設備進行關聯，便可構造車站物理網絡拓撲，鐵路車站物理網絡拓撲圖如圖3 所示。各設備存儲有本設備特征數據及相鄰設備連接關系數據，研究將道岔圖元拆分為3 個子節點與2 條連接邊，另外將軌道區段、信號機圖元拆分為2 個子節點和1 條連接邊，設備間的連接關系由不同圖元的子節點連接的邊表示，構建車站拓撲無向圖并根據圖元子節點生成鄰接矩陣。圖3 中車站進出口(ENT)設置于站內最外側的進站信號機，與路網區間拓撲元素相連，實現車站與區間的拓撲連接。

圖3 鐵路車站物理網絡拓撲圖Fig.3 Physical network topology of train stations

1.1.2 列車進路數據構建方法

為構建精細化列車徑路表達，徑路在各車站內的走行過程以基于車站(車場)拓撲結構的列車進路數據描述。進路是由若干個信號機、道岔及道岔位置、軌道區段組成的列車在車站內行車時所經過的通路，并可由始端按鈕和終端按鈕決定進路的相關信息[17]。根據按鈕使用規則[18]，即可確定車站內可組成基本進路的始終端信號機組合，進而生成車站內的列車基本進路數據?；趫D2 車站站型，根據進路按鈕組合XLA、S3LA(LA 為按鈕標識)，即可確定一個簡單的接車進路(X，1，5，S3，3G)。

列車進路可作為車站進出口連通拓撲的數據支撐，同時也可作為徑路搜索下的列車站內走行可視化展示，根據上文構建車站物理網絡拓撲，參考聯鎖車站聯鎖圖表編制原則[19]，通過采用遍歷算法生成車站的列車進路數據，算法簡述如下。

步驟1：遍歷車站的列車信號機，作為進路起始信號按鈕，依次在車站物理網絡拓撲鄰接矩陣中進行檢索。

步驟2：查找并遍歷與起始信號按鈕相連的拓撲元素并遞推至信號類型的拓撲元素，若該信號可作為終端按鈕，遍歷并記錄經由不同的所有進路道岔信息、終端信號按鈕及關聯股道；若不可作為終端按鈕，則繼續遞推至下一個信號或直到無解情況。

步驟3：判斷迂回進路。遍歷各進路的道岔順序編號，如道岔順序x，y，z可由數位更少的x，z連通，則包含x，y，z道岔順序的進路標記為迂回進路。

步驟4：算法結束。

1.1.3 車站進出口連通拓撲構建方法

基于列車進路數據描述車站進出口間的拓撲關系，即構建車站層級連通拓撲?；趫D2 車站站型，根據存在X-S3(3G)和X3(3G)-SN的列車進路，可構建車站進出口ENT1(X)-ENT3(SN)的連通關系。

考慮車站車場和線路所等車站拓撲結構，按進出口的位置及連通關系主要分為以下幾類，車站層級進出口連通圖如圖4所示，①→②可表示不過股道轉場路徑；③→④可表示過股道的轉場路徑；⑤→⑥可表示過股道的通過路徑；⑤→⑦可表示同側到發的折返路徑；⑩→⑨可表示不過股道的線路所通過路徑。綜合上述各類情況可知，若車場間有列車徑路行駛條件，且無場間進站信號，可于轉場道岔處設置虛擬信號，便于生成轉場進路；不經過股道的進出口間的路徑可由一條進路或多條分段進路表示，過股道的進出口間的路徑可由與該股道相關的2 條進路或多條分段進路表示，綜合考慮同側到發的折返路徑等問題，設計基于列車進路數據的車站進出口拓撲圖算法實現過程如下。

圖4 車站層級進出口連通圖Fig.4 Entrance and exit connectivity at the station level

步驟1：遍歷車站的進出口，提取與進出口相連的按鈕信號，檢索以該信號為始端按鈕信號的基本進路。

步驟2：記錄各進路的關聯股道于集合V1，轉步驟4；若進路無關聯股道，將進路終端按鈕信號記錄于集合V2，轉步驟3。

步驟3：若V2中信號與車站進出口相連，則記錄進出口間存在連通關系；否則檢索以該信號為始端按鈕信號的分段進路，返回步驟2。

步驟4：遍歷車站進出口，進行如下判定：①連通性判定。對比各進出口的集合V1，若存在相同股道，則記錄進出口間的連通關系。②車站同側到發判定。對比進出口間的接車進路終端按鈕信號與發車進路始端按鈕信號，若相同，則記錄進出口間為同側到發。

步驟5：算法結束。

1.2 路網層級連通拓撲構建及徑路表達

基于高速鐵路網干支線、站間聯絡線、場間聯絡線等區間信息，構建基于車站(車場)進出口的區間有向連通圖，路網層級車站進出口的連通圖如圖5所示，線路所C的區間起始點ENT5與車站B的區間結束點ENT1 通過區間聯絡線相連。結合車站層級連通情況可以看出，基于車站進出口的連通圖可分為站內連通和區間連通，前者主要影響徑路線路選擇，可以判斷出車站轉場、跨線、立折等列車行車條件，避免徑路解空間內的不可行解；后者主要影響整體徑路的權值，如區間長度、區間運行時分等，精細化徑路搜索算法求解結果即為列車的實際具有運行條件的路徑，求解過程更為高效。

圖5 路網層級車站進出口的連通圖Fig.5 Entrance and exit connectivity at the railway network level

高速鐵路網為稀疏連通網絡，節點較多，但節點的連通數量較少，因此選取以車站進出口為節點的鄰接表模型，并對鄰接表數據進一步處理和優化，提升算法搜索效率，將區間連通關系合并處理?；谲囌具M出口的高速鐵路網鄰接連通關系描述為：車站A 進出口a1→車站A 進出口a2(→車站B 進出口b1)，以圖5 為例，線路所C 的1 接口鄰接表可表示為C1[C2(A1)，C5(B1)]。實現算法如下。

步驟1：遍歷車站進出口，根據區間上下行方向提取與進站方向(區間結束點)相連的進出口，作為鄰接表的表頭節點元素。

步驟2：遍歷鄰接表的表頭元素，檢索存在拓撲關系且與出站方向(區間起始點)相連的同站進出口，記錄鄰接關系。

步驟3：遍歷各出站方向的車站進出口，檢索得到具有區間拓撲關系的另一個車站進出口(區間結束點)，記錄鄰接關系。

步驟4：算法結束。

通過構建車站物理網絡拓撲生成列車進路表，再由列車進路數據構建基于車站進出口的站內拓撲網絡，結合路網區間等數據構建基于車站進出口的多維度高速鐵路拓撲網，實現車站或車場內線路連通判斷、徑路是否存在同方向到發、徑路搜索結果的站內路徑展示等，支持更精細化的徑路搜索結果。

2 基于A*的高速鐵路網多徑路搜索算法研究

2.1 多維度路徑搜索參數設計

基于車站進出口的多維度路徑包括車站層級連通關系及路網層級連通關系，需要對構建的精細化高速鐵路拓撲網的車站、車場、線路、區間等信息進行統一的編碼設計，涉及車站經緯度、車站車場關系、進路、車站進出口等數據，以滿足路網數據的規范化存儲、路徑表達，以及準確高效計算，便于實現多徑路搜索算法。

（1）車站經緯度數據。定義車站列表V［v1，lon，lat］，分別表示車站編號、經度、緯度。

（2）車站車場關系數據。定義車站vi的車場集合若車站無分場，

（3）車站進路數據。定義車站車場的一條進路j集合為分別表示進路起始信號按鈕、所經道岔(以集合SW表示)、結束信號按鈕、關聯股道。

（4）線路屬性數據。定義線路集合L［li，tp，sv］，分別表示線路編號、線路類型、線路設計速度。

（5）車站進出口數據。定義車站車場的進出口ek集合[e1，e2，…]。

（6）區間屬性數據。定義線路li的區間j集合即區間的起始車站車場的車站進出口為est，結束車站的車站進出口為efn；dir為區間單雙向行車類型；phe(l，t)為區間長度、區間運行時分。

（7）基于車站進出口的鄰接表例如ex存在站內的連通關系ea，通過區間EL與車站車場的車站進出口eb相連。按同方向到發的進出口是否連通可分為，。

2.2 路網分層優化

高速鐵路中間站節點連接關系簡單，數目較多，具有路網拓撲簡化的技術條件，通過對鄰接表模型進行優化，對節點進行分層處理，快速檢索。通過遍歷鄰接表R，提取進出口連接數量大于等于2(len≥2)的節點組成點集合V*，合并節點間區間E及鄰接關系R*，重構組成高層簡化路網G*=(V*，E*，R*)。針對位于底層路網的源vx、匯vy，構建Gx，y進行徑路搜索，構建算法如下。

步驟1：初始化，令Gx，y=G*。

步驟2：檢索源vx的車站進出口的徑路，在底層路網G內按上、下行分別推算至高層路網G*中的車站時截止，得到2 個低層路網，，將其加入Gx，y。

步驟3：檢索匯vy車站進出口的徑路，同理可得到2個低層路網，，將其加入Gx，y。步驟4：算法結束，得到

2.3 基于A*算法的k短路徑路算法

高速鐵路物理網絡節點、邊數目大，樞紐地區網絡連接結構復雜，采用傳統的遍歷算法計算效率較低。A*算法是一種常用的啟發式搜索算法，搜索過程中各節點的目標函數如下，由起始搜索節點至當前節點的計算值、當前節點至結束節點的估值組成。

Nilsson 等人在1968 年證明A*算法的3 個重要性質：若路徑規劃問題存在有效路徑，A*算法必能找到該解路徑；A*算法能夠最有效地利用啟發式，即在使用相同啟發式時，沒有一種搜索算法的搜索空間比A*算法??；A*算法收斂效果與啟發式函數有關，當啟發式函數值h(x)小于等于其實際代價h*(x)時，必能找到最優解路徑；當啟發式函數等于實際代價，可更快速度收斂至最優解。

2.3.1 最短路徑路搜索

啟發函數h(x)需根據具體問題來設置，高速鐵路網徑路邊的權值h*(x) 主要由區間長度[phe(l，t)]確定，顯然以節點之間的直線距離作為啟發函數h(x)，可滿足h(x)

利用標準A*搜索算法，可縮減搜索范圍，最大程度減少無效搜索的時間開銷，提升搜索效率，實現最短徑路的快速搜索，算法詳細流程不再贅述。

2.3.2 多徑路搜索

多徑路搜索可用Dijkstra 算得的最短路作為啟發函數。對于源vx、匯vy的路網Gx，y，以匯vy為起始節點對路網進行Dijkstra 運算，得到路網內任意節點vi至匯vy的最短路徑dis(xi，y)，此時啟發函數h(xi，y)=dis(xi，y)=h*(xi，y)，算法收斂速度快且可得到K短路最優解。

以DRC[vi].[，vi，f，g，h，Vroute，Eroute，Rroute]存儲搜索過程中節點vi的徑路信息于OPEN 或CLOSE列表中，其元素分別表示搜索過程中vi節點的前續父節點、當前節點、f值、g值、h值、所經節點集合、所經邊集合、所經節點連接關系集合?；贏*的多徑路搜索流程圖如圖6所示，算法步驟如下。

圖6 基于A*的多徑路搜索流程圖Fig.6 Flowchart of multi-route search based on A* algorithm

步驟1：對于源vx、匯vy，檢索其是否位于高層路網G*，若節點不滿足，則按2.3 節路網簡化算法構建Gx，y。

步驟2：初始化待擴展節點集合OPEN 列表、已擴展節點集合CLOSE 列表；將起始節點的徑路信息DRC放入OPEN列表中，令k= 0。

步驟3：當k≤K時，若OPEN 列表不為空，轉步驟4，否則表示問題無k個最短路，算法結束；當k>K時，轉步驟7，輸出k短路解。

步驟4：遍歷OPEN 列表的節點vi，提取f值最小的節點記為v*，將v*從OPEN列表中刪除，并放入CLOSE集合中。

步驟5：判斷v*是否為終點，若是則得到問題的一個k短路解，k=k+ 1，轉步驟3；若v*不是終點，則對該節點進行鄰域拓展，得到有關v*的一系列后繼節點vi，若vi∈DRC[v*].[Vroute]，則說明包含環形徑路，不再進行鄰域拓展；對于所有其余vi計算DRC[vi]徑路信息并添加于OPEN 集合(集合中可能存在前續父節點不同的同名vi節點，即k短路下不同徑路搜索過程)。

①標記vi的前續節點v* =DRC[vi].[]。

②計算DRC[vi].[g]=DRC[v*].[g]+e，e為vi與前續節點間路徑的權值；計算DRC[vi].[h]=dis(vi，y)；DRC[vi].[f]=DRC[vi].[g]+DRC[vi].[g]。

③更新vi的節點、邊和連接關系集合，如DRC[vi].[Vroute]=DRC[v*].[Vroute]+vi。

步驟6：完成v*的所有后繼節點vi檢查后，轉步驟3。

步驟7：根據節點的節點、邊和連接關系集合，描述k短路徑解。

3 實例驗證

研究建立了基于車站進出口的多維度高速鐵路拓撲網，包括車站層級拓撲及路網層級拓撲2 部分，下面分別從上述2方面展開實例驗證。車站拓撲方面，樞紐內客運站一般有多條線路銜接，連接關系復雜，研究以一個小型樞紐實例驗證高精度高速鐵路站內拓撲網的準確性，A，B等6個站組成的小型樞紐仿真實例如圖7所示。其中A站銜接有3條線路、上下行共計10個延伸方向，其余車站均為中間站。

圖7 小型樞紐仿真實例Fig.7 Simulation example of small railway hub

根據車站拓撲結構，通過列車進路生成算法、車站進出口拓撲生成算法、路網鄰接表拓撲算法等，計算A 站與B，C 等站的連通性，并與基于車站節點連通關系的中觀路網徑路求解進行對比分析，不同路網精度下徑路搜索結果對比如表2 所示。通過對比分析可得知，基于車站進出口的高精度徑路搜索在車站層級是可行、有效的，且徑路結果展示、車站內線路連通性判定、車站內同方向到發判定等方面精度更高。

表2 不同路網精度下徑路搜索結果對比Tab.2 Comparison of route search results under different precision of railway networks

以截至2022 年底我國高速鐵路網為例，構建高精度高速鐵路網連通拓撲圖，對北京南高速場—上海虹橋高速場的列車徑路進行分析，在不考慮同側到發折返作業的情況下，北京南高速場至上海虹橋高速場前5 條最短路如表3 所示，北京南高速場至上海虹橋高速場前5條最短路示意圖如圖8所示，徑路聯絡線信息不在表中展示。由結果可看出最短路全程為京滬高速鐵路(北京南—上海虹橋)；次短路在德州東與濟南西間走石濟客專(德州東—齊河)線路；徐鹽(徐州東—鹽城)、連鎮客專(董集—丹徒)方向無可行k短路，因為徑路僅能通達至上海虹橋綜合場。高精度路網下最短路求解耗時300 ms左右，k短路求解時間受OD及k值影響有一定波動，可以實現高效、準確地完成精細化的路網徑路搜索。

圖8 北京南高速場至上海虹橋高速場前5條最短路示意圖Fig.8 First five shortest routes from Beijingnan high speed railway yard to Shanghai Hongqiao high speed railway yard

表3 北京南高速場至上海虹橋高速場前5條最短路Tab.3 First five shortest routes from Beijingnan high speed railway yard to Shanghai Hongqiao high speed railway yard

4 結束語

研究針對大規模復雜高速鐵路網，考慮線路區間信息、站場結構以及站內進路信息，構建基于車站進出口的復雜拓撲網絡及多維度路徑信息表示方法，設計基于啟發式A*算法的考慮精細化站場結構的多徑路搜索算法。實例驗證表明，該方法可以求解復雜路網條件下高速鐵路列車運行精細化徑路，為高速鐵路列車運輸組織工作提供技術支持。