随城市人口的增长和社会经济的持续发展.ppt

随城市人口的增长和社会经济的持续发展，城市交通问题日益突出。立足长远目标，搞好城市交通规划，加强交通基础设施的建设是十分重要的。,交通分配模型,一般城市交通网络优化，通常彩所谓的“四阶段法”：交通生成，交通分布，交通方式选择和交通分配。其中前三阶段的模型方法比较成熟，第四阶段在实际路网中的实现难度比较大，由此派生的理论和方法也很多，但都难达到很好的效果，本节主要讨论交通分配模型。,数学模型,第一节交通网络系统的描述,我们用节点和弧来描述交通网络，节点对应于交叉路口，节点间的有向道路或路段对应于弧。,用出行成本综合表示出行者在弧上行驶所花费的时间、费用等因素。,起论点（origin-destination，常称OD对）则是交通量的最早开始和结束节点。路或路径是指连接2个起论点之间的有向路段（弧）的序贯集合。,路径的出行成本就是该条路径所所含的弧出行成本之和，用G（N，A）表示一个交通网，其中N是节点集合，A是弧集合。,令：,I：产生交通量的起始节点集合，,J：吸引交通量的终迄节点的集合，,数学模型,：路段（弧）a上的交通流量。记,：路段（弧）a上的费用，记,数学模型,一个可行的路径流量h是指满足如下流量守恒条件的流量：,费用满足如下关系式：用矩阵表示如下：,（2）,数学模型,第二节UE配流的数学规划模型,在进行成市交通网络规划时，交通分配的目的是如何将每个OD对的交通需求量（在前三阶段已经求得）分配到交通网络的各条路段上去。通常采用的是均衡配流模型，这一类模型是在Wardrop平衡原则的基础上建立模型的。本节及今后几节着重讨论这一类模型。,Wardrop平衡配流原则：在起讫点之间所有可供选择的路线中，使用者所利用的各条路线上的出行费用全部相等，而且不大于未被利用路线上的出行费用。,满足这一原则的交通状态称为Wardrop平衡状态，上述配流原则又可称为用户平衡（UserEquilibrium，UE）配流。在平衡状态下，系统达到稳定，此时任何一个使用者（用户）在起记讫点之间都不能找到一条费用更小的线路，换句话说，任何一个用户都不能单方面改变其路径并能降低其费用。,数学模型,Becrmann用以下数学形式描述Wardrop平衡状态：其中为平衡状态下OD对之间的出行费用。,（4）,（5）,（6）,（7）,UE配流通常被归纳为如下一个凸规划问题：,（P1）,数学模型,（8）,（9）,在这个模型中，基于如下两个假设：1、假定弧费用仅仅是该弧流量的函数，与其它弧上的流量没有关系；2、拥挤效应：假定弧的费用是流量的严格增函数，用数学形式表达为：,数学模型,模型（P1）是凸规划问题（证明略），因而它的解是存在唯一的。其目标函数本身并没有什么直观的经济意义，但模型的解与Wardrop平衡原理是等价的。,下面我们将论述这一结论。,事实上，其拉格朗日函数为：,（10）,其中，、分别为拉格朗日乘子，、分别为其对应的向量表示。一阶条件为：,（11）,（12）,（13）,数学模型,其中,又因为,数学模型,（16）,（17）,注意到，是非负变量的拉格朗日乘子，因此有于是，（11）式为：,即,从而,又由（12）、（13）式得：,数学模型,显然，以上所推导出的一阶必要条件表达了用户平衡原则，即：连接OD对的路径可分为两类：一类路径上有流量，其费用总是等于最小OD费用；另一类路径上没有流量，其费用总是大于或等于最小OD费用，当流量分布达到平衡状态时，再没有一个司机能够通过单方面改变行驶路径而可以减少其行驶费用了。,数学模型,显然，（16）、（17）就是流量守恒约束，它们在平衡状态下自然满足。我们来分析（13）、（14）式。当时；当时，。这就是说，对应于OD对的拉格朗日乘子总是小于或等于连接OD对的任意路径的费用。因此,是起始节点到终讫节点之间的最小费用。,Becrmann等提出的城市交通平衡配流模型沉睡了多年以后，求解这个模型的有效算法才得以产生。其原因是模型（P1）的约束条件过多，而一般算法只适合小于型问题的求解，因而无法解决实际的平衡交通最分配问题。直到上世纪60年代后期，人们对问题（P1）的进一步研究才发现Flanr-Wolfe算法可以有效的解决这个问题。下面我们来介绍模型（P1）的求解算法。,F-W算法求解非线性凸规划模型（P1）的一般步骤是，当迭代次数为几时，令目标函数值下降的搜索方向应由解下面的线性规划问题得到：,（P2）,（19）,（20）,数学模型,（21）,（22）,（P2）,其中是可行路径流量，是可行路段流量。,由得，式（19）可变为：,以上各式中，是已知数，即由决定的路段出行费用，是要求解的未知数。因此，该模型实际上是在各路段出行费用一定的条件下使网络总费用最小的经典运输问题。显然，在这种情况下，将OD需求量全部沿OD间的最短路径上分配即可使目标函数值最小。求解出的决定了第n次迭代方向，即下一步迭代的方向为与的连线。至于本模型求解，一般的运算学书都人介绍。,数学模型,（24）,（25）,迭代长由下面的一维极值问题决定：,这一问题的求解，一般的高等数学书都可以查到。这样，线性规划（P2）可以得到下一步的迭代方向，求解一维极值问题（P3）可以得到迭代步长。因此，下一步的迭代点便可以由下式得出：,（P3）,对于算法的收敛性则，可以根据两次相邻迭代中交通流量的变化来判定，如果变化很小，就可以认为达到平衡而停止迭代：,（26）,其中为预选给定的值。,数学模型,现将以上算法规纳如下：第1步：初始化，令，将OD需求量全部加载到最短路径，得到弧流量，这一加载方法称为“全有全无”法（AllorNothing），置n=1；第2步：计算；第3步：搜索可行方向，根据，用“全有全无”法将OD需求量加载上网，得到弧流量；第4步：寻找迭代步长，求解一维极小值问题：求得步长；,数学模型,第5步：更新流量：置，第6步：收敛性检查：如果满足收敛性则，则算法终止，否则令n=n+1，转到第2步。此算法中在理论上需要求解满足相应约束条件的线性规划问题，对于大规模网络来说，求解这个线性规划问题的计算量相当大，而且在算法里每次迭代都要求解这样一个问题。从上面我们看到，由于交通网络的特殊结构，线性规划问题将被寻找最短路径所代替，从而大大缩短了算法的计算时间。,数学模型,第三节系统最优模型,该原理为：,在考虑拥挤对走行时间（出行费用）影响的网络中，网络中的交通量应该按某种方式分配以使网络中交通量的总走行时间（出行费用）最小。,该原则有时又称为Wardrop第二原则，相应地，前面的Wardrop原则称为Wardrop第一原则。,第一平衡原则反映了道路网利用都选择路线的一种准则。而第二平衡原则反映了一种目标，即按什么样的方式分配是最好的。在实际网络中不可能出现第二原则所描述的状态，除非所有的驾驶员互相协作为系统最优化而努力。这在现实中是不可能的。但第二原理为规划管理人员提供了一种决策方法。,数学模型,下面我们来分析系统最优模型SO与用户最优模型UE之间的关系。,则,因此，如果以作出行费用函数进行用户平衡分配，得到的解即是系统最优模型SO的解，即模型,数学模型,（32）,加上约束条件（5）、（6）、（7）式，即为SO模型（P3）如果令,则系统最优的目标函数,即为用户最大优模型中的目标函数。因而，对费用函数进行不同的修改，UE模型与SO模型可以相互转换。,数学模型,系统最优化比较容易用数学规划来表达。其目标函数是对系统的总走行时间（总出行费用）取最小值。约束条件与UE模型完全一样。因此，该问题可以归纳为下述模型：（P3）系统最优化（SgstemOptimization）模型，简称SO，其等价性证明与UE模型类似。,（27）,（28）,（29）,（30）,数学模型,第四节弹性需求的UE配流模型,前面介绍的UE模型是在OD交通量已知并且为常量的前提下建立的模型，但在现实中，OD交通量的大小可能会受网络运行情况的影响，比如当网络中两个节点之间的拥挤程度增加时，有些出行者可能会改变自己的出行计划或放弃出行，相应的OD对之间的交通量会减少。为反映这一现象，可以用一个函数来描述这种关系：,（33）,数学模型,其是是OD对之间的最小费用，表示之间的流量需求函数。通常是单调减函数，并且有上界。这类问题便是弹性需求下的配流问题。相对应地，前几节的问题移为固定需求问题。我们假设路段上的费用仅取决于该路段上的流量，而与每条路径有效的交通量仅取决于路径上的费用。这样，我们得出这一问题的数学规划模型描述：（P5）,（34）,（35）,（36）,（37）,此模型的等价性证明与UE平衡配流模型相似，模型的求解算法也大同小异，这些我们留给读者来完成。,数学模型,第五节随机平衡配流模型,不同的出行者对最短路径的估计是不同的，对于某一特定出行者来说，他总是选择最小估计阻抗的路径出行，这样的平衡配流问题称为随机平衡配流问题（StochasticUserEguilibrium,SUE）。,在实际出行过程中，出行者对路网状况以及交通现状并不可能完全了解，而且存在一些难以量化的因素，因此将路径费用视为随机变量更符合事实。如果我们仍用Wardrop平衡原则作为出行者的路径选择原则，所不同的是，这里的最短路径为估计的最短路径。,数学模型,由于每条路径的估计阻抗是随机变量，具有相应的概率密度函数，对于某一特定的出行者，每条路径均有一个被选择的概率。随机平衡配流模型就是研究在路径阻抗分布函数的基础上，计算有多少出行者选择每一条路径。假定OD对之间第r条路径被选择的概率是也就是其估计阻抗在i-j之间所有可能路径的估计阻抗中为最小的概率，即：由随机平衡配流的定义知，在这种平衡状态下，某个OD对之间所有被选用的路径上，并不一定有相同的实际阻抗值，而只满足下述条件：,（38）,（39）,数学模型,在此式中，路径流量与有关，而一估计路径阻抗大小有关，而实际路段阻阻是流量的函数，如此循环达到SUE的条件。显然，UE问题仅是SUE问题的特例。首先构造如下的数学规划模型，然后证明其与SUE条件之间的等价性以及解的唯一性。（P6）,（40）,如同UE问题一样，上述模型没有任何直观的行为或经济上的解释，仅是一个无约束的极小值问题，不过我们可以证明它的解满足SUE条件，且在解点上满足网络的所有守恒约束。,数学模型,下面我们来完成等价性和解的唯一性证明。等价性证明：对无约束的极值问题，其极值点上的一阶条件为：对于第一项有：=由于,（41）,数学模型,故上式可得对于第二项，有：对于第三项，有：从而，一阶条件为：,（42）,数学模型,如果路段阻抗函数是严格单调递增函数，即则当且仅当而此式正是SUE的条件，因此可知无约束最小化问题（P6）的解与SUE条件等价。解的唯一性证明：易证，目标函数的Hessian阵虽然是不确定阵，但其在平衡点上是正定的，即平衡点是该无约束极小化问题的一个局部极小点。而是严格凸的，从而该局部极小点是全局极小点。模型的算法留给读者去完成。,（43）,数学模型,第六节考虑路段交通量相互影响的平衡模型,在实际的交通网络中，路段旅行时间只与该路段流量有关的假设一般不成立，因为某路段的行走时间不仅仅受该路段交通量的影响，至少相邻路段交通量的相互影响在有些情况下是很严重的，例如在无信号灯路口的车流交织点或者双向车道上拥挤时对向车流间的相互影响等。,本节的路径费用只当作旅行时间，首先考虑受其它路段影响的一般路段旅行时间函数，然后分析路段交通量存在相互影响下的数学模型的建立和求解问题。,数学模型,6.1一般路段旅行时间函数考虑路段交通量相互影响时，这段旅行时间函数可表求为：当假设路段之间的相互影响对称时，有：反之，影响不对称时，有：此外，我们还假设：路段旅行时间为该路段上流量的严格增强函数，即：,（44）,（45）,（46）,（47）,数学模型,路段旅行时间主要受该路段本身流量的影响，也就是说，其它路段上交通量对该路段旅行时间的影响要比基本身流量的影响小得多有：考虑路段交通量相互影响时，这段旅行时间函数可表求为：,（48）,数学模型,式中表示集合A的元素个数。,6.2路段间相互影响对称情况一的均衡问题及解法我们先给出模型，然后再证明它的等价性和解的唯一性。对固定需求问题，相应的数学规划问题形式为：（P7）,（49）,数学模型,讨论只涉及小汽车和公共交通出行两种方式间的均衡，为简便起见，此处只考虑两个路段间有相互影响的情况，则上模型改写为：,（50）,数学模型,事实上，（50）式中求中项的第一项对求导，得（50）式中第2项对求导，得,数学模型,其等价生和解的唯一性证明如下：,事实上，（50）式中求中项的第一项对求导，得（50）式中第2项对求导，得,数学模型,其等价生和解的唯一性证明如下：,从而可见，目标函数对路段交通量的导数仍等于路段的旅行时间。从而其等价性成立。又因为路段旅行函数的Jacob矩阵为：当此矩阵为正定阵时，即目标函数的海赛矩阵正定时，问题具有唯一均衡解。由6.1节的假设、即得为正定矩阵。,数学模型,本模型用凸组合法解的步骤如下：（1）方向搜索所阶段需求解的线性规划问题为：即在第几步迭代的路网结果基础上进行一次全有全无分配。,数学模型,（2）步长的确定辅助流量确定后，通过求解下列一维优化问题得到步长：其它步骤与前面所述的算法类似，不再赘述。,数学模型,6.3路段间相互影响不对称情况下的平衡问题及解法由前述证明过程可知，当路段的旅行时间函数的Jacob矩阵不对称时，