第09章-基本交通分配模型PPT课件.ppt

单击此处编辑母版标题样式单击此处编辑母版副标题样式长沙理工大学交通运输工程学院第九章基本交通分配模型长沙理工大学交通运输工程学院9.1 交通分配与平衡 v 由于连接OD对间的道路有很多条，如何将OD交通量正确合理地分配O与D之间的各条路线上，是交通分配模型要解决的首要问题 v 如果两点之间有很多条路线，而这两点之间的交通量又很少的话，这些交通量显然会选择最短的路行走随着两点间交通量的增加，选次短路，最后两点间的所有路线都有可能被利用 v 如果道路用户都能准确知道各路线的行驶时间，并选择时间最短的路线，最终两点间被使用的各条道路的行驶时间会相等；而没有被利用的路线的行驶时间更长这种状态称为：道路网的均衡状态 v 由于在实际的交通分配过程中，有很多对OD，每一OD对间又有很多条路线，且路线间有许多路段相互交织由于这种复杂性，1952年Wardrop提出了网络均衡的概念和定义后，如何求解均衡交通分配成了运输研究者的重要课题 长沙理工大学交通运输工程学院v 1956年，Backmann提出了均衡交通分配的数学规划模型20年后即1975年才由LeBlance等人将Frank-Wolfe算法用于求解Backmann模型获得成功，从而形成了现在的实用解法。

v Wardrop对交通网络均衡的定义为：在考虑拥挤对走行时间影响的网络中，当网络达到均衡状态时，每对OD间各条被使用的路线具有相等而且最小的走行时间，其它任何未被使用的路线其走行时间大于或等于最小走行时间通常称为Wardrop第一原理或用户优化均衡原理 v 实例长沙理工大学交通运输工程学院9.2 交通分配模型的分类 长沙理工大学交通运输工程学院举例说明非均衡交通分配、均衡交通分配与随机交通分配 长沙理工大学交通运输工程学院v 均衡模型一般都可以归结为一个维数很大的凸规划问题或非线性规划问题理论上说，这类模型结构严谨，思路明确，比较适合于宏观研究但是，由于维数太大、约束条件太多，这类模型的求解比较困难，尽管人们提出了一些近似方法，但计算仍很复杂，实际工程中很难应用v 相比之下，非均衡模型具有结构简单、概念明确、计算简便等优点，因此在实际工程中得到了广泛的应用非均衡模型根据其分配手段可分为无迭代和有迭代2类，就其分配形态可分为单路径与多路径2类因此，非均衡模型可分为如下表所示的分类体系 长沙理工大学交通运输工程学院非均衡模型的分类体系长沙理工大学交通运输工程学院9.3 非均衡交通分配模型 9.3.1 最短路交通分配法（all or nothing traffic assignment model） v 分配原理：每一OD对对应的OD量全部分配在连接该OD对的最短路线上，其它道路上分配不到交通量。

v 分配步骤n 计算网络中每个出发地O到目的地D的最短路线；n 将该OD交通量全部分配最短路线上；n 每分配完一对OD后进行流量迭加，直到最后一对OD分配完毕 长沙理工大学交通运输工程学院v 0-1分配法的特点n 计算简单；n 是其它交通分配的基础；n 出行量分布不均匀，全部集中在最短路上；n 未考虑路段上的容量限制，有时分配到的路段交通量大于道路的通行能力；n 有时某些路段上分配到的交通量为0，与实际情况不符；n 随着交通量的增加，未考虑到行程时间的改变 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院0-1分配算例：长沙理工大学交通运输工程学院9.3.2 容量限制最短路交通分配法 v 为克服最短路交通分配方法的缺陷，可采用容量限制最短路交通分配方法，这种方法既考虑了路权与交通负荷之间的关系（即随着道路上交通量的增大，行程时间也发生变化，即增大），同时也考虑到了交叉口、路段的通行能力限制v 容量限制最短路交通分配法的原理如下：将原始的OD矩阵（nn） 阶分成 k 个同阶的小OD矩阵，然后分 k 次用最短路分配模型分配OD量，每次分配一个小OD矩阵，每分配完一个小OD矩阵，修正路权一次（采用路段阻抗函数模型），再分配下一个小OD矩阵，直到所有的小OD矩阵都分配完为止。

v 在具体应用时，视路网的大小选取分配次数k及每次分配的OD量比例实际常使用五级分配制，第一次分配OD总量的30%，第二次25%，第三次的20%，第四次15%，第五次10% 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院9.3.3 增量分配法（incremental traffic assignment model） v 增量分配法是容量限制最短路交通分配法的进一步推广，又称为比例配流方法 v 分配原则n 将原OD矩阵分成 N 等份，对每一个小矩阵用最短路分配方法分配，完成以后，根据阻抗函数重新计算各条边的阻抗（时间），然后再对下一个小矩阵进行分配，直到 N 个矩阵分配完毕 长沙理工大学交通运输工程学院v 算法描述长沙理工大学交通运输工程学院v 增量分配法的特点n 当 N = 1 时为01分配；当 N 时，趋向均衡分配n 该方法简单，精度可以根据 N 的大小来调节，因而在实际中常被采用n 该方法仍然是近似算法，有时会将过多的流量分配到容量小的路段nN 越大，配流结果越接近均衡解，但计算工作量相应增加另外，非常大的 N 值也不能完全保证配流结果一定满足用户均衡条件。

长沙理工大学交通运输工程学院算例：长沙理工大学交通运输工程学院9.3.4 二次加权平均分配法 (method of successive averages) v 分配思路：该方法是一种介于增量分配法和均衡分配法之间的一种循环分配方法基本思路是不断调整已分配到各路段上的交通流量而逐渐达到或接近均衡分配在每步循环中，根据已分配到各路段上的交通量进行一次01分配，得到一组各路段的附加流量，然后用该循环中各路段的分配交通量和附加交通量进行加权平均，得到下一循环中的分配交通量当连续两个循环中的分配交通量十分接近时，即可停止计算最后一个循环中得到的分配交通量即是最终结果 v 分配步骤长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院分配算例： 试用二次加权平均分配法（MSA方法）求解下面的固定需求交通分配问题（迭代2次） 长沙理工大学交通运输工程学院9.4 用户优化均衡交通分配模型（User Equilibrium Model） UE（用户均衡）的概念最早由Wardrop于1952年提出User Equilibrium的基本假设有：v 假设出行者都力图选择阻抗最小的路径；v 假设出行者能随时掌握整个网络的状态，即能精确计算每条路径的阻抗从而做出完全正确的路径选择决策；v 假设出行者的计算能力和计算水平是相同的。

v User Equilibrium的定义：当不存在出行者能单方面改变其出行路径并能降低其阻抗时，达到了UE状态长沙理工大学交通运输工程学院9.4.1 均衡分配模型的建立 Wardrop第一原理的数学描述 v 变量说明：v 变量关系 ：长沙理工大学交通运输工程学院v Wardrop第一原理的数学描述长沙理工大学交通运输工程学院 等价最优性条件（Backmann模型） 长沙理工大学交通运输工程学院算例：长沙理工大学交通运输工程学院 对Beckmann模型的进一步说明 长沙理工大学交通运输工程学院9.4.2 模型解的等价性和唯一性证明 v 模型解的等价性证明就是证明UE模型与Wardrop第一原理等价，模型解的唯一性证明就是证明UE模型具有唯一的路段流量解 模型解的等价性证明 v 对于任何一个非线性规划问题，其驻点（最优解）均满足一阶必要条件如果UE模型的一阶必要条件等价于Wardrop均衡，则说明UE模型的解服从Wardrop均衡 v 由于UE模型的一阶最优性条件与Wardrop第一原理的数学描述相同，因此，模型的解为均衡网络流 v 具体有两种证明方法（拉格朗日函数法）长沙理工大学交通运输工程学院 模型解的唯一性证明 v 凸规划：约束集是凸集（函数为凹函数）、目标函数是凸函数。

v 对于凸规划，任何局部最优解必是全局最优解，即目标函数的最优值是唯一的v 严格凸规划：约束集是凸集、目标函数是严格凸函数v 对于严格凸规划问题，其最优点唯一v 多元函数的梯度v 向量对向量的导数v 多元函数的Hesse矩阵长沙理工大学交通运输工程学院v 考察UE模型的目标函数是否为严格凸函数长沙理工大学交通运输工程学院v 考察UE模型的约束集是否为凸集n 分析UE模型，可见UE模型的约束均为等式约束和不等式（非负）约束，且约束条件均是线性约束根据线性函数既是凸的又是凹的这一性质，所以UE模型符合“各约束函数都是凹函数”的条件，即约束集合是凸集 v UE模型的唯一性结论n UE模型的约束集是凸集，目标函数是严格凸函数，故UE模型是严格凸规划，模型有唯一最优解n 这就是说，当达到均衡状态时，分配到各路段上的流量是唯一的 v 需注意的问题n UE分配对于路段流是严格凸的、对于路径流则不一定是严格凸的即模型有唯一的路段流量解而没有唯一的路径流量解 长沙理工大学交通运输工程学院UE模型路径流不唯一的反例 长沙理工大学交通运输工程学院9.4.3 UE模型的求解 v Backmann提出的上述交通分配数学规划模型沉睡20年后，1975年LeBlance等学者成功地将Frank-Wolfe算法用于模型的求解。

最终形成了目前广泛应用的一种既严格又实用的解法（F-W算法）v UE模型是一组非线性规划模型对于非线性规划模型既使现在也没有普遍通用的解法只是对于某些特殊的非线性规划模型才有可靠的解法，而UE模型正是一种特殊的非线性规划模型v Frank-Wolfe算法是用线性规划逐步逼近非线性规划的方法来求解UE模型的该方法是一种迭代算法思路如下：从某一初始点出发，进行迭代，每步迭代中，先找到一个最速下降的方向，然后再找到一个最优步长，在最速下降方向上截取最优步长得到下一步迭代的起点重复此过程，直到找到最优解此法的前提条件是模型的约束条件必须都是线性的 长沙理工大学交通运输工程学院Frank-Wolfe算法简介长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院UE模型的搜索方向问题 长沙理工大学交通运输工程学院最优步长的确定问题 长沙理工大学交通运输工程学院用户均衡交通分配模型的求解步骤 长沙理工大学交通运输工程学院F-W算法的缺陷 v F-W算法在迭代后期阶段收敛很慢，原因是当趋近于最优解时，搜索方向将垂直于目标函数在点 的梯度v 影响F-W算法收敛速度的因素还有：初始解、网络结构和拥挤程度。

初始解离平衡点越近，则需要的迭代次数就越少；网络结构越复杂，或者说从起点到终点的可行路径数越多，则需要的迭代次数就越多；拥挤程度越大的网络，需要更多的迭代次数来达到平衡点v 在实际应用中，对于大规模网络，通常4至6次迭代就够了确定迭代次数时，要综合考虑原始数据的准确性、财力约束和具体的网络结构 长沙理工大学交通运输工程学院UE分配算例：网络模型如下，试用F-W算法求两边的交通量 长沙理工大学交通运输工程学院9.5 系统优化均衡交通分配模型（SO Model） 9.5.1 SO模型的基本思想 v Wardrop第一原理有时也称为用户均衡（UE）原理、或用户最优原理UE模型就是建立在UE原理上的数学模型v Wardrop第二原理 系统最优原理n Wardrop还提出了另一原理，即系统最优原理，也称第二原理n Wardrop第二原理：在考虑拥挤对走行时间影响的网络中，网络中的交通量应该按某种方式分配以使网络中交通量的总行驶时间最小v 第一原理与第二原理的比较n Wardrop第一原理反映了用户选择路线的一种准则，分配出来的流量结果是道路网上交通利用者实际路径选择的结果；n Wardrop第二原理反映的是一种系统目标，即按什么样的分配是最好的，为规划管理人员提供了一种决策方法，在实际中难以实现，除非所有的道路使用者都相互协作为系统最优而努力。