[發明專利]一種基于加權有向網絡模型的公交換乘方法

無效

• 申請號: 201210297826.X
• 申請日: 2012-08-20
• 公開（公告）號: CN102880642A
• 公開（公告）日: 2013-01-16
• 發明（設計）人: 楊旭華;張永振;蔣峰嶺
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G08G1/00
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;王利強

1.一種基于加權有向網絡模型的公交換乘方法，其特征在于：包括以下步驟：

步驟一：構建城市公交的無權有向網絡模型，將某一城市實際公交網絡抽象成用鄰接矩陣表示的無權有向圖，其中，將站點抽象為節點，對任意兩個站點i和j，如果至少存在一條從i至j的直達線路，則存在一條從i指向j的有向邊，用1表示；否則，視為從i到j無連接，用0表示；

步驟二：構建城市公交的加權有向網絡模型，將某一城市實際公交網絡抽象成用鄰接矩陣表示的加權有向圖，其中，將站點抽象為節點，對任意兩個站點i和j，如果從i到j有k條直達線路，則從i指向j的邊的權值w_ij記為1/k，當k等于0時，w_ij記為∞；

步驟三：對于任意給定的起始站點V_start和目的站點V_end，在無權有向網絡應用廣度優先搜索算法，查找并返回一組最短路徑集合R；如果R是直達線路集合或R中只有一個元素，算法終止；否則，轉至步驟四；

步驟四：應用加權有向網絡，計算上述最短路徑集R中每條路徑的路徑特征時間系數，所述的路徑特征時間系數記為p_od(r)，即其中，t₁、t₂……t_n是路徑r中依次經過的中間換乘站點，是從站點t_i到站點t_j的邊上的邊權；

并按路徑特征時間系數由小到大的順序，對最短路徑集R中的元素進行排序，取路徑特征時間系數最小的一條路徑為最優路徑。

2.如權利要求1所述的基于加權有向網絡模型的公交換乘方法，其特征在于：所述步驟四中，在無權有向網絡中計算出從起始站點o到目的站點d的所有最短路徑集合R，然后計算R中每條路徑的路徑特征時間系數，取其中路徑特征時間系數最小的路徑作為最優路徑，如果出現多條具有最小且相等的路徑特征時間系數的路徑，則其中任意一條均為最優路徑，即R中路徑特征系數等于的路徑均是最優路徑，其中r₁、r₁……r_n是R中的全部元素。

3.如權利要求1或2所述的基于加權有向網絡模型的公交換乘方法，其特征在于：所述步驟三中，所述廣度優先搜索算法的過程為：當輸入一個源節點在指定的數據文件中搜索相關數據時，首先遍歷其所有的鄰居節點，查看查詢的結果當中是否包含所需要的數據，如果存在，則返回相應的數據；否則，繼續以鄰居節點為新的源節點，重復上述遍歷過程，直到找到目標數據為止。