城市公交线路选择算法优化

为提高城市居民乘坐公交出行的意愿,解决出行路径选择问题。拟从居民乘坐公交车出行的换乘次数最少为前提,提出用广度优先迭代结合Dijkstra算法为居民出行提供最优的公交线路。首先用广度优先迭代找出连接起讫点之间所有的换乘次数最少的公交线路,再使用Dijkstra算法在换乘次数少的线路中找到行程时间最短的线路,使得乘客在整个乘坐公交出行过程中换乘次数最少、乘坐时间最少。采用python编程实现结果验证,与实际结果路线对比,所提供的线路接近于实际运营,证明了该算法的有效性并且运行速度较快。

Optimization of Selection Algorithm for Urban Bus Routes

To encourage urban citizens to prioritize bus as a transportation means,and solve the route selection problem,we proposed to combine breadth-first iterations with Dijkstra algorithm to provide the optimized bus path for the residents with the least number of transfers in bus travel as the objective.First of all,we used the breadth-first iteration to find all the bus routes with the least number of transfers between the starting and ending points.Then,we adopted the Dijkstra algorithm to identify the route taking shortest time among the routes with least number of transfers,so that passengers could have the least number of transfers and shortest time during the whole bus travel.Finally,we verified the result with Python programming,and found that compared with the actual route,the route provided was close to the actual operation,which proved the validity and fast running speed of the proposed algorithm.