基于動態(tài)規(guī)劃的鐵路三維空間智能選線方法*

蒲 浩，趙海峰，李 偉

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

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

1 目標函數(shù)和約束條件

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

1．1 設計變量

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

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

1．2 目標函數(shù)

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

1．3 約束條件

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

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

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

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

④必須經(jīng)過的點、必須繞避的自然保護區(qū)或不良地質(zhì)地區(qū)等其他幾何約束。

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

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

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

2 三維動態(tài)規(guī)劃模型的建立和求解

2．1 三維空間網(wǎng)格劃分

首先對線路可能經(jīng)行的區(qū)域進行三維空間網(wǎng)格劃分。如圖1所示。

圖1 三維網(wǎng)格的平面投影Fig．1 Plan of the search grid

圖2 三維搜索網(wǎng)格Fig．2 A 3D search grid

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

2．2 線路平面的生成

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

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

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

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

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

2．3．1 地面線平順

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

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

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

2．3．2 變坡點個數(shù)的確定

確定變坡點位置，即選擇曲線上的反彎點及曲率發(fā)生變化的點。經(jīng)上述平順處理所建立的地面模型并不完全光滑，其一階倒數(shù)并不連續(xù)［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)。

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

(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)。

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

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

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

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

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

2．4 動態(tài)規(guī)劃模型建立

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

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

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

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

(4)狀態(tài)轉(zhuǎn)移方程為:

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

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

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

(6)動態(tài)規(guī)劃基本方程。動態(tài)規(guī)劃的遞推方程為:

邊界條件。

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

2．5 第K階段中2個狀態(tài)間綜合費用的計算

式(15)中的函數(shù)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)若該段線形滿足平面線設計約束條件，對于該區(qū)間內(nèi)的縱斷面，當連接zk與zk+1的坡度大于允許最大坡度或小于允許最小坡度時，則該縱斷面設計無論如何也不可能滿足坡度約束條件。同樣，該區(qū)間的線路設計方案綜合費用也按無窮大數(shù)來對待。令 Vk(Sk，Uk)=fk(Pk，Pk+1)= ∞ 。

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

2．6 模型求解

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

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

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

和從該節(jié)點到終點的最優(yōu)路徑:

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

和從該節(jié)點到終點的最優(yōu)路徑:

定義符號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)為連接起終點并且經(jīng)過該三維網(wǎng)格點Pk，j的最小代價函數(shù)。

(2)為連接起終點并且經(jīng)過該三維網(wǎng)格點Pk，j的最優(yōu)路徑。

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

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

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

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

3 系統(tǒng)的開發(fā)與應用

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

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

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

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

4 結語

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

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

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

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

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

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

［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］葉亞麗．公路智能選線與決策支持系統(tǒng)研究及開發(fā)［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］劉好德，楊曉光．基于改進遺傳算法的公交線網(wǎng)優(yōu)化設計研究［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］戴光明．避障路徑規(guī)劃的算法研究［D］．武漢:華中科技大學，2004．DAI Guang-ming．Research on algorithm for avoidance obstacle path planning［D］．Wuhan:Huazhong University of Science and Technology，2004．

［12］谷 克．遺傳算法在公路路線智能決策系統(tǒng)中的應用研究［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］李 偉，蒲 浩，彭先寶．基于方向加速法的鐵路既有線平面重構優(yōu)化算法［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］謝春玲．基于改進遺傳算法的鐵路縱斷面優(yōu)化研究［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］陳慧勇，路 偉．鐵路線路縱斷面計算機輔助設計及優(yōu)化方法的研究與運用［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．