图2.1 乘客信息系统示意图 5公交乘客出行路径选择模型 公交乘客出行路径选择模型的研究对于公交乘客信息系统的研究和开发有着重要的意义。乘客信息系统是智能交通系统中的重要组成部分。乘客信息系统中以提供公交信息为主的部分称为公交乘客信息系统。公交乘客信息系统最重要的一个功能是在乘客给出起讫点后，自动生成最优的出行路径方案供乘客选择。 搜索与生成最优出行路径的理论模型就是公交乘客出行路径选择模型。公交乘客出行路径选择模型研究的实质是寻找乘客的出行在公交网或道路网上分布的规律。研究和建立更接近现实的模型,有利于得到更合理的公交客流分配结果。 目前，大多数的公交乘客信息系统都能根据一定的目标与约束条件出行距离、换乘次数等)，在出行者指定的起讫点寻找一条最优乘车路径。但由于公交乘客出行路径选择心理的复杂性，往往单一的乘车路径并不能满足所有乘客的需要。例如，一些乘客希望选择换乘次数最少的乘车路径，而另外一些乘客则倾向于选择出行距离更短的乘车路径。即使是出行这选中的路径方案，在实际中也可能由于公交车辆满载或道路交通拥挤而被放弃。因此，一个先进、有效的公交乘客信息系统不能只为用户提供单一的路线优化方案，还应提供一定数量的合理备选路径出行者根据实际情况进行选择。 5.1公交出行路径选择算法思想 公交出行路径的选择就是用户从起点出发到目的地，究竟选择乘坐哪路公交车，如何换乘才最方便。因此，现在的问题是在已经建立好的公交网络上寻找一条换乘次数最少、距离最短的路径。现有的出行路径选择算法一般有两种模式： ①以换乘次数为代价换取空间上的距离最短[12]；②以算法搜索时间为代价换取换乘次数最少[13]。在模式①中，起讫点之间的最短路径已确定，需要在该路径上匹配公交线路实现两点之间的连通，搜索效率较高，但结果不一定理想。因为一条路径路程值最短，但必须转乘多次车才能到达，而另一条路径路程较长，却只要转乘较少次车就能达到，那么乘客大部分会选择后者，因为换乘所带来的不便和不可预期的等待时间往往是人们力图避免的。所以很多学者采用模式②，在这种模式中，需要集合的逐步扩展、排序、求交等，对于小城市的公交网络可能在搜索时间和空间上可以忍受，但对复杂而庞大的大城市公交网络来说，对每条公交线路进行操作是不太现实的，并且该种模式并不考虑距离。也就是说，只要起讫点之间通过较少换乘能实现连通，无论多长的距离都是允许的。但在人们的实际出行中，还是希望能快速地(一般可通过距离来体现) 到达目的地，并且在城市道路规划中，公交网络的线路分布一般都是基于最短路径布线的[14]。 5.2几种最短路算法的特点和不足 出行路径选择模型的基础是最短路算法。常用的几种网络最短路算法有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]提出了一种以换乘次数少为首要目标，以出行距离短为次要目标的公交网络静态多路径选择算法，但该算法不能
首页 上一页 1 2 3 下一页 尾页 2/3/3
