[發明專利]一種基于空間節點聚類方法的快速公交換乘方法

有效

• 申請號: 201210504325.4
• 申請日: 2012-11-28
• 公開（公告）號: CN102982395A
• 公開（公告）日: 2013-03-20
• 發明（設計）人: 楊旭華;陳光;趙久強;汪向飛
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;王利強

技術領域

本發明涉及網絡科學和公共交通領域，特別是指一種基于空間節點聚類方法的快速公交換乘方法。

背景技術

城市公共交通系統是城市重要的基礎設施，它是維持城市有序運作的必要工具。當前我國正處于社會經濟快速發展期，大力發展城市交通、進行交通的合理規劃已被提上議題。作為城市交通運行的軟設施，城市公共交通服務系統承載了城市中大部分人群的出行。優化和完善城市公共交通服務系統，對緩解城市擁堵和改善乘客出行有著至關重要的作用。

解決城市公交換乘問題是完善城市公共交通服務系統的一個重要方面，因為它直接關系到積極有效地引導乘客合理、高效使用城市公共交通服務系統。傳統上人們在解決問題時，將公交站點看成網絡節點，將站點間通過公交車產生的連接看成網絡連邊，并依此生成一個網絡矩陣，然后使用成熟的Dijkstra算法（Floyd算法）即可運算得到任意公交站點對之間的換乘方案。然而這種傳統方法存在很多的不足。其中最主要的不足就是算法的運算時間過長，其計算特定站點對之間換乘的時間復雜度接近O(n²)（其中n為網絡中的節點個數）。所以對于大型網絡，在實際運用該方法時一般需要配合數據庫技術，預先花費一定時間計算所有站點對間的換乘方案并存入數據庫。當用戶查詢時，即可通過訪問數據庫查詢快速獲取換乘方案。

發明內容

為了克服已有的城市公交換乘算法計算時間過長、實時性較差的不足，本發明提出一種有效縮短計算時間、實時性良好的基于空間節點聚類方法的快速公交換乘方法。

本發明解決其技術問題所采用的技術具體步驟是：

一種基于空間節點聚類方法的快速公交換乘方法，包括以下步驟：

步驟一：建立城市公交站點的鄰近關系網絡T，在這個網絡中，當兩個站點間的物理空間距離小于等于閾值時，在兩個公交站點間存在一條連邊；

步驟二：使用空間節點聚類方法對網絡T進行站點聚類，所述聚類方法是通過查找網絡T中的所有最大完全子圖完成；

步驟三：將通過步驟二運算得到的最大完全子圖映射為節點，并由這些節點生成一個新的網絡P并進行存儲；

在網絡P中，當兩個節點在網絡T中對應的最大完全子圖間存在直接的公交線路連接時，這兩個節點間存在一條連邊；

步驟四：根據實際限制與實時路況信息，每隔設定時間更新調整網絡P的連邊的權值；

步驟五：確定用戶查詢指定的起始站點S與終止站點D各自在網絡P中歸屬的節點SC和DC，通過Dijkstra算法計算節點SC和DC之間由節點構成的最小代價路徑，最后通過存儲信息反向生成起始站點S到終止站點D之間的優化換乘方案。

進一步，所述步驟三中，若存在網絡P中的兩個節點A和B，分別對應網絡T中的兩個最大完全子圖SGA和SGB，如果SGA中存在至少一個站點與SGB中國的至少一個站點間存在直接的公交線路連接，那么A和B在網絡P中就存在連邊。

再進一步，對網絡T、網絡P以及兩者之間通過聚類算法得到的映射關系采用持久化的存儲方式。

所述步驟五中，通過迪杰斯特拉算法（即Dijkstra算法）計算節點SC和DC之間由節點構成的最小代價路徑。

所述Dijkstra算法是經典的單源最短路徑算法，用于計算在一個網絡中一個節點到其他所有節點的最短路徑。主要特點是以起始節點為中心向外層擴展節點，直到擴展到終點為止。算法的思想是按路徑長度遞增次序產生最短路徑。具體實現過程中算法把網絡的節點集合V分成兩組：（1）S集合：已求出最短路徑的節點的集合。（2）V-S=T集合：尚未確定最短路徑的節點集合。算法運行過程中會將T中節點按最短路徑遞增的次序加入到S中。算法的具體步驟為：

1.令S={源節點V0}，T={其余節點點}，設置網絡中任意兩個節點Vi,Vj間的路徑長度d(Vi,Vj)為：若兩節點間存在連邊<Vi,Vj>，則d(Vi,Vj)為<Vi,Vj>的權值，否則d(V0,Vi)為無窮。

2.從T中選取一個路徑長度最小且不在S中的節點W，加入S。

3.對其余T中節點的路徑長度進行修改：若加進W作中間頂點，從V0到Vi的距離值縮短，即d(V0,W)+d(W，V0)<d(V0,Vi)，則修改d(V0,Vi)=d(V0,W)+d(W，V0)。

4.重復上述步驟2、3，直到S中包含網絡中的所有節點為止。

或者是：所述步驟五中，通過弗洛伊德算法（即Floyd算法）計算節點SC和DC之間由節點構成的最小代價路徑。