復(fù)雜建設(shè)環(huán)境下基于Hybrid A*算法的鐵路平面線形綠色優(yōu)化設(shè)計

張?zhí)忑?何 慶 高 巖 高天賜 李子涵

（西南交通大學(xué)，成都 610031）

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

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

1 改進(jìn)Hybrid A*算法模型

改進(jìn)Hybrid A*算法流程如圖1所示，具體可分為數(shù)據(jù)準(zhǔn)備階段和迭代優(yōu)化階段。

圖1 改進(jìn)Hybrid A*算法實現(xiàn)流程圖

1.1 幾何參數(shù)變量表征

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

圖2 線路幾何參數(shù)表征方法圖

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

1.2 模型幾何約束與改進(jìn)Hybrid A*探索

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

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

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

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

1.3 順序探索流程

原始Hybrid A*算法是基于傳統(tǒng)網(wǎng)格順序探索算法的改進(jìn)和延伸。網(wǎng)格順序探索算法基于動態(tài)規(guī)劃的思想，將已探索的區(qū)域信息加以存儲，在新的探索步驟中將不再考慮已探索過的區(qū)域，大幅降低了算法的空間復(fù)雜度，使之能夠進(jìn)行整個優(yōu)化空間的遍歷搜索，從中確定接近最優(yōu)的線路結(jié)果。

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

圖4 傳統(tǒng)離散網(wǎng)格探索流程圖

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

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

圖5 原始Hybrid A*算法網(wǎng)格探索流程圖

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

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

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

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

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

1.5 智能選線模型綜合優(yōu)化目標(biāo)

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

式中：TC——綜合成本；

CL——線路長度相關(guān)的建設(shè)成本；

CN——沿線用地相關(guān)成本；

CE——沿線生態(tài)環(huán)境成本。

本文考慮的生態(tài)成本指標(biāo)為歸一化植被指數(shù)NDVI，為了量化該指標(biāo)，采用加權(quán)的方式簡化考慮該成本：即鐵路線路每100 m長度的建設(shè)成本設(shè)為單位1，NDVI相關(guān)的生態(tài)成本在此基礎(chǔ)上進(jìn)行比例折減，系數(shù)為α，如式（3）所示。

2 案例測試

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

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

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

表1 改進(jìn)Hybrid A*算法求解最優(yōu)成本線路結(jié)果表

圖7 改進(jìn)Hybrid A*算法求解最優(yōu)成本線路結(jié)果圖

3 結(jié)束語

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

本文將生態(tài)環(huán)境指標(biāo)通過加權(quán)的形式融合在建設(shè)成本中，采用的是單目標(biāo)優(yōu)化模型。在將來的研究中，需要引入多目標(biāo)優(yōu)化理論進(jìn)一步提升模型的優(yōu)化能力。此外，本文僅考慮了鐵路線路的平面優(yōu)化。對于復(fù)雜山區(qū)的鐵路線路優(yōu)化問題，還需要進(jìn)一步將算法拓展到三維。