城市轨道交通客流诱导系统理论基础

1、城市轨道交通客流诱导系统理论基础一、城市轨道交通客流诱导系统的研究背景随着全球经济的腾飞、社会的进步以及城市化进程的加快，交通运输在人们 的日常生活中起着越来越重要的作用，对交通的需求日益增长，交通运输已然成 为了社会经济生活的重要组成部分。为了适应城市发展的要求，目前，主要大城 市都在加快轨道交通网络的建设。随着轨道交通网络的日趋完善，未来的轨道交 通网络将会出现一些前所未有的新的特点，其中主要表现在路网的结构和规模将 更加复杂，客流需求将有大幅度增长。由于轨道交通网络结构复杂，线路间相互 连通，这就使得出行者出行时将会有更加多样的路径选择。随着轨道交通系统规 模的不断扩大，沿线小区的不断开

2、发，越来越多的出行者出行时将趋向于选择轨 道交通。这样，轨道交通将会涌现大量的客流，对人们日常出行和轨道交通中客 流的诱导逐渐成为大家关注的焦点，其需求的迫切程度也越发明显。所以急需开 发关于城市轨道交通客流诱导的系统。在轨道交通路网结构相对简单的情况下，由于考虑时间最短或距离最短因素 得到的有效路径比较少，也就是说在每一个0D对间，出行者路径选择比较单一， 客流诱导系统的作用并不明显。随着路网规模的不断扩大，人们出行时的路径选 择不再单一，而是逐渐趋于多样化，在这种情况下，如果没有合适的客流诱导系 统对出行者的路径选择进行诱导，将会导致过多的客流聚集在0D间旅行时间最 短或者距离最短的路径上

3、，容易造成客流拥挤、换乘拥堵等等很多问题。基于上 述考虑，本文提出城市轨道交通客流诱导系统的理论基础。二、城市轨道交通客流诱导系统的研究意义城市轨道交通客流诱导根据轨道交通路网结构、站点和断面的客流信息等， 利用改进的最优路径选择算法和交通分配模型，对轨道交通的客流进行统计分析 与诱导。客流诱导系统能够根据出行者的个人情况和轨道中实时的客流分布信息， 为出行者提供可供选择的出行路径，有效地避免轨道中的客流聚集，有助于提高 轨道交通的利用率，也能够缓解道路交通的压力。三、轨道交通出行最优路径选择模型的研究最短路径是运筹学、图论等领域中的概念。所谓最短路径，即由起点至终点 间的路径代价最小的路径。

4、它既要求能求得一条总路径代价最小的路径，又要求1 / 9采用具有较小的时空复杂度的求解算法。经过多年的研究，在图论的基础上结合 数据结构和算法，大量的在使用范围与时空复杂度上拥有各自优势的最短路径求 解算法被提出。最优路径问题，通俗的说，即求解道路中两点间的最短路径的问题。最优路 径算法因为具有现实背景，所以不像传统的最短路径算法那么简单，它需要考虑 实际的影响因素和约束条件，但它们的本质是一样的。在图论中，最短路径指的 是图中某一结点到其余任一结点的总权值最小的连接初始结点和目标结点的边 的序列；而与此对应的，在交通路网中，最短路径指的是一个站点到另一站点间 总路径阻抗最小的一系列依次连接的

5、路段的序列。最优路径选择算法一般也叫做最短路径算法，指的是寻找图中给定结点到其 余任意一个结点的一条最短路径的算法。本文主要介绍3种常用的最优路径选择 算法：Dijkstra算法、Floyd算法和A*算法。Dijkstra算法Dijkstra算法是在1959年由荷兰的一位数学家E.W.Dijkstra提出的，用来寻找 单源点的最短路径的算法，适用于图中所有的边的权值均为非负的情况，并且最 短路径是依据路径的长度非递减的顺序搜索得到的。Dijkstra算法是迄今为止研 究最深入、运用最普遍的寻找最短路径的算法，用于求图中一个给定结点到其余 任意结点间的最短路径。Dijkstra算法的基本思想：给

6、定赋权图G = (V,E)，其中V表示结点的集合，E 表示弧的集合。初始时，设D为辅助向量，其各分量Di的含义是当前得到的由 起点v至各终点，间的最短路径的长度。其初态可以设置为：如果v和 连通， 那么Di的值就为弧上的权值；否则，将Di的值设置为。很明显，长度为的路径即为以v为起点，且具有最小长度的路径，表示为 。假定S为已计算得到的最短路径所有终点的集合，那么能够得出的结论是： 下一条终点为x的最短路径可能为弧(v,x)，或仅途经S中结点并且最终到达x的 路径。可以用反证法来证明。假设该路径上的某一结点未包含于S中，那么说明 存在这样的一条路径，其终点不在5中但长度小于该路径的长度。然而，

7、这种假设是不可能的。因为最短路径的搜索是依据路径的长度非递减的顺序实现的， 所以，比该路径的长度小的路径已全部求出，其终点一定包含于S中，由此得出， 假设不成立。通常情况下，搜索的下一条为长度次短路径，其长度为-2 / 9其中，Di的值可能为弧 的权值，也可能为Dk()与弧的权值之和。Floyd算法Floyd算法是Floyd在1962年提出的，它是用来搜索图中各个结点对间的最短路径的算法。Floyd算法能够一次性搜索得到图中任意结点对间的最短 路径及其长度。Floyd算法的基本思想：假设一个nxn的方阵 ，它的对角线元素均为0， 其余元素为由 到 的路径的长度(其中 为运算步骤)。初始时，任意

8、两结点间的弧的权值作为其路径长度，表示为；然后在每次计算时，逐渐在原路径中依次添加其它结点作为中间结点(添加结点时可依结点在 图中的序号依次加入)。若在第k步将 添加到路径中作为中间结点，那么需要 计算是否成立，若成立，就将新的路径长度作为 的值，反之，路径长度仍为原值，即：,k=1,2, n按照上述步骤类推，n次计算和比较后，得到的结果即为从到的最短路 径，其中，所求得的长度为 的值。由上述公式可得， 为图的邻接矩阵， 为 中间结点序号不超过k的、由 到 的最短路径的长度。A*算法启发式搜索(Heuristic Search)算法是指在搜索过程中，根据一个估价函数来 搜索下一个结点。其中最常

9、用的是A*算法。A*算法最初由Hart、Nilsson、Raphael等人提出。它的独特之处表现在，当 对下一个结点进行检查时，会根据已经获得的信息，估算出当前点到终点的长度， 以此来判断该检查的结点是否有可能处在最优路径上。它一般用已经付出的代价 与即将付出的代价之和作为其评价的标准，按照这种计算方法，可以大大节约搜 索时间，提高搜索效率，因为它总是优先搜索最有可能处于最优路径上的结点。 A*算法以Dijkstra算法为基础，而且也是启发式搜索中最重要、最常用的算法之 一。A*算法利用估价函数，搜索最有可能处于最优路径上的结点，算法中引进了 结点j的估价函数。其定义如下：其中， 表示由起始点

10、至j的实际费用值，表示由至终止点的最小费3 / 9用估量值。当时，A*算法退化为Dijkstra算法。A*算法适用于对路网的最佳优先搜索，它的前提条件是选择的估价函数必须满足某一特性，并且最优路 径是存在的，那么A*算法就一定可以搜索到此最佳路径。A*算法的估价函数随着问题的不同而不尽相同，使用者可以根据实际的情况 来选择的类型，在不大于j到终点的最小花费的情况下，就必然会有最优解，这时A*算法就可以求得最短路径。四、轨道交通客流分配模型的研究交通分配，即根据某种特定的方法将道路网中各0D间的交通量分配到各线 路上。其本质是模拟出行者选择路径的行为，以了解各OD间交通量的动态，从 而得出各路段

11、上的交通量。进行交通分配理论研究时，一般的做法是把城市系统 抽象为网络。如果讨论的对象为一个城市的话，那么所抽象的网络的结点就对应 着现实中的道路交叉点，连接两个结点的边对应着现实中的交叉点间的路段；而 如果讨论的对象为一个区域的话，那么所抽象的网络的结点就对应着区域中的一 个城市，连接两个结点的边对应着现实中的城市间的道路。简而言之，交通分配的问题实际上就是在起讫点间的交通量、道路交通网络 图、路径选择时的综合路径阻抗函数已知的前提下，将路网中的交通量按一定比 例分配，求解各路段的交通量。其中，起讫点间的交通量通常称为OD量，它是 指由Original （起始点）至Destination （

12、目的地）间的交通量。客流分配模型是城市轨道交通客流诱导系统的主要技术基础，它为诱导决策 提供依据。城市轨道交通客流分配模型以交通分配理论为依托，以乘客为交通出 行实体展开研究。交通分配准则交通分配准则，是对道路使用者选择路径的行为的描述。其一，OD间所有 可供选择的路径彼此制约；其二，网络中各路段均有其相应的路阻函数。路网中 的平衡交通流模式正是由二者的相互作用，以及道路使用者选择路径的原则所决 定的。J.GWardrop于1952年提出与出行路径选择相关的第一、第二原理48。 内容如下：第一原理：网络上的交通需求以这样一种方式分配，就是任一 OD对间所有 使用者的路径的出行费用都相等，且比未

13、使用的路径费用小。第二原理：网络上的交通分配，使得网络上所有出行的总费用最小。通常情 况，人们的出行符合Wardrop第一原理，相应的平衡状态是用户最优平衡（User4 / 9Equilibrium,即UE）；符合Wardrop第二原理所描述的平衡状态是系统最优平衡 （System Optimum，艮口 SO ）。UE的前提是出行者都想使自己在OD间所花费的时间最短，但是最短路径 上花费的时间会随着交通量而发生变化，当时间增加达到某个临界值时，由于拥 挤而使最短路径降为次短路径。此时，一些出行者就开始选择新的最短路径。以 此类推，新的最短路径也会变成次短路径。当只利用选择路径的方法不能减少出

14、行时间的时候，就达到了一种平衡的状态。这便是用户平衡分配的特征。与用户 最优平衡状态相对应的交通流称为用户最优平衡流。SO是系统规划者理想中的一种平衡状态，前提条件为所有出行者要彼此协 作，听从管理者的调度安排，使得系统的总费用最低。与系统最优平衡状态相对 应的交通流称为系统最优平衡流。通常认为，出行者独立选择路径的行为形成了路网中交通流的分布。在SO 模式下，出行者选择不同的路径能降低所花费的时间，所以，出行者趋于选择时 间最短的路径。最终，路网上交通量会达到UE状态的分布。UE状态相对于SO 状态可以更好地反映现实的交通状态。其分配准则是交通平衡分配模型的基础。 前提假设为：出行者了解整个

15、交通网当前状态下的全部信息，而且能够持续做出正确选 择；所有出行者的路径选择准则相同。根据Wardrop第一、第二原理，交通分配方法可以分成平衡模型和非平衡模 型。交通分配模型如果符合Wardrop第一、第二原理，那么就是平衡模型，否则， 就是非平衡模型。平衡分配的方法有很多种，一般都能够转化成一个有很大维数 的非线性的或凸规划的问题。理论上，此类模型的思路清晰，结构严谨，在宏观 研究中比较常用。然而，该类模型维数大，限制多，难以求解，虽然有近似的方 法，但是计算繁琐，难以用于实际的工程项目中。非平衡分配模型的结构简单， 概念清晰，计算简洁，普遍应用于实际的工程项目中。非平衡分配模型非平衡分配

16、模型依据不同的标准有不同的分类。一般可以按照分配手段和分 配形态划分。将非平衡模型分类组合，可得到：最短路径分配最短路径分配是静态交通分配的一种方法。计算时，假设路段上花费的时间 为一个不变的值，所有0D对间的OD量都分配到其间的最短路上，其它路径上 的交通量为零，即全有全无分配。最短路径分配计算过程简单，但由于0D量 都聚集在最短路中，导致某些路段上交通量过大，不符合实际交通流的状态。通 常，该方法不适合单独用于路网的交通量分配中。容量限制分配容量限制分配是动态分配的一种方法，由于考虑了路段出行时间和交通最大 容量间的关系，接近实际，因而被广泛应用。可以细分为容量限制一一增量加载 分配和容量

17、限制t迭代平衡分配这两种方式。容量限制一一增量加载分配，是一种使用启发式算法的近似平衡分配方法。 基本思想为：将路网中的0D量分成若干部分，然后依次把每一部分的OD量分 到各个路段上。每次都根据最短路方法分配，之后重新对各个路段的费用进行计 算，然后按照新的费用值再次进行分配，直至所有OD量分配完为止。此方法运 算简单、容易实现，可根据分配次数调整精度，比较实用，但也存在着隐患，可 能出现大量的客流被分配到容量较小的路段上，难以求出平衡解。容量限制一一迭代平衡分配是一种循环的分配方法，它处于增量分配和平衡 分配之间。基本思想为：首先假设所有路段上的流量均为零，并且根据流量计算 路径费用，通过不

18、断调整已分配到路段上的客流量，使各路段交通流近似或达到 平衡。每次分配，都依据路段已得到的交通量求出路径费用，然后按最短路方法 分配，如果两次相邻分配的交通流量相差不多，计算就可以终止。最后一次计算 求出的分配量就是最终的交通量。否则，就需要重复进行分配。此方法在理论上 存在不足，因为它不能预先估算迭代的次数，且无法确定算法最后是否收敛。静态多路径分配静态多路径分配，即Logit分配。由于交通环境复杂以及存在的不确定状况， 出行者可以使用概率分配方法来选择出行路径，综合各种影响因素确定每条路径 被选择的概率，之后，按照各路段的概率将交通量合理分配。此方法恰当地体现 了路径选择时的最短路因素和随

19、机因素。动态多路径分配动态多路径分配类似于容量限制分配，也分为动态多路径一一增量加载分配 和动态多路径一一迭代平衡分配这两种方式。动态多路径分配的步骤、路径费用 更新和参数确定的方法与容量限制分配是一样的，唯一的区别为：容量限制分配 方法每次使用最短路方法进行分配，而动态多路径分配方法，每次使用静态多路 径方法进行分配。有效路径搜索算法城市轨道交通中的有效路径的搜索结果对路网中的配流有直接的影响。目前， 常用的有效路径的搜索算法包括K条渐短路径搜索算法、Dial算法以及基于图的 遍历算法。K条渐短路径搜索算法由于预测时会有误差，所以诱导系统中得到的最短路径可能并非实际的最短 路径。而出行者出行

20、时也并不是非要只选择最短路径，也可能考虑其它因素选择 次短路径、渐短路径。况且，如果仅向出行者提供唯一的最短路径，很容易造成 车流积聚。所以诱导系统需要同时提供目标值从小到大的K条最短路径，供出行 者选择。同时计算出某范围内的若干条最短路径的问题在学术上称为K条渐短路 径问题。i最短路径(FSP)算法根据Dijkstra算法可以计算出路网中任意两站之间的最短路径。ii次短路径(SSP)算法次短路径算法的实质：计算出起讫站点间的最短路径后，依次删去原图中属 于最短路径的一条边，然后根据算法(1)计算新图的最短路径，即得出次短路径， 不断循环该过程，直至最短路径中所有边均被删除过为止。iii渐短路

21、径(TSP)算法渐短路径算法是以算法(2)为基础计算的。首先判断最短路径和次短路径中 是否存在相同边，如果存在，那么删除该相同边，并用算法(1)进行搜索，重复 此过程直至最短路径与次短路径中不存在相同的边为止；然后把最短路径和次短 路径中剩余的不同的边进行匹配，依次删除边对，再用算法(1)进行搜索。Dial算法有效路径在Dial算法中的定义如下：路径中的各路段均使出行者到起点的路 径费用逐渐增大，而到终点的路径费用逐渐减小，满足该要求的路径称为有效路 径。Dial算法在路网中各路段的两端点(i,j)，引入两个变量：r(i)：结点i至起点r的最小路径费用；s(j)：结点j至终点s的最小路径费用。

22、当且仅当满足条件r(i)s(j)时，路段(i,j)可以称为0D对(r,s)间的一条 有效路径。基于图的遍历搜索算法该算法搜索有效路径时有一个前提条件，它假设每一条路径中都不存在重复 的结点，也就是说所有的路径中均没有回路存在的现象。这个假设前提在现实的 轨道交通路网中是符合实际情况的，因为在正常情况下，没有人出行的起点和终 点是一样的，走一圈又回到原点的事情是不存在的。该算法的基本思想：根据图的遍历算法，在图中搜索由指定起点至终点的有 效路径，即相互连通并满足约束条件的路径，若满足约束条件，那么就将此路径 记下来，否则，就要向上一层结点回溯，然后再重新进行遍历。如此循环选择和 回溯，直至搜索到图中全部有效路径。进行该算法时，遍历到任何一个结点，该 结点都有多个后继结点可以选择，至于要选择哪个结点可以顺利找到有效路径并 没有任何明确的暗示或是确定信息，只能尝试选择某一结点继续向下搜索，直至 终点。如果搜索过程中不满足约束条件的话，就需要向上一层结点返回，之后重 新遍历。该算法利用深度优先搜索进行图