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

在審

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

本發明請求保護一種基于改進Floyd算法的交通網絡線路優化方法，該方法包括：建立城市交通網絡拓撲模型；將選取節點的平均度、網絡直徑、平均路徑、網絡效率和平均聚類系數匯總分析結果；利用改進的Floyd算法縮短運行時長，提高仿真效率；改進節點之間的邊權值，再對比二次仿真的結果；重新改變交通網絡圖，對比三次仿真結果，優化了交通網絡的工作效率。

技術領域

本發明屬于數據分析領域，涉及一種基于Floyd算法改進應用于交通網絡上 的方法。

背景技術

根據2019年人民日報大數據統計，2019年國慶假期全國共接待國內游客7.82 億人次，同比增長7.81％，再次刷新紀錄。這一方面說明我們國家的人民確實富 裕了，但從另一方面來看，我國交通設施的建設也取得了不錯的成果才能跟得 上龐大的人群流動帶來的交通挑戰。

我國正處于城市化進程的關鍵建設階段，而城市的基礎交通建設正是和大 眾生活息息相關的重要基礎建設，就使用搭乘成本而言，公交基本都是全程兩 元，絕大部分市民都可以承擔起這項費用，這是一項福利性社會公共服務項目， 符合人民的根本利益。現在重慶市公共交通體系呈多態式發展，輕軌和公交共 行豐富了重慶市的公共交通運輸手段，也提高了公共交通的綜合承載運輸能力。 但是作為典型的山地城市，重慶市市民相比于平原地區人民更加依賴于公交出 行，而且從可持續發展性和易建設性來看，公交系統擁有資金投入較低、運營 時間較靈活、投入產出高等不少優勢。不過從重慶市的空間形態看，由于地形 和往年發展原因，重慶市呈現多中心發展趨勢，而且由于是山城，重慶市基本 都是由主干道承擔交通壓力，路網的連接度不夠。尤其是當前人口因為政策改 變呈上升趨勢加上城市化規模的迅速擴張，公交網絡受到了周期性通勤壓力， 有時由于天氣情況和特殊重大事件的發生，這都會導致公交網絡的可靠性下降， 有時還會導致局部交通癱瘓。所以需盡快地找到一個新的方法使重慶市交通網 絡運行效率提升，優化公交線路網絡，讓重慶的公交網絡得到進一步發展和完 善。

現在的研究中主要是利用dijkstra算法計算點與點之間的最短距離，但是如 果圖中節點過多，dijkstra算法會運行較慢，所以本次采用Floyd算法進行仿真。

發明內容

本發明旨在解決以上現有技術的問題。提出了一種基于改進Floyd算法的交 通網絡線路優化方法。本發明的技術方案如下：

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

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

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

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

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

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

進一步的，所述步驟一建立目標城市的交通網絡模型，具體為：在交通 部最新發布的城市地圖上截取觀測地點，對節點信息進行處理得到一個節點為 500邊數為7125的公交網絡，利用PAJEK軟件繪制出城市交通網絡拓撲模型， 以便觀測增添修改情況。

進一步的，所述步驟二具體步驟如下：