[發明專利]一種基于改進Floyd算法的交通網絡線路優化方法

在審

• 申請號: 202011443377.6
• 申請日: 2020-12-11
• 公開（公告）號: CN112529292A
• 公開（公告）日: 2021-03-19
• 發明（設計）人: 文凱;龍欣;羅菊;羅瑤
• 申請（專利權）人: 重慶郵電大學;重慶信科設計有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/30;G06K9/62
• 代理公司: 重慶市恒信知識產權代理有限公司 50102
• 代理人: 陳棟梁

1.一種基于改進Floyd算法的交通網絡線路優化方法，其特征在于，包括以下步驟：

步驟一：建立目標城市的交通網絡模型；

步驟二：在MATLAB中對步驟一的交通網絡模型數據進行獲取，將權值為1，Floyd算法未改進的原始模型的各項數據記錄匯編進行初步分析，分析其度分布、平均路徑和聚類系數的具體數據；

步驟三：利用無向圖的矩陣對稱性對Floyd算法進行改進，跳過了不存在的邊，減少了算法循環次數，用改進Floyd算法將其數值與正常算法數據相對比判斷結果；

步驟四：對步驟三的Floyd算法進行優化，改變邊權值帶入算法中，重新計算數據與原始數據進行第二次對比，判斷結果；

步驟五：優化不合理的交通線路布局再進行第三次數據對比，進行總結。

2.根據權利要求1所述的一種基于改進Floyd算法的交通網絡線路優化方法，其特征在于，所述步驟一建立目標城市的交通網絡模型，具體為：在交通部最新發布的城市地圖上截取觀測地點，對節點信息進行處理得到一個節點為500邊數為7125的公交網絡，利用PAJEK軟件繪制出城市交通網絡拓撲模型，以便觀測增添修改情況。

3.根據權利要求1所述的一種基于改進Floyd算法的交通網絡線路優化方法，其特征在于，所述步驟二具體步驟如下：

(1)對于得到的公交站點關系矩陣用{a_ij}表示，它們之間的距離用{d_ij}表示，當節點與節點之間有邊相連時a_ij＝1，d_ij＝1，沒有邊相接時a_ij＝0，d_ij＝∞；

(2)把節點i的度ki定義為與其他節點連接個數的數目，網絡中所有節點度的平均值就是平均度，記為N為所有節點的個數，所需公式如下(1)所示：

(3)所有節點的聚合系數的均值被定義為網絡的聚類系數，在網絡拓撲圖中，用節點的相鄰點之間具有連接邊的比例表示該網絡的聚類系數，用于衡量網絡拓撲圖中各節點間的聚類程度；

假設網絡中一個節點i有ki條邊，將它與其他ki個節點相連，這ki個節點就被視為i的鄰居。由于本次網絡圖是無向圖，這ki個節點中最多有條邊，這ki個節點之間實際存在的邊數和可能的總邊數之比就是節點i的聚類系數。所需公式如下(2)所示：

整個網絡的聚類系數C就是所有節點聚類系數Ci的平均值，且C≦1；

(4)網絡中任意兩個節點i、j之間的距離被定義為連接這兩個節點最短路徑上的邊權值之和，網絡中任意兩個節點的最大值稱為網絡的直徑，網絡的平均路徑長度定義為網絡中所有節點任意兩兩配對相連之間距離的平均值，所需公式如下(3)所示：

(5)統計500個站點的平均度、網絡直徑、平均路徑、網絡效率和平均聚類系數，分析結果；

(6)按照出現頻率高低選取前50個節點，依次刪除，重復(2)(3)(4)步驟，把結果匯聚成表；

(7)按照度值高低和聚類系數高低選取前20個節點，依次刪除，重復(2)(3)(4)步驟，分析數據；

(8)按照(6)(7)步驟的數據相對比，選取前10個單個節點刪除之后最影響平均路徑大小的站點依次重復(2)(3)(4)步驟，觀察網絡整體情況；

(9)將(6)(7)(8)步驟所得結果用圖表進行對比，得出結果。