刘香菊 杨夏青 乔 石 房 丽

（齐鲁理工学院 山东济南 250200）



城市公共交通系统中的最佳路径问题

刘香菊 杨夏青 乔 石 房 丽

（齐鲁理工学院 山东济南 250200）

摘 要：通过分析城市公共交通系统网络图的特点，采用改进的Dijkstra 算法的最短路径问题构造公共交通网络模型。最佳乘车路线的获得，需要在满足换乘次数要求的基础上，提出换乘的实现算法，并在此过程中采用用换乘矩阵的形式描述最短路径中的站点及线路。

关键词：公共交通系统 最佳路径 最短路 最小换乘

一、引言

研究公交换乘的问题，首先要解决的问题是合理地表述公共交通网络模型；其次还需要对公交换乘问题思想做准确描述［2］。本文将解决换乘算法的实现问题，在此过程中还需综合考虑换乘次数的因素，距离因素的影响。

二、城市公共交通系统的特点［3］

与道路网络有所不同，城市公共交通系统有其自身特点，公交网络不能直接采用与道路网络相同的模型。

1.结点性质

在模拟不同公交线可换乘情况［4］时，需要考虑空间上比较接近的不同线路但同名的公交站点的抽象问题。

2.弧段性质

由于弧段与属性之间的一对多的关系，那么就会导致需重复记录在公共交通系统中，每条公交线路通过的弧段，这必然导致数据冗余问题的出现。

3.有向线性质

由于边的有向性不能体现公交系统图有向性特点，因此需要考虑另外的解决方法，即通过引入有向线路集的方法来解决。

三、建立城市公交系统模型

距离最短路段及最少换乘公交线路的集合构成了最优出行路径。……