[發(fā)明專利]一種啟發(fā)式搜索的高速路網(wǎng)約束尋路算法

有效

• 申請(qǐng)?zhí)枺?/td>: 201811415513.3
• 申請(qǐng)日: 2018-11-26
• 公開（公告）號(hào): CN109540165B
• 公開（公告）日: 2022-07-01
• 發(fā)明（設(shè)計(jì)）人: 王剛;李劍;梅樂翔;劉旭;高薪;張鵬;李婧芳;劉晶;宋杰;王夢(mèng)佳;賀文濤;趙晴
• 申請(qǐng)（專利權(quán)）人: 交通運(yùn)輸部路網(wǎng)監(jiān)測(cè)與應(yīng)急處置中心
• 主分類號(hào): G01C21/34
• 分類號(hào): G01C21/34
• 代理公司: 北京萬象新悅知識(shí)產(chǎn)權(quán)代理有限公司 11360
• 代理人: 黃鳳茹

1.一種基于啟發(fā)式搜索的高速路網(wǎng)約束尋路算法，以指定路網(wǎng)、指定路網(wǎng)中的道路起點(diǎn)、道路終點(diǎn)和駛經(jīng)的收費(fèi)路段集合為輸入數(shù)據(jù)，通過啟發(fā)式搜索，生成連接道路起點(diǎn)與道路終點(diǎn)之間的多條路徑，并從多條路徑中選擇一條與輸入的收費(fèi)路段重合度最高的路徑，作為輸出路徑；包括如下步驟：

1)遍歷輸入的收費(fèi)路段集合中的每個(gè)收費(fèi)路段的原子路段，將收費(fèi)路段包含的原子路段中至少有一條原子路段在所述指定路網(wǎng)上的收費(fèi)路段作為有效收費(fèi)路段，生成有效收費(fèi)路段集合，建立從原子路段到所在收費(fèi)路段集合的映射；所述映射的定義域僅需要包含所有有效收費(fèi)路段包含的原子路段；

初始化尋路算法的數(shù)據(jù)結(jié)構(gòu)，包括：用于啟發(fā)式搜索的優(yōu)先隊(duì)列和用于記錄搜索狀態(tài)及對(duì)應(yīng)路徑的數(shù)據(jù)結(jié)構(gòu)；

優(yōu)先隊(duì)列中的元素為搜索的狀態(tài)；優(yōu)先隊(duì)列具有以下結(jié)構(gòu)：

1C)當(dāng)前所處位置的索引；所述位置為不同類型的路網(wǎng)結(jié)點(diǎn)；

1D)當(dāng)前路徑覆蓋的有效收費(fèi)路段集合；

1E)當(dāng)前路徑的長(zhǎng)度；

1F)從當(dāng)前位置到達(dá)終點(diǎn)的預(yù)估距離；

1G)存放路徑鏈表的線性表中的索引，指向當(dāng)前路徑在邊鏈上的最后一個(gè)結(jié)點(diǎn)在線性表中的位置；

初始化優(yōu)先隊(duì)列即用起點(diǎn)的索引構(gòu)建優(yōu)先隊(duì)列的初始元素；優(yōu)先隊(duì)列的啟發(fā)函數(shù)使用路網(wǎng)結(jié)點(diǎn)的地理位置信息進(jìn)行輔助導(dǎo)向；

2)取出優(yōu)先隊(duì)列的隊(duì)首狀態(tài)，作為當(dāng)前狀態(tài)；以當(dāng)前狀態(tài)所處位置為中心，在路網(wǎng)上遍歷鄰接的原子路段，擴(kuò)展并篩選得到新狀態(tài)；如果優(yōu)先隊(duì)列已為空，則返回已有的最佳路徑；具體執(zhí)行如下步驟：

21)不斷取出優(yōu)先隊(duì)列的隊(duì)首狀態(tài)為當(dāng)前狀態(tài)，執(zhí)行步驟22)～25)；如果優(yōu)先隊(duì)列已為空，則返回當(dāng)前的最佳路徑；此時(shí)如果最佳路徑為空，說明路網(wǎng)中沒有從起點(diǎn)到終點(diǎn)的通路；

22)找到當(dāng)前狀態(tài)所處位置的鄰接原子路段集合，遍歷該集合中的原子路段并執(zhí)行步驟23)～25)；

23)計(jì)算從當(dāng)前狀態(tài)經(jīng)過該原子路段后到達(dá)的新狀態(tài)；如果新狀態(tài)到達(dá)終點(diǎn)的預(yù)估距離超過了已有最佳路徑的長(zhǎng)度的指定倍數(shù)，則回到步驟22)并選擇下一個(gè)原子路段；其中，所述指定倍數(shù)是算法的范圍參數(shù)，用于控制算法在尚未找到完美路徑時(shí)的最大搜索范圍；

所述完美路徑是一條從起點(diǎn)到終點(diǎn)的路徑，該路徑包含的原子路段覆蓋了所有有效的收費(fèi)路段，而且是在滿足要求的所有路徑中長(zhǎng)度最短的那條路徑；

尚未找到完美路徑時(shí)，最佳路徑是一條從起點(diǎn)到終點(diǎn)的、覆蓋了最多的有效收費(fèi)路段的所有路徑中，路徑長(zhǎng)度最短的路徑；

24)考察在搜索產(chǎn)生的歷史狀態(tài)中，所處位置和上一步得到的新狀態(tài)的位置是相同的，并且具有相同的有效收費(fèi)路段覆蓋集合的所有歷史狀態(tài)，并確定狀態(tài)中對(duì)應(yīng)路徑長(zhǎng)度的最小值；其中，一個(gè)狀態(tài)的有效收費(fèi)路段覆蓋集合指的是狀態(tài)對(duì)應(yīng)的路徑上所有原子路段所屬的有效收費(fèi)路段集合的并集；

25)如果新狀態(tài)對(duì)應(yīng)的路徑長(zhǎng)度大于等于該最小值，則返回步驟22)并選擇下一個(gè)原子路段，否則接納該狀態(tài)到歷史狀態(tài)中；

3)如果新狀態(tài)沒有抵達(dá)終點(diǎn)，則將該新狀態(tài)插入到優(yōu)先隊(duì)列中的有序位置，再回到步驟2)以繼續(xù)擴(kuò)展新的狀態(tài)；

如果新狀態(tài)抵達(dá)了終點(diǎn)，則表示該狀態(tài)對(duì)應(yīng)了一條完美路徑或該狀態(tài)將被用來嘗試更新當(dāng)前的最佳路徑；若該狀態(tài)對(duì)應(yīng)了一條完美路徑，則直接返回該完美路徑；

通過上述步驟，實(shí)現(xiàn)基于啟發(fā)式搜索的高速路網(wǎng)約束尋路。

2.如權(quán)利要求1所述基于啟發(fā)式搜索的高速路網(wǎng)約束尋路算法，其特征是，步驟1)生成有效收費(fèi)路段的集合，建立從路網(wǎng)中的原子路段到所在收費(fèi)路段集合的映射，具體包括如下步驟：

11)建立一個(gè)空映射，將原子路段映射到所屬的有效收費(fèi)路段的集合；建立一個(gè)有效收費(fèi)路段的空集；

12)遍歷輸入的所有收費(fèi)路段，執(zhí)行步驟13)～16)；

13)從路網(wǎng)中取得當(dāng)前收費(fèi)路段包含的原子路段列表；如果該列表為空，即沒有屬于該收費(fèi)路段的原子路段存在于指定路網(wǎng)中，則回到步驟12)并選擇下一個(gè)收費(fèi)路段，否則將該收費(fèi)路段添加到有效收費(fèi)路段集合中；

14)遍歷取得的原子路段列表中的每一條原子路段，重復(fù)執(zhí)行步驟15)；

15)如果該原子路段已在映射的定義域中，則將當(dāng)前收費(fèi)路段添加到原子路段映射后的收費(fèi)路段集合中，并更新映射，否則，將該原子路段添加到映射的定義域中，并使其映射后的值為只包含該收費(fèi)路段的單元集；

16)返回步驟12)并選擇下一個(gè)收費(fèi)路段。