[發明專利]簡化路網KSP優化算法

有效

• 申請號: 202010139515.5
• 申請日: 2020-03-03
• 公開（公告）號: CN111369052B
• 公開（公告）日: 2021-02-12
• 發明（設計）人: 李向農;高文杰;范丁元;吳青松;王京偉;張夢心;高明陽;盧立川;孟昕馨;彬德麗婭
• 申請（專利權）人: 中鐵工程設計咨詢集團有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06F30/18
• 代理公司: 北京集智東方知識產權代理有限公司 11578
• 代理人: 陳亞斌;關兆輝

本發明屬于交通網絡規劃和交通路徑分析領域，具體涉及簡化路網KSP優化算法。將網絡節點分為枝節點、中間節點和真節點；消除所述枝節點和所述中間節點后的路網稱為簡化路網；路網多路徑計算只需在所述簡化路網上計算真節點間的多條路徑。其中，所述枝節點定義為：在路網中相鄰節點非枝節點數不大于1的節點，所述中間節點定義為在路網中相鄰非枝節點數為2的節點，真節點定義為既非枝節點又非中間節點的節點。本發明提供的算法能夠滿足多路徑計算結果的計算和存儲，提高算法的通用性，從而提高鐵路運量設計、路網規劃、徑路查詢的效率和科學性。

技術領域

本發明屬于交通網絡規劃和交通路徑分析領域，具體涉及簡化路網KSP優化算法。

背景技術

在交通規劃和交通網絡分析中，經常需要計算全部交通網絡中每個節點對之間的K條較短徑路(K短路徑或KSP問題)，但隨著路網規模的擴大，其計算復雜度和空間復雜度呈指數增長。有效減少KSP問題計算和空間復雜度，對內存限制下KSP算法可行性和軟件的實時反應能力，對提高交通網絡規劃的效率和科學性具有重要意義。

目前國內外對路網KSP的經典算法主要有YEN的網絡無環K短徑路算法和Floyd擴展算法。YEN算法主要用于計算一對節點間的K短路徑，其計算復雜度為O(KN³)(其中K為徑路數，N為節點數，下同)，計算全部節點對間K短路徑時，計算復雜度為O(KN⁵)，空間復雜度為O(KN³)；Floyd擴展算法便于計算全部節點對間K短路徑，其計算復雜度為O(K²N³)，空間復雜度為O(KN²)，當N＝1000，K＝10000時，YEN算法復雜度和空間復雜度數量級分別為10¹⁹、10¹⁴，Floyd擴展算法將分別為10¹⁷、10¹⁰。可以看出，對現狀PC計算機4G內存配置下空間復雜度已不可接受，為計算大規模路網的多條數K短路徑，有必要尋求降低節點規模或復雜度的方法。

發明內容

針對上述技術問題，本發明提供一種簡化路網KSP優化算法，通過將網絡節點劃分為真節點、中間節點和枝節點，將真正參與計算的節點限定為真節點，其他節點間路徑根據真節點KSP算法結果簡單導出，從而大大縮短算法和空間復雜度。

本發明是通過以下技術方案實現的：

簡化路網KSP優化算法，包括：

將網絡節點分為枝節點、中間節點和真節點；所述枝節點定義為：在路網中與枝節點相鄰的節點為非枝節點的數量不大于1，所述中間節點定義為：在路網中與中間節點相鄰的節點為非枝節點的數量為2，真節點定義為既非枝節點又非中間節點的節點；

消除所述枝節點和所述中間節點后的路網稱為簡化路網；

路網多路徑計算只需在所述簡化路網上計算真節點間的多條路徑。

進一步地，在所述簡化路網上計算真節點間的多條路徑，具體方法為：

將真節點i和真節點j間的第k條路徑R_ij(k)用以下數據結構遞歸表示：

{v,R_iv(k_i),R_vj(k_j)}；

其中，v為真節點i到真節點j的經由節點；R_iv(k_i)表示真節點i至真節點v間的第k_i條徑路；R_vj(k_j)表示真節點v至真節點j間的第k_j條徑路；

真節點對間K短路徑的計算采用Floyd擴展算法進行計算。

進一步地，所述枝節點包括如下特征：