高速鐵路網(wǎng)列車運(yùn)行徑路精細(xì)化搜索算法研究

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

（1.中國鐵道科學(xué)研究院集團(tuán)有限公司 中國鐵路列車運(yùn)行圖技術(shù)中心，北京 100081；2.中國鐵道科學(xué)研究院集團(tuán)有限公司 運(yùn)輸及經(jīng)濟(jì)研究所，北京 100081；3.中國國家鐵路集團(tuán)有限公司運(yùn)輸部，北京 100844）

0 引言

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

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

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

上述研究聚焦路網(wǎng)構(gòu)建、徑路搜索等方面，主要以車站或車場為路網(wǎng)節(jié)點(diǎn)，未考慮車站的結(jié)構(gòu)和進(jìn)路信息，在樞紐等連通關(guān)系復(fù)雜的地區(qū)徑路搜索更容易產(chǎn)生誤差，徑路搜索精細(xì)化程度有待提升。本研究針對大規(guī)模復(fù)雜的高速鐵路網(wǎng)，重點(diǎn)考慮詳細(xì)的車站站場結(jié)構(gòu)，并構(gòu)建區(qū)間屬性信息，提出全國高速鐵路網(wǎng)的多徑路精細(xì)化搜索算法。

1 精細(xì)化高速鐵路拓?fù)渚W(wǎng)構(gòu)建方法

高速鐵路網(wǎng)指有動車組列車開行的高速鐵路、城際鐵路、高普混行線路。高速鐵路拓?fù)渚W(wǎng)根據(jù)構(gòu)建精細(xì)程度的不同，可分為宏觀、中觀、微觀3 個(gè)層級，其復(fù)雜程度有較大差距，不同精度層級下鐵路網(wǎng)構(gòu)建涉及數(shù)據(jù)如圖1 所示。宏觀和中觀層面下通過車站節(jié)點(diǎn)的線路默認(rèn)連通，車站節(jié)點(diǎn)內(nèi)線路連通關(guān)系精度不足；微觀路網(wǎng)層面下可真實(shí)反映路網(wǎng)站間、站內(nèi)實(shí)際連通拓?fù)浣Y(jié)構(gòu)。

圖1 不同精度層級下鐵路網(wǎng)構(gòu)建涉及數(shù)據(jù)Fig.1 Railway network construction at different precision levels

為支持列車走行徑路的全過程、精細(xì)化研究，研究建立基于車站進(jìn)出口的多維度路徑信息表示方法，包括車站內(nèi)進(jìn)路關(guān)系及區(qū)間連通關(guān)系：在車站物理網(wǎng)絡(luò)拓?fù)涞幕A(chǔ)上，構(gòu)建車站進(jìn)路數(shù)據(jù)，并以車站進(jìn)路數(shù)據(jù)為基礎(chǔ)構(gòu)建車站內(nèi)進(jìn)站信號節(jié)點(diǎn)(車站進(jìn)出口)間的連通關(guān)系，以線路區(qū)間數(shù)據(jù)為基礎(chǔ)構(gòu)建不同車站間進(jìn)出口的連通關(guān)系，最后實(shí)現(xiàn)路網(wǎng)層的連通拓?fù)錁?gòu)建。上述路徑信息對基礎(chǔ)路網(wǎng)數(shù)據(jù)的準(zhǔn)確性和規(guī)范性有很高要求，下面從車站、線路區(qū)間實(shí)際物理拓?fù)浣Y(jié)構(gòu)出發(fā)，研究高速鐵路網(wǎng)拓?fù)錁?gòu)建和徑路數(shù)據(jù)表達(dá)。

1.1 車站層級連通拓?fù)錁?gòu)建

1.1.1 車站物理網(wǎng)絡(luò)拓?fù)錁?gòu)建方法

車站的物理網(wǎng)絡(luò)拓?fù)涫擒囌具M(jìn)路的數(shù)據(jù)支撐，構(gòu)建車站拓?fù)鋾r(shí)應(yīng)以車場為一個(gè)獨(dú)立的車站單元，使得進(jìn)路只涉及相應(yīng)車場。高速鐵路車站站場結(jié)構(gòu)主要由道岔、信號機(jī)、軌道區(qū)段等設(shè)備構(gòu)成，車站站型示意圖如圖2 所示，各類設(shè)備關(guān)鍵位置坐標(biāo)由圖元控制點(diǎn)確定(圖中紅點(diǎn))，可通過對比關(guān)鍵位置坐標(biāo)確定各設(shè)備的左側(cè)和右側(cè)相鄰的設(shè)備類型及名稱[16]。

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

通過對設(shè)備進(jìn)行關(guān)聯(lián)，便可構(gòu)造車站物理網(wǎng)絡(luò)拓?fù)?，鐵路車站物理網(wǎng)絡(luò)拓?fù)鋱D如圖3 所示。各設(shè)備存儲有本設(shè)備特征數(shù)據(jù)及相鄰設(shè)備連接關(guān)系數(shù)據(jù)，研究將道岔圖元拆分為3 個(gè)子節(jié)點(diǎn)與2 條連接邊，另外將軌道區(qū)段、信號機(jī)圖元拆分為2 個(gè)子節(jié)點(diǎn)和1 條連接邊，設(shè)備間的連接關(guān)系由不同圖元的子節(jié)點(diǎn)連接的邊表示，構(gòu)建車站拓?fù)錈o向圖并根據(jù)圖元子節(jié)點(diǎn)生成鄰接矩陣。圖3 中車站進(jìn)出口(ENT)設(shè)置于站內(nèi)最外側(cè)的進(jìn)站信號機(jī)，與路網(wǎng)區(qū)間拓?fù)湓叵噙B，實(shí)現(xiàn)車站與區(qū)間的拓?fù)溥B接。

圖3 鐵路車站物理網(wǎng)絡(luò)拓?fù)鋱DFig.3 Physical network topology of train stations

1.1.2 列車進(jìn)路數(shù)據(jù)構(gòu)建方法

為構(gòu)建精細(xì)化列車徑路表達(dá)，徑路在各車站內(nèi)的走行過程以基于車站(車場)拓?fù)浣Y(jié)構(gòu)的列車進(jìn)路數(shù)據(jù)描述。進(jìn)路是由若干個(gè)信號機(jī)、道岔及道岔位置、軌道區(qū)段組成的列車在車站內(nèi)行車時(shí)所經(jīng)過的通路，并可由始端按鈕和終端按鈕決定進(jìn)路的相關(guān)信息[17]。根據(jù)按鈕使用規(guī)則[18]，即可確定車站內(nèi)可組成基本進(jìn)路的始終端信號機(jī)組合，進(jìn)而生成車站內(nèi)的列車基本進(jìn)路數(shù)據(jù)?；趫D2 車站站型，根據(jù)進(jìn)路按鈕組合XLA、S3LA(LA 為按鈕標(biāo)識)，即可確定一個(gè)簡單的接車進(jìn)路(X，1，5，S3，3G)。

列車進(jìn)路可作為車站進(jìn)出口連通拓?fù)涞臄?shù)據(jù)支撐，同時(shí)也可作為徑路搜索下的列車站內(nèi)走行可視化展示，根據(jù)上文構(gòu)建車站物理網(wǎng)絡(luò)拓?fù)?，參考?lián)鎖車站聯(lián)鎖圖表編制原則[19]，通過采用遍歷算法生成車站的列車進(jìn)路數(shù)據(jù)，算法簡述如下。

步驟1：遍歷車站的列車信號機(jī)，作為進(jìn)路起始信號按鈕，依次在車站物理網(wǎng)絡(luò)拓?fù)溧徑泳仃囍羞M(jìn)行檢索。

步驟2：查找并遍歷與起始信號按鈕相連的拓?fù)湓夭⑦f推至信號類型的拓?fù)湓?，若該信號可作為終端按鈕，遍歷并記錄經(jīng)由不同的所有進(jìn)路道岔信息、終端信號按鈕及關(guān)聯(lián)股道；若不可作為終端按鈕，則繼續(xù)遞推至下一個(gè)信號或直到無解情況。

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

步驟4：算法結(jié)束。

1.1.3 車站進(jìn)出口連通拓?fù)錁?gòu)建方法

基于列車進(jìn)路數(shù)據(jù)描述車站進(jìn)出口間的拓?fù)潢P(guān)系，即構(gòu)建車站層級連通拓?fù)洹；趫D2 車站站型，根據(jù)存在X-S3(3G)和X3(3G)-SN的列車進(jìn)路，可構(gòu)建車站進(jìn)出口ENT1(X)-ENT3(SN)的連通關(guān)系。

考慮車站車場和線路所等車站拓?fù)浣Y(jié)構(gòu)，按進(jìn)出口的位置及連通關(guān)系主要分為以下幾類，車站層級進(jìn)出口連通圖如圖4所示，①→②可表示不過股道轉(zhuǎn)場路徑；③→④可表示過股道的轉(zhuǎn)場路徑；⑤→⑥可表示過股道的通過路徑；⑤→⑦可表示同側(cè)到發(fā)的折返路徑；⑩→⑨可表示不過股道的線路所通過路徑。綜合上述各類情況可知，若車場間有列車徑路行駛條件，且無場間進(jìn)站信號，可于轉(zhuǎn)場道岔處設(shè)置虛擬信號，便于生成轉(zhuǎn)場進(jìn)路；不經(jīng)過股道的進(jìn)出口間的路徑可由一條進(jìn)路或多條分段進(jìn)路表示，過股道的進(jìn)出口間的路徑可由與該股道相關(guān)的2 條進(jìn)路或多條分段進(jìn)路表示，綜合考慮同側(cè)到發(fā)的折返路徑等問題，設(shè)計(jì)基于列車進(jìn)路數(shù)據(jù)的車站進(jìn)出口拓?fù)鋱D算法實(shí)現(xiàn)過程如下。

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

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

步驟2：記錄各進(jìn)路的關(guān)聯(lián)股道于集合V1，轉(zhuǎn)步驟4；若進(jìn)路無關(guān)聯(lián)股道，將進(jìn)路終端按鈕信號記錄于集合V2，轉(zhuǎn)步驟3。

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

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

步驟5：算法結(jié)束。

1.2 路網(wǎng)層級連通拓?fù)錁?gòu)建及徑路表達(dá)

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

圖5 路網(wǎng)層級車站進(jìn)出口的連通圖Fig.5 Entrance and exit connectivity at the railway network level

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

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

步驟2：遍歷鄰接表的表頭元素，檢索存在拓?fù)潢P(guān)系且與出站方向(區(qū)間起始點(diǎn))相連的同站進(jìn)出口，記錄鄰接關(guān)系。

步驟3：遍歷各出站方向的車站進(jìn)出口，檢索得到具有區(qū)間拓?fù)潢P(guān)系的另一個(gè)車站進(jìn)出口(區(qū)間結(jié)束點(diǎn))，記錄鄰接關(guān)系。

步驟4：算法結(jié)束。

通過構(gòu)建車站物理網(wǎng)絡(luò)拓?fù)渖闪熊囘M(jìn)路表，再由列車進(jìn)路數(shù)據(jù)構(gòu)建基于車站進(jìn)出口的站內(nèi)拓?fù)渚W(wǎng)絡(luò)，結(jié)合路網(wǎng)區(qū)間等數(shù)據(jù)構(gòu)建基于車站進(jìn)出口的多維度高速鐵路拓?fù)渚W(wǎng)，實(shí)現(xiàn)車站或車場內(nèi)線路連通判斷、徑路是否存在同方向到發(fā)、徑路搜索結(jié)果的站內(nèi)路徑展示等，支持更精細(xì)化的徑路搜索結(jié)果。

2 基于A*的高速鐵路網(wǎng)多徑路搜索算法研究

2.1 多維度路徑搜索參數(shù)設(shè)計(jì)

基于車站進(jìn)出口的多維度路徑包括車站層級連通關(guān)系及路網(wǎng)層級連通關(guān)系，需要對構(gòu)建的精細(xì)化高速鐵路拓?fù)渚W(wǎng)的車站、車場、線路、區(qū)間等信息進(jìn)行統(tǒng)一的編碼設(shè)計(jì)，涉及車站經(jīng)緯度、車站車場關(guān)系、進(jìn)路、車站進(jìn)出口等數(shù)據(jù)，以滿足路網(wǎng)數(shù)據(jù)的規(guī)范化存儲、路徑表達(dá)，以及準(zhǔn)確高效計(jì)算，便于實(shí)現(xiàn)多徑路搜索算法。

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

（2）車站車場關(guān)系數(shù)據(jù)。定義車站vi的車場集合若車站無分場，

（3）車站進(jìn)路數(shù)據(jù)。定義車站車場的一條進(jìn)路j集合為分別表示進(jìn)路起始信號按鈕、所經(jīng)道岔(以集合SW表示)、結(jié)束信號按鈕、關(guān)聯(lián)股道。

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

（5）車站進(jìn)出口數(shù)據(jù)。定義車站車場的進(jìn)出口ek集合[e1，e2，…]。

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

（7）基于車站進(jìn)出口的鄰接表例如ex存在站內(nèi)的連通關(guān)系ea，通過區(qū)間EL與車站車場的車站進(jìn)出口eb相連。按同方向到發(fā)的進(jìn)出口是否連通可分為，。

2.2 路網(wǎng)分層優(yōu)化

高速鐵路中間站節(jié)點(diǎn)連接關(guān)系簡單，數(shù)目較多，具有路網(wǎng)拓?fù)浜喕募夹g(shù)條件，通過對鄰接表模型進(jìn)行優(yōu)化，對節(jié)點(diǎn)進(jìn)行分層處理，快速檢索。通過遍歷鄰接表R，提取進(jìn)出口連接數(shù)量大于等于2(len≥2)的節(jié)點(diǎn)組成點(diǎn)集合V*，合并節(jié)點(diǎn)間區(qū)間E及鄰接關(guān)系R*，重構(gòu)組成高層簡化路網(wǎng)G*=(V*，E*，R*)。針對位于底層路網(wǎng)的源vx、匯vy，構(gòu)建Gx，y進(jìn)行徑路搜索，構(gòu)建算法如下。

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

步驟2：檢索源vx的車站進(jìn)出口的徑路，在底層路網(wǎng)G內(nèi)按上、下行分別推算至高層路網(wǎng)G*中的車站時(shí)截止，得到2 個(gè)低層路網(wǎng)，，將其加入Gx，y。

步驟3：檢索匯vy車站進(jìn)出口的徑路，同理可得到2個(gè)低層路網(wǎng)，，將其加入Gx，y。步驟4：算法結(jié)束，得到

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

高速鐵路物理網(wǎng)絡(luò)節(jié)點(diǎn)、邊數(shù)目大，樞紐地區(qū)網(wǎng)絡(luò)連接結(jié)構(gòu)復(fù)雜，采用傳統(tǒng)的遍歷算法計(jì)算效率較低。A*算法是一種常用的啟發(fā)式搜索算法，搜索過程中各節(jié)點(diǎn)的目標(biāo)函數(shù)如下，由起始搜索節(jié)點(diǎn)至當(dāng)前節(jié)點(diǎn)的計(jì)算值、當(dāng)前節(jié)點(diǎn)至結(jié)束節(jié)點(diǎn)的估值組成。

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

2.3.1 最短路徑路搜索

啟發(fā)函數(shù)h(x)需根據(jù)具體問題來設(shè)置，高速鐵路網(wǎng)徑路邊的權(quán)值h*(x) 主要由區(qū)間長度[phe(l，t)]確定，顯然以節(jié)點(diǎn)之間的直線距離作為啟發(fā)函數(shù)h(x)，可滿足h(x)

利用標(biāo)準(zhǔn)A*搜索算法，可縮減搜索范圍，最大程度減少無效搜索的時(shí)間開銷，提升搜索效率，實(shí)現(xiàn)最短徑路的快速搜索，算法詳細(xì)流程不再贅述。

2.3.2 多徑路搜索

多徑路搜索可用Dijkstra 算得的最短路作為啟發(fā)函數(shù)。對于源vx、匯vy的路網(wǎng)Gx，y，以匯vy為起始節(jié)點(diǎn)對路網(wǎng)進(jìn)行Dijkstra 運(yùn)算，得到路網(wǎng)內(nèi)任意節(jié)點(diǎn)vi至匯vy的最短路徑dis(xi，y)，此時(shí)啟發(fā)函數(shù)h(xi，y)=dis(xi，y)=h*(xi，y)，算法收斂速度快且可得到K短路最優(yōu)解。

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

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

步驟1：對于源vx、匯vy，檢索其是否位于高層路網(wǎng)G*，若節(jié)點(diǎn)不滿足，則按2.3 節(jié)路網(wǎng)簡化算法構(gòu)建Gx，y。

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

步驟3：當(dāng)k≤K時(shí)，若OPEN 列表不為空，轉(zhuǎn)步驟4，否則表示問題無k個(gè)最短路，算法結(jié)束；當(dāng)k>K時(shí)，轉(zhuǎn)步驟7，輸出k短路解。

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

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

①標(biāo)記vi的前續(xù)節(jié)點(diǎn)v* =DRC[vi].[]。

②計(jì)算DRC[vi].[g]=DRC[v*].[g]+e，e為vi與前續(xù)節(jié)點(diǎn)間路徑的權(quán)值；計(jì)算DRC[vi].[h]=dis(vi，y)；DRC[vi].[f]=DRC[vi].[g]+DRC[vi].[g]。

③更新vi的節(jié)點(diǎn)、邊和連接關(guān)系集合，如DRC[vi].[Vroute]=DRC[v*].[Vroute]+vi。

步驟6：完成v*的所有后繼節(jié)點(diǎn)vi檢查后，轉(zhuǎn)步驟3。

步驟7：根據(jù)節(jié)點(diǎn)的節(jié)點(diǎn)、邊和連接關(guān)系集合，描述k短路徑解。

3 實(shí)例驗(yàn)證

研究建立了基于車站進(jìn)出口的多維度高速鐵路拓?fù)渚W(wǎng)，包括車站層級拓?fù)浼奥肪W(wǎng)層級拓?fù)? 部分，下面分別從上述2方面展開實(shí)例驗(yàn)證。車站拓?fù)浞矫妫瑯屑~內(nèi)客運(yùn)站一般有多條線路銜接，連接關(guān)系復(fù)雜，研究以一個(gè)小型樞紐實(shí)例驗(yàn)證高精度高速鐵路站內(nèi)拓?fù)渚W(wǎng)的準(zhǔn)確性，A，B等6個(gè)站組成的小型樞紐仿真實(shí)例如圖7所示。其中A站銜接有3條線路、上下行共計(jì)10個(gè)延伸方向，其余車站均為中間站。

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

根據(jù)車站拓?fù)浣Y(jié)構(gòu)，通過列車進(jìn)路生成算法、車站進(jìn)出口拓?fù)渖伤惴?、路網(wǎng)鄰接表拓?fù)渌惴ǖ龋?jì)算A 站與B，C 等站的連通性，并與基于車站節(jié)點(diǎn)連通關(guān)系的中觀路網(wǎng)徑路求解進(jìn)行對比分析，不同路網(wǎng)精度下徑路搜索結(jié)果對比如表2 所示。通過對比分析可得知，基于車站進(jìn)出口的高精度徑路搜索在車站層級是可行、有效的，且徑路結(jié)果展示、車站內(nèi)線路連通性判定、車站內(nèi)同方向到發(fā)判定等方面精度更高。

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

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

圖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 結(jié)束語

研究針對大規(guī)模復(fù)雜高速鐵路網(wǎng)，考慮線路區(qū)間信息、站場結(jié)構(gòu)以及站內(nèi)進(jìn)路信息，構(gòu)建基于車站進(jìn)出口的復(fù)雜拓?fù)渚W(wǎng)絡(luò)及多維度路徑信息表示方法，設(shè)計(jì)基于啟發(fā)式A*算法的考慮精細(xì)化站場結(jié)構(gòu)的多徑路搜索算法。實(shí)例驗(yàn)證表明，該方法可以求解復(fù)雜路網(wǎng)條件下高速鐵路列車運(yùn)行精細(xì)化徑路，為高速鐵路列車運(yùn)輸組織工作提供技術(shù)支持。