nullnull9.1平衡和非平衡分配
9.2非平衡分配法
9.3平衡分配法
9.4随机分配(Stochastic Assignment)方法
null【例
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
9-1】
设OD之间交通量为q=2000辆，有两条径路a 与b。径路a行驶时间短，但是通行能力小，径路b行驶时间长，但通行能力大。假设各自的行驶时间（min）与流量的关系如下式所示，求径路 a 与b上分配的交通量。
null根据 Wardrop平衡第一原理的定义，很容易建立下列的方程组：
则有：
显然 qb只有在非负解时才有意义，即：
也就是说，当OD交通量小于250时， ，则
当OD交通量大于250时，两条径路上都有一定数量的车辆行驶.当q=2000时，平衡流量为:null目前，在交通流分配理论的中，以 Wardrop第一原理为基本指导思想的分配方法比较多。国际上通常将交通分配方法分为平衡分配和非平衡分配两大类。
对于完全满足Wardrop原理定义的平衡状态，则称为平衡分配方法；对于采用启发式方法或其他近似方法的分配模型，则称为非平衡分配方法。nullnull非平衡分配方法
按其分配方式可分为变化路阻和固定路阻两类；
按分配形态可分为单径路与多径路两类。表9-1 非平衡分配模型分类 null算法思想：
将OD交通量q加载到路网的最短径路上，从而得到路网中各路段流量的过程。
计算步骤：
步骤0初始化，使路网中所有路段的流量为0，并求出各路段自由流状态时的阻抗。
步骤1计算路网中每个出发地O到每个目的地D的最短径路。
步骤2将O、D间的OD交通量全部分配到相应的最短径路上。null0-1分配法的特点
计算简单；
是其它交通分配的基础；
出行量分布不均匀，全部集中在最短路上；
未考虑路段上的容量限制，有时分配到的路段交通量大于道路的通行能力；
有时某些路段上分配到的交通量为0，与实际情况不符；
随着交通量的增加，未考虑到行程时间的改变。 nullnull增量分配法是容量限制最短路交通分配法的进一步推广，又称为比例配流方法。
分配原则
将原OD矩阵分成 N 等份，对每一个小矩阵用最短路分配方法分配，完成以后，根据阻抗函数重新计算各条边的阻抗（时间），然后再对下一个小矩阵进行分配，直到 N 个矩阵分配完毕。
nullStep0：初始化。将每组OD交通量平分成N等份，即使 。同时令 。
Step1：更新路段行驶时间 。
Step2：增量分配。按Step1计算出的路段时间 ，用最短路分配法将 分配到网络中去，得到一组附加交通流量 。
Step3：累加交通流量，即
Step4：判断终止条件。如果n=N，停止计算，当前路段流量即是最终分配结果；如果n
规划
污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文
模型。
经过20年之后，即到1975年才由LeBlanc等学者
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
出了求解Beckmann模型的算法（将Frank-Wolfe算法用于求解该模型），从而形成了现在的实用解法。
nullUser Equilibrium（用户均衡）的基本假设有：
假设出行者都力图选择阻抗最小的路径；
假设出行者能随时掌握整个网络的状态，即能精确计算每条路径的阻抗从而做出完全正确的路径选择决策；
假设出行者的计算能力和计算水平是相同的。
UE的定义：当不存在出行者能单方面改变其出行路径并能降低其阻抗时，达到了UE状态。null一、用户平衡分配模型及其求解算法
（1） 模型化
其中，hkrs：OD对rs间第k条径路的交通量。
tkrs ：OD对rs间第k条径路的行驶时间。
trs：OD对rs间最短径路的行驶时间。
qrs ：OD对rs的分布交通量。
null路段阻抗： ta=ta (xa)【例9-3】 如图表示了一对由两条可选路径连接的起终点，t1,t2分别表示路段1,2上的交通时间，用x1, x2表示相应的交通流量，q表示总的OD流量，则q=x1+x2。
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
：当q非常小时，所有用户都选择路段1，也即：
当q=q’时， x1>0, x2>0;此时，若已知t=t1= t2则 x1=t1-1 (t)，x2=t2-1 (t)null(2) Wardrop第一平衡原理的等价最优化问题
原理理论上合理，实际求解非常困难。
Beckmann（1956）等价数理最优化模型（有约束非线性最优化问题）
其中： ，表示路段a上的交通流量；
：路段 - 径路相关变量，即 0-1 变量。如果路段a属于从出发地为r目的地为s的OD间的第k 径路 ，则其值为1 ，否则为0 ；
fkrs ：出发地为r ，目的地为s的 OD 间的第k条径路上的流量；
qrs ：出发地r和目的地s之间的 OD 交通量。
null【 例题 9 -4 】：
如图所示， 为一个只有两条径路（同时也是路段）、连接一个出发地和一个目的地的 简单交通网络，两个路段的阻抗函数分别是：
t1 =2+x1 ， t2 =1+2x2
OD 量为 q=5 ，分别求该网络的 Beckmann 模型的解和均衡平衡状态的解。
null【 解 】 ：
先求 Beckmann 模型的解。将阻抗函数带入模型，得：
将 x2 =5-x1带入目标函数并进行积分，转换为无约束的极小值问题：
min: Z(X)=1.5x12 -9 x1 +30
另 dZ/dx1=0 ，解得 x1*=3 ， x2*=2 。
null下面求平衡状态的解，根据 Wardrop 用户平衡原理，网络达到平衡是应该有：
t1=t2和 x1+ x2 =5 。联立求解这个方程组，很容易求得 x1=3 ， x2 =2 。此时 ，t1=t2=5 。
可见，对于该路网，Beckmann 模型的解和平衡状态的解完全相同。
null（3）Beckmann 模型等价于 Wardrop 原理的证明
证明：
对Bechmann的模型构造拉格朗日方程如下：
（9-1）
其中， urs是拉格朗日乘子。根据非线性规划理论中的库恩 -塔克（ Kuhn-Tucher ）条件，拉格朗日函数在极值点必须满足下列条件：
（9-2）
另外，对拉格朗日乘子求偏导，可得到：
（9-3）
null通过对拉格朗日函数求偏导可以得到 式 （9-2）和 式 （9-3）中各项的具体结果，过程如下：
（9-4）
其中， (L：网络中路段的集合)
又因为， 以及，
所以， （9-5）
其中clmn：出发地为m，目的地为n的 OD 间的第l条径路的阻抗； null另外，在式（9-4）的第二项中， 。 因此，第二项可以简化为：
（9-6）
将式（9-5）和 式（9-6）代回式（9-4），得:
因此式（9-2）的库恩-塔克条件可以简化表 式示为：
（9-7a）
（9-7b）
null式（9-7）对任意的k，r，s都成立，即对任意的OD对都成立。进一步分析其实际意义可知 ，对于某个特定的连接r和s的径路，某径路k的流量fkrs由两种可能：
①如果fkrs >0，由式（9-7a），得ckrs =urs ；
②如果fkrs =0，由式（9-7b），得ckrs ≥urs 。
因此，任何情况下， 径路k的阻抗总是不小于拉格朗日乘子urs 。据此推断， 就是(r,s)间的最小阻抗。
当径路k上有从(r,s)的流量时， 径路k的阻抗必等于(r,s)间最短 径路的阻抗；当径路k上没有从(r,s)的流量时， 径路k的阻抗必大于或等于(r,s)间最短径路的阻抗。
而这正是 Wardrop 平衡原理所描述的，因此， Beckmann 模型的解满足 Wardrop 的平衡准则。null（4）解的唯一性证明
模型具有唯一解的条件：约束条件式形成凸领域，并且目标函数为狭义凸函数。
补充知识：
对于区间I, 设f(x)为定义在区间I上的函数，若对I上的任意两点x1， x2和任意的实数λ∈(0,1)，总有
f(λ x1 +(1-λ) x2)≤λf(x1)+(1-λ)f(x2),
则f(x)称为I上的凸函数。
判定方法可利用定义法、已知结论法以及函数的二阶导数nullBeckmann模型的约束条件均为线性函数，所以形成的领域为凸领域。
Z函数为凸函数的条件为：∂2Z/ ∂xa2>0
由目标函数知，∂Z/ ∂xa=ta(xa),因为 Beckmann 模型建立的假设前提是路段的阻抗只和自身的流量有关，与别的路段的流量无关，所以：
null所以，目标函数Z海赛矩阵为：
当所有路段的阻抗函数都是单调递增函数时， ，则目标函数 Z 的海赛矩阵是正定的，目标函数是严格凸的。根据 Beckmann 模型建立时对阻抗函数要求是单调递增函数的前提，所以说 Beckmann 模型有唯一的最小点 x* 。也就是说，当达到分配平衡时，分配到各路段上的流量是唯一的。
null二、用户平衡分配模型求解算法
1975 年由 LeBlanc 等学者将 Frank-Wolfe 算法（F-W算法）用于求解 Beckmann 模型
F-W算法是用线性规划逐步逼近非线性规划的方法来求解UE模型的。思路如下：从某一初始点出发，进行迭代，每步迭代中，先找到一个最速下降的方向，然后再找到一个最优步长，在最速下降方向上截取最优步长得到下一步迭代的起点。重复此过程，直到找到最优解。此法的前提条件是模型的约束条件必须都是线性的。null梯度法(最速下降法 steepest descent method) null
（1）F-W算法简介
设有非线性规划模型：
min：Z= f(X)
s.t. AX=B ，X ≥ 0
式中 ：X 、B： 向量；A：矩阵。
对目标函数f(X)进行在X0处的一阶泰勒展开，得：
f(X) = f(X0 ) +▽f(X0) (X- X0 ) （ 9-8）
null此展开式将目标函数f(X)近似地表达成线性函数，则上述的非线性规划模型可以近似转化为下列线性规划模型：
min： Z=f(X0 ) +▽f(X0) (X- X0 ) （ 9-9）
s.t. AX=B ，X ≥ 0
去掉目标函数中的常数项，简化成如下等价的线性规划：
min ： Z=▽f(X0)X （ 9-10）
s.t. AX=B ，X ≥ 0
null解（ 9-10）线性规划问题，可以得到一组最优解 。 F-W 方法认为 和 的连线为目标函数的最速下降方向。然后把根据线性极值问题：
求得的 λ 作为最优步长。
令 ，从而得到下一步迭代的起点。如此循环，直到 和 十分接近为止。
由于该方法在每一步迭代中都必须求解一组线性规划问题，在一般的非线性规划模型中，该方法由于计算量过大而不适用。只是在近似线性规划模型易于求解时，该方法才有应用价值，而交通分配模型正好具有这一特点。null（2） Beckmann模型的搜索方向问题
已知迭代起点 ，求下一步迭代方向，即求解以下式为目标函数的线性规划：
s.t. ； ；
式中， 表示目标函数的梯度，X,Y表示矩阵；
ya为辅助路段流；
分析： 为已知数，求一系列ya ，使网络的总行驶时间最小的交通分配问题。
解法：0-1分配即可实现，即每一OD对均沿最短路分配，以获取辅助路段流ya。
求出的xn与yn的连线即为下一步迭代的方向，即
dn =yn -xn null（3）最优步长的确定问题
迭代步长由下面的一维极值问题决定：
s.t.
令 ，有：
可用许多一维搜索方法求得最优步长 （如二分法、0.618法等）。
null（4）Beckmann 模型的F-W算法求解方法:
步骤 1 ： 初始化。按照 ，进行 0-1交通分配，得到各路段的流量 ；令 n=1 。
步骤 2 ： 更新各路段的阻抗： 。
步骤 3 ： 寻找下一步迭代方向：按照更新后的{tan}，再进行一次 0-1 交通分配，得到一组附加流量 {yan}。
步骤 4 ： 确定迭代步长：用二分法求满足下式的λ 。
步骤 5 ： 确定新的迭代起点： 。
步骤 6 ： 收敛性检验 。 如果满足 ：
其中ε是预先给定的误差限值 。如果条件满足，则{ }就是要求的平衡解，计算结束；否则，令n=n+1 ，返回 步骤 2 。 null设图所示交通网络的OD交通量为200辆，各径路的交通费用函数分别如下式所示，试用F-W法求出分配结果。null【解】：
建立用户均衡模型为：
（1） 用全有全无分配法求解初始可行解：
（2） 求最佳搜索方向
继续用全有全无分配法求解，得：null(3)求最佳步长λ *
将 代入目标函数中，得 ：
这时，求满足dZ/d λ =0的λ*，：
所以， λ* =0.6
null这时，交通量：
费用（时间）：
目标函数：
收敛判定：
所以，满足了Wardrop第一平衡原理nullF-W算法的缺陷
F-W算法在迭代后期阶段收敛很慢，原因是当趋近于最优解时，搜索方向将垂直于目标函数在点 的梯度。
影响F-W算法收敛速度的因素还有：初始解、网络结构和拥挤程度。
初始解离平衡点越近，则需要的迭代次数就越少；
网络结构越复杂，或者说从起点到终点的可行路径数越多，则需要的迭代次数就越多；
拥挤程度越大的网络，需要更多的迭代次数来达到平衡点。
在实际应用中，对于大规模网络，通常4至6次迭代就够了。确定迭代次数时，要综合考虑原始数据的准确性、财力约束和具体的网络结构。 null（一）系统最优分配模型
（二） UE模型与SO模型解的比较
Wardrop第二平衡原理：在系统平衡条件下，拥挤的路网上交通流应该按照平均或总的出行成本最小为依据来分配。
适用于最大限度地使用现有道路系统的场合（智能交通系统），出于交通管理者的角度考虑。从径路选择角度，该分配方法与用户平衡分配法中用户一直选择时间上的最短径路不同，它有必要让用户选择最短径路以外的径路。null系统最优原理比较容易用数学模型来表述，其目标函数是网络中所有用户总的阻抗最小，约束条件和用户平衡分配模型一样。因此，系统最优分配模型是：
其中：
null对阻抗函数进行变换 ，令：
则：
null【 例题 9 -6 】：试用系统最优分配法求出例 9 -5 中分配结果，并与用户均衡模型结果进行比较。
【解】：
建立系统最优分配模型
也即:
null（1） 用全有全无分配法求解初始可行解：
（2） 求最佳搜索方向
继续用全有全无分配法求解，得：
(3)求最佳步长λ *
将 代入目标函数中，得 ：null代入上述目标函数Z中，得：
这时，求满足dZ/d λ =0的λ*，
所以， λ* =0.7。这时，交通量：
费用（时间）：
目标函数：
null(4)收敛判定：
(5)第二次迭代，按照更新后的费用进行全有全无分配：
(6)求最佳步长λ *
null代入上述目标函数Z中，得：
这时，求满足dZ/d λ =0的λ*，
所以， λ* =0 ，这时，交通量：
则知已得到最优解。
表9-2 结果比较null随机分配(Stochastic Assignment)
由于交通网络的复杂性和路段上交通状况的多变性，以及各个出行者主观判断的多样性，某OD点对之间不同出行者所感知的最短路径将是不同的、随机的，因此这些出行者所选择的“最短路径”不一定是同一条，从而出现多路径选择的现象。这种交通分配叫做“多路径分配”，或“随机加载”；
单一径路分配→多径路分配
null假定用户对当前路网信息的掌握不完全；同时出行者对阻抗的估计视为随机变量。
仍然用Wardrop第一原理选择路径，但这里的路径为估计最短路径，即OD对间存有多条路线，同一出行者对不同的路径存在着不同的估计，不同的出行者对同一路径也存在着不同的估计。对某一特定的出行者来说，他总是选择估计阻抗最小的路径。
随机分配模型就是在研究路径估计阻抗分布函数的基础上，计算有多少出行者选择每一条路径。
null设某OD对（r,s）之间每个道路利用者总是选择自己认为阻抗最小的径路k，此时称道路利用者主观判断的阻抗值为“感知阻抗”，用Ckrs表示；用ckrs表示径路的实际阻抗，则有：
式中 ：εkrs—随机误差项，有E[εkrs]=0。
根据Wardrop径路选择原则，第k条径路被选择的概率为：
根据效用理论中有关“效用”的定义，可以用径路感知阻抗的负值来表示选择的效用 ，即：
null此时，径路的选择就是一个多项选择中挑选效用最大的选择枝的问题。根据随机效用理论，假定εkrs相互独立，且服从相同的Gumbel分布（此时，可以用一个ε表示所有的εkrs ）的条件下，径路k的选择概率为：
式中 ： b—参数，与ε的方差有关，可以证明 。
上式即为第七章中讲述的Logit模型。用该模型求径路选择概率需要把点对（r，s）之间所有的径路都找出来，这在实际中是非常困难的。null1971年Dial发明了一种算法，能够在网络上有效地实现Logit模型，但它并不需要求解连接OD点对的所有径路的选择概率和交通量。该算法具有下列特点：
（1）认为道路利用者不是在出发点就决定选择哪条径路，而是在出行过程中的每一个节点都做一次关于下一步选择哪条路段走向目的地的选择。
即真正选择的不是径路，而是路段
（2）道路利用者在一个节点处选择路段时，并不是以该节点为起点的每个路段都考虑，只有并选择“有效路段”。null有效路段的定义是：当路段（i,j）的上游端点i比下游端点j离起点r近，而且i比j离终点s远，则该路段为有效路段。
由有效路段组成的径路称为有效径路。
Dial算法可以确保出行量分配在使其有效地远离其起始节点的径路上，那些“走回头路”的径路将被剔除掉。
Dial算法与Logit模型的计算结果完全一致，二者是等价的。nullDial算法的具体步骤如下：
步骤1 初始化。确定有效路段和有效径路。
1 ）计算从起点r到所有节点的最小阻抗，记为r(i)；
2） 计算从所有节点到终点s的最小阻抗，记为s(i)；
3） 定义Qi为路段起点为i的路段终点的集合；
4）定义Di为路段终点为i的路段起点的集合；
5）对每个路段（i, j），根据下式计算“ 路段似然值（Link Likelihood）” L(i,j)（此时通常假定参数b=1）： null步骤2 从起点r开始按照r(i)上升的顺序，向前计算路段权重。
步骤3 从终点s开始，按照s(j)上升的顺序，向后计算路段交通量。null【例9-7】如图a所示的交通网络，图中边上的数值是路段的交通阻抗，起点r为①，终点s为⑨，设q19=1000，求该网络的随机分配结果。(a) 交通网络图null【解】
步骤1 初始化。找出有效路段和有效径路。
（1）根据最短路算法，求出所有的r(i)和s(i)值，如图(b)所示；
(b) 最短路权r(i)和s(i)值null（2）根据路段似然值公式，求出所有路段的似然值（此时设b=1），如图(c)所示。
以L(5,8)为例说明如何计算：
因为 ，
所以
根据上述计算结果，可知从1到9并非6条径路都是有效径路，其中只有4条为有效径路，即：1→2→5→6→9，1→4→5→6→9，1→2→5→8→9，1→4→5→8→9
null步骤2 从起点r开始按照r(i)上升的顺序，向前计算路段权重。
各路段的权重标于图(d)上。
以W(5,8)为例说明如何计算：
W(5,8)=L(5,8) *[W(2,5)+W(4,5)]=1*(0.368+1)=1.368
null步骤3 从终点s开始，按照s(j)上升的顺序，向后计算路段交通量。
各路段分配的交通量图(e)上：
以x(2,5)为例说明如何计算：
可以证明，上述算法得到的结果与Logit模型的分配结果完全一致，即Dial算法与Logit模型是等价的。
null容量限制的多路径分配方法即为阻抗随交通量发生变化的分配方法。与容量限制－最短路交通分配法类似，考虑了路权与交通负荷之间的关系，也考虑了交叉口和路段的通行能力限制，分配结果将更加合理。
与非平衡分配方法中介绍的阻抗变化的单径路分配方法相同， 阻抗变化的多径路分配方法也可分为增量加载和迭代加权两种方法。
null容量限制 — 增量加载分配法
将初始OD表（n×n 阶）分解成 k 个OD分表（ n×n 阶），分 k 次用多路径分配模型分配OD量。每次分配一个OD分表，每分配完一个OD分表修正路权一次，直至 k 个OD分表全部分配到网络上。
容量限制－增量加载分配法的分配流程如下图所示。
nullnull交通分配问题虽然可以用数学模型来加以描述并求解，但仍然存在着如下的一些问题。
（1）对交通流量的近似假定。
常见的分配模型总是假定OD对间的OD量为一个常数，并且只有在这种条件下，才会达到网络的“平衡”。
然而在现实的网络中，OD量总是随时间发生变化的，因此在实际的分配中最好是使用动态OD量来进行交通分配，但这样一来会增加模型的复杂性和求解的难度。
同时在分配过程中还需要考虑到弹性需求交通分配问题。 null（2）用户路径选择行为的假定
在交通分配模型中，常假定路网的使用者都知道网络中各条线路的拥挤状况和所需的走行时间，但实际中道路使用者往往对路网的信息是不完全掌握的，因此要使用适当的变量来衡量用户对路网的熟悉程度。
在分配模型中，总假定用户以相同的
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
来进行路径选择，即所有的出行者都选择从起点到终点的最短路径，但实际当中人们的路径选择行为是不同的，路径选择的标准是多方面的，因此在分配中还有必要考虑用户的交通需求特性和出行的目的特性。 null（3）交通网络的局限性
交通分配中所采用的网络通常是经过简化后的网络，如删除网络中的某些狭窄道路，同一交通小区内假定有一个小区形心等，所有这些都会使分配的结果偏离实际情况。
同时，分配过程不仅对网络进行了简化，还对线路上的走行时间进行了简化，如分配模型中常用到的BPR函数仅考虑了线路上的流量和通行能力两个因素，而没有考虑到道路线形、交通管制、混合交通等因素的影响。综上所述，对交通分配模型还要进行进一步的研究，力争使分配的结果接近路网上的实际情况。 
浙公网安备 33021202002483