一种改进的最短路径算法在公交查询系统中的应用研究

【摘 要】提出查询算法HCCS，并将其运用在公交查询系统的设计中。算法能求解多点间的以最少换乘次数为第一目标、最少出行时间为第二目标的公交出行方案。

【关键词】最短路径算法；换乘次数算法；公交查询系统

【Abstract】This paper propose the inquiry algorithm HCCS， and use it in the transportation design. It can solve transport problems in multi-point at the minimum number of change for the first goal， and the least time at the second.

【Key words】The shortest path algorithm；The transfer times algorithm；Inquiry system of public transportation

0 引言

最短路径问题是数据结构中图论研究的经典问题，用来求解图中任意两点间的最短路径，常应用于交通网络中求两点间的最短路径。目前，求解最短路径问题最成熟的算法是荷兰数学家E.W.Dijkstra在1959年提出的Dijkstra算法。

一般意义上，完整的出行问题主要是解决从出发点到达目的地的路径选优问题。随着城市规模的扩大，人们的活动范围变得更广，选择公交出行变得不再一车直达，可能需多次换乘才能到达目的地。基于此，如何选择最优公交出行线路，即如何选择换乘的次数及方式，越来越成为人们出行首要考虑的问题。

本文主要探讨一种改进的Dijkstra算法，同时利用几何图形对搜索范围加以限制，可用于解决多点间的最短路径问题，并将其应用于公交查询系统的设计中，可提高公交出行效率。

1 几何图形限制搜索线路范围

1.1 椭圆限制算法

在一个网络中给定起点和终点，即决定了最短路径所对应的大致极限距离MP，据此可构造一个圆，以起点为圆心，以MP为半径。以起点为原点，由极限距离所决定的地理服务范围内的结点集合是圆内结点集合的真子集。圆外的点已超出了所估的极限距离，因此可在算法中不予考虑。设网络中的一个点N到起点S和终点E的直线距离分别为|SN|、|EN|，限制条件可以写为|SN|+|EN|≤MP。显然，这正好形成了一个以S和E为焦点，以MP为长轴的椭圆。

椭圆限制算法使搜索规模大大减少，但计算过程中对每个结点都需判断其是否在椭圆内部，大量非线性运算降低了算法效率。在最小包含多边形中，三角形面积最大，随着多边形边数的增加，多边形的面积逐渐减少，直至逼近椭圆的面积，但是随着最小包含多边形边数增多，多边形限制的计算量将成倍增加。通过比较，找到最优的多边形边数为4。

1.2 平行四边形限制分析

3 换乘次数查询算法的设计

综合选取最短路径算法Dijkstra算法、换乘次数算法及平行四边形限制路径范围的算法，设计公交系统的查询算法——换乘次数算法。算法设计综合了居民出行的多种影响因素，如：出行距离、出行时间、换乘次数、出行花费、出行舒适度等，形成以最少换乘次数为第一目标，以最短出行时间为第二目标的公交出行线路查询解决方案。

3.1 算法思想

算法的主要设计思想：以换乘次数最少作为最优路径算法的第一约束目标，以出行耗时最少为第二约束条件。选择从A站到B站的出行线路，首先查找经过A站的车是否有直达B站的，若有，选择直达车，若存在多条直达线路，再选择距离最近的乘车方案；若无直达车，则考虑换一次车的方案：即判断经过A站的车与经过B站的车是否有公共站C，若有，则可在公共站C转车；若没有换一次车的方案，则需考虑乘坐经过A点的车到某站C下车，判断经过C站的车与经过B站的车是否有公共D，若有则到D转车，即两次转车可到达B；若无，则需转乘三次或以上才可到达目的地。在上述情况中，若存在多种选择方案，则再根据乘车距离，选择出行时间最短的乘车方案。

3.2 算法应用

以长春市公交网络数据为例，在基于移动设备的公交查询系统设计中应用了换乘次数查询算法，查询子系统中有三个主要功能：

（1）查询站点A至站点B的公交路线；

（2）查询经过站点A的公交路线；

（3）查询公交车路线经过站点。

4 结论

本文基于对经典的最短路径求解算法Dijkstra算法，及目前的几种改进算法的比较研究，运用可提高路径搜索效率的几何图形限制搜索范围算法，提出了最优路径查询算法——换乘次数算法，并将其应用于公交查询系统的设计中，经过测试，可实现查询两点间的换乘次数最少的乘车路线，提高了查询效率，为公交出行提供了优质高效的线路方案，具有一定实际推广应用价值。

【参考文献】

[1]高岚.公交查询系统中查询算法HCCS的研究与设计[D].吉林大学，2008，12.

[2]张三群.最短路径算法在公交网络中的应用[J].软件导刊，2009（9）.

[3]马东岭.城市公交网络的最短路径算法研究[J].科技信息，2008（26）.

[责任编辑：刘展]