一种基于加权复杂网络的最优公交换乘算法

An Optimal Bus Transport Transfer Algorithm Based on Weighted Complex Networks

用spaceP方法对公共汽车交通网络(公交网络)进行建模,得到一个无权的复杂网络模型,并简单分析了其统计特性.利用广度优先搜索算法得到需换乘两公交站点间的所有最少次数换乘方案.在此基础上,引入了网络点权,即站点的经纬度,进而得到网络的边权,即站点间的直线距离,把公交网络进一步建模成一个加权的复杂网络模型.结合得到的最少换乘次数方案,最终得到一种在保证换乘次数最少的基础上站间总直线距离也最短的换乘方案,并用杭州的实际数据验证了此算法的有效性.

First, using the method of space P to model the bus transport network （BTN）, an unweighted complex network model is obtained. Second the statistical characteristics of BTN are analyzed simply. Then by using the breadth-first search algorithm, all the least transfer routes between two inquired stations are gotfen. Third the vertex weight is introduced, namely every station＇s longitudes and latitudes. The edge weight-straight-line distance between every two stations-will be got by computing the vertex weight. Further the BTN to a weighted complex network is modelled. A final transfer route which has the shortest total straight-line distance on the basis of the least transfer is obtained by this weighted complex network model and all the least transfer routes are got in prior. The practical data of Hangzhou is used to testify the new algorithm＇s efficiency.