[發(fā)明專利]一種復雜山區(qū)鐵路線站協(xié)同優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201510740892.3
• 申請日: 2015-11-04
• 公開（公告）號: CN105243233A
• 公開（公告）日: 2016-01-13
• 發(fā)明（設計）人: 蒲浩;李偉;張洪;鄭曉強;王雷;劉威;袁文輝;羅詩瀟;嚴基團;熊佳興;李帥;陳晨
• 申請（專利權）人: 中南大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 長沙市融智專利事務所 43114
• 代理人: 楊萍

1.一種復雜山區(qū)鐵路線站協(xié)同優(yōu)化方法，其特征在于，包括以下步驟：

S₁：劃分單元格：

將選線范圍劃分為包含M×N個正方形單元格的規(guī)則格網，格網內各單元格的寬度為w，取值范圍為30m-90m；線路起點和線路終點分別位于該格網左上角和右下角的單元格處。

S₂：建立綜合地理信息模型，添加單元格的地理信息屬性：

采集線路搜索所需要的各類信息，包括描述地形、地物、地價和工程單價信息，將其作為各單元格的地理環(huán)境屬性。

S₃：初始化各單元格的線站協(xié)同搜索相關屬性；

定義單元格的線站協(xié)同搜索相關屬性及其賦初值情況如下：

(1)分別以起點和終點為目標點時，各單元格距最近站址的連接距離DIST，初值賦為0；

(2)各單元格到目標點的連接代價COST，包括各單元格到線路起點的連接代價和到線路終點的連接代價：起點到起點的連接代價初值賦為0，終點到終點的連接代價初值賦為0，其他所有單元格到起點和終點的連接代價初值均賦為無窮大；

(3)分別以起點和終點為目標點時，使得單元格的COST最小的連接方案下，單元格距相應的鄰域單元格的橫向偏移量XV，初值賦為0；

(4)分別以起點和終點為目標點時，使得單元格的COST最小的連接方案下，單元格距相應的鄰域單元格的縱向偏移量YV，初值賦為0；

(5)表征各單元格是否為站址單元格的類型屬性，記為TYPE；若單元格為非站址單元格，則TYPE賦值為False，若單元格為站址單元格，則TYPE賦值為True；所有單元格的TYPE初值均賦為False，即所有單元格的初始類型均為非站址單元格；

(6)表征各單元格能否通行鐵路線路的屬性，記為PROPERTY；若單元格不能通行鐵路線路，則PROPERTY＝0，若單元格可以通行鐵路線路，則PROPERTY＝1；所有單元格PROPERTY的初始值均為1；

S₄：線站協(xié)同優(yōu)化掃描

S_4-1：依據“預處理”約束要求，剔除不符合約束條件的單元格；

S_4-2：對剩下的單元格，基于線站協(xié)同搜索雙鄰域模板，即站址搜索鄰域模板和線路搜索鄰域模板，依次進行四次掃描；

第一次掃描和第二次掃描均以線路起點為目標點；第一次掃描以線路起點為起始點，從上至下、從左至右進行逐行掃描，直到掃描到線路終點；第二次掃描從線路終點沿第一次掃描的原路返回掃描至線路起點；第一次掃描和第二次掃描完成后生成以線路起點為目標點掃描的距離圖DT_S；

第三次掃描和第四次掃描均以線路終點為目標點，第三次掃描以線路終點為起始點，從下至上、從右至左進行逐行掃描，直到掃描到線路起點；第四次掃描從線路起點沿第三次掃描的原路返回掃描至線路終點，第三次掃描和第四次掃描完成后生成以線路終點為目標點掃描的距離圖DT_E；

每一次掃描的具體步驟如下：

S_4-2-1：首先基于站址搜索鄰域模板進行掃描，判斷當前單元格與所涉及的鄰域單元格之間是否滿足站址搜索過程中的“中處理”約束要求，如均不滿足，則跳至步驟S_4-2-6進行線路鄰域模板掃描；如存在滿足約束要求的站址鄰域單元格，則進行如下步驟：

S_4-2-2：依次計算當前單元格與滿足約束要求的每一個鄰域單元格的連接代價；加上相應的鄰域單元距目標點的連接代價，得到當前單元格經相應的鄰域單元格至目標點的連接代價COST’；若該連接代價COST’小于當前單元格的COST，則更新當前單元格的COST，令當前單元格的COST＝COST’；找出使得當前單元格的COST(當前單元格距目標點的連接代價)最小的連接方案；

S_4-2-3：計算使得當前單元格的COST最小的連接方案中，當前單元格距相應的鄰域單元格的橫向偏移量XV和縱向偏移量YV，并更新當前單元格的相應屬性；

S_4-2-4：更新當前單元格為站址單元格，即將TYPE賦值為True；

S_4-2-5：更新當前單元格距最近站址的連接距離為0，即將當前單元格的DIST賦值為0；返回步驟S_4-2-1進行下一單元格的掃描，直至所有單元格掃描完成；

S_4-2-6：對當前單元格基于線路搜索鄰域模板進行掃描，判斷當前單元格與所涉及的鄰域單元格之間是否滿足線路搜索過程中的“中處理”約束要求，如均不滿足，則結束當前單元格搜索，并將當前單元格屬性賦為不可行單元格，不更新其到目標點的連接代價COST，其值仍為無窮大；返回步驟S_4-2-1進行下一單元格的掃描；如存在滿足約束要求的連接方案，則進行如下步驟：

S_4-2-7：依次計算當前單元格與滿足約束要求的每一個鄰域單元格之間的連接代價；加上相應的鄰域單元距目標點的連接代價，得到當前單元格經相應的鄰域單元格至目標點的連接代價COST’；若該連接代價COST’小于當前單元格的COST，則更新當前單元格的COST，令當前單元格的COST＝COST’；找出使得當前單元格的COST最小的連接方案；

S_4-2-8：計算使得當前單元格的COST最小的連接方案中，當前單元格距相應的鄰域單元格的橫向偏移量XV和縱向偏移量YV，并更新當前單元格的相應屬性；

S_4-2-9：更新當前單元格距最近站址的連接距離DIST為：使得當前單元格的COST最小的連接方案中，與其相連的鄰域單元格的DIST值與線路搜索鄰域模板的搜索半徑R的和；返回步驟S_4-2-1進行下一單元格的掃描，直至所有單元格掃描完成；

S₅：依據掃描距離圖生成線路路徑方案群，具體包括以下步驟：

S_5-1：疊加以線路起點為目標點掃描的距離圖DT_S和以線路終點為目標點掃描的距離圖DT_E；

S_5-2：遍歷疊加距離圖中的所有單元格，選出距線路起點和線路終點的連接代價均不為無窮大的單元格作為雙向連接單元格；

S_5-3：選取任一雙向連接單元格，并以雙向連接單元格為中心，根據單元格內存儲的連接信息屬性XV和YV，分別向線路的起點和終點擴展，生成線路路徑方案；

S_5-4：遍歷所有雙向連接單元格，并根據步驟S_5-3所述的方法生成起點到終點的線路路徑方案群；

S_5-5：依據“后處理”約束要求對所S_5-4中生成的線路路徑方案進行逐一判斷，調整不符合“后處理”約束要求的線路路徑方案；

S₆：生成線-站方案群：

S_6-1：選取步驟S_5-5中得到的任意一條線路路徑方案，遍歷該路徑方案上的所有單元格，找出其站址單元格，并由站址單元格和其鄰域單元格形成站址連接段；

S_6-2：判斷各個站址連接段間是否滿足最大、最小站間距要求，如滿足則選為線-站方案，如不滿足則剔除此方案；

S_6-3：遍歷步驟S₅生成的所有線路路徑方案，選出滿足要求的方案，生成線-站方案群。

所述步驟S_4-2中的線路搜索鄰域模板用于遍歷與當前單元格距離為R的所有單元格，所遍歷的單元格均分布在一個以當前單元格為中心的半圓弧上；半徑R根據設計人員的經驗設置；

線路搜索鄰域模板分為線路搜索鄰域正向模板和線路搜索鄰域反向模板；記所遍歷的單元格相對于當前單元格的行列偏移值為△R，△C，則線路搜索鄰域正向模板中△R，△C的計算方法為：

α=w/Rn=π/αΔR=-[R×sin(α×i)],i=1,...nΔC=[R×cos(α×i)],i=1,...n---(1)]]>

線路搜索鄰域反向模板中△R，△C的計算方法為：

α=w/Rn=π/αΔR=[R×sin(α×i)],i=1,...nΔC=-[R×cos(α×i)],i=1,...n---(2)]]>

所述步驟S_4-2中的站址搜索鄰域模板用于遍歷與當前單元格距離為R₁的所有單元格，所遍歷的單元格均分布在一個以當前單元格為中心的半圓弧上，半徑R₁取值為站坪長度L_sta；

站址搜索鄰域模板分為站址搜索鄰域正向模板和站址搜索鄰域反向模板；記所遍歷的單元格相對于當前單元格的行列偏移值為△R，△C，則站址搜索鄰域正向模板中△R，△C的計算方法為：

α=w/R1n=π/αΔR=-[R1×sin(α×i)],i=1,...nΔC=[R1×cos(α×i)],i=1,...n---(3)]]>

線路搜索鄰域反向模板中△R，△C的計算方法為：

α=w/R1n=π/αΔR=[R1×sin(α×i)],i=1,...nΔC=-[R1×cos(α×i)],i=1,...n---(4)]]>

所述第一次掃描和第四次掃描均基于線路搜索鄰域正向模板和站址搜索鄰域正向模板進行掃描；所述第二次掃描和第三次掃描基于線路搜索鄰域反向模板和站址搜索鄰域反向模板進行掃描。