基本交通分配模型

基本交通分配模型第1页，课件共69页，创作于2023年2月9.1交通分配与平衡由于连接OD对间的道路有很多条，如何将OD交通量正确合理地分配O与D之间的各条路线上，是交通分配模型要解决的首要问题。如果两点之间有很多条路线，而这两点之间的交通量又很少的话，这些交通量显然会选择最短的路行走。随着两点间交通量的增加，选次短路，，最后两点间的所有路线都有可能被利用。如果道路用户都能准确知道各路线的行驶时间，并选择时间最短的路线，最终两点间被使用的各条道路的行驶时间会相等；而没有被利用的路线的行驶时间更长。这种状态称为：道路网的均衡状态。由于在实际的交通分配过程中，有很多对OD，每一OD对间又有很多条路线，且路线间有许多路段相互交织。由于这种复杂性，1952年Wardrop提出了网络均衡的概念和定义后，如何求解均衡交通分配成了运输研究者的重要课题。第2页，课件共69页，创作于2023年2月1956年，Backmann提出了均衡交通分配的数学规划模型。20年后即1975年才由LeBlance等人将Frank-Wolfe算法用于求解Backmann模型获得成功，从而形成了现在的实用解法。Wardrop对交通网络均衡的定义为：在考虑拥挤对走行时间影响的网络中，当网络达到均衡状态时，每对OD间各条被使用的路线具有相等而且最小的走行时间，其它任何未被使用的路线其走行时间大于或等于最小走行时间。通常称为Wardrop第一原理或用户优化均衡原理。实例第3页，课件共69页，创作于2023年2月9.2交通分配模型的分类第4页，课件共69页，创作于2023年2月举例说明非均衡交通分配、均衡交通分配与随机交通分配。第5页，课件共69页，创作于2023年2月均衡模型一般都可以归结为一个维数很大的凸规划问题或非线性规划问题。理论上说，这类模型结构严谨，思路明确，比较适合于宏观研究。但是，由于维数太大、约束条件太多，这类模型的求解比较困难，尽管人们提出了一些近似方法，但计算仍很复杂，实际工程中很难应用。相比之下，非均衡模型具有结构简单、概念明确、计算简便等优点，因此在实际工程中得到了广泛的应用。非均衡模型根据其分配手段可分为无迭代和有迭代2类，就其分配形态可分为单路径与多路径2类。因此，非均衡模型可分为如下表所示的分类体系。第6页，课件共69页，创作于2023年2月非均衡模型的分类体系第7页，课件共69页，创作于2023年2月9.3非均衡交通分配模型9.3.1最短路交通分配法（allornothingtrafficassignmentmodel）分配原理：每一OD对对应的OD量全部分配在连接该OD对的最短路线上，其它道路上分配不到交通量。分配步骤计算网络中每个出发地O到目的地D的最短路线；将该OD交通量全部分配最短路线上；每分配完一对OD后进行流量迭加，直到最后一对OD分配完毕。第8页，课件共69页，创作于2023年2月0-1分配法的特点计算简单；是其它交通分配的基础；出行量分布不均匀，全部集中在最短路上；未考虑路段上的容量限制，有时分配到的路段交通量大于道路的通行能力；有时某些路段上分配到的交通量为0，与实际情况不符；随着交通量的增加，未考虑到行程时间的改变。第9页，课件共69页，创作于2023年2月第10页，课件共69页，创作于2023年2月0-1分配算例：第11页，课件共69页，创作于2023年2月9.3.2容量限制最短路交通分配法为克服最短路交通分配方法的缺陷，可采用容量限制最短路交通分配方法，这种方法既考虑了路权与交通负荷之间的关系（即随着道路上交通量的增大，行程时间也发生变化，即增大），同时也考虑到了交叉口、路段的通行能力限制。容量限制最短路交通分配法的原理如下：将原始的OD矩阵（n×n）阶分成k个同阶的小OD矩阵，然后分k次用最短路分配模型分配OD量，每次分配一个小OD矩阵，每分配完一个小OD矩阵，修正路权一次（采用路段阻抗函数模型），再分配下一个小OD矩阵，直到所有的小OD矩阵都分配完为止。在具体应用时，视路网的大小选取分配次数k及每次分配的OD量比例。实际常使用五级分配制，第一次分配OD总量的30%，第二次25%，第三次的20%，第四次15%，第五次10%。第12页，课件共69页，创作于2023年2月第13页，课件共69页，创作于2023年2月第14页，课件共69页，创作于2023年2月9.3.3增量分配法（incrementaltrafficassignmentmodel）增量分配法是容量限制最短路交通分配法的进一步推广，又称为比例配流方法。分配原则将原OD矩阵分成N

等份，对每一个小矩阵用最短路分配方法分配，完成以后，根据阻抗函数重新计算各条边的阻抗（时间），然后再对下一个小矩阵进行分配，直到N个矩阵分配完毕。第15页，课件共69页，创作于2023年2月算法描述第16页，课件共69页，创作于2023年2月增量分配法的特点当N=1时为0—1分配；当N→∞时，趋向均衡分配。该方法简单，精度可以根据N

的大小来调节，因而在实际中常被采用。该方法仍然是近似算法，有时会将过多的流量分配到容量小的路段。N越大，配流结果越接近均衡解，但计算工作量相应增加。另外，非常大的N值也不能完全保证配流结果一定满足用户均衡条件。第17页，课件共69页，创作于2023年2月算例：第18页，课件共69页，创作于2023年2月9.3.4二次加权平均分配法(methodofsuccessiveaverages)分配思路：该方法是一种介于增量分配法和均衡分配法之间的一种循环分配方法。基本思路是不断调整已分配到各路段上的交通流量而逐渐达到或接近均衡分配。在每步循环中，根据已分配到各路段上的交通量进行一次0—1分配，得到一组各路段的附加流量，然后用该循环中各路段的分配交通量和附加交通量进行加权平均，得到下一循环中的分配交通量。当连续两个循环中的分配交通量十分接近时，即可停止计算。最后一个循环中得到的分配交通量即是最终结果。分配步骤第19页，课件共69页，创作于2023年2月第20页，课件共69页，创作于2023年2月分配算例：

试用二次加权平均分配法（MSA方法）求解下面的固定需求交通分配问题（迭代2次）。第21页，课件共69页，创作于2023年2月9.4用户优化均衡交通分配模型（UserEquilibriumModel）UE（用户均衡）的概念最早由Wardrop于1952年提出。UserEquilibrium的基本假设有：假设出行者都力图选择阻抗最小的路径；假设出行者能随时掌握整个网络的状态，即能精确计算每条路径的阻抗从而做出完全正确的路径选择决策；假设出行者的计算能力和计算水平是相同的。UserEquilibrium的定义：当不存在出行者能单方面改变其出行路径并能降低其阻抗时，达到了UE状态。第22页，课件共69页，创作于2023年2月9.4.1均衡分配模型的建立Wardrop第一原理的数学描述变量说明：变量关系：第23页，课件共69页，创作于2023年2月Wardrop第一原理的数学描述第24页，课件共69页，创作于2023年2月

等价最优性条件（Backmann模型）第25页，课件共69页，创作于2023年2月算例：第26页，课件共69页，创作于2023年2月

对Beckmann模型的进一步说明第27页，课件共69页，创作于2023年2月9.4.2模型解的等价性和唯一性证明模型解的等价性证明就是证明UE模型与Wardrop第一原理等价，模型解的唯一性证明就是证明UE模型具有唯一的路段流量解。模型解的等价性证明对于任何一个非线性规划问题，其驻点（最优解）均满足一阶必要条件。如果UE模型的一阶必要条件等价于Wardrop均衡，则说明UE模型的解服从Wardrop均衡。由于UE模型的一阶最优性条件与Wardrop第一原理的数学描述相同，因此，模型的解为均衡网络流。具体有两种证明方法（拉格朗日函数法）。第28页，课件共69页，创作于2023年2月

模型解的唯一性证明凸规划：约束集是凸集（函数为凹函数）、目标函数是凸函数。对于凸规划，任何局部最优解必是全局最优解，即目标函数的最优值是唯一的。严格凸规划：约束集是凸集、目标函数是严格凸函数。对于严格凸规划问题，其最优点唯一。多元函数的梯度向量对向量的导数多元函数的Hesse矩阵第29页，课件共69页，创作于2023年2月考察UE模型的目标函数是否为严格凸函数第30页，课件共69页，创作于2023年2月考察UE模型的约束集是否为凸集分析UE模型，可见UE模型的约束均为等式约束和不等式（非负）约束，且约束条件均是线性约束。根据线性函数既是凸的又是凹的这一性质，所以UE模型符合“各约束函数都是凹函数”的条件，即约束集合是凸集。UE模型的唯一性结论UE模型的约束集是凸集，目标函数是严格凸函数，故UE模型是严格凸规划，模型有唯一最优解。这就是说，当达到均衡状态时，分配到各路段上的流量是唯一的。需注意的问题UE分配对于路段流是严格凸的、对于路径流则不一定是严格凸的。即模型有唯一的路段流量解而没有唯一的路径流量解。第31页，课件共69页，创作于2023年2月UE模型路径流不唯一的反例第32页，课件共69页，创作于2023年2月9.4.3UE模型的求解Backmann提出的上述交通分配数学规划模型沉睡20年后，1975年LeBlance等学者成功地将Frank-Wolfe算法用于模型的求解。最终形成了目前广泛应用的一种既严格又实用的解法（F-W算法）。UE模型是一组非线性规划模型。对于非线性规划模型既使现在也没有普遍通用的解法。只是对于某些特殊的非线性规划模型才有可靠的解法，而UE模型正是一种特殊的非线性规划模型。Frank-Wolfe算法是用线性规划逐步逼近非线性规划的方法来求解UE模型的。该方法是一种迭代算法。思路如下：从某一初始点出发，进行迭代，每步迭代中，先找到一个最速下降的方向，然后再找到一个最优步长，在最速下降方向上截取最优步长得到下一步迭代的起点。重复此过程，直到找到最优解。此法的前提条件是模型的约束条件必须都是线性的。

第33页，课件共69页，创作于2023年2月Frank-Wolfe算法简介第34页，课件共69页，创作于2023年2月第35页，课件共69页，创作于2023年2月UE模型的搜索方向问题第36页，课件共69页，创作于2023年2月最优步长的确定问题第37页，课件共69页，创作于2023年2月用户均衡交通分配模型的求解步骤第38页，课件共69页，创作于2023年2月F-W算法的缺陷F-W算法在迭代后期阶段收敛很慢，原因是当趋近于最优解时，搜索方向将垂直于目标函数在点的梯度。影响F-W算法收敛速度的因素还有：初始解、网络结构和拥挤程度。初始解离平衡点越近，则需要的迭代次数就越少；网络结构越复杂，或者说从起点到终点的可行路径数越多，则需要的迭代次数就越多；拥挤程度越大的网络，需要更多的迭代次数来达到平衡点。在实际应用中，对于大规模网络，通常4至6次迭代就够了。确定迭代次数时，要综合考虑原始数据的准确性、财力约束和具体的网络结构。第39页，课件共69页，创作于2023年2月UE分配算例：网络模型如下，试用F-W算法求两边的交通量。第40页，课件共69页，创作于2023年2月9.5系统优化均衡交通分配模型（SOModel）9.5.1SO模型的基本思想Wardrop第一原理有时也称为用户均衡（UE）原理、或用户最优原理。UE模型就是建立在UE原理上的数学模型。Wardrop第二原理——系统最优原理Wardrop还提出了另一原理，即系统最优原理，也称第二原理。Wardrop第二原理：在考虑拥挤对走行时间影响的网络中，网络中的交通量应该按某种方式分配以使网络中交通量的总行驶时间最小。第一原理与第二原理的比较Wardrop第一原理反映了用户选择路线的一种准则，分配出来的流量结果是道路网上交通利用者实际路径选择的结果；Wardrop第二原理反映的是一种系统目标，即按什么样的分配是最好的，为规划管理人员提供了一种决策方法，在实际中难以实现，除非所有的道路使用者都相互协作为系统最优而努力。第41页，课件共69页，创作于2023年2月9.5.2数学模型UE/SO模型目标函数的含义UE模型仅仅是一个能有效产生UE条件的数学结构，缺乏直观的物理或经济含义。Beckmann变魔术产生的。SO模型是可以直观理解的，其目标是令系统的总交通时间最小。数学模型第42页，课件共69页，创作于2023年2月UE模型与SO模型解的比较除非是特殊情况（如所有路段的时间是固定的常数），否则一般情况下SO解和UE解是不会相同的。在SO状态，所有的出行者都能够在统一指挥下做出协调路径选择，以确保系统的总时间最小，而UE状态下的出行者只考虑个体的出行时间最小。

SO问题的一阶最优性条件类似于UE模型的一阶最优性条件第43页，课件共69页，创作于2023年2月SO问题解的唯一性证明SO问题的约束条件是线性等式约束和非负约束，因此其可行域是凸集。考察SO模型的目标函数是否是严格凸函数。第44页，课件共69页，创作于2023年2月SO模型的Hessian矩阵是一个对角矩阵，由于路段走行时间函数是一个典型的凸的升函数，因此Hessian矩阵为正定矩阵。即SO模型的目标函数是一个严格凸函数。约束集是凸集，目标函数是严格凸函数，故SO模型是一个严格凸规划，有唯一的路段流量解。第45页，课件共69页，创作于2023年2月9.5.3SO模型和UE模型之间的关系很显然，二者只有目标函数不同，约束条件完全一致，故二者之间可以进行转化。

SO模型转化成UE模型来求解通过对走行时间函数的修正，可以利用UE模型来求解SO模型。只有当交通量较小时，道路上不存在拥挤时，系统最优和用户均衡才有可能相等；若道路上的交通量大时，二者不可能相等。

UE模型转化为SO模型显然，通过对走行时间函数进行不同的修改可使UE模型和SO模型进行相互转换。

UE模型与SO模型之间的差别举例第46页，课件共69页，创作于2023年2月9.5.4SO模型求解算例网络如下，试求系统最优均衡解。第47页，课件共69页，创作于2023年2月9.5.5能力诡异现象城市交通网络中，经常会遇到一种奇怪的反常现象。即在拥挤的道路网络中增加一条新的路段或对某些路段进行投资改造，增加其能力后不但不能达到改善交通状况的本意，反而会导致整个交通网络中拥挤程度的加剧，或使每个出行者的出行阻抗增加。这称之为Braess诡异现象。Braess诡异现象指出：增加网络中路段的数量反而使网络的总阻抗增加，而不是预料中的减少。第48页，课件共69页，创作于2023年2月Braess诡异现象的算例：

已知qOD=6，各路段的走行时间函数为t1(x1)=50+x1、t2(x2)=50+x2、t3(x3)=10x3、t4(x4)=10x4，试用Wardrop第一原理和第二原理直接求解网络①并计算系统的总走行时间。为缓解交通拥挤，在节点A和节点B之间再建一条道路，假设这条道路的走行时间函数为t5(x5)=10+x5，试用Wardrop第一原理求解网络②并计算系统的总走行时间。比较新建道路后，系统总走行时间的变化并简要分析其原因。（网络图中路段数字为路段的编号）

网络①网络②第49页，课件共69页，创作于2023年2月增加一条道路后系统的总走行时间反而增加了，这就是著名的Braess悖论。产生这种现象的根源在于UE原则下的交通分配每个人都极小化个人的出行时间，而不考虑对别人的影响，这样下来，尽管系统新增了道路但没有效果、甚至比以前更差。进一步分析还可以说明所谓的Braess悖论只可能发生在按照UE原则进行的交通分配上。就本例而言，产生能力诡异现象的根本原因在于：新增路段AB后，出行者新增了可选路径的机会（即路径OABD），但构成这条路径的路段3和路段4是网络的瓶颈路段，从而导致在一定的OD需求下网络的总出行时间增加。因此，投资当局在决定增扩线路时，一定要谨慎，并非增加或扩建了线路就一定能改善交通状态。相反，有的约束交通规则，如限制车辆在某—时间段（如高峰期）进入主干道，或有意让司机们走一些表面上不经济的路线，能使整个网络的交通拥挤程度减小，这就是考虑了系统最优原则。第50页，课件共69页，创作于2023年2月9.6随机交通分配模型（Logit型/Probit型）0-1分配法假定出行者对交通网络的结构和各条路段的阻抗非常清楚，因此在假定阻抗为常数的前提下，每对OD点之间的出行者都同时选择该点对之间的最短路径。但实际上，由于交通网络的复杂性和路段上交通状况的多变性，以及各个出行者主观判断的多样性，某OD点对之间不同出行者所感知的最短路径将是不同的、随机的，因此这些出行者所选择的“最短路径”不一定是同一条，从而出现多路径选择的现象。这种交通分配叫做“多路径分配”，或“随机加载”。第51页，课件共69页，创作于2023年2月9.6.1Logit型随机配流的基本理论假定用户对当前路网信息的掌握不完全；同时出行者对阻抗的估计视为随机变量。仍然用Wardrop第一原理选择路径，但这里的路径为估计最短路径，即OD对间存有多条路线，同一出行者对不同的路径存在着不同的估计，不同的出行者对同一路径也存在着不同的估计。对某一特定的出行者来说，他总是选择估计阻抗最小的路径。随机分配模型就是在研究路径估计阻抗分布函数的基础上，计算有多少出行者选择每一条路径。第52页，课件共69页，创作于2023年2月第53页，课件共69页，创作于2023年2月第54页，课件共69页，创作于2023年2月9.6.2Dial算法Dial算法（1971年由Dial提出）是有效体现Logit型随机分配思想的方法。Dial算法的基本原理：每一OD对对应的OD量只能在连接该OD对的有效路径上进行分配，流量分配的分离公式为Logit模型。有效路径：全部由有效路段组成的路径。有效路段是指令出行者离其起点越来越远、离其终点越来越近的路段，即沿着该路段前进能更靠近出行的终点。路段似然值为：如果仅考虑有效路径，则Dial算法产生的流量与在每一起终点间使用Logit路径分配模型的结果一致，即Dial算法产生的流量与Logit模型配流的结果等价。第55页，课件共69页，创作于2023年2月第56页，课件共69页，创作于2023年2月第57页，课件共69页，创作于2023年2月Dial分配例题：q19=1000，=1.0，按Dial算法进行分配。第58页，课件共69页，创作于2023年2月第59页，课件共69页，创作于2023年2月9.7随机多路径交通分配模型9.7.1多路径交通分配模型的改进由出行者的路径选择特性可知，出行者总是希望选择最合适的路线出行，如最短的、最快的、最方便的、最舒适的路线等，通常称之为最短路因素。但是由于交通网络的复杂性和交通状况的随机性，出行者在选择路线时往往带有不确定性，通常称之为随机因素。对于随机因素可理解如下，由于用户对当前路网信息的不完全掌握，出行时选择他认为是最短的路径，但这条路径实际上并不一定是最短的。并且不但同一出行者对不同的路径存在着不同的估计，而且不同的出行者对同一路径也存在着不同的估计。对某一特定的出行者而言，他总是选择他估计阻抗最小的路径出行。通常，最短路因素和随机因素存在于出行者的整个出行过程中，两因素所处的主次地位取决于可供选择的出行路线的路权差（时间、距离或费用差）。因此，各出行路径被选用的概率不同，其概率可采用Logit型的路径选择概率来进行计算。第60页，课件共69页，创作于2023年2月第61页，课件共69页，创作于2023年2月9.7.2有效路段与有效出行路线（1）路段与路线路线是指出行者从OD对的起点到OD对的讫点行走的线路；而路段则是指这一条线路上的某一段。（2）有效路段有效路段[i,j]定义为路段的终点j

比路段的起点i

更靠近出行终点s

的路段。即沿着此路段前进能更接近（或至少不远离）出行终点s

。（3）有效出行路线有效出行路线定义为由有效路段组成的出行路线。每一OD点对对应的OD量只能在其相应的有效出行路线上进行分配。第62页，课件共69页，创作于2023年2月（4）有效出行路线的长度有效出行路线L(i–j,s