[發(fā)明專利]一種多目標點路徑規(guī)劃方法和裝置

無效

• 申請?zhí)枺?/td>: 200810032948.X
• 申請日: 2008-01-23
• 公開（公告）號: CN101493329A
• 公開（公告）日: 2009-07-29
• 發(fā)明（設(shè)計）人: 王麗蘋;董軍;吳春元
• 申請（專利權(quán)）人: 華東師范大學(xué)
• 主分類號: G01C21/26
• 分類號: G01C21/26;G01C21/34
• 代理公司: 上海專利商標事務(wù)所有限公司
• 代理人: 陳 亮

1.一種多目標點路徑規(guī)劃方法，包括：

(1)從地理信息數(shù)據(jù)中讀取地理數(shù)據(jù)中網(wǎng)絡(luò)層的屬性數(shù)據(jù)集信息，其中該屬性數(shù)據(jù)集信息包括各個路徑上的信息素濃度；

(2)按定義的數(shù)據(jù)結(jié)構(gòu)存儲數(shù)據(jù)，同時初始化各個路徑上的信息素濃度；

(3)接收用戶路徑規(guī)劃的請求；

(4)獲取輸入的路徑規(guī)劃的起始點和所有的終止點的信息并存儲；

(5)通過蟻群算法搜索從起點到終點的路徑，其中該起點的初始值是步驟(4)中輸入的該路徑規(guī)劃的起始點，該終點的初始值是步驟(4)輸入的該些終止點中的第一個；

(6)判斷是否搜索到路徑，如果搜索到則進入步驟(7)，否則轉(zhuǎn)入步驟(10)；

(7)記錄最優(yōu)路徑信息，并更新起點信息為當前終點的信息；

(8)判斷是否存在下一個終止點，如果存在則進入步驟(9)，否則轉(zhuǎn)入步驟(11)；

(9)更新終點信息為下一個終止點，返回步驟(5)；

(10)搜索失敗，反饋失敗的信息，流程結(jié)束；

(11)搜索結(jié)束，反饋路徑搜索的結(jié)果。

2.根據(jù)權(quán)利要求1所述的多目標點路徑規(guī)劃方法，其特征在于，步驟(5)進一步包括：

(a)初始化迭代次數(shù)NC；

(b)判斷迭代次數(shù)NC是否到達最大循環(huán)迭代次數(shù)，如果未到最大循環(huán)迭代次數(shù)則進入步驟(c)，否則結(jié)束對當前終點的路徑搜索；

(c)設(shè)置蟻群算法中的參數(shù)值，初始化所有的螞蟻狀態(tài)為運行狀態(tài)，螞蟻已經(jīng)訪問的結(jié)點數(shù)置為1；

(d)判斷是否有運行狀態(tài)的螞蟻，如果有則進入步驟(e)，否則更新信息素濃度和最優(yōu)路徑信息，迭代次數(shù)NC加1，然后返回步驟(b)；

(e)選擇一只運行狀態(tài)的螞蟻將其編號為k，得到與螞蟻k當前位置相鄰的、未到達過的結(jié)點集合；

(f)獲得螞蟻k到每一個相鄰點的距離以及對應(yīng)路徑上的信息素濃度，計算出螞蟻到每一個相鄰點的概率；

(g)判斷是否有可移動的結(jié)點，如果有則進入步驟(h)，否則螞蟻k的狀態(tài)置為死亡然后轉(zhuǎn)入步驟(d)；

(h)選擇一個概率值最大的相鄰點作為螞蟻k要移動到的下一個結(jié)點；

(i)判斷是否存在兩個或者兩個以上的概率最大的相鄰點，如果存在則進入步驟(j)，否則進入步驟(k)；

(j)用隨機數(shù)確定螞蟻移動到的結(jié)點；

(k)螞蟻k移動到選定的概率最大的結(jié)點；

(l)判斷螞蟻k所在的結(jié)點是否為終點，如果不是終點則進入步驟(m)，否則將螞蟻k的狀態(tài)設(shè)為到達并轉(zhuǎn)入步驟(d)；

(m)判斷螞蟻經(jīng)過的路徑長度是否小于最大搜索范圍，如果小于最大搜索范圍則返回步驟(f)，否則螞蟻k的路徑搜索過程結(jié)束并返回步驟(d)。

3.根據(jù)權(quán)利要求2所述的多目標點路徑規(guī)劃方法，其特征在于，步驟(d)中更新信息素濃度和最優(yōu)路徑信息并對迭代次數(shù)NC加1的過程進一步包括：

(d.1)判斷是否有運行狀態(tài)的螞蟻，如果有則進入步驟(d.2)，否則進入步驟(d.3)；

(d.2)選擇一只運行狀態(tài)的螞蟻將其編號為k，得到與螞蟻k當前位置相鄰的、未到達過的結(jié)點集合，該過程結(jié)束；

(d.3)判斷是否有沒有訪問過的到達狀態(tài)的螞蟻，如果沒有則進入步驟(d.4)，否則進入步驟(d.5)；

(d.4)將迭代次數(shù)NC的值加1，繼續(xù)下一次的迭代，該過程結(jié)束；

(d.5)計算螞蟻經(jīng)過的路徑長度；

(d.6)判斷該路徑長度是否小于已有的最優(yōu)長度，如果小于則進入步驟(d.7)，否則進入步驟(d.8)；

(d.7)更新最優(yōu)路徑的信息；

(d.8)更新螞蟻所經(jīng)過的路徑上的信息素濃度。

4.根據(jù)權(quán)利要求1所述的多目標點路徑規(guī)劃方法，其特征在于，該屬性數(shù)據(jù)集信息還包括網(wǎng)絡(luò)層中的道路對象標識、路徑起始點和終止點的標識。