计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (5): 246-248.DOI: 10.3778/j.issn.1002-8331.2010.05.074

• 工程与应用 • 上一篇    

基于二部图模型的公交网络路径搜索算法

闫小勇1,尚艳亮2   

  1. 1.石家庄铁道学院 交通工程分院,石家庄 050043
    2.石家庄铁道学院 土木工程分院,石家庄 050043
  • 收稿日期:2008-08-22 修回日期:2008-11-11 出版日期:2010-02-11 发布日期:2010-02-11
  • 通讯作者: 闫小勇

Path-finding algorithm of public transport networks based on bipartite graph model

YAN Xiao-yong1,SHANG Yan-liang2   

  1. 1.Department of Transportation Engineering,Shijiazhuang Railway Institute,Shijiazhuang 050043,China
    2.Department of Civil Engineering,Shijiazhuang Railway Institute,Shijiazhuang 050043,China
  • Received:2008-08-22 Revised:2008-11-11 Online:2010-02-11 Published:2010-02-11
  • Contact: YAN Xiao-yong

摘要: 采用二部图模型描述公交网络,将公交站点和公交线路抽象为二部图中的两类顶点,用参照距离值度量站点间出行路径的长度。考虑换乘因素和距离因素对公交出行者路径选择行为的共同影响,在Dijkstra算法基础上,设计了公交网络最优路径搜索算法。引入迭代惩罚函数,将其进一步扩展为多路径搜索算法。通过算例验证了算法的有效性。

关键词: 公交网络, 二部图, 路径搜索

Abstract: The paper describes the bipartite graph model to represent public transport networks.In bipartite graph,bus stops and routes are all considered as vector,and the length of path is calculated by links’ referencing distance.Based on the bipartite graph model and Dijkstra’s algorithm,an optimal path-finding algorithm for public transport network is designed.It is found that the proposed algorithm can efficiently consider both the transfer factor and the distance factor of the path choice of public transport passengers.Furthermore,a multi-path selection algorithm for public transport network is designed based on the iterative penalty method.Finally,a numerical example is provided to demonstrate the effectiveness of the algorithm.

Key words: public transport networks, bipartite graph, path-finding

中图分类号: