一种基于区域规划换乘点查找的公交换乘方案算法

2018-07-09 12:52:01王杉
科技风 2018年30期

王杉

摘要:该算法针对城市公交路网的特点,充分利用城市公交基础数据库,基于对城市公交区域规划,查找经行起终站点的公交线路的换乘点,根据换乘点类型和数量进行换乘方案的计算,按优化规则换乘方案的优先权值后获得最优方案。在很大程度上降低了公交换乘算法的时间复杂度,并提高了方案的准确率。

关键词:公交换乘;算法研究

中图分类号:TP311文献标识码:A

1 绪论

公交乘车方案也叫公交换乘方案,主要目的是为用户提供从甲地到乙地如何乘坐公交车的方案,给用户出行带来方便。一个城市的公交线路网是一个典型的图结构,公交站点作为图的结点,站点与站点之间有多条线路相联系。从甲地到乙地的公交换乘在图结构中可描述为两结点间最短路径的查找,其典型算法为求取图中最短路径的Dijikstra算法和Floyd算法。此类算法及其改进算法都常被用于公交换乘方案的求取。但是,Dijikstra算法和Floyd算法也存在局限性,当问题规模较大时,算法循环及穷举次数较多,其算法的时间复杂度高,将会降低查询的效率。同时,求取的路径虽然是最短路径,但有可能会产生多次公交的换乘,这在实际生活中是完全不适用的。[1][2]

因此,以昆明市为例,经过对城市公交路网的分析,认为大多数中型规模以上的城市在城市公交路网的建设上都具备较好的规模,公交线路覆盖率较高,在主城区公交路网辐射范围内,90%以上的任意两个站点,最多只需一次换乘即可到达。……

登录APP查看全文