《基於路徑和權的最短路徑搜尋方法》是珠海市規劃設計研究院於2016年3月10日申請的專利，該專利的公布號為CN105512169A，授權公布日為2016年4月20日，發明人是趙自力、段莊、但秋君、楊炯、魏金占、崔佳。
《基於路徑和權的最短路徑搜尋方法》旨在提供一種基於路徑和權的最短路徑搜尋方法，包括以下步驟：1）每段路的路徑長度為真實距離除以權值；2）將待分析區域內各條道路連線；3）連線起始點和終點得到連線線，得到多個初始路徑多邊形；4）將多個初始路徑多邊形合併，得到外包多邊形；5）以連線線為界，取得外包多邊形的起始左路徑及起始右路徑；6）用較短的連線代替起始路徑對應兩點的連線線，依次搜尋得到新左路徑和新右路徑；7）若新左路徑和新右路徑有重疊，重疊部分必為最短路徑部分，若新左路徑和新右路徑未重疊，得到最終左路徑和最終右路徑；8）合併最終左路徑和最終右路徑內的中間多邊形，得到合併多邊形；9）將新左右路徑公共部分與求得的結果合併，得到最終最短路徑。該發明搜尋效率和精度高，可在當前各大空間數據處理軟體平台實現。
2020年7月14日，《基於路徑和權的最短路徑搜尋方法》獲得第二十一屆中國專利獎優秀獎。
（概述圖為《基於路徑和權的最短路徑搜尋方法》摘要附圖）
基本介紹
- 中文名：基於路徑和權的最短路徑搜尋方法
- 申請人：珠海市規劃設計研究院
- 申請日：2016年3月10日
- 申請號：2015107906365
- 公布號：CN105512169A
- 公布日：2016年4月20日
- 發明人：趙自力、段莊、但秋君、楊炯、魏金占、崔佳
- 地址：廣東省珠海市香洲梅華東路302號
- Int. Cl.：G06F17/30(2006.01)I、G06Q10/04(2012.01)I
- 類別：發明專利
專利背景,發明內容,專利目的,技術方案,改善效果,附圖說明,技術領域,權利要求,實施方式,榮譽表彰,
專利背景
最短路徑搜尋常見有Dijkstra算法（單源最短路徑）、Floyd算法（插點法）、AStar算法（啟發式最短路徑算法）等，其中最著名的算法是Djikstra算法。此算法的實現基於圖的鄰接矩陣表示法，它不僅能夠找到任意兩點的最短路徑，還可以找到某個指定點到其他所有頂點的最短路徑。Dijkstra算法雖然簡單，但需搜尋範圍內所有路徑，如網內節點數非常大，則計算效率將急劇下降。Floyd算法的優點是提出了初始條件，避免了Dijkstra算法搜尋的無目的性，搜尋效率有很大提高，但是其假設的初始路徑仍與整個搜尋範圍內節點數有關，搜尋效率依然不高且最終結果不一定是最短路徑。AStar算法實際是一種啟發式搜尋，就是利用一個估價函式評估每次搜尋的路徑，決定選用合適的評估函式。這樣可以極大的最佳化普通的廣度優先的路徑搜尋，但是搜尋準確度受到估價函式的影響，其結果不一定是最短路徑。
以上方法雖然可以實現最短路徑搜尋問題，但存在如下缺點和不足：1）搜尋效率低，搜尋結果與效率難以得到均衡；2）處理過程複雜，算法雖然成熟，卻未能結合空間關係提升搜尋效率和準確率；3）道路情況各異，當前最短路徑搜尋算法多考慮幾何最短路徑，很少能動態及時根據路況實時更新最短路徑且需要重新再次搜尋。
發明內容
專利目的
《基於路徑和權的最短路徑搜尋方法》的目的在於提供一種基於路徑和權的最短路徑搜尋方法。該發明將結合各種算法的優點，提出一種全新的最短路徑搜尋算法，將最短路徑搜尋擴展到面層，利用點線面的拓撲關係，實現不受搜尋範圍影響的、可根據道路情況調整權值、簡單高效的最短路徑搜尋。
技術方案
《基於路徑和權的最短路徑搜尋方法》包括以下步驟：
1）首先將不同類型的道路賦予不同的權值，每段路的路徑長度為真實距離除以權值；
2）再將待分析區域內各條道路連線，空間拓撲分析，將區域內的道路線構面；
3）直線連線起始點和終點得到連線線，對連線線通過地理信息系統平台的空間查詢功能進行空間查詢分析，得到與連線線空間相交的多個初始路徑多邊形；
4）將得到的多個初始路徑多邊形通過地理信息系統平台合併，得到外包多邊形；
5）以連線線為界，方向為起始點到終點，取得外包多邊形的起始左路徑及起始右路徑，取起始左路徑和起始右路徑為起始路徑；
6）以該起始路徑為準，從起始點開始，依次檢查多個路徑多邊形，若起始路徑中該段兩端的連線線路徑長度大於對應路徑多邊形中另一邊的連線的路徑長度，用較短的連線代替起始路徑對應兩點的連線線，依次搜尋得到新左路和新右路徑；
7）以新左路徑和新右路徑為起算，若新左路徑和新右路徑有重疊，新左右路徑公共部分，則重疊部分必為最短路徑部分，若新左路徑和新右路徑未重疊，以新左路徑和新右路徑的相交點為分割點，將相鄰的新左右路徑多邊形中新左路徑和新右路徑通過的、且具有公共邊的多邊形合併，重複以上步驟6、7，得到最終左路徑和最終右路徑；
8）合併最終左路徑和最終右路徑內的中間多邊形，得到合併多邊形，求得兩相鄰左右路徑交點間的路徑，取短者為結果；
9）再次將新左右路徑公共部分與求得的結果合併，得到最終最短路徑。
上述步驟1）包括以下步驟：
11）首先將道路根據不同的等級，分別賦予不同的權值；
12）取得每段道路的實際長度；
13）將長度與權值相除，得到每段路的路徑長度。
上述步驟2）包括以下步驟：
21）通過地理信息系統平台檢查道路連線拓撲錯誤，確保每條道路正確的連線關係；
22）通過地理信息系統平台進行空間拓撲分析，將區域內的道路拓撲構面；
23）通過地理信息系統平台檢查拓撲構面錯誤，如出現斷頭路等，不參與構面；
24）構面成功後的多邊形應該依次相連，共點或共邊；
25）若出現未依次相連的多邊形，檢查錯誤，若存在錯誤，重複步驟22）、23）、24）；
26）若不存在錯誤，則未連線多邊形之間路徑孤立邊必為最短路徑的一部分，記錄該孤立線段。
上述步驟3）包括以下步驟：
31）連線起始點和終點，得到兩點間的連線線，即為兩點間的理論最短距離；
32）以連線線為準，通過地理信息系統平台空間查詢與連線線有空間相交的多個初始路徑多邊形。
上述步驟4）包括以下步驟：
41）通過地理信息系統平台檢查查詢得到多個初始多邊形，若依次相連，則將多邊形地理信息系統平台合併，得到外包多邊形，進入步驟5）；
42）若存在不相連情況，則通過地理信息系統平台將相連的部分多邊形合併，轉入步驟43）；
43）記錄合併後的外包多邊形，若存在孤立線，該連線路徑必為最短路徑的一部分。
上述步驟5）包括以下步驟：
51）以連線線為界，方向為終點到起始點；
52）若路徑多邊形不連線，以孤立線為公共部分，則左右邊線與孤立線分別相連即為左邊線和右邊線；
53）若路徑多邊形連線，取得該外包多邊形的起始左路徑及起始右路徑，作為起始路徑。
上述步驟6）包括以下步驟：
61）以該起始路徑為準，從起始點開始，依次檢查多個初始路徑多邊形，若起始路徑中該段兩端的連線線路徑長度大於路徑多邊形中另一邊的連線的路徑長度，用較短的連線代替起始路徑對應兩點的連線線；
62）依次搜尋每一個路徑多邊形，得到新左路徑和新右路徑。
上述步驟7）包括以下步驟：
71）若新左路徑和新右路徑有重疊，則重疊部分必為最短路徑部分；
72）若新左路徑和新右路徑未重疊，以新左路徑和新右路徑相交點為分割點，將相鄰新左路徑和新右路徑通過的、且具有公共邊的左右路徑多邊形合併：
73）重複以上步驟6、7，得到最終左路徑和最終右路徑。
上述步驟8）包括以下步驟：
81）合併最終左路徑和最終右路徑包含的路徑中間多邊形，得到合併多邊形；
82）以合併多邊形為準，求得兩相鄰分割點間的最短左路徑和最短右路徑，取短者為結果。
上述步驟9）包括以下步驟：
91）若不是是斷頭路，再次將新左右路徑公共部分與求得的結果合併，得到最終最短路徑19；
92）若是斷頭路，搜尋得到的最短路徑連線斷頭路即為最終的最短路徑。
改善效果
《基於路徑和權的最短路徑搜尋方法》的最短路徑搜尋方法優選用城市複雜道路情況的最短路徑搜尋環境。該發明通過將最短路徑搜尋方法的傳統算法擴展到空間領域，利用空間關係及最短路徑的要求，既實現了初始路徑的快速化確定，搜尋算法的科學化，又實現了搜尋過程效率的高效化。該方法可以在各大空間數據處理平台實現，具有原理簡單，易於實現，高效穩定的特點，可以大大提升搜尋效率和準確度。
附圖說明
圖1為《基於路徑和權的最短路徑搜尋方法》的流程示意圖；
圖2至圖9為該發明基於路徑和權的最短路徑搜尋方法實施例的搜尋過程示意圖。
技術領域
《基於路徑和權的最短路徑搜尋方法》涉及數學與計算機圖形學領域，具體涉及一種基於路徑和權的最短路徑搜尋方法。
權利要求
1.一種基於路徑和權的最短路徑搜尋方法，其特徵在於包括以下步驟：
1）首先將不同類型的道路賦予不同的權值，每段路的路徑長度為真實距離除以權值；
2）再將待分析區域內各條道路連線，空間拓撲分析，將區域內的道路線構面；
3）直線連線起始點和終點得到連線線，對連線線通過地理信息系統平台的空間查詢功能進行空間查詢分析，得到與連線線空間相交的多個初始路徑多邊形；
4）將得到的多個初始路徑多邊形通過地理信息系統平台合併，得到外包多邊形；
5）以連線線為界，方向為起始點到終點，取得外包多邊形的起始左路徑及起始右路徑，取起始左路徑和起始右路徑為起始路徑；
6）以該起始路徑為準，從起始點開始，依次檢查多個路徑多邊形，若起始路徑中該段兩端的連線線路徑長度大於對應路徑多邊形中另一邊的連線的路徑長度，用較短的連線代替起始路徑對應兩點的連線線，依次搜尋得到新左路和新右路徑；
7）以新左路徑和新右路徑為起算，若新左路徑和新右路徑有重疊，新左右路徑公共部分，則重疊部分必為最短路徑部分，若新左路徑和新右路徑未重疊，以新左路徑和新右路徑的相交點為分割點，將相鄰的新左右路徑多邊形中新左路徑和新右路徑通過的、且具有公共邊的多邊形合併，重複以上步驟6、7，得到最終左路徑和最終右路徑；
8）合併最終左路徑和最終右路徑內的中間多邊形，得到合併多邊形，求得兩相鄰左右路徑交點間的路徑，取短者為結果；
9）再次將新左右路徑公共部分與求得的結果合併，得到最終最短路徑。
2.根據權利要求1所述的基於路徑和權的最短路徑搜尋方法，其特徵在於上述步驟1）包括以下步驟：
11）首先將道路根據不同的等級，分別賦予不同的權值；
12）取得每段道路的實際長度；
13）將長度與權值相除，得到每段路的路徑長度。
3.根據權利要求1所述的基於路徑和權的最短路徑搜尋方法，其特徵在於上述步驟2）包括以下步驟：
21）通過地理信息系統平台檢查道路連線拓撲錯誤，確保每條道路正確的連線關係；
22）通過地理信息系統平台進行空間拓撲分析，將區域內的道路拓撲構面；
23）通過地理信息系統平台檢查拓撲構面錯誤，如出現斷頭路等，不參與構面；
24）構面成功後的多邊形應該依次相連，共點或共邊；
25）若出現未依次相連的多邊形，檢查錯誤，若存在錯誤，重複步驟22）、23）、24）；
26）若不存在錯誤，則未連線多邊形之間路徑孤立邊必為最短路徑的一部分，記錄該孤立線段。
4.根據權利要求1所述的基於路徑和權的最短路徑搜尋方法，其特徵在於上述步驟3）包括以下步驟：
31）連線起始點和終點，得到兩點間的連線線，即為兩點間的理論最短距離；
32）以連線線為準，通過地理信息系統平台空間查詢與連線線有空間相交的多個初始路徑多邊形。
5.根據權利要求1所述的基於路徑和權的最短路徑搜尋方法，其特徵在於上述步驟4）包括以下步驟：
41）通過地理信息系統平台檢查查詢得到多個初始多邊形，若依次相連，則將多邊形地理信息系統平台合併，得到外包多邊形，進入步驟5）；
42）若存在不相連情況，則通過地理信息系統平台將相連的部分多邊形合併，轉入步驟43）；
43）記錄合併後的外包多邊形，若存在孤立線，該連線路徑必為最短路徑的一部分。
6.根據權利要求1所述的基於路徑和權的最短路徑搜尋方法，其特徵在於上述步驟5）包括以下步驟：
51）以連線線為界，方向為終點到起始點；
52）若路徑多邊形不連線，以孤立線為公共部分，則左右邊線與孤立線分別相連即為左邊線和右邊線；
53）若路徑多邊形連線，取得該外包多邊形的起始左路徑及起始右路徑，作為起始路徑。
7.根據權利要求1所述的基於路徑和權的最短路徑搜尋方法，其特徵在於上述步驟6）包括以下步驟：
61）以該起始路徑為準，從起始點開始，依次檢查多個初始路徑多邊形，若起始路徑中該段兩端的連線線路徑長度大於路徑多邊形中另一邊的連線的路徑長度，用較短的連線代替起始路徑對應兩點的連線線；
62）依次搜尋每一個路徑多邊形，得到新左路徑和新右路徑。
8.根據權利要求1所述的基於路徑和權的最短路徑搜尋方法，其特徵在於上述步驟7）包括以下步驟：
71）若新左路徑和新右路徑有重疊，則重疊部分必為最短路徑部分；
72）若新左路徑和新右路徑未重疊，以新左路徑和新右路徑相交點為分割點，將相鄰新左路徑和新右路徑通過的、且具有公共邊的左右路徑多邊形合併：
73）重複以上步驟6、7，得到最終左路徑和最終右路徑。
9.根據權利要求1所述的基於路徑和權的最短路徑搜尋方法，其特徵在於上述步驟8）包括以下步驟：
81）合併最終左路徑和最終右路徑包含的路徑中間多邊形，得到合併多邊形；
82）以合併多邊形為準，求得兩相鄰分割點間的最短左路徑和最短右路徑，取短者為結果。
10.根據權利要求1所述的基於路徑和權的最短路徑搜尋方法，其特徵在於上述步驟9）包括以下步驟：
91）若不是是斷頭路，再次將新左右路徑公共部分與求得的結果合併，得到最終最短路徑19；
92）若是斷頭路，搜尋得到的最短路徑連線斷頭路即為最終的最短路徑。
實施方式
- 實施例1
該實施例基於路徑和權的最短路徑搜尋方法，包括以下步驟：
該實施例某市主城區兩點間最短路徑搜尋，運行平台為PC上的Windows7作業系統，地理信息系統開發平台為北京超圖地理信息平台軟體5.3.3版本。
為了準確定義概念，確保語言表述的正確性及便於程式實現，特對以下內容進行說明及定義：節點：道路的特徵點；度：節點連線線的條數，度為2是為普通節點，度大於2為結點；結點：不同道路的交點；道路：自然道路；路徑多邊形：所有弧段圍成的區域。四者關係：節點為道路的特徵點，兩端（度大於2）時，即為結點。臨近結點連線即為弧段，結點的度大於2。弧段為這些多邊形的邊界，每個弧段為兩個相鄰多邊形的公共邊即空間關係為相交。
具體步驟如下：
1）首先將不同類型的道路賦予不同的權值，每段路的路徑長度為真實距離除以權值；
2）再將待分析區域內各條道路連線，通過北京超圖地理信息平台軟體的空間拓撲功能進行分析，將區域內的道路線通過北京超圖地理信息平台軟體的空間數據處理功能構面；
3）直線連線圖2所示起始點1和終點2，對連線線3通過北京超圖地理信息平台軟體的空間查詢功能進行空間查詢分析，得到與該連線線3空間相交的多個圖2所示的初始路徑多邊形4；
4）通過北京超圖地理信息平台軟體將初始路徑多邊形4合併，得到該連線線的圖2所示外包多邊形5；
5）以圖2所示連線線3為界，方向為圖2終點1到圖2起點2，取得圖3外包多邊形1的初始左路徑6及初始右路徑7，取圖3初始左路徑6和初始右路徑7為起始路徑；
6）以該起始路徑為準，從圖2起點1開始，依次檢查圖2多個路徑多邊形4，若起始路徑中該段兩端的連線線路徑長度大於對應路徑多邊形中另一邊的連線的路徑長度，用較短的連線代替起始路徑對應兩點的連線線，依次搜尋得到圖4所示新左路徑9和新右路徑10；
7）以圖4所示新左路徑9和新右路徑10起算，若新左路徑9和新右路徑10重疊，則重疊部分圖4所示的新左右路徑公共部分11必為最短路徑部分，若新左路徑9和新右路徑100未重疊，以相鄰的圖5所示的左右路徑交點15為分割點，通過北京超圖新左路徑9和新右路徑10通過的、且具有公共邊的左右路徑多邊形合併，重複以上步驟6、7，得到最終的路徑13和最終右路徑14；
8）合併圖5所示最終左路徑13和最終右路徑14內的多邊形，得到圖6所示的合併多邊形16，求得兩相鄰圖5所示的最終左右路徑交點15間左右兩邊的路徑，取短者為結果；
9）通過北京超圖地理信息平台軟體的空間數據處理功能，再次將圖4所示的新左右路徑公共部分11與求得的結果合併，得到圖8所示最終最短路徑19。
步驟1包括以下步驟：
11）首先將道路根據不同的等級，分別賦予不同的權值P，如主幹道權值為1，次幹道為0.8，支路為0.6；
12）取得每段道路的實際長度L；
13）將長度與權值相除，得到每段路的路徑長度L/P；
步驟2包括以下步驟：
21）通過北京超圖地理信息平台軟體檢查道路連線拓撲錯誤，對具有拓撲錯誤的路徑進行檢查，確保每條道路正確的連線關係；
22）通過北京超圖地理信息平台軟體進行空間線拓撲，將區域內的道路拓撲構面；
23）再次通過北京超圖地理信息平台軟體檢查拓撲構面錯誤，如出現斷頭路即檢查完畢後依然存在拓撲錯誤的道路，不參與構面；
24）通過北京超圖地理信息平台軟體構面成功後的多邊形應該依次相連，共點或共邊，空間關係為面面之間相切；
25）若出現未依次相連的多邊形，檢查錯誤，若存在錯誤，重複22）、23）、24）；
26）若不存在錯誤，則未連線多邊形之間路徑圖9所示孤立路徑1必為最短路徑的一部分，記錄該孤立線段；
步驟3）包括以下步驟：
31）若圖2所示起始點1或圖2所示終點2在斷頭路上，則將起始點1或終點2沿斷頭路搜尋到對應的路徑多邊形，以斷頭路與路徑多邊形的交點作為起始點1或終點2；
32）連線圖2所示起始點1和圖2所示終點1，得到兩點間的圖2所示連線線段3，即為兩點間的理論最短距離；
33）以連線線段為準，通過北京超圖地理信息平台軟體空間查詢與連線線有空間相交的圖2所示的多個路徑多邊形4；
步驟4包括以下步驟：
41）通過北京超圖地理信息平台軟體空間查詢得到的多個路徑多邊形4，若依次相連，則通過北京超圖地理信息平台軟體的空間數據處理功能將多邊形合併得到圖3所示的外包多邊形5，進入步驟5）；
42）若存在不相連情況，則通過北京超圖地理信息平台軟體將相連的部分多邊形合併得到圖3所示的外包多邊形5，轉入43）；
43）記錄合併後的外包多邊形之間連線圖9所示孤立線20，該連線路徑必為最短路徑的一部分；
步驟5包括以下步驟：
51）以圖2所示連線線3為界，方向為圖2所示終點2到圖2所示起始點1，取得圖3所示外包多邊形5的初始左邊線6和初始右邊線7；
52）若路徑多邊形不連線，則圖9所示左邊線21和右邊線22與孤立線20分別相連即為初始左邊線6和初始右邊線7；
53）以初始左邊線6和初始右邊線7為起始路徑，進入步驟6；
步驟6）包括以下步驟：
61）以該起始路徑為準，從起點開始，依次檢查圖2所示的多個初始路徑多邊形4，若起始路徑中該段兩端的連線線路徑長度大於路徑多邊形中另一邊的連線的路徑長度，用較短的連線代替起始路徑對應兩點的連線線；
62）依次搜尋每一個路徑多邊形，得到新的圖4所示新左路徑9和新右路徑10；
步驟7）包括以下步驟：
71）以圖4所示新左路徑9和新右路徑10為起算，若新左路徑9和新右路徑10有重疊圖4所示的新左右路徑公共部分11，則重疊部分必為最短路徑部分；
72）若新左路徑9和新右路徑10未重疊，以圖5所示的臨近左右路徑交點15為起始點，通過北京超圖地理信息平台軟體的空間數據處理功能將相鄰、新左路徑9和新右路徑10通過的且具有公共邊的多邊形合併；
73）重複以上步驟6、7，最終得到圖5所示的最終左路徑13和最終右路徑14，最終左路徑13和最終右路徑14的交點是最終左右路徑交點15；
步驟8）包括以下步驟：
81）通過北京超圖地理信息平台軟體的空間數據處理能力合併圖5所示最終左路徑13和最終右路徑14內的多邊形，得到圖6所示的多個合併多邊形16；
82）求得兩相鄰分割點間左右兩邊的最短左路徑17和最短右路徑18，圖7所示，取短者為結果；
步驟9包括以下步驟：
91）若不是是斷頭路，再次將圖4所示的新左右路徑公共部分11與求得的結果合併，得到圖8所示最終最短路徑19；
92）若是斷頭路，搜尋得到的最短路徑連線斷頭路即為最終的最短路徑。
榮譽表彰
2020年7月14日，《基於路徑和權的最短路徑搜尋方法》獲得第二十一屆中國專利獎優秀獎。
