距离加权公交换乘复杂网络最短路算法研究

为研究乘客使用公共交通的实际出行距离,基于公交复杂网络中的换乘网络Space P拓扑结构,结合公交车站的经纬度坐标,建立以距离为边权的加权公交换乘网络。基于该加权网络,设计了综合考虑换乘次数和路径长度的最短路算法,该算法可保证在站间换乘次数最少的基础上通过的路径也相对最短。利用成都市公交网络进行实例分析,并与Floyd算法进行对比,结果显示,由该算法得到的平均最短路径长度增加3.7 km,但平均换乘次数下降0.64次,更符合乘客的出行习惯;随机选择一些车站进行最优换乘路径选取试验,结果表明,由该算法得到的方案在保证换乘次数最少基础上,得到的路径也基本最短,证明了算法的有效性。

Shortest Path Algorithm Based on the Weighted Distance in Complex Bus Transfer Network

In order to study the actual travel distance of passengers using public transportation,this paper develops a distance-weighted complex bus transfer network with the geodetic coordinates of bus stops based on the Space P topological mapping method in the complex network theory.On the basis of the weighed network,the paper further develops a shortest path calculation algorithm,which guarantees that the path is the shortest based on the premise of having the minimum transfer times.Then,data from Chengdu public transportation network is used to validate the proposed algorithm.Comparison with the Floyd algorithm indicates that the proposed algorithm has slightly increased the average shortest distance by 3.7 km but decreases the average transfer by 0.64 times,which is more in agreement with travel habits of passengers.Finally,the effectiveness of the algorithm is verified by experiments with randomly selected bus stops.The results show that a shortest path with minimum transfer times can be obtained with the proposed algorithm.