復雜建設環境下基于Hybrid A*算法的鐵路平面線形綠色優化設計

張天龍 何 慶 高 巖 高天賜 李子涵

（西南交通大學，成都 610031）

鐵路選線是一個復雜的系統工程，決定工程項目的投資成本、難易程度和安全風險等因素［1］。針對鐵路和公路線形優化問題，近年來國內外學者開展了大量的研究工作，引入了多種算法，包括：梯度投影法［2］、遺傳算法［3］、動態規劃算法［4］、粒子群算法［5］、線性規劃算法［6］等。以上絕大部分算法需預先給定控制點的個數以及初始分布情況，隨后以平面交點的位置、曲線半徑等作為變量，以滿足約束條件下的建設成本最小為優化目標，開展逐步優化。值得注意的是，線路的控制點的初始分布對于最終優化結果有著重要影響，設置合理的初始控制點對于設計人員的設計經驗有著較高要求。對于復雜環境條件下的設計問題，人工往往難以給出合理的初始控制點分布，使得最終優化結果不理想。針對上述問題，學者們開始嘗試引入不需要設置初始控制點的先進算法，包括雙向距離變換法［7］、深度強化學習算法［8］、離散網格算法［9］等。然而，以上算法基本采用的是圓曲線-直線協同優化，考慮到模型的復雜性，難以在算法中引入緩和曲線，從而進行符合實際線形規范的幾何協同優化。

此外，隨著近年來“綠色鐵路”概念的提出，在原有的復雜優化問題下，引入“綠色”“低碳”等因素并提出了新的要求。本文提出了一種基于改進自動駕駛汽車導航算法的順序探索算法——Hybrid A*算 法［10］，能夠在未給定初始控制點信息的前提下，考慮鐵路線形的實際幾何約束，同時將環境生態成本與建設成本融合在內，開展自動化求解擬全局最優的鐵路平面設計線形。

1 改進Hybrid A*算法模型

改進Hybrid A*算法流程如圖1所示，具體可分為數據準備階段和迭代優化階段。

圖1 改進Hybrid A*算法實現流程圖

1.1 幾何參數變量表征

在鐵路線形平面優化過程中，常采用的幾何變量的參數形式如圖2（a）中所示，可用［（xi，yi，Ri，ωi），（xi+1，yi+1，Ri+1，ωi+1），...］來確定一條線路的幾何形位。其中每個水平交點包含4個變量：交點橫坐標x，縱坐標y，圓曲線半徑R以及圓曲線對應的圓心角ω。通過優化各個交點相應的參數，實現最優化目標的效果。本文提出的改進Hybrid A*算法采用的幾何變量參數形式如圖2（b）所示，用［（xi，yi，θi，Ri，li，Ti），（xi+1，yi+1，θi+1，Ri+1，li+1，Ti+1），…］來確定一條線路的幾何形位，其中每個節點上包含6個變量：x，y分別表示節點的橫、縱坐標；θ表示該節點處線路方向角；R表示節點對應的圓曲線半徑，其中直線段對應的半徑為None，緩和曲線半徑對應的半徑為相接圓的半徑；l表示該節點開始到下一節點的長度；T表示線類型，用數字‘1’表征圓曲線，‘0’表征圓曲線，‘-1’表征直-圓緩和曲線，‘-2’表征圓-直緩和曲線。

圖2 線路幾何參數表征方法圖

本文采用圖2（b）中的表征方法，盡管對應的優化變量相較于圖2（a）變多，但其能直接給出里程等信息，并且搜索過程能夠從起點逐步過渡到終點，實現漸近式優化。該方法各個節點間的耦合關系相較于圖2（a）中更小，更易于優化模型的解耦，提升優化效果。

1.2 模型幾何約束與改進Hybrid A*探索

為了保障優化算法的最終精度，往往采用較小的探索步長開展探索工作，較小的探索步長意味著在整個優化空間內考慮更多的線型組合，從中選出的最優組合將具備更好的效果。本文采用的探索方式為定長探索，即除緩和曲線外，直線段和圓曲線都采用相同的單位步長。此外，在改進Hybrid A*算法的探索過程中，還需要考慮線形的幾何約束。本文提出的改進Hybrid A*算法中，考慮的幾何約束有：最短直線段長度（LSmin）約束，如圖3（b）所示；最短圓曲線長度（Lcmin）約束，如圖3（e）所示；‘C’形曲線約束，如圖3（a）、圖3（d）所示；最大曲線半徑；最小曲線半徑；圓曲線最大偏角（防止回頭曲線）。

圖3 考慮幾何約束的Hybrid A*探索圖

在滿足約束的條件下，可探索的方式為：直線節點的下一個節點可以為直線，也可以為多個方向的定長緩和曲線，緩和曲線對應的相接圓半徑R由式（1）確定。圓曲線節點下一個節點可同為圓曲線，也可為緩和曲線，用以向直線段過渡，如圖3（f）所示。

式中：Rmin、Rmax——最小曲線半徑和最大曲線半徑（m）；

1.3 順序探索流程

原始Hybrid A*算法是基于傳統網格順序探索算法的改進和延伸。網格順序探索算法基于動態規劃的思想，將已探索的區域信息加以存儲，在新的探索步驟中將不再考慮已探索過的區域，大幅降低了算法的空間復雜度，使之能夠進行整個優化空間的遍歷搜索，從中確定接近最優的線路結果。

典型的離散網格探索算法——Dijkstra算法［11］被廣泛運用于各領域中。Dijkstra算法順序探索最短路徑的流程如圖4所示，該算法從起點出發向四周網格探索，探索過的網格將以列表的形式存儲，正在探索的末端節點用樹結構存儲，樹頂為當前總成本最小的探索節點。已探索的區域和正在探索的區域網格存儲時，包含當前節點信息和父節點（上個節點）信息。這樣一來，一旦探索節點到達終點，便可往前回溯到起點，并且該路徑為最優路徑。

圖4 傳統離散網格探索流程圖

NE——探索方向總數（圖3（c）中NE為5）。

原始Hybrid A*算法將離散網格探索算法進行延伸，根據給定的起點坐標和方向，按一定步長進行直線和圓曲線探索，每個探索節點將歸入所屬的離散網格中，如圖5（a）所示。然而，與傳統離散網格探索算法的不同之處在于：實際的網格除了平面x，y坐標，還包含節點的角度坐標θ。為了利用動態規劃降低模型求解復雜度，并存儲已探索的區域，區分未探索的區域，實際采用了兩套坐標系統：實際幾何連續的坐標系和動態規劃離散網格坐標系。前者用于獲得實際的線路參數信息，后者用于降低模型復雜度。例如，實際節點坐標為（1.1，2.7，31°），若采用的坐標分辨率為（1，1，5°）進行離散化，記錄用于動態規劃求解的節點坐標為（1，2，6），已探索過的離散網格節點坐標將不納入新的探索中。

圖5 原始Hybrid A*算法網格探索流程圖

此外，為了提升探索效率，原始Hybrid A*算法將傳統Dijkstra算法作為輔助手段，先利用Dijkstra算法從終點到起點進行一次全局探索，從而獲得每個節點到終點的大致距離，并將此作為啟發式成本歸入算法模型中，如圖5（b）所示。其實現方法為在樹結構存儲正在探索區域時，錄入的成本為實際成本與啟發式成本的總和，每次選出的最優節點將快速向終點靠近。值得注意的是，啟發式成本項在歸入模型時，需乘以一個放大系數H-cost。采用改進的Hybrid A*算法時，在上述流程中還需要按1.2小節中的給出的幾何約束進行限制性探索。

1.4 最終路徑生成與迭代終止條件

在Hybrid A*算法探索過程中，隨著順序探索的進行，探索的節點逐漸向終點方向靠近。考慮到終點處不僅僅包含橫縱坐標的約束，同時也具有角度方向的約束，為此，需要一些特殊的手段將已探索的部分與終點進行最后的連接。原始的Hybrid A*算法采用的方式為利用R-S曲線連接已探索的區域和終點，然而，R-S曲線中允許出現反向曲線，符合車輛行駛約束，但與鐵路線形設計約束不符。為此，本文提出了一種符合鐵路線形設計的連接方法，如圖6所示。圖中，RL為某一約定半徑，表示距離終點一定半徑內的區域（連接區域）允許進行終點連接，最先進入連接區域的點為探索區域中最優的節點。連接的方式為：先基于最優節點方向和終點方向，結合半徑R確定切點，R的取值與探索時的RE相同，每一個R都需要進行連接計算，判斷幾何約束并在符合約束的結果中取最優；待切點求得后，依據緩和曲線長度和切點位置重新計算得到新的R'，隨即確定整條線路的線型。

圖6 Hybrid A*算法終點連接方式圖

值得注意的是，盡管最先進入連接區域的是探索區域中的最優節點，但其與終點的連接部分也包含一定的成本，不一定能夠保證探索區域中的成本與連接區域中的成本之和是最優結果。為此，本文提出了一種較為簡單有效地方式來解決這一問題：將前n個進入連接區域的節點與終點依次進行連接計算，取其中的最優結果作為線路的線型輸出，有效地提升了算法的穩定性。

1.5 智能選線模型綜合優化目標

上述小節中的提到的原始Hybrid A*算法和改進Hybrid A*算法的優化目標均為路徑最短，在平原地區進行鐵路平面線形設計中，若考慮線路單位長度造價一致，該優化目標對應于建設成本最低。然而，實際情況下，計算綜合成本還需要考慮沿線征地、拆遷和生態破壞等成本，對于一條設定的水平線路（HA），實際綜合成本由式（2）確定。在改進Hybrid A*算法中，拓展性地將式中后兩項成本通過離散網格方式融入線路成本中，方式與啟發式成本的融入方式一致。

式中：TC——綜合成本；

CL——線路長度相關的建設成本；

CN——沿線用地相關成本；

CE——沿線生態環境成本。

本文考慮的生態成本指標為歸一化植被指數NDVI，為了量化該指標，采用加權的方式簡化考慮該成本：即鐵路線路每100 m長度的建設成本設為單位1，NDVI相關的生態成本在此基礎上進行比例折減，系數為α，如式（3）所示。

2 案例測試

選用的測試案例為華東某地區的衛星影像，影像的尺寸為38.6 km×19.5 km。利用原始衛星影像，經波譜分析得到影像區域范圍內的歸一化植被指數NDVI，NDVI值越大，表示該處植被越發育。此外，利用衛星影像和其他補充資料，還可以得到該影像區域內各類保護區的位置，鐵路線路設計時需要繞避保護區。保護區主要有兩類，分別為綠色生態保護區和水資源生態保護區；NDVI圖的像素精度為0.1 km× 0.1 km。NDVI的值實際介于-1到1之間，此案例中，為了計算方便，對NDVI值進行了歸一化處理，將-1至1歸一化到0至1之間。

此案例中，在采用改進Hybrid A*算法求解鐵路最優線路時，優化目標只考慮式（2）中的CL和CE，使用的平面幾何約束參數有：最小曲線半徑4 000 m；最大曲線半徑12 000 m；緩和曲線長度200 m；最短圓曲線長度200 m；最短夾直線長度200 m；最大圓曲線偏角180°。使用的算法模型參數有：x，y，θ的分辨率分別為100 m，100 m，0.1°；每個節點向前探索時方向數為20，即對應19組不同的圓半徑；啟發式成本的放大系數H-cost取0.95；鐵路線路每100 m長度的建設成本設為單位1，NDVI相關的生態成本在此基礎上進行比例折減，系數為α；在連接區域內取前n=10個最優節點中的最優解作為最終輸出結果。將影像左下角的點定義為坐標原點，正東和正北方向分別為x軸和y軸的正向，線路的起點在動態規劃離散坐標系內的平面坐標系內坐標為（30，20），角度為0°（正東方向），三維離散坐標為（30，20，0）；線路的終點在動態規劃離散坐標系內的平面坐標系內坐標為（370，170），角度為40°（順時針）。

在不同的α參數下，改進Hybrid A*算法求解得到的最后線路也不同，在α分別等于0，0.01和0.1時求解得到的結果如表1所示，分別對應于圖7（a）、圖7（b）和圖7（c）。由表1可知，改進Hybrid A*算法能夠自動控制迭代次數，給出不同數量圓曲線段數的優化線路結果。在α=0.01時，線路總長度為384.51單位，相較于α= 0.1時的392.21單位小，造成此差異的原因之一是不同的α將導致單步探索的成本變化，而優化過程中選取的最優路線是控制總成本最低。由圖7可知，改進Hybrid A*選出的路線接近最短路徑，與設計目的相符。從表1還可以看出，進行上萬次的探索，程序的實際運行時間都在10 s以內。相較于人工選線，大幅提升了計算效率，并且由于人工優化線形難以考慮過多的水平交點個數，優化結果也相較于算法優化效果差。

表1 改進Hybrid A*算法求解最優成本線路結果表

圖7 改進Hybrid A*算法求解最優成本線路結果圖

3 結束語

本文引入了目前前沿的車輛無人駕駛導航算法Hybrid A*算法，針對鐵路選線問題，嵌入了各類幾何約束，提出了新的終點連接方法和迭代終止策略，并在算法中融入了離散信息疊加模型。將改進Hybrid A*算法運用到鐵路綠色選線案例時，結果表明，相較于人工優化，該方法能夠自動、高效地求解出接近全局最低成本、符合幾何約束條件的鐵路線路，對于指導實際線路設計工作，具有較好的參考價值。

本文將生態環境指標通過加權的形式融合在建設成本中，采用的是單目標優化模型。在將來的研究中，需要引入多目標優化理論進一步提升模型的優化能力。此外，本文僅考慮了鐵路線路的平面優化。對于復雜山區的鐵路線路優化問題，還需要進一步將算法拓展到三維。