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

有效

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

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

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

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

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

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

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

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

2.如權利要求1所述的基于空間節點聚類方法的快速公交換乘方法，其特征在于：所述步驟三中，若存在網絡P中的兩個節點A和B，分別對應網絡T中的兩個最大完全子圖SGA和SGB，如果SGA中存在至少一個站點與SGB中國的至少一個站點間存在直接的公交線路連接，那么A和B在網絡P中就存在連邊。

3.如權利要求1或2所述的基于空間節點聚類方法的快速公交換乘方法，其特征在于：對網絡T、網絡P以及兩者之間通過聚類算法得到的映射關系采用持久化的存儲方式。

4.如權利要求1或2所述的基于空間節點聚類方法的快速公交換乘方法，其特征在于：所述步驟五中，通過迪杰斯特拉算法計算節點SC和DC之間由節點構成的最小代價路徑。

5.如權利要求1或2所述的基于空間節點聚類方法的快速公交換乘方法，其特征在于：所述步驟五中，通過弗洛伊德算法計算節點SC和DC之間由節點構成的最小代價路徑。