[發明專利]一種基于虛擬邊界的動態橢圓限制搜索區域最短路徑方法

在審

• 申請號: 202110232834.5
• 申請日: 2021-03-03
• 公開（公告）號: CN112800353A
• 公開（公告）日: 2021-05-14
• 發明（設計）人: 魏海濤;張述勝;赫曉慧
• 申請（專利權）人: 鄭州大學
• 主分類號: G06F16/9537
• 分類號: G06F16/9537;G06Q10/04;G06Q10/08
• 代理公司: 鄭州科維專利代理有限公司 41102
• 代理人: 李天霞

1.一種基于虛擬邊界的動態橢圓限制搜索區域最短路徑方法，其特征在于，包括以下步驟：

1）給出路網的矢量數據，在交通網絡節點集合中系統抽取具有代表性的一定數目的節點，構造兩個節點集合并求得其笛卡爾乘積，則笛卡爾乘積中的每個元素可以看成是待求最短路徑的起終結點；

設起終結點實際距離為F_OD，歐式距離為E_OD，則可求得比值系數R=F_OD/E_OD。對于所抽取樣本，則可得到比值系數集合R_OD；對R_OD中的元素在一定的置信水平下進行統計分析擬合，可以得到某一擬合函數f(x)，使得R_OD中總數為滿足一定置信水平的元素，其值不大于f(x)；

2）給出起始節點和終止節點，并計算兩點之間的歐式距離；將兩點之間的歐式距離α代入擬合函數中得出一個比值系數R；以起始節點和終止節點作為焦點，以Rα為長軸長建立橢圓限制搜索區域；

OD對在橢圓搜索區域內得不到最優路徑的完整解S時，通過構造虛擬邊界作為虛擬解VS=(vs_i,…,vs_j)代替橢圓區域外的解，從而在橢圓區域內得到虛擬完整解S’= (s₁,s₂,…,vs_i,…,vs_j,…,s_n)；然后分別對每段連續的虛擬解根據起點和終點在橢圓外尋找最優完整解OS=(s_i,…,s_j)；最后將OS中的解代替S’中的虛擬解即可得到最優路徑的完整解S=(s₁,s₂,…,s_i,…,s_j,…,s_n)；

3）在路網中隨機選取一定數量的樣本元素，計算出所有樣本元素在不同置信水平下得到路徑最優解的概率；選取較低置信水平下的得到最優解概率最大的統計參數函數作為路網最終的統計參數函數。

2.根據權利要求1所述的一種基于虛擬邊界的動態橢圓限制搜索區域最短路徑方法，其特征在于：所述步驟3中得到的統計參數是由一定置信水平下的比值系數點擬合得到的統計參數函數。