[發(fā)明專利]一種基于道路等級的最短路徑規(guī)劃算法

有效

• 申請?zhí)枺?/td>: 201410697096.1
• 申請日: 2014-11-26
• 公開（公告）號: CN104406590A
• 公開（公告）日: 2015-03-11
• 發(fā)明（設計）人: 趙陽陽;張福浩;石麗紅;仇阿根;陶坤旺;胡璐錦;張章;張衛(wèi)平
• 申請（專利權(quán)）人: 中國測繪科學研究院
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 北京匯信合知識產(chǎn)權(quán)代理有限公司 11335
• 代理人: 吳甘棠

技術領域

本發(fā)明屬計算機科學與地理信息科學領域，涉及一種基于道路等級的最短路徑規(guī)劃算法。?

背景技術

最短路徑的計算問題是一個經(jīng)典的問題，一個最實際的應用就是在道路網(wǎng)絡中進行路徑分析，如在給定的道路網(wǎng)中，尋找起點到目標點的最佳路徑問題。當前最短路徑分析方法從算法的可實現(xiàn)性以及穩(wěn)定性來講，可以概括為兩類：一類是充分利用最短路徑在道路網(wǎng)中的空間相關性，把道路網(wǎng)中的最短路徑壓縮成為簡單的格式，這樣可以大幅度提高查詢效率，這種方法比較有代表性的是H.Samet和J.Sankaranarayanan等人提出的SILC(Spatially?Induced?Linkage?Cognizance)改進算法，以及J.Sankaranarayanan等人提出的PCPD(Path-Coherent?Pairs?Decomposition)算法；另外一種方法是基于道路網(wǎng)中某些節(jié)點對最短路徑查詢的重要性，然后以Dijkstra算法為基礎進行改進。雖然當前已有根據(jù)此提出的一些新的算法，但是這些算法并不是很有效。對于第一類方法需要計算道路結(jié)點所構(gòu)建的不同道路之間的關聯(lián)性，從而進行替代計算，算法復雜，計算量大。因此，第二類方法較為常用，但是現(xiàn)有研究往往只考慮道路結(jié)點權(quán)重，但是未考慮不同道路等級以及在不同道路等級下對最短時間的限制，因此研究一種結(jié)合道路等級以及道路等級約束下最短時間的新算法是非常有必要的。?

發(fā)明內(nèi)容

鑒于此，本發(fā)明提出一種基于道路等級的最短路徑規(guī)劃算法，在傳統(tǒng)最短路徑規(guī)劃的基礎上，充分考慮道路通行能力，通過道路等級實現(xiàn)道路層次化表達，與此同時，采用時間成本變量代替距離變量，通過計算最短通行時間規(guī)劃最佳救援路徑。?

一種基于道路等級的最短路徑規(guī)劃算法，包括如下步驟：?

步驟1，數(shù)據(jù)準備與數(shù)據(jù)預處理，?

所述數(shù)據(jù)準備是通過GPS導航獲取道路網(wǎng)數(shù)據(jù)，通過交通部門獲取道路單行線信息數(shù)據(jù)，以及通過網(wǎng)絡查詢獲取每個道路等級的最大通行速度數(shù)據(jù)，其中，?

所述道路網(wǎng)數(shù)據(jù)包括道路名稱、道路等級和道路節(jié)點坐標，將所述道路網(wǎng)數(shù)據(jù)以shape格式存儲；所述道路單行線信息數(shù)據(jù)包括道路名稱、道路起點、道路終點和道路單行方向，所述道路等級的最大通行速度數(shù)據(jù)包括道路名稱、道路等級和最大通行車速，將所述道路單行線信息數(shù)據(jù)和道路等級的最大通行速度數(shù)據(jù)以dbf格式存儲。Shap?e文件格式是一種矢量數(shù)據(jù)格式，它沒有拓撲信息，一個Shape?files由一組文件組成，其中必要的基本文件包括坐標文件(.shp)、索引文件(.shx)和屬性文件(.dbf)三個文件；dbf格式存儲為一種特殊的文件格式，表示數(shù)據(jù)庫文件，F(xiàn)oxbase，Dbase，Visual?FoxPro等數(shù)據(jù)庫處理系統(tǒng)所產(chǎn)生的數(shù)據(jù)庫文件。?

所述數(shù)據(jù)預處理包括道路數(shù)據(jù)通行方向處理和道路數(shù)據(jù)節(jié)點信息處理，其中，?

所述道路數(shù)據(jù)通行方向處理是將道路單行方向分為正向和逆向兩種，在道路網(wǎng)shape屬性表中增加正向和逆向字段，用二值0和1分別表示道路在該方向不通行或通行，用所述0和1對所述道路單行方向進行賦值，得到處理后的道路單行方向數(shù)據(jù)；?

所述道路數(shù)據(jù)節(jié)點信息處理方法為：當兩條道路相交且通車時，在相交處增加節(jié)點，增加道路節(jié)點坐標，原來兩條道路變成四條道路，當兩條道路相交但不通車時，道路節(jié)點坐標保持不變，通過所述道路數(shù)據(jù)節(jié)點信息處理得到處理后的道路節(jié)點坐標；?

步驟2，對步驟1中獲取的道路網(wǎng)數(shù)據(jù)中的道路等級進行劃分，劃分后的道路等級分為：公路、城市道路和鄉(xiāng)村道路，其中，?

公路劃分為高速公路、一級公路、二級公路、三級公路和四級公路，城市道路劃分為快速路、主干路、次干路和支路，鄉(xiāng)村道路劃分為農(nóng)村硬化道路、機耕路和鄉(xiāng)村路；?

將所述劃分后的道路等級進行層次化表達，將道路視為由連接邊和節(jié)點組成的網(wǎng)狀圖形，如果每個節(jié)點與其聯(lián)通的節(jié)點間的道路是通?行的，那么記錄所述每個節(jié)點和其聯(lián)通的節(jié)點，同時記錄所述每個節(jié)點與其聯(lián)通的節(jié)點間的連接邊，得到聯(lián)通的兩節(jié)點間的連接邊數(shù)據(jù)；?

步驟3，基于步驟2中的節(jié)點及聯(lián)通的兩節(jié)點間的連接邊數(shù)據(jù)，利用距離公式根據(jù)道路節(jié)點坐標計算每個道路段的距離，其中聯(lián)通的兩節(jié)點間通行的道路是一條以上的，計算不同道路段的距離，利用獲得的所述距離、所述道路的最大通行車速求出兩聯(lián)通的節(jié)點間不同道路的通行時間，比較所述不同道路的通行時間得出聯(lián)通的兩節(jié)點間的最短通行時間；?