[發明專利]一種面向虛擬地球的最短路徑分層規劃方法

有效

• 申請號: 201710218708.8
• 申請日: 2017-04-05
• 公開（公告）號: CN107092978B
• 公開（公告）日: 2020-11-03
• 發明（設計）人: 陳靜;董全華;劉婷婷;毛天陽
• 申請（專利權）人: 武漢大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 嚴彥

本發明提供一種面向虛擬地球的最短路徑分層規劃方法，包括面向虛擬地球的數據預處理過程和最短路徑分層規劃過程，所述面向虛擬地球的數據預處理過程，包括路網數據分層分塊組織，記錄格網點，上層瓦片局部最短路徑預存；所述最短路徑分層規劃過程，包括在分層路網的上層確定入點和出點，在上層路網中獲取入點和出點之間的最短路徑，在下層中確定入點和出點對應的格網點，在下層路網中獲取起點和入點之間、出點和終點之間的最短路徑，將上下兩層中的最短路徑連接起來，作為最終的最優路徑輸出。本發明在虛擬地球中運用最優路徑分層規劃方法，實現了大規模路網的最短路徑分析，同能夠實現大規模路網和最短路徑的高效可視化。

技術領域

本發明涉及三維地理信息路徑規劃應用領域，特別是涉及一種虛擬地球中基于多尺度路網數據的最短路徑規劃。

背景技術

在三維虛擬地球中，基于矢量空間數據，可以展開各種空間分析，最優路徑分析作為GIS的一個應用，在交通規劃，物流管理中發揮著關鍵的作用。隨著社會的進步，針對大規模復雜道路網的高效最優路徑規劃算法成為近幾年的一個研究熱點，其中面向虛擬地球采用分層技術處理大規模路網中的路徑規劃方面的研究較少。

在最短路徑的研究方面，目前較多的研究都是以DIJKSTRA算法為核心，在此基礎上結合不斷發展完善的數據結構、算法以及圖形學的相關理論，涌現出了Dijkstra算法改進的最短路徑算法。Sommer C.Shortest-path queries in static networks[J].ACMComputing Surveys(CSUR),2014,46(4):45；Rice M N.Algorithms for constrainedroute planning in road networks[J].2013；王少華,鐘耳順,張小虎等.最短路徑算法加速技術及其搜索空間分析[J].地理空間信息,2013,(6)；Delling D,Sanders P,SchultesD,et al.Engineering route planning algorithms[M].Algorithms of large andcomplex networks.Springer Berlin Heidelberg,2009:117-139；劉剛,李永樹.一種面向城市復雜路網最短路徑提取的定向收斂算法[J].計算機應用研究,2011,(6):2082-2084。以上這些文獻中對對最短路徑算法的改進主要集中在優化存儲結構以及排序算法、限制搜索空間等方面。

這些改進后的最短路徑算法在其適用條件下提高了路徑規劃的效率，但是Dijkstra算法自身的缺陷決定了它僅在小范圍的路徑規劃中有著廣泛的應用，而在處理海量大規模網絡數據時，計算過程復雜，內存消耗過大，因此不能應用于大范圍大尺度路網中的路徑規劃。