[發明專利]一種基于動態路網信息的最優路徑分析方法

在審

• 申請號: 202111456613.2
• 申請日: 2021-12-02
• 公開（公告）號: CN114418165A
• 公開（公告）日: 2022-04-29
• 發明（設計）人: 張永智;歐平均;徐克強
• 申請（專利權）人: 杭州衣科信息技術股份有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06F16/29;G06Q50/26;G06Q50/30
• 代理公司: 杭州天昊專利代理事務所(特殊普通合伙) 33283
• 代理人: 趙志鵬

1.一種基于動態路網信息的最優路徑分析方法，其特征在于：具體步驟如下：

101)數據采集步驟：采集每個路徑上路段的靜態信息和動態信息，靜態信息包括路段的長度、路況、地理位置等，動態信息包括發生事故、車流量大小、指示燈狀況、大霧天氣等路況變化實時信息；

102)數據接入步驟：將需要分析的起始地址和終點地址接入，獲取兩地址之間的所有路段的靜態信息和動態信息；

103)緩存數據步驟：采用集中式緩存機制將步驟101)采集的數據進行緩存，將各個服務器共用一個緩存服務器，當發生緩存不夠用時，通過新增緩存服務器來解決；即將新增的緩存服務器與之前的緩存服務器構成新的大空間的緩存服務器；

104)數據分析步驟：將緩存的數據通過分割并行計算進行運算分析處理，分割并行計算是將整個數據形成的有向圖先分成若干區域，然后先計算出各區域間的最優路徑對，形成一個上層的主干網；基于該主干網，再分析兩點間最優路徑時，只要先分析出源點和終點距自身所在區域邊界點的最優路徑，然后結合源區域和終點區域之間的主干最優路徑，快速得出最終的最優路徑。

2.根據權利要求1所述的一種基于動態路網信息的最優路徑分析方法，其特征在于：靜態信息包括權重屬性參數和極值屬性參數，路段的權重屬性參數通過累計疊加獲得整合后路段的權重屬性參數，權重屬性參數包括路段的長度、路段的收費額等；路段的極值屬性參數只獲取整合后路段中的其中一段的最大值或最小值。

3.根據權利要求1所述的一種基于動態路網信息的最優路徑分析方法，其特征在于：采集每個路徑上路段的靜態信息采用定時人工現場采集，動態信息采用人工采集、GPS位置采集、視頻監控識別采集的方式進行。

4.根據權利要求1所述的一種基于動態路網信息的最優路徑分析方法，其特征在于：集中式緩存機制包括數據構造方法；

數據構造方法，其定義以一個節點為源點，到其余各節點最優路徑的緩存內容；若到某點的最優路徑還未求出，則其點集標志為false；具體通過類DijCacheItem實現，類DijCacheItem內部有Dij方法、addOneStation方法、addToRedSet方法和addBlueSet方法；

DijData方法，用于存放各頂點的最短路徑權值；

addOneStation方法，實現在一個源點的cache項中，動態追加一個站點，并對該站點的cache值作初始化；

addToRedSet方法，把藍點集中的一個點移動到紅點集中，紅點集中的點為已經找到最優路徑的點，藍點集中的點為未找到最優路徑的點；

addToBlueSet方法，把紅點集中的點取消撤回到藍點集中，常用于動態站點移除的場合。

5.根據權利要求1所述的一種基于動態路網信息的最優路徑分析方法，其特征在于：集中式緩存機制包括緩存命中方法；

緩存命中方法在進行路徑數據分析之前，先根據起始地址和終點地址的索引號、權重類型參數，從緩存池中查找有無對應的緩存項；若沒有找到，則新建一個緩存項，并加入緩存池；若找到了，則在這個緩存項的基礎上繼續進行最優路徑分析；

若目標點的最優路徑在上述緩存項中已經進行過相同分析，則可以直接命中返回；否則需要在已有的路徑分析基礎上繼續按常規的方法進行路徑分析，直至找到目標點為止；同時把結果作為新的緩存內容加入到原有緩存中；

若進行路徑數據分析時附帶了分析條件，則此時緩存機制失效，只能按常規路徑分析方法進行。