城市公交网络出行路线选择的计算机算法探讨

胡竟伟 河套学院 巴彦淖尔 015000

【文章摘要】

优秀的城市公交网络出行路线图的制定首先应该站在公交乘客的角度上进行研究，在对城市公交网络路线最短路径算法的基础上，同时充分的利用地理信息系统，对公共交通网络中进行两个结点间的最佳路线的选择，通过此路线能够达到最大程度的减少换车的次数。本文充分探讨了基于地理信息系统的城市公交网络出行路线的最佳选择。

【关键词】

城市；公交网络；出行路线；地理信息系统

对于任何一个城市来说，公共交通信息系统是至关重要的交通工具，它能够进行各种交通信息的查询，这样便为统计提供了更加方便直观的手段。同时公共交通信息系统也为市民的日常出行带来了方便。公共交通信息系统具有一个最为重要的功能，就是它能够在乘客给出起始点后，为乘客选择出最优的出行方案。在公交网或者是道路网上找出顾客出行的路径的分布规律是城市交通网络出行路线选择算法的根本所在。为了能够对公交客流更为合理的分配，就需要研究并建立更为接近现实的城市公交网络出行线路。

1 城市公交乘客出行的心理期望

一般情况话，城市公交的换乘次数，出行的距离、费用以及耗时是乘客在出行的时候选择城市公交路线所受影响的几大因素。通过具体的调查研究表明，大部分的乘客在选择城市公交时，换乘的公交车的次数是其考虑的重要因素，再就是进行出行时间长短的考虑。综上所述，城市公交网络出行路线选择的计算机算法以换乘次数最少为其优化目标。

2 城市公交网络所具备的特点

城市中公共交通汽车时沿着道路进行的，这就使其具有自身的一些特点，并且因其区别于其他不同的道路交通网络。

2.1 连通性

就单向的城市公共交通来说它是不具备连通性的，只有经过换乘从而使弧度有效的连接起来，才能够构成较为完整并具连通性的公交网络。

2.1.1 有向线性

实际情况中，城市公交路线都是具有方向性的，不仅不同路线的公交具有不同的行驶方向及路线，即便是同路线的公交，上下行车的路线也不尽相同。城市公交网络中这些公交路线的方向性只有通过有向线性才能够进行表现，因此来说有向线路集应该被引入到城市公交网络中。

2.1.2 时间性

一般来说城市公共交通都是具有相应的运行时间表，但是在实际运行过程中也会受到交通状况等因素的影响。

2.1.3 换乘性

相同站点的换乘以及不同站点的换乘共同构成了公共交通的换乘。通常情况下，同站点的换乘，乘客只需要对站点的内部细节有较为熟悉的掌握便可，异站点的换乘则需要建立在各个站点能够相互连接的接触上，同时站点的换乘也是需要付出相应的成本的，比如说时间或者金钱等。

3 城市公交网络中路径选择的计算机方法研究

3.1 以时间链为基准的公交网络数据模型算法

现阶段人们的生活速度不断加快，此公交网络模型的算法便是将时间作为乘客出行的重要因素进行考虑计算。以时间链的角度来计算，就可以把行车中的不同类型的其他因素进行以时间的换算。

人们持续出行的时间被称为相对时间，相对时间是一个较为完整的时间链。相对时间的计算公式为：相对时间= 步行时间+ 等成时间+ 实际乘车时间+ 换乘所消耗的时间。因此来说可以通过控制四种不同因素的时间来选择路径最优的出行路线。通常情况下，乘客是不会轻易的选择换乘车次的，因为换乘车次需要具有较高的时间代价。乘客的步行时间主要是由出发点到达站牌的距离所决定的，因此距离成为影响步行时间的重要因素。乘客等车时间的影响因素则较为复杂，主要包括发车的频率、交通的顺畅以及停车的耗时。乘客的换乘时间则主要是受上下车时间、换乘距离以及换乘数所决定的。

以时间链为基准的公交网络数据算法是一种较为简洁的公交路线选择法，通常只适用于中小型城市的公交运行，而大城市的公交运行时间链较为复杂，此种方法便不适用。

3.2 传统意义上的Dijkstra 最优化路径选择算法

稳定性以及能够适应网络拓扑的变化是Dijkstra 最优化路径算法的特点， 使得其在地理信息系统以及计算机网络拓扑路径选择中广泛应用，但是传统的Dijkstra 并不适应公交路线的选择。公交线路网络具有非常复杂的数据结构，采用Dijkstra 算法，不仅算法时间长且在碰到大计算量的问题时，系统的整体运算效率也会有较为明显的下降。除此之外，利用Dijkstra 算法只能进行两个结点之间存在的计算，这也就导致所计算出的路线可能是最短的路线，但是却无法保证公交的换乘次数是最少的，也就无法得到换乘次数最优化的目的。而从之前的出行乘客心理期望的研究来看，换乘次数少才是乘客在公交出行时首先考虑的因素。

3.3 改进后的Dijkstra 最优化路径选择算法

改进之后的Dijkstra 算法可以充分的利用最小换乘次数矩阵，来计算出换乘次数最少的最短路径。但是此种算法只能使用于一些较为简单的公交网络拓扑，而面对一些复杂的公交网络拓扑时还需要进行相应的简化，这无疑又提高了整个算法的复杂度。

3.4 广度优先搜素算法

广度优先搜索算法在进行方案选择时会搜索出大量的不合理的路径，这就容易造成维数爆炸，从而为整个算法增加不必要的麻烦，由此来说此种算法很难适用于大型的实际公交网。

3.5 蚂蚁算法

蚂蚁算法是一种仿生类算法，最早是由意大利学者提出的。此种算法具有较强的灵活性、组织性以及分散性，是一种将并行以及随机搜索的优化算法。蚂蚁算法的提出正是因为城市道路复杂，影响公交网络规划因素较多等因素与蚂蚁觅食的现象极为相似。在此算法中公共密集的场所被比喻为蚂蚁的巢穴，蚂蚁所向前行的每一步便作为对应公交网络中一个节点到另一个节点。路径上蚂蚁所留下的信息素，则在交通网络中被认为是一个状态到另一个状态的变化，也就是指路权值所发生的变化。

3.6 城市公交网络中的二分图法计算方法

二分图不仅在理论研究中具有丰富的意义，在实际应用中同样具有。在二分图的计算方法里，所有的公交结点都被分为M 集合与N 集合。并且两个集合中的点都是无法直接相连的。

城市公交网络中的二分图模型是包含线路及站点集合的网络。在二分图中线路与站点之间则用无向线段进行相连并用数字将站牌号表示出来，从而选择出两点之间最优路径的算法及路径选择。

4 结语

在实际的生活中，城市公交网络是异常复杂的，如果仅仅是局限在出行距离最短、换乘次数最少或者是出行时间最短等单一因素上是具有非常大的局限性的。地理信息系统对空间信息的管理以及图形的表现都具有很强的能力，充分的结合城市自身的特点以及长时间以来人们累积的实际路径寻求知识，进行具有现代交通发展需要的地理信息系统是有非常重要的实际意义的。

【参考文献】

[1] 刘波涛. 城市公交网络出行路径选择的计算机算法研究[J]. 电脑知识与技术,2010,30:8420- 8421+8426.

[2] 张本群. 城市公交网络出行路径选择的计算机算法研究[J]. 信息与电脑( 理论版),2011,12:184+186.

[3] 梁萌. 基于计算机算法的城市公交网络出行路径问题研究[J]. 陕西教育( 高教版),2014,04:64+67.

【作者简介】

胡竟伟，女，内蒙古，讲师，研究生，计算机技术。145

网络通信

Network Communication

电子制作