公交乘客信息系统研究(四)
出行路径选择模型的基础是最短路算法。常用的几种网络最短路算法有Dijkstra算法、Floyd 算法、Moore-pape算法等。针对建模的需要，对几种方法进行分析如下：
Dijkstra算法是由Dijkstra于1959年首先提出的。此算法的思想是对节点赋以标号，在迭代过程中不断更新标号。每一步的节点标号代表从起点s 至该点有向路径长度的上界。迭代结束时，节点的标号就是从s 到该点最短有向路的准确长度。
Floyd 算法可求出所有点对之间的最短有向路。设表示从点i到点j 且不经过m，m + 1，…， n (除去点i 和点j) 的最短有向路的长度，则自点i 到点j 不经过点m + 1 ，m + 2，…，n (除去点i 和点j) 的最短有向路有2 种情况：①不经过点m，此时有 = ；②经过点m ,此时有= + 。因此，总有= min{ ， + } . 显然,当m = n 时， 就等于网络中自点i 到点j 的最短有向路的长度。
Moore-pape 算法使用了链表管理技术。设路段节点集合为V 表示，路段ij 的路权为 ，表示节点i 的最短路权，即从根节点r 至i 的最短距离。 表示i 的前节点，算法的步骤如下：
①初始化。将根节点r 置于链表T，T 为一维有序数组，其内容为节点的编号。 令 = 0 i ∈V ， = 0 i = r
∞ i ≠ r , i ∈V
②若链表T 非空，取出T 中第1个节点i ，检验所有与i 相连接的节点j. 如果 + < ，则令 = i ，且 = + ，并将j 加入T ，当所有的j 都检验完后，将i 从T 中删除。
③当链表T 中没有节点时，通过追踪p 找到r 到所有节点的最短路径，否则返回步骤②。
在步骤②中，为提高计算效率，对j 在T 中的位置分为3 种情况处理。如果j 曾在T 中出现过，但现在不在其中，将其放在当前检查的节点i 之后；如果j 从来没有在T 中出现过，则将其置于T 末尾；如果j 正在T 中时，不用增加。
3 种算法在道路网络上都是适用的，其缺点为：Dijkstra 算法虽可用于大型网络，但计算速度慢；Floyd 算法虽然可以快速地进行“多对多”的计算，但它不能应用于大型网络；Moore-pape算法由于采用了链表技术，计算速度较快，亦可用于大型网络，但它无法进行“一对一”的计算,即使用该算法时，只有访问完所有的节点后才能输出正确的结果，Moore-pape 方法将大量的计算时间耗费在寻找起点与终点点对以外的最短线路，这显然不适用于公交网络。而且以上几种算法都没有考虑换乘问题。
6 提出的改进方法
通过上述文献分析可以看出，现有的公交网络多路径选择算法在路径选择合理性及执行效率等方面还存在不足。对于城市公交网络中多条备选路径的选择算法，目前国内外已有一定研究。张国伍等[8]结合公交网络的特点，在推广Floyd算法的基础上提供了一种公交网络多条最短路径算法，该算法一次可以搜索出所有站点间的多条最短路径，但在只需选择两点间路径的情况下应用效率较低；Koncz等[9]提出了一种以换乘次数少为首要目标，以出行距离短为次要目标的公交网络静态多路径选择算法，但该算法不能处理2次以上换乘的情况；在公交客流多路径分配中使用较多的是Nguyen等[10]提出的基于Dial算法的有效超级路径方法，但当两点距离较远时，该方法产出的“有效”路径较多，而其中很大部分是基本不被乘客考虑的路径；Qiujin Wu等[11]利用图论中的K最短路径算法求解公交网络中的多路径优化问题，但该算法产生的多条路径往往过于相似，很难称为真正意义上的备选方案。
针对这些问题，应结合公交乘客出行路径选择行为的特点建立了公交网络路径优化模型。所以，针对人们的出行心理、公交线网的实际布线原则以及在已有的研究基础上[9]，提出了一种在基于最短路径上对集合向外扩展、两个集合之间逐渐逼近的搜索方法。在算法中，判断的原则是优先考虑换乘次数少的路径，在换乘次数相同的情况下，再考虑出行距离最短。
公交乘客信息系统研究(四)由毕业论文网（www.huoyuandh.com）会员上传。
