基于動態規劃的鐵路三維空間智能選線方法*

蒲 浩，趙海峰，李 偉

(1．中南大學土木工程學院，湖南 長沙410075;2．高速鐵路建造技術國家工程實驗室，湖南長沙410075)

國內外的路線優化研究從平面優化、縱斷面優化和平縱聯合優化3個方向進行。平面線形優化的目的在于嘗試使用系統的數學方法，利用計算機輔助技術找出最優線形。平面優化時，主要采用通過尋求平面交點位置后依規范插入曲線的方法。目前國外主要采用的方法有變分法、網絡優化法、動態規劃法和遺傳算法［1］。進行平面線形設計后，再配合平面線形進行縱斷面設計。縱斷面線形的數學描述相對簡單，早期縱斷面線形優化設計主要是在假設平面線形已知的情況下，研究如何以各種數學模式描述并優化縱斷面線形。縱斷面線形優化常見的幾種方法有枚舉法，動態規劃法，線性規劃法、梯度投影、降維法和遺傳算法［2－3］。空間線形優化采用的方法有動態規劃法、隨機搜索法、兩階段優化法和遺傳算法。其中，變分法得到的優化結果具有全局優化和連續性的特點，但由于目標函數是有不連續性的各項費用(如占地費用)組成，因此，方法的假設并不符合實際情況，建立的目標函數不適合不連續因子，會出現局部收斂現象。網絡優化算法由于要計算網格間的連通費用，如果缺乏GIS系統的支持，其費用區劃分以及網格連通費用計算量非常大，而且輸出結果不平滑，無法完成連續空間的搜索。線性規劃法不適合非線性目標函數，僅能對受坡度和曲率限制的有限的點進行優化。隨機搜索法以德國的EPOS－1程序為典型代表，此方法計算模型復雜，容易導致局部收斂，不易處理不連續費用情況［3］。近年來，隨著現代優化技術與地理信息科學的發展，Jong 等［1，4－8］基于遺傳算法構建了智能路線設計的框架。遺傳算法雖已被證實適合于大規模復雜非線性優化問題的求解，但前期進化易早熟和后期進化速度緩慢是其最大的缺點［9－10］，而且遺傳算法并不能保證達到全局優化，它仍然可能陷入局部極值的陷阱［11］。因此，有待尋求性能更好的算法來求解路線優化問題。由于選用動態規劃法解決平縱面優化比較理想，因此得到了比較廣泛的應用［12］，如美國麻省理工學院的空間線形選線程序OPTLOC、法國的平面線形優化程序APPOLON、丹麥的道路縱優程序以及我國交通部重慶公路研究所和重慶交通學院聯合研制的 OPTSLD－2程序等［13］。該方法通常與網絡優化結合，將線路優化視為連接起終點的最短路徑問題，具有算法簡單、理論完備、能夠搜索到全局最優的特點［1］。另外，應用動態規劃法，使得最優化問題數學模型的建立及約束條件的處理變得非常容易，從而使該模型具有比基于偏導數最優化方法的其他模型易于實用的優點［13］。但在以往動態規劃的研究中，也存在將連續折線等非實用線形近似代替線路的問題。為此，本文作者提出一種基于動態規劃法三維空間智能選線方法。在動態規劃中直接采用更符合線路實際的“直線—曲線—直線”線形，在三維空間中搜索出符合平縱約束的全局最優和較優方案。算法實現簡單，穩定性好。

1 目標函數和約束條件

在三維空間優化問題中，一般來說交點不包括線路的起終點，因為它們是已知的、不變的。緩和曲線長和豎曲線對線路的位置影響不大，這里不考慮平面緩和曲線和豎曲線的具體設計，在優化時只在夾直線的約束條件下預留緩和曲線位置即可［14］。以線路平面交點位置坐標、曲線半徑和縱斷面設計標高為設計變量，以線路設計規范及其他技術條件為約束條件，以換算工程費為目標函數，則鐵路三維空間優化問題可以歸結為求解下述非線性規劃問題:

1．1 設計變量

X= ［x1，x2，…，xN］T，Y= ［y1，y2，…，yN］T，R= ［R1，R2，…，RN］T分別為平面交點坐標向量和曲線半徑向量，N為平面交點個數(不含起終點)。

D= ［d1，d2，…，dM］T，Z= ［z1，z2，…，zM］T，為相應的縱斷面變坡點里程向量和標高向量，M為縱斷面變坡點個數。

1．2 目標函數

其中:f1為土石方工程費用;f2為橋涵費用;f3為隧道費用;f4為擋墻圬工工程費;f5為換算運營費、用地費;f6為與線路長度有關的軌道、通信設備等費用。

1．3 約束條件

式(2)中gi(X，Y，R)≥0為平面約束，主要包括:

①曲線半徑不得小于允許的最小曲線半徑值:Ri≥Rmin;

②夾直線長度(包括預留緩和曲線)滿足規范要求:LJi≥LJmin;

③圓曲線長度(包括預留緩和曲線)滿足規范要求:LYi≥ LYmin。

④必須經過的點、必須繞避的自然保護區或不良地質地區等其他幾何約束。

式(3)中hj(D，Z)≥0為縱面約束，主要包括:

①選用技術標準限制:坡度限制、坡長限制等;

②標高限制:起終點銜接標高、路線通過固定標高點、路線標高必須限制在界定范圍以內等。

2 三維動態規劃模型的建立和求解

2．1 三維空間網格劃分

首先對線路可能經行的區域進行三維空間網格劃分。如圖1所示。

圖1 三維網格的平面投影Fig．1 Plan of the search grid

圖2 三維搜索網格Fig．2 A 3D search grid

假設 S(xS，yS)、E(xE，yE)分別為路線的起點和終點，線段為起終點連線。假定用N個垂直面 A1，A2，…，Ai，…，An等分線段，則這些垂直面與路線交于 N 個不同的三維點 P1，P2，…，Pi，…，PN。假設每個垂直面上的點個數分別為 m1，m2，…，mi，…，mN。并規定線路與每個垂直面的交點必須在這些三維網格點中選擇，即Pi必須在面Ai上的 mN個三維網格點 Pi，1，Pi，2，…，Pi，mi中選擇，如圖2。這N個垂直面將線路劃分為了N+1個區間。

2．2 線路平面的生成

為了使三維搜索網格能更好的控制線路的走向，這里將每個垂直面上可選的三維點視為線路圓曲線的曲中點，而非線路的交點或鏈路折點。因而，由此選出的線路直接是符合線路要求的“直線－曲線－直線”的平面線形，而非由連續折線所組成的非實用線形。根據規范要求對每個圓曲線配置最小曲線半徑為初始半徑，即

R0= ［Rmin，Rmin，…，Rmin，…，Rmin］T

若令起點 S(xS，yS)=P0，終點 E(xE，yE)=PN+1，則P0，…，PN+1這N+2個點的選擇就決定了1個線路的平面線形。

2．3 兩點間線路縱斷面的自動生成

一般來說，變坡點的個數和平面交點的個數并不相同，相鄰2個曲中點間線路所對應的縱斷面設計線也并不一定是單一的坡度，即任何2個曲中點之間的縱斷面設計線應該是和地形相適應的。因此，本文將平順地面線與最小二乘法相結合，研究了一種自動生成優化縱斷面的方法，以快速決定線路上兩點之間的縱斷面設計線。即利用平順地面線一階差商反號處的里程作為坡段劃分的界限值，從而可以獲得不同的坡段劃分方案，再采用最小二乘原理擬合直線獲得坡度線。最后進行約束檢驗和縱坡調整。

2．3．1 地面線平順

利用計算機尋求變坡點的位置，其實質就是尋求地面線走勢發生改變的位置。原始地面線是一條不規則的鋸齒狀折線，這里采用屋架函數對地面線進行圓順。設縱斷面地面線有n個中樁，Xi，Yi(i=1，2，3，…，n)分別為其里程和地面高程，用屋架函數進行平滑的公式為［15］:

式中:R為平順半徑(m)，一般取最小坡段長;m1和m2為計算i點的平順高程時將屋架函數中心置于i點，在函數2R范圍內中樁起止序號;lj為j號中樁距i號中樁的距離(m)，lj=Xi－Xj;Yj為j號中樁的地面高程(m)。

利用上述函數對地面線進行平順處理時，改變平順次數或平順半徑R，都會對最后得到的曲線產生較大的影響，平順次數越大曲線越趨近于平緩，平順半徑R越大曲線越趨近于平緩［15］。本文根據線路等級采用不同的平順半徑R及不同的平順次數。

2．3．2 變坡點個數的確定

確定變坡點位置，即選擇曲線上的反彎點及曲率發生變化的點。經上述平順處理所建立的地面模型并不完全光滑，其一階倒數并不連續［16］。因此，需對平滑地面線進行三階及一階均差計算，以查找其反彎點和曲率變化點，從而確定坡段的劃分。

(1)三階差商計算:

當 i=1 時，dy′1=(y′2－ y′1)/(x′2－ x′1);當i=n 時，dy′n=(y′n－ y′n－1)/(x′n－ x′n－1)。

經上述差商后，平滑曲線呈近似折線，需進一步進行一階差商處理。

(2)一階差商計算:

當 i=1 時，ddy′1=(dy′2－ dy′1)/(x′2－ x′1);當i=n 時，ddy′n=(dy′n－ dy′n－1)/(x′n－ x′n－1)。

經一階差商處理后，差商值反號的點即為折線斜率發生變化的點，也就是平滑地面線的反彎點，以此劃分線路坡段是最符合地面線起伏情況的。因此取一階差商值反號處的里程為變坡點的分段里程。再對該方案的變坡點進行處理，刪除不滿足最小坡長的坡段，從而確定變坡點的個數。

2．3．3 變坡點位置的確定

為使所生成縱斷面方案的工程數量最小，采用最小二乘原理擬合直線獲得坡度線。設經平順地面線某一坡段范圍(Mi，Mi+1)內有m個地面線樁號點，設其中第i個樁號處的里程和高程分別為si和hi，設該坡段的直線方程為y=kx+a，根據最小二乘原理可得直線方程的系數k和a分別為［17］:

i=1，2，…，m。利用擬合所得相鄰2條直線相交所產生的交點，得第i個變坡點坐標(Si，Hi)如下:

以依次連接各交點所得的折線為初始縱斷面方案的坡度線，經約束處理后，根據規范要求配置適當的豎曲線即可得符合設計需要的縱斷面設計線。

2．4 動態規劃模型建立

(1)如圖2中所示，N個垂直面將線路切分成N+1個區間，這N+1個區間可作為動態規劃法決策中的 N+1個階段:P0至 P1，P1至 P2，…，PN至PN+1。

(2)狀態和決策。對第k階段進行分析(其中k=0，1，…，N)，設第k階段的狀態變量用Sk表示，決策變量為Uk，決策集為Dk(Sk)，且令m0=1，則

(3)策略。全過程策略記為為Q0，N，則

k 子過程策略記為 Qk，N，則

(4)狀態轉移方程為:

(5)指標函數和最優指標函數。若用fk(Pk，Pk+1)表示第k區間線路的綜合費用，則階段指標函數為:

過程指標函數即鐵路建造的綜合費用為:

把過程指標函數Vk，N對k子過程策略 Qk，N求最優，得到關于狀態Sk的最優值函數，即從第k階段到終點PN+1的最小綜合費用。記為fk(Sk)，則

(6)動態規劃基本方程。動態規劃的遞推方程為:

邊界條件。

根據邊界條件，從k=N開始，由后向前逆推，逐步求得各階段的最優決策和相應的最優值，最后求出f0(S0)時，就得到整個問題的最優解。

2．5 第K階段中2個狀態間綜合費用的計算

式(15)中的函數Vk(Sk，Uk)的計算方法如下。設第k階段，在2個垂直面上選擇的點分別為Pk(xk，yk，zk)和 Pk+1(xk+1，yk+1，zk+1)。首先，以 Rmin為初始半徑，Pk點為圓曲線的曲中點反算出Pk和Pk+1之間的鐵路線形。

(1)若該段線形不滿足平面線設計約束條件，則令 Vk(Sk，Uk)=fk(Pk，Pk+1)= ∞ 。

(2)若該段線形滿足平面線設計約束條件，對于該區間內的縱斷面，當連接zk與zk+1的坡度大于允許最大坡度或小于允許最小坡度時，則該縱斷面設計無論如何也不可能滿足坡度約束條件。同樣，該區間的線路設計方案綜合費用也按無窮大數來對待。令 Vk(Sk，Uk)=fk(Pk，Pk+1)= ∞ 。

(3)若不屬于上述2種情況，則對該區間的線路按縱斷面自動生成方法自動生成相應的縱斷面，自動配置橋梁、隧道等，并按式(4)計算該區間線路的目標函數f，即為第k階段此方案的 Vk(Sk，Uk)。

2．6 模型求解

根據上述的動態規劃基本方程式(18)，對所有的狀態變量Sk，按K=N，N －1，…，0的順序計算各個fk(SK)的值，最終求取f0(S0)即為起點P0到終點PN+1的最小代價函數。根據各階段的狀態轉移方程Sk+1=Tk(Sk，Uk)得到全過程策略Q0，N={U0，U1，…，UN}，即得到了整體最優的線路方案。

2．7 雙向搜索獲得線路方案群

動態規劃的實質是記憶化搜索。因此，對于從終點到起點的搜索過程。根據動態規劃最優子結構的性質，第k階段的決策過程中，狀態變量Sk某一個可選節點 Pk，j(k=1，2，…，N+1，j=1，2，…，mk)都記錄了從當前三維節點到終點的最小代價函數:

和從該節點到終點的最優路徑:

對于從起點到終點的搜索過程，Pk，j點記錄了從該節點到起點的最小代價函數:

和從該節點到終點的最優路徑:

定義符號f(Pk，j)=fk(Pk，j)+f′k(Pk，j)，Q(Pk，j)=Qk，N(Pk，j)+Q′k，0(Pk，j)，則有:

(1)f(Pk，j)為連接起終點并且經過該三維網格點Pk，j的最小代價函數。

(2)為連接起終點并且經過該三維網格點Pk，j的最優路徑。

證明:假設存在經過點Pk，j有代價函數更小的路徑，該路徑從Pk，j到起點和終點的代價函數分別設為 fQD(Pk，j)和 fZD(Pk，j)，并 且 有 fQD(Pk，j)+fZD(Pk，j)＜ f(Pk，j)。根據動態規劃最優子結構的性質，有

將由(24)和(25)相加，得:

與假設 fQD(Pk，j)+fZD(Pk，j)＜ f(Pk，j)矛盾。結論得證。

采用雙向的動態規劃搜索，將每個網格點Pk，j計算經過該點的最小代價函數 f(Pk，j)，并按f(Pk，j)由小到大排序，即可得連接起終點的一組最優的線路方案群，然后，由狀態轉移方程Sk+1=Tk(Sk，Uk)即可得到對應的線路路徑。

3 系統的開發與應用

應用本文所提出的理論和方法，開發了基于數字地球的鐵路三維空間智能選線系統，系統包括集成的視窗管理、線路的自動搜索、方案的對比和評價、圖表輸出、線路方案的三維場景漫游等內容。

選取了某70 km的1條線路作為算例，計算結果表明:應用本文中提到的理論和方法能有效的搜索出一組優化的線路方案群，搜索出的線路方案能很好的繞避障礙物和適應地形。選線的結果可以作為工程設計人員提供前期設計參考，降低設計人員勞動強度和鐵路的建造費用。三維可視化功能使規劃設計人員能直觀全面地掌握定線區域的地形、環境、地理、交通、地質等信息進行方案比選。

如圖3所示，系統顯示了1個繞避方案、1個隧道方案和1個人工設計方案。圖中所示的繞避方案能夠很好地適應地形并成功繞避山體，隧道方案接近人工選線的結果，但線路長度更短，工程造價更省。

圖3 鐵路三維空間智能選線系統Fig．3 Three dimensional spatial intelligent route selection system

4 結語

(1)基于三維空間的選線方法。即并不是通過不同的目標函數去獨立地優化平面線設計和縱斷面設計，而是著眼于以綜合費用為目標函數來同時決定最優的平、縱斷面設計線。

(2)符合實際的平面搜索線形。為了使三維搜索網格能更好的控制線路的走向，這里將三維網格點做為線路圓曲線的曲中點，而非線路的交點或鏈路折點。由此選出的線路是能很好反映線路特點的“直線－曲線－直線”的平面線形，而非由連續折線所組成的非實用線形。

(3)程序實現簡單。動態規劃法把一個復雜的選線問題轉化為一系列單階段問題，利用各階段之間的關系逐個求解。對于較長的線路可以將其分成多個段落，在程序設計時利用多線程等技術同時搜索，最終得到整個區域的最優方案。并且動態規劃法不需要得到目標函數的顯式表達式，也不需要對目標函數求導。

(4)約束處理容易。文中提出的方法用三維空間網格點控制了線路的位置。對于不良地質地帶、自然保護區等必須繞避區域的約束，只需要將三維空間網格中處于繞避區域的點設置禁忌，并將動態規劃各階段搜索中線路與繞避區域有交叉的方案造價設置為無窮大，就能很好地實現繞避。

(5)選線效率高。利用計算機一次性生成大量的備選方案，設計人員幾個月甚至成年的工作量，最多幾天便可完成選線的任務，大大提高設計效率。

(6)方案多樣性好、效率高。系統最終生成的不是1個方案，而是1個包含繞避方案、架設橋隧方案等不同特點的最優方案群，可以為線路設計人員提供有價值的參考和比選，避免了由于設計人員主觀因素而遺漏可行方案。

［1］Jong J C．Optimizing highway alignments with genetic algorithms［D］．Maryland:University of Maryland，1998．

［2］Eungcheol K，Jha M K，Bongsoo S．Improving the computational efficiency of highway alignment optimization models through a stepwise genetic algorithms approach［J］．Transportation Research:Part B，2005(39):339 －360．

［3］葉亞麗．公路智能選線與決策支持系統研究及開發［D］．西安:長安大學，2010．YE Ya-li．Researeh and development of highway alignment intelligent selection and decision support system［D］．Xi＇an:Chang’an University，2010．

［4］Jha M K．A geographic information systems－based model for highway design optimization［D］．Maryland:University of Maryland，2000．

［5］Jha M K，Schonfeld P．Integrating genetic algorithms and GIS to optimize highway alignments［J］．Transportation Research Record，2000(1719):233 －240．

［6］Jong J C，Jha M K，Schonfeld P．Preliminary highway design with genetic algorithms and geographic information systems［J］．Computer － Aided Civil and Infrastructure Engineering，2000(15):261 －271．

［7］Jha M K，Schonfeld P．A highway alignment optimization model using geographic information systems［J］．Transportation Research:Part A，2004(38):455 －481．

［8］Jong J C，Schonfeld P．An evolutionary model for simultaneously optimizing three－dimensional highway alignments［J］．Transportation Research:Part B，2003(37):107－128．

［9］劉好德，楊曉光．基于改進遺傳算法的公交線網優化設計研究［J］．計算機工程與應用，2007，43(8):10 －14．LIU Hao-de，YANG Xiao-guang．Research on transit network design based on improved genetic algorithm［J］．Computer Engineering and Applications，2007，43(8):10－14．

［10］涂圣文，蘇 州．基于GIS和遺傳－粒子群的公路智能選線方法［J］．長安大學學報:自然科學版，2010，30(4):39－45．TU Sheng-wen，SU Zhou．Intelligent route selection of highway alignments based on GIS and hybrid genetic algorithm and particle swarm optimization［J］．Journal of Chang’an University:Natural Science Edition，2010，30(4):39－45．

［11］戴光明．避障路徑規劃的算法研究［D］．武漢:華中科技大學，2004．DAI Guang-ming．Research on algorithm for avoidance obstacle path planning［D］．Wuhan:Huazhong University of Science and Technology，2004．

［12］谷 克．遺傳算法在公路路線智能決策系統中的應用研究［D］．西安:長安大學，2008．GU Ke．Study on the genetic algorithms’application in highway alignment intelligent decision system［D］．Xi＇an:Chang’an University，2008．

［13］馮 曉，謝遠光．線形工程計算機輔助選線設計理論與方法［M］．成都:西南交通大學出版社，2008．FENG Xiao，XIE Yuan-guang．Alignment engineering computer aided design theory and methodology［M］．Chengdu:Southwest Jiaotong University Press，2008．

［14］李 偉，蒲 浩，彭先寶．基于方向加速法的鐵路既有線平面重構優化算法［J］．鐵道科學與工程學報，2009，6(3):47 －51．LI Wei，PU Hao，PENG Xian-bao．Existing railway plane line reconstruction algorithm based on direction acceleration method［J］．Journal of Railway Science and Engineering，2009，6(3):47 －51．

［15］謝春玲．基于改進遺傳算法的鐵路縱斷面優化研究［D］．長沙:中南大學土木工程學院，2010．XIE Chun-ling．Study on railway profile optimizing system based on genetic algorithms［D］．Changsha:School of Civil Engineering，Central South University，2010．

［16］陳慧勇，路 偉．鐵路線路縱斷面計算機輔助設計及優化方法的研究與運用［J］．中國鐵路，2002，15(6):49－50．CHEN Hui-yong，LU Wei．Study and application of computer aided design in railway track vertical section and its optimization［J］．China Railways，2002，15(6):49－50．

［17］Baker J E．Adaptive selection methods for genetic algorithms［J］．Proceedings of the 1st International Conference on Genetic Algorithms，1985:101 －111．