北京交通大学交通运输学院城市轨道交通客流诱导系统理论基础1 / 9城市轨道交通客流诱导系统理论基础城市轨道交通客流诱导系统理论基础一、城市轨道交通客流诱导系统的研究背景一、城市轨道交通客流诱导系统的研究背景随着全球经济的腾飞、社会的进步以及城市化进程的加快，交通运输在人们的日常生活中起着越来越重要的作用，对交通的需求日益增长，交通运输已然成为了社会经济生活的重要组成部分。为了适应城市发展的要求，目前，主要大城市都在加快轨道交通网络的建设。随着轨道交通网络的日趋完善，未来的轨道交通网络将会出现一些前所未有的新的特点，其中主要表现在路网的结构和规模将更加复杂，客流需求将有大幅度增长。由于轨道交通网络结构复杂，线路间相互连通，这就使得出行者出行时将会有更加多样的路径选择。随着轨道交通系统规模的不断扩大，沿线小区的不断开发，越来越多的出行者出行时将趋向于选择轨道交通。这样，轨道交通将会涌现大量的客流，对人们日常出行和轨道交通中客流的诱导逐渐成为大家关注的焦点，其需求的迫切程度也越发明显。所以急需开发关于城市轨道交通客流诱导的系统。在轨道交通路网结构相对简单的情况下，由于考虑时间最短或距离最短因素得到的有效路径比较少，也就是说在每一个 0D 对间，出行者路径选择比较单一，客流诱导系统的作用并不明显。随着路网规模的不断扩大，人们出行时的路径选择不再单一，而是逐渐趋于多样化，在这种情况下，如果没有合适的客流诱导系统对出行者的路径选择进行诱导，将会导致过多的客流聚集在 0D间旅行时间最短或者距离最短的路径上，容易造成客流拥挤、换乘拥堵等等很多问题。基于上述考虑，本文提出城市轨道交通客流诱导系统的理论基础。二、城市轨道交通客流诱导系统的研究意义二、城市轨道交通客流诱导系统的研究意义城市轨道交通客流诱导根据轨道交通路网结构、站点和断面的客流信息等，利用改进的最优路径选择算法和交通分配模型，对轨道交通的客流进行统计分析与诱导。客流诱导系统能够根据出行者的个人情况和轨道中实时的客流分布信息，为出行者提供可供选择的出行路径，有效地避免轨道中的客流聚集，有助于提高轨道交通的利用率，也能够缓解道路交通的压力。三、轨道交通出行最优路径选择模型的研究三、轨道交通出行最优路径选择模型的研究最短路径是运筹学、图论等领域中的概念。所谓最短路径，即由起点至终点间的路径代价最小的路径。它既要求能求得一条总路径代价最小的路径，又北京交通大学交通运输学院城市轨道交通客流诱导系统理论基础2 / 9要求采用具有较小的时空复杂度的求解算法。经过多年的研究，在图论的基础上结合数据结构和算法，大量的在使用范围与时空复杂度上拥有各自优势的最短路径求解算法被提出。最优路径问题，通俗的说，即求解道路中两点间的最短路径的问题。最优路径算法因为具有现实背景，所以不像传统的最短路径算法那么简单，它需要考虑实际的影响因素和约束条件，但它们的本质是一样的。在图论中，最短路径指的是图中某一结点到其余任一结点的总权值最小的连接初始结点和目标结点的边的序列；而与此对应的，在交通路网中，最短路径指的是一个站点到另一站点间总路径阻抗最小的一系列依次连接的路段的序列。最优路径选择算法一般也叫做最短路径算法，指的是寻找图中给定结点到其余任意一个结点的一条最短路径的算法。本文主要介绍 3 种常用的最优路径选择算法：Dijkstra 算法、Floyd 算法和 A*算法。 Dijkstra 算法Dijkstra 算法是在 1959 年由荷兰的一位数学家 E.W.Dijkstra 提出的，用来寻找单源点的最短路径的算法，适用于图中所有的边的权值均为非负的情况，并且最短路径是依据路径的长度非递减的顺序搜索得到的。Dijkstra 算法是迄今为止研究最深入、运用最普遍的寻找最短路径的算法，用于求图中一个给定结点到其余任意结点间的最短路径。Dijkstra 算法的基本思想：给定赋权图 G = (V,E)，其中 V 表示结点的集合，E 表示弧的集合。初始时，设 D 为辅助向量，其各分量 Di的含义是当前得到的由起点 v 至各终点， 间的最短路径的长度。其初态可以设置为：如果 v 和 连通，那么 Di的值就为弧上的权值；否则，将 Di的值设置为。很明显，长度为 = | 的路径即为以 v 为起点，且具有最小长度的路径，表示为。(,)假定 S 为已计算得到的最短路径所有终点的集合，那么能够得出的结论是:下一条终点为 x 的最短路径可能为弧(v,x)，或仅途经 S 中结点并且最终到达 x 的路径。可以用反证法来证明。假设该路径上的某一结点未包含于 S 中，那么说明存在这样的一条路径，其终点不在 5 中但长度小于该路径的长度。然而，这种假设是不可能的。因为最短路径的搜索是依据路径的长度非递减的顺序实现北京交通大学交通运输学院城市轨道交通客流诱导系统理论基础3 / 9的，所以，比该路径的长度小的路径已全部求出，其终点一定包含于 S 中，由此得出，假设不成立。通常情况下，搜索的下一条为长度次短路径，其长度为- = | 其中，Di的值可能为弧的权值，也可能为 Dk()与弧的(,) (,)权值之和。Floyd 算法Floyd 算法是 Floyd 在 1962 年提出的，它是用来搜索图中各个结点对间的最短路径的算法。Floyd 算法能够一次性搜索得到图中任意结点对间的最短路径及其长度。Floyd 算法的基本思想：假设一个 nxn 的方阵，它的对角线元素均为()0，其余元素为由 到的路径的长度（其中为运算步骤） 。初始时，()( )任意两结点间的弧的权值作为其路径长度，表示为；然后在每次(0)= (,)计算时，逐渐在原路径中依次添加其它结点作为中间结点（添加结点时可依结点在图中的序号依次加入） 。若在第 k 步将添加到路径中作为中间结点，那么需要计算是否成立，若成立，就将新的路径长度作为( 1)+ ( 1)s(j)时，路段(i,j)可以称为 0D 对(r,s)间的一条有效路径。基于图的遍历搜索算法该算法搜索有效路径时有一个前提条件，它假设每一条路径中都不存在重复的结点，也就是说所有的路径中均没有回路存在的现象。这个假设前提在现实的轨道交通路网中是符合实际情况的，因为在正常情况下，没有人出行的起点和终点是一样的，走一圈又回到原点的事情是不存在的。该算法的基本思想：根据图的遍历算法，在图中搜索由指定起点至终点的有效路径，即相互连通并满足约束条件的路径，若满足约束条件，那么就将此路径记下来，否则，就要向上一层结点回溯，然后再重新进行遍历。如此循环选择和回溯，直至搜索到图中全部有效路径。进行该算法时，遍历到任何一个结点，该结点都有多个后继结点可以选择，至于要选择哪个结点可以顺利找到有效路径并没有任何明确的暗示或是确定信息，只能尝试选择某一结点继续向下搜索，直至终点。如果搜索过程中不满足约束条件的话，就需要向上一层结点返回，之后重新遍历。该算法利用深度优先搜索进行图的遍历，深度优先搜索从根结点 s 开始，首先将 s 标记为已被访问。然后把 s 看作当前扩展结点开始搜索，若是 s 的邻接点有未被访问的，那么就访问该邻接点，访问后标记为己被访问，此时，刚刚被访问过的结点就成了当前扩展结点。如果 v 为当前扩展结点，而且 v 的邻接点均已被访问，那么，该算法就回溯到 v 之前的那个扩展结点作为当前扩展结点。此过程直至遍历到终点 t 结束。如果该算法没有约束条件的话，其结果就是路径的枚举，得到的是起讫点间相互连通的全部路径。然而在结构复杂的轨道交通路网中，任意两点间是有北京交通大学交通运输学院城市轨道交通客流诱导系统理论基础9 / 9很条相互连通的路径的，若是所有的路径都考虑计算量相当大，是不现实的，出行者出行时并不是要考虑所有路径，所以，需要一定的约束条件对有效路径的选择加以限制。假设已知起讫点间的最小路径代价，可以设一个阈值，用来表示若起讫点间的某路径的路径代价比出行者承受能力范围内的最大路径代价还要大的话，这条路径就不被考虑，也就不是有效路径。五、基于五、基于 Web 的轨道交通客流诱导系统功能的设计思路的轨道交通客流诱导系统功能的设计思路轨道交通客流诱导系统要完成两部分功能的实现，具体如下：第一，面向乘客的乘车诱导功能和面向工作人员的实时客流监控功能。该功能要求软件系统必须基于浏览器/服务器(B/S)架构，且具备直观的图形交互能力。第二，面向开发人员的系统维护功能。该功能要求软件系统具备高内聚、低祸合、高弹性、易维护的特点。这两部分功能的实现要求基于 B/S 架构的软件系统，而且还要能够直观地进行图形界面交互。六、总结六、总结城市轨道交通客流诱导系统是一个完整而庞大的体系，它涉及到许多理论与算法。本文只是对于该系统中最优路径选择模型，客流分配模型以及展望软件设计功能进行了介绍，并得出了一些有意义的结论。但本文只限于理论的研究，深度不够，只能作为参考。