随机用户平衡

随机用户平衡（共4篇）

随机用户平衡 篇1

1 前言

灵敏度分析是研究带有参数的数学系统的解随参数扰动而变化的问题,其内容包括计算解对扰动参数的偏导数、梯度等,借以掌握解依参数的变化趋势。常见的有微分方程、差分方程、代数方程、线性规划、非线性规划、变分不等式等问题的灵敏度分析。

一般来说,灵敏度分析主要有以下几个作用:

①当其中的一个或者几个参数有所扰动时用来求解新问题的解;

②可以较为容易地构造出解的一阶近似;

③可用来判断某个参数的灵敏性,使参数选取与控制更加适当;

④可用来对实际问题作预测;

⑤从理论角度来说,通过它可以对所研究的问题有更深入的了解,以便于发现新问题。

对非线性规划(或者变分不等式)的灵敏度分析进行研究的目的就是能够在实际问题中得以应用,比如经济学模型、运筹学以及交通分配、信号配时等问题。本文主要讨论的是交通分配模型的灵敏度分析,其作用主要有三个方面:第一,可以用来计算针对一些实际参数如绿信比、匝道及其交通需求等的灵敏性;第二,对扰动后的问题作预测,从而对实际路网及其控制策略的改进提供指导;第三,可以考虑用来构造求解交通中二层规划问题的算法,一定程度上降低求解这类NP难问题的复杂性。至今,已有许多人对数学规划和变分不等式的灵敏度分析进行了研究,其中比较重要的两篇就是A.V.Fiacco[1]和R.L.Tobin[2]。文献[1]主要讨论了可微二阶局部唯一解的灵敏度分析,并给出了一种采用罚函数法求解非线性规划问题的解的特殊的灵敏度分析结果; 文献[2]主要给出并证明了一系列关于变分不等式的灵敏度分析定理, 这些定理随后在作者的文献[5]中得以应用。另外也有一些关于特殊的数学规划的灵敏度分析方面的文章, 如S.C.Dafermos[3]和Qiu[4]。文献[3]给出了带线性供求函数的平衡网络模型的灵敏度分析,文献[4]专门介绍定义在多面体集上的变分不等式的灵敏度分析。至今已经有不少文章介绍了在交通分配方面的应用,其中比较重要的一篇是R.L.Tobin[5],文献[5]采用限制法讨论了平衡交通分配问题(变分不等式)的灵敏度分析, 给出了计算平衡路径流关于一些扰动参数的梯度信息等。Hai Yang在文献[6]、 文献[7]、 文献[8]中借助于常规的灵敏度分析结果分别给出了排队平衡网络、 带弹性需求的静态网络平衡问题的灵敏度分析。T.L.Friesz应用灵敏度分析法给出了平衡网络流的求解算法[9]。文献[12]针对信号控制问题利用启发式算法得到了延误函数的导数。文献[13]主要讨论灵敏度分析在求解二层规划的应用,并针对不同的约束条件给出了详细的算例分析。总体上说,前面所提到的灵敏度分析基本上都是利用一般的灵敏度结果对于静态交通分配扰动问题进行研究。对于以前所给出的灵敏度分析结果的不足之处要么是计算维数太高,要么是利用启发式算法给出近似结果,本文针对于此,给出了一种降低维数的解析法:利用文献[1]中所给出的Lagrange函数及带柯朗二次惩罚项的对数边际函数之间的关系,将原扰动问题的灵敏度分析结果利用无约束问题的分析结果近似,然后利用此种近似讨论了随机用户平衡分配的灵敏度分析结果,并给出了严格的证明及其算例。

2 非线性规划问题的灵敏度分析定理

考虑一般的非线性规划扰动问题P(ε)如下:

${\rm P}(\epsilon )\begin{array}{l}\underset{x}{{\displaystyle \min }}f(x,\epsilon )\\ \text{s}.\text{t}.g{}_i(x,\epsilon )\ge 0,i=1,2,\cdots ,m\\ h{}_j(x,\epsilon )=0,j=1,2,\cdots ,p\end{array}(1)$

对应的Lagrange函数及带柯朗二次惩罚项的对数边际函数分别为:

$\begin{array}{l}L(x,\pi ,\mu ,\epsilon )=f(x,\epsilon )-{\displaystyle \sum _{i=1}^m\pi }{}_{i}g{}_i(x,\epsilon )+{\displaystyle \sum _{j=1}^p\mu }{}_{j}h{}_j(x,\epsilon )\\ W(x,\epsilon ,r)=f(x,\epsilon )-r{\displaystyle \sum _{i=1}^m\text{l}}\text{n}g{}_i(x,\epsilon )+\frac{1}{2r}{\displaystyle \sum _{j=1}^{p}h}{}_j^2(x,\epsilon )\end{array}(2)$

其中πi,μj分别为对应于各个不等式约束和等式约束的Lagrange乘子,r为大于0的参数。

定理1(采用罚函数法时的一阶灵敏度结果) 若P(ε)满足以下条件:

(1) f(x,ε),gi(x,ε),hj(x,ε)在(x*,0)的邻域内二次连续可微;

(2) P(0)在x*,π*,μ*处满足局部极小点的二阶充分条件,即

(a) Kuhn-Tucker条件成立;

(b)对任意满足下条件的y(y≠0):

$\{\begin{array}{l}y{}^{{\rm T}}\nabla g{}_i(x{}^{*},0)\ge 0,g{}_i(x{}^{*},0)=0\\ y{}^{{\rm T}}\nabla g{}_i(x{}^{*},0)=0,\pi {}_i^{*}>0\\ y{}^{{\rm T}}\nabla h{}_j(x{}^{*},0)=0,j=1,2,\cdots ,p\end{array}$

有yTᐁ2L(x*,π*,μ*,0)y>0;

(3) 对于满足gi(x*,0)=0的i,ᐁgi(x*,0)和ᐁhj(x*,0)(j=1,2,…,p)组成的向量组线性无关;

(4) 严格互补松弛条件成立,即若gi(x*,0)=0,则π*i>0。

则有以下结论成立:

①在(ε,r)=(0,0)的某个小邻域内,存在唯一的一次连续可微向量函数(x(ε,r),π(ε,r),μ(ε,r))满足(x(0,0),π(0,0),μ(0,0))=(x*,π*,μ*)且满足以下方程组:

$\{\begin{array}{l}\nabla L(x,\pi ,\mu ,\epsilon )=0\\ \pi {}_{i}g{}_i(x,\epsilon )=r,i=1,2,\cdots ,m\\ h{}_j(x,\epsilon )=\mu {}_{j}r,j=1,2,\cdots ,p\end{array}(3)$

② 对靠近点(0,0)且r>0的(ε,r),x(ε,r)为无约束优化问题$\underset{x}{{\displaystyle \min }}W(x,\epsilon ,r)$的局部唯一极小点且满足:

(i) gi(x(ε,r),ε)>0,ᐁ2W(x(ε,r),ε,r)为正定矩阵;

(ii) 约束变量及其对应的Lagrange乘子关于扰动变量的梯度计算公式如下:

$\begin{array}{l}\begin{array}{l}\frac{dx(\epsilon ,r)}{d\epsilon }\\ =-[\nabla {}^{2}W(x(\epsilon ,r),\epsilon ,r)]{}^{-1}\frac{\partial }{\partial \epsilon }[\nabla W(x(\epsilon ,r),\epsilon ,r)]\end{array}\\ \frac{\partial \pi {}_i}{\partial \epsilon {}_s}=-\frac{r}{g{}_i^2}\left(\nabla {}_i^{{\rm T}}\frac{\partial x(\epsilon ,r)}{\partial \epsilon {}_s}+\frac{\partial g{}_i}{\partial \epsilon {}_s}\right)\\ \frac{\partial \mu {}_j}{\partial \epsilon {}_s}=\frac{1}{r}\left(\nabla {}_j^{{\rm T}}\frac{\partial x(\epsilon ,r)}{\partial \epsilon {}_s}+\frac{\partial h{}_j}{\partial \epsilon {}_s}\right)(4)\end{array}$

(iii) 当ε→$\overline{\epsilon }$,r→0时,有

$\begin{array}{l}x(\epsilon ,r)\to x(\overline{\epsilon })\\ \frac{dx(\epsilon ,r)}{d\epsilon }\to \frac{dx(\overline{\epsilon })}{d\epsilon }\\ \frac{d\pi (\epsilon ,r)}{d\epsilon }\to \frac{d\pi (\overline{\epsilon })}{d\epsilon }\\ \frac{d\mu (\epsilon ,r)}{d\epsilon }\to \frac{d\mu (\overline{\epsilon })}{d\epsilon }(5)\end{array}$

采用此种灵敏度分析结果进行近似的好处是ᐁ2W为n×n阶矩阵,而在一般的灵敏度分析结果的M(ε)[1]为(n+m+p)×(n+m+p)阶矩阵,因此在求解时可以降低维数,从而可以简化计算。

3 随机用户平衡分配(SUEA)扰动问题的灵敏度分析

符号说明:

I:所有O-D对所组成的集合,∀i∈I,记m=|I|;

Ki:第i个O-D对间的所有路径组成的集合,$\forall k\in {\rm K}{}_i‚{\rm K}={\displaystyle \underset{i\in {\rm I}}{\cup }{\rm K}}{}_i$,记p=|K|;

A:所有路段组成的集合,∀a∈A,记n=|A|;

hk:第k条路径的流量,组成的向量记为h=(hk)k∈K;

xa: 路段a上的交通流量, 组成的向量记为x=(xa)a∈A;

qi:第i个O-D对间的交通需求,∀i∈I;

ca(x):路段a的费用函数;

Ca:路段a的最大通行能力;

Δn×p=(δ${}_a^k$):路段-路径的关联矩阵,若第k条路径经过路段a,则δka=1,否则为0;

Λm×p=(σik):O-D对-路径的关联矩阵,若k∈Ki,则σik=1,否则为0。

文中作以下假设:

假设1:假设ca(x)只与本路段的流量xa有关,并且关于xa连续可微且严格单增。

假设2:每个O-D对之间至少有一条路径。

一般的随机用户平衡分配(SUEA)模型如(6)所示:(其中θ>0为常数)

$\begin{array}{l}\min f(h,x)=\frac{1}{\theta }{\displaystyle \sum _{k\in {\rm K}}h}{}_k\text{l}\text{n}h{}_k+{\displaystyle \sum _{a\in A}{\displaystyle {\int }_0^{x{}_a}c}}{}_a(w)dw\\ \text{s}.\text{t}.\{\begin{array}{l}x{}_a={\displaystyle \sum _{k\in {\rm K}}h}{}_k\delta {}_a^k,\forall a\in A\\ {\displaystyle \sum _{k\in {\rm K}{}_i}h}{}_k=q{}_i,\forall i\in {\rm I}\\ x{}_a\le C{}_a,\forall a\in A,\forall k\in {\rm K}{}_i,i\in {\rm I}\end{array}\end{array}(6)$

其中第一个约束条件代表路段—路径的流量守恒约束,第二个约束条件代表O-D对—路径间流量的守恒约束,第三个约束条件为路段容量限制。

首先验证目标函数f的严格凸性,f的二阶偏导数矩阵如下:

$\nabla {}_{(h,x)}^{2}f=\left(\begin{array}{cccccc}\frac{1}{\theta h{}_1}& & & & & \\ & \ddots & & & 0& \\ & & \frac{1}{\theta h{}_p}& & & \\ & & & c^{\prime }{}_1(x{}_1)& & \\ & 0& & & \ddots & \\ & & & & & c^{\prime }{}_n(x{}_n)\end{array}\right)$

由假设1可知c′a(xa)>0,而且$\frac{1}{\theta h{}_k}>0$,故ᐁ2(h,x)f为正定矩阵,所以f是严格凸函数,又因为约束域为凸集,因此此问题存在唯一解,不妨假设为(h*,x*)。

下面考虑随机扰动问题SUEA(ε):

$\begin{array}{l}\min f=\frac{1}{\theta }{\displaystyle \sum _{k\in {\rm K}}h}{}_k\text{l}\text{n}h{}_k+{\displaystyle \sum _{a\in A}{\displaystyle \int {\displaystyle {\int }_0^{x{}_a}c}}}{}_a(w,\epsilon )dw\\ \text{s}.\text{t}.\{\begin{array}{l}x{}_a={\displaystyle \sum _{k\in {\rm K}}h}{}_k\delta {}_a^k,\forall a\in A\\ {\displaystyle \sum _{k\in {\rm K}{}_i}h}{}_k=q{}_i(\epsilon ),\forall i\in {\rm I}\\ x{}_a\le C{}_a(\epsilon ),\forall a\in A\end{array}\end{array}(7)$

为得到扰动问题详细的灵敏度分析结果,将第三个路段容量约束条件当作惩罚项加入目标函数,则SUEA(ε)(7)可等价地转化为问题(8):(其中M为任意大的正数)

$\begin{array}{l}\min F=\frac{1}{\theta }{\displaystyle \sum _{k\in {\rm K}}h}{}_k\text{l}\text{n}h{}_k+{\displaystyle \sum _{a\in A}{\displaystyle {\int }_0^{x{}_a}c}}{}_a(w,\epsilon )dw\\ +{\rm M}{\displaystyle \sum _{a\in A}(}x{}_a-C{}_a(\epsilon ))\\ \text{s}.\text{t}.\{\begin{array}{l}x{}_a={\displaystyle \sum _{k\in {\rm K}}h}{}_k\delta {}_a^k,\forall a\in A\\ {\displaystyle \sum _{k\in {\rm K}{}_i}h}{}_k=q{}_i(\epsilon ),\forall i\in {\rm I}\end{array}\end{array}(8)$

对应的Lagrange函数及带柯朗二次惩罚项的对数边际函数分别为:

$\begin{array}{l}L(h,x,\pi ,\mu ,\epsilon ,{\rm M})=F(h,x,\epsilon ,{\rm M})\\ +{\displaystyle \sum _{a\in A}\pi }{}_a(x{}_a-{\displaystyle \sum _{k\in {\rm K}}h}{}_k\delta {}_a^k)+{\displaystyle \sum _{i\in {\rm I}}\mu }{}_i({\displaystyle \sum _{k\in {\rm K}{}_i}h}{}_k-q{}_i(\epsilon ))\\ W(h,x,\epsilon ,r,{\rm M})=F(h,x,\epsilon ,{\rm M})\\ +\frac{1}{2r}{\displaystyle \sum _{a\in A}(}x{}_a-{\displaystyle \sum _{k\in {\rm K}}h}{}_k\delta {}_a^k){}^2+\frac{1}{2r}{\displaystyle \sum _{i\in {\rm I}}(}{\displaystyle \sum _{k\in {\rm K}{}_i}h}{}_k-q{}_i(\epsilon )){}^2\end{array}$

注在本文中梯度向量均记为行向量。

下面针对问题(8)对定理1中的条件进行逐条验证:条件(1)显然成立。

对于条件(2),经过简单计算可知5 2(h,x)F=5 2(h,x)f,由f的严格凸性可以得到F也是严格凸函数,而约束域为凸集,故问题(8)在X=0时也存在唯一解(h*,x*)。又因为此问题的约束全部为线性约束,故约束规范条件成立([16]条件8.2.9),然后由[16]中的推论8.2.10可知最值点必为KKT点,即存在相应的Lagrange乘子c*,＿*满足KKT条件。又因为

显然此矩阵为正定矩阵,故对任意的y(y≠0),均有yT5 2L(x*,c*,＿*,0)y>0,所以条件(2)成立。

另外由于约束问题中只有等式约束,故条件(4)的严格互补松弛条件自动成立。

下面验证条件(3),因为所考虑的问题中只有等式约束,且等式约束组对应的梯度向量组为,要验证条件(3)成立也就是要证明5 h行向量组线性无关,即验证方程组YT5 h=0只有零解,其中Y为m+n维列向量,证明过程如下:

将向量Y分块,记YT=Y1Y2,则Y,故可以得到Y1Λm×p=0,下面证明Y1=0,由于Λm×p为O-D对-路径关联矩阵,且一条路径只能属于一个O-D对,故矩阵Λm×p的每列中只有一个1,其余全为0,因此Y1Λm×q应具有下面的形式:

Y1Λm×p=[yi1yi2…yip](9)其中yik(k∈{1,2,…,p})为向量Y1中的某个分量,由假设2可以得到向量Y1的所有分量均包含在集合{yi1,yi2,…,yip}中,而Y1Λm×p=0,由(9)可得yik=0(k∈{1,2,…,p}),故Y1=0,由此可得Y=0,即方程组YT5 h=0只有零解,所以条件(3)满足。

至此对定理1中的所有条件进行了验证,故有以下结论成立:

<1>在(X,r)=(0,0)的某个小邻域内,存在唯一的一次连续可微向量函数(h(X,r),x(X,r),c(X,r),＿(X,r)),满足

其中c(X,r),＿(X,r)为相应的约束条件的Lagrange乘子组成的向量,且(h(0,0),x(0,0),c(0,0),＿(0,0))=(h*,x*,c*,＿*);

<2>5 2W(h(X,r),x(X,r),X,r)正法,约束变量扰动变量的梯度计算公式如下:

且当X→X-,r→0时,有

由此可以得到具体的决策变量关于扰动参数的梯度表达式,Lagrange乘子关于参数的梯度也可类似得出,并且由结论<2>得到可以利用下面的等式(14)和(15)来对扰动问题的解进行预测及其灵敏度分析,当X=0,rk→0(k→+∞)时,

4具体算例及其分析

在此考察如下交通路网(图1),假设此网络图中有(1,12),(12,1),(9,4),(4,9)四个O-D对,由此可以枚举O-D对之间的所有路径,另外假设此路网中只有6和7两个信号交叉口。各条路段上的行驶时间采用美国公共道路署提出的费用-流量(BRP)函数:

其中ca0代表路段a的自由流行驶时间,Sa的路段a的饱和流量,另外在本例中取T=0.5,U=4,各O-D对间的交通需求分别为[200 300 350 300],每个路段的饱和容量均设为150,对于不与信号交叉口相联接的路段a,假设λa=1。首先可利用[14]中所介绍的仿射内点尺度算法,得到无扰动问题即当λ28=λ29=0.5时的解,然后给参数一个扰动Wλ28=Wλ29=0.05,可以式(10)～式(15)得到扰动问题的近似解,表1中列出了非扰动问题的准确解、扰动后问题的准确解及近似解,然后画出了准确解与近似解的线状图和散点图,如图2所示,其中“+”代表近似解,“*”代表准确解,从图中不难发现两者的近似程度是非常接近的,因此可以说利用此灵敏度分析方法所得的解来近似准确解是可行的。另外本例对应所求矩阵逆的维数为74×74,但是如果运用传统的灵敏度分析法,则需计算112阶矩阵的逆,因此大大简化了计算的复杂性。

5总结与展望

本文主要是利用一种新的降维方法讨论了随机用户平衡分配的灵敏度分析结果,给出了一个关于信号控制参数扰动问题的算例并与扰动问题的准确解进行比较,得到了比较好的效果。此方法的优点是可以大大降低维数,简化计算。在以后的研究学习中会针对更多的交通分配模型,如用户最优模型、系统最优模型、边约束配流模型和更多的扰动参数,如匝道数、交通需求等进行讨论,并将其结果加以应用,比如对实际问题的预测和指导意义,构造二层规划问题的求解算法等。

摘要：基于随机用户平衡分配扰动模型的Lagrange函数及带柯朗二次惩罚项的对数边际函数之间的关系给出了一种的新的降维灵敏度分析方法,与通常所说的灵敏度分析相比它的优点是大大减小了计算的维数,降低了复杂性。论文首先给出了关于一般的非线性规划扰动问题基于罚函数法的灵敏度分析结论,然后采用转换约束条件及其约束变量的方法给出并且证明了随机分配扰动问题的灵敏度分析结果,最后将其结果应用到一个具体的算例并将近似解与准确解进行比较,验证了方法的可行性。

关键词：非线性规划,降维灵敏度分析,随机用户平衡分配,罚函数

随机用户平衡 篇2

1圆明亮琢型宝石平衡状态和特征

1.1物体的重心与平衡关系

在重力场中,物体处于任何方位时所有各组成支点的重力的合力都通过的那一点,称之为重心,相当于是物体各个部分所受重力的等效作用点。重心的位置一方面取决于物体的几何形状,另一方面取决于物体的质量分布情况。对于质量均匀分布的物体而言,物体的重心取决于物体的几何形状[8]。

物体的平衡问题是物理学中一大类问题,从物理学的角度来看,重心的位置和物体的平衡之间有着密切联系,主要体现在两个方面:

( 1) 物体的重心在竖直方向的投影只有落在物体的支撑面内或支撑点上,物体才可能保持平衡。

( 2) 物体的重心位置越低,物体的稳定程度越高。

1.2宝石的几何结构和重心

圆明亮琢型 宝石的结 构和名称 如图1所示[1,9],整个宝石由冠部( C) 、腰部( G) 和亭部( P) 三大部分构成。其中,冠部由中间为八边形的台面和冠主面、星小面以及上腰小面所构成; 腰部为中间薄薄的一圈,腰部的宽度为宝石的直径也称为宝石的宽( W) ; 亭部由16个下腰小面和8个亭主面构成。各部分比例在不同的文献和应用场合略有变化,综合文献[9]和文献[10]的数据,取各部分比例为

亭部/宽度( Pavilion /Width) :

冠部/宽度( Crown /Width) :

腰厚 = 冠部/宽度( Girdle /Width) :

台面/宽度( Table /Width) :

对于单粒宝石可以认为它的密度是均匀的,而且从它的几何结构可知,整个宝石关于中心轴对称, 因此其重心必定落在中心轴上。设W的长度为单位1,利用式( 1) ~ 式( 4) 的比例关系,取中心轴所在的剖面,在Matlab中进行重构如图2所示。利用Matlab图像处理技术可以获得宝石的重心位置为图2中“o”的位置,并计算出其与台面的距离为:

重心到亭部的距离为:

1.3宝石平衡状态分析

由1. 1节中( 1) 物体的重心在竖直方向的投影只有落在支撑面内,物体才可能保持平衡。以冠部、 亭部、台面所在平面为支撑面,并进行受力分析如图3所示。可知,重心在竖直方向的投影落在以冠部为支撑面的平面外,而以台面和亭部为支撑面时重心落在所在平面内。因此,宝石只有处在台面或亭部为支撑面时才可以平衡。

由1. 1节中( 2) 物体的重心位置越低,物体的稳定程度越高。比较式( 5) 和式( 6) 得LOT< LOP,因而宝石处在台面为支撑面时的稳定度更高。

另外,考虑外界的影响,例如载物平面振动或移动时,可能会导致宝石发生转动或者是移动。由物理知识可知,相同的宝石接触面积越大,摩擦力越大就越稳定。为了计算的简便,把台面近似为圆形,亭部近似由8个小三角形组成,则台面接触面面积近似为:

亭部接触面面积近似为

即有ST1> SP1。

综上所述,宝石处于台面或亭部为支撑面都可以平衡,而且处于台面时的稳定性更高。因此,随机放置的宝石处于平衡时,宝石应该处在台面或亭部为支撑面,而且以台面为支撑面的状态出现的概率更大。

2图像中宝石平衡状态和特征

2.1图像中宝石的平衡状态

根据1. 2节圆明这琢型宝石的几何结构和参数,利用Pro /engineer三维参数化建模软件建立宝石模型,然后获取宝石处于台面和亭部为支撑面的各视平面图如图4所示。假设摄像头垂直安装于宝石所在的平面,将宝石随机呈现平台上,则图像中的宝石为处于对应支撑面时的俯视图。

2.2图像中宝石平衡状态下的特征

由图4可知,当宝石处在台面为支撑面时,宝石的俯视图即此时宝石在二维平面上投影为直径等于宝石直径的圆,其面积为

当宝石处在亭部为支撑面时,宝石的俯视图为椭圆形,其面积为:

式( 10) 中,a为椭圆的宽度,是宝石的直径W在支撑面的投影,夹角大小为宝石亭部角度。设夹角为A,则

因此,可得

综上所述,宝石处在台面和亭部为支撑面时的形状和面积大小都有着明显的不同。鉴于这两种状态对应的形状为圆形和椭圆形,因此,可以进一步用圆形度作为特征。

3宝石图像实验及分析

3.1宝石图像处理过程

将一批宝石分开并随机放置在水平面内,摄像头垂直安装于宝石所在的平面,采集宝石图像。为了准确获得宝石的圆形度和面积,首先对宝石图像进行图像预处理,具体过程包括:

Step1将所获得的图像转化为灰度图像并统计灰度分布;

Step2采用自动获取全局阈值分割或利用灰度分布进行阈值分割,获得二值化图像,去除背景;

Step3对二值化图像进行形态学处理,采用圆形结构元素进行开启和闭合组合运算,平滑边界,去除噪声和杂质影响;

Step4采用8邻域连通区域法,对预处理及去除噪声后的图像进行连通区域标记,即对宝石进行标记( 粘连时多颗为一个连通区域) ,并记录标记宝石图像的基本信息( 每个连通区域的面积A、圆心、 边界坐标( x,y) 等) 。

3.2宝石特征及分类原则

由2. 2节分析可知,可以利用宝石面积和圆形度作为特征,判断宝石的随机平衡的状态。宝石圆形度的计算过程如下:

Step1从3. 1节的图像处理过程Step4中获得宝石的面积A和边界坐标( x,y) ;

Step2通过对坐标求微分 ( 前后坐标值差分) 再平方求和得到周长L

Step3通过周长计算对应的圆的面积为:

Step4得到圆形度deg计算公式:

宝石的圆形度范围为0 ~ 1之间,越接近于1则圆形度越高。图6为标记宝石圆形度的统计结果。 根据2. 2节的分析,圆形度接近于1的是以台面为支撑面的宝石,把具有此特征的宝石称之为典型宝石。而其余同样处于台面为接触面时的宝石称之为非典型宝石。非典型宝石的出现主要是由于宝石高反射率的特性,反射光线不在摄像头所在方向时,宝石在图像中呈现的亮度较弱,或者是宝石不完全处在摄像头的垂直平面导致的。

对圆形度接近于1的典型宝石进行数目和面积统计,求出其平均面积SA即STP2。然后,对所有的连通区域进行面积统计。根据最大似然法则,利用特征与状态的对应关系,哪种状态出现的可能概率最大,就判断为该状态。因此,根据节3. 2所分析,推断出如图7所示的宝石特征及对应状态分类方法。

3.3宝石分类结果

根据图7所述宝石特征和分类原则,对图像中的宝石状态进行分类,分类结果如图8所示。其中, 台面支撑面宝石中,用红色O标注的为圆形度高的典型宝石,未标注的为圆形度较低的非典型宝石。 从图8中可以看出宝石可以正确地进行分类和状态识别; 随机放置的单粒宝石中多数以台面为支撑面同时也有一部分处于亭部支撑面,而且以台面为支撑面的宝石数目远大于亭部为支撑面的宝石数目。 与前面分析宝石以台面和亭部支撑面均可以平衡, 而台面为支撑面的稳定度更高出现的概率更大的结论相一致。由此可见,以面积和圆形度为宝石的典型特征是可行的。

4结论

随机用户平衡 篇3

为了分析交通拥挤特性以及对交通流进行最优控制, 必须对动态交通流进行建模研究, 动态交通分配 (DTA) 考虑了交通需求随时间变化的特性, 能够给出瞬时的交通流分布状态, 它是ITS (智能交通系统) 项目中最重要的关键核心技术基础之一。动态交通分配理论经过20多年的发展, 目前有许多有效的方法。其中, 变分不等式理论在处理不对称方面的优势以及其清晰的解析特性, 使得动态最优交通分配的变分不等式模型的研究迅速发展[1]。

Ran等从单用户角度, 在1996年提出了一系列基于路段的理想动态用户最优路径选择问题的变分不等式模型[2,3,4]。文献[5] 针对我国城市混合交通的特点, 借助于share需求模型, 建立了混合交通运量分布与平衡分配的极值模型, 证明了模型的最优解与Wardrop用户最优均衡条件等价, 提出了求解的方向搜索法。文献[6]建立了随机动态用户最优路径选择模型, 并提出了两种K最短路径的启发式算法。文献[7]将车辆分为小汽车和卡车, 在路段费用函数中充分考虑了共用同一道路设施的用户间的相互作用及其不对称性, 建立了多用户类的动态交通分配拟变分不等式模型, 提出了实用的嵌套修正投影算法。文献[8]在多起点多讫点的一般结构城市交通网络上建立了离散动态均衡的交通分配模型, 允许用户对路径和出发时间同时选择。文献[9]在多用户类和多停车设施的条件下, 建立了同时考虑出行时间、路径、停车位置和停车时间选择的动态网络均衡模型, 并且提出了一种启发式算法和算例。文献[10]在分析出发时间和路径选择的组合DUO条件的基础上, 建立了与之等价的双层VI模型, 并给出了两种启发式算法。Chen[11]等建立了离散时间基于路段的动态用户最优路径选择模型, 并且给出了一个嵌套对角化算法和算例。文献[12]提出了交通系统的三维结构, 指出要有效缓解交通阻塞问题, 必须从系统工程的角度综合考虑交通系统间各维度的协调控制。 文献[13]在路段出行成本是流量的单调函数的较弱条件下, 分别对于固定需求和弹性需求的情形, 首次证明了静态的随机用户配流模型可以表示为一个变分不等式问题。文献[13]将具有弹性需求的随机用户平衡 分配问题描述为一个等价的变分不等式, 在路段出行成本函数是路段流量的严格单调上升函数的假定下, 给出了其等价的凸数学规划问题, 并针对公交网络问题的特殊性, 提出了相应的算法。文献[14]首次把瞬时的路径选择和出发时间决定的动态用户均衡问题表示为一个变分不等式模型, 该模型满足先进先出 (FIFO) 条件。

本文在个体用户基于logit模式进行出行选择的假设下, 建立满足动态随机用户最优出行方式、出发时间和路径选择条件的变分不等式 (VI) 组合模型, 说明该VI模型解的存在唯一性, 并且在此基础上使用投影算法对一个简单网络进行算例验证。

1 符号和假设

假设G (N, A) 是具有多起多讫点的强连通交通网络, N是网络节点集, A为有向路段集, 起节点集合O⊂N, 讫节点集合D⊂N, 起节点个数为|O|, 讫节点个数|D|, r∈O表示任一决策节点, s∈D表示任一目的节点, 网络中所有OD对集合为W={rs:r∈O, s∈D}, 网络中OD对集合的个数为|W|, |M|为所有出行模式的数目, |R|为rs对间路径的条数。考虑一个固定的时间段[0, T] (T是能够满足所有用户在高峰时间出行且能够完成旅行的时间) , 假设在时间段T内任一OD对间总的出行需求已知, 为Drs (T) , 用户可选择的出行方式有M种 (公交车、小汽车、摩托车、自行车等) , 可供选择的出发时间t为[0, T]中任意一点。相关的决策变量表示如下, 这些变量中, 所有带有上标rs的变量均表示决策节点为r, 目的节点为s.

xma (t) ——时刻t行驶在路段a上的第m种方式的出行数量*; (m∈{1, …, M}, 以下均同)

uma (t) ——时刻t第m种出行方式进入路段a的流入率**;

vma (t) ——时刻t第m种出行方式离开路段a的流出率**;

f${}_m^{rs}$ (t) ——时刻t第m种出行方式从起点r到讫点s的出发率**;

frsmp (t) ——时刻t第m种出行方式从起点r到讫点s间第p条路径上的出发率**;

τma (t) ——时刻t进入路段a的第m种出行方式的交通流在路段a上花费的实际旅行时间。

其中带有*的变量表示状态变量, 带有**的变量表示控制变量。个体用户进行出行方式、出发时间和出行路径的选择, 假设个体用户每种出行方案 (一个出行方案是出行方式、出发时间和出行路径的组合) 的效用函数的随机误差项服从相互独立的Gumbel分布。

2 出行方式/出发时间/路径选择问题

实际生活中, 用户的出行方式和出发时间一般并不事先给定, 而是根据出行目的, 参考自己的经验和外界的信息进行确定。在出行活动实施的过程中, 用户往往根据某种原则动态选择自己的行进路线, 原先确定的路径就有可能发生变化, 个人行为的变化导致了交通流量在路网上的分配不是一成不变的, 这实际是一个结构 (出行方式) 、时间 (出发时间) 、空间 (出行路径) 的三维决策问题。假设个体用户完全了解路网上的交通信息, 能精确计算每条路径的出行成本从而做出完全正确的出行决策, 则将导致确定性动态用户最优均衡, 如果个体用户不完全了解路网上的出行交通信息, 在出行中按照个人理解的最小出行成本来进行出行决策, 则将导致随机动态用户最优均衡[15]。实际中这种按照个人理解进行出行决策的情况是大量存在的, 我们的目标是要在得到在每个出发时刻, 每一条路径上各种出行方式的流量速率, 以及各条路段上的流入率、流出率、出行数量。

2.1 出行方式/出发时间选择

对网络中任何一个产生出行的决策节点, 用户选择不同的出行方式、出发时间和出行路径, 会产生不同的出行成本 (包括时间、经济支出和一定的心理成本等) 。

令frs (t) = (frs1 (t) , …, frs|M| (t) ) T是t时刻rs间出发率向量。后面用带下标1的c1表示出行方式/出发时间选择下的实际成本, 用带下标2的c2表示出行路径选择下的实际成本。

令c1 (frs (t) ) = (c1 (frs1 (t) ) , …, c1 (frs|M| (t) ) ) T为OD对rs间所有出行方案下的实际出行成本向量, 其中每一个分量c1 (frsm (t) ) 表示OD对rs间从t时刻出发的采用第m种出行方式下的实际出行成本, 假设c1 (frsm (t) ) 是瞬时出发率frsm (t) 的单调递增可微函数。

c1 (frsm (t) ) 由以下四部分的加权和构成:①该种出行方式下的经济成本支出 (车票、油耗等交通费用) , ②在出发的起节点由于等待造成的损失, ③花费在路上的旅行时间, ④由于早到带来的利益或者迟到带来的损失。

将实际出行成本函数c1 (frsm (t) ) 定义为

$\begin{array}{l}c{}_1(f{}_m^{rs}(t))=\mu {}_m+\alpha {}_{m}t+\tau {}_m^{rs}(t)+[{\rm T}{}^{rs}-(t+\tau {}_m^{rs}(t))],\\ \forall r,s\in {\rm O}D(1)\end{array}$

其中, μm是与出行方式相关的经济成本支出, amt是由于等待而产生的效用项, 参数αm≥1表示对用户而言, 1单位时间等待造成的损失比1单位时间在路上行驶造成的损失大, τrsm (t) 是OD对rs间采用第m种出行方式在时刻t的实际旅行时间, Trs是要求到达的时间。

下面给出动态随机用户最优出行选择条件的定义。

定义1 (动态随机用户最优出行方式/时间选择均衡条件) 称网络上的交通流满足动态随机用户最优出行方式/出发时间选择条件, 如果对任一OD对rs, 在任一时刻t, 每一种被使用的出发时间和出行方式下的瞬时出行成本都等于该rs对在t时刻的最小理解瞬时出行成本, 称此时的网络流量状态满足动态随机用户最优出行方式/出发时间均衡条件。

2.2 路径选择

当个体用户确定了出行方式和出发时间后, 在出行过程中, 用户会根据实际路网的情况适时调整自己的行进路线, 假设用户按照个人理解出行成本进行路径选择, 那么网络达到的均衡状态称为随机用户最优均衡。

假设rs间总的路径条数为|R|条, 令grsm (t) = (frsm1 (t) , …, frsm|R| (t) ) T是t时刻rs间采用第m种出行方式的路径向量。

令c2 (grsm (t) ) = (c2 (frsm1 (t) ) , …, c2 (frsm|R| (t) ) ) T为OD对rs间所有出行方案 (这里出行方案是选择某条出行路径) 下的实际出行成本向量, 其中每一个分量c2 (frsmp (t) ) 表示OD对rs间从t时刻出发的采用第m种出行方式下第p条路径的实际出行成本, 假设c2 (frsmp (t) ) 是瞬时流量速率frsmp (t) 的单调递增可微函数。将实际出行成本函数c2 (frsmp (t) ) 定义为:

$c{}_2(f{}_{mp}^{rs}(t))={\displaystyle \sum _{a\in A{}_p^{rs}}\tau }{}_{ma}(t)(2)$

这里, τma (t) 表示时刻t采用第m种方式路段a上的旅行时间, Arsp表示rs间第p条路径所包含的路段集合。

下面给出动态随机用户最优路径选择条件的定义。

定义2 (动态随机用户最优路径选择均衡条件) 称网络上的交通流满足动态随机用户最优路径选择条件, 如果对任一OD对rs, 在任一时刻t, 使用同种出行方式同时出发的用户, 该rs对间所有被使用的路径的瞬时阻抗都等于该rs对的最小理解瞬时旅行阻抗, 称此时的网络流量状态满足动态随机用户最优出行方式/出发时间均衡条件。

3 多维动态随机用户最优变分不等式模型、算法和算例

3.1 模型

命题1 满足多维动态随机用户最优均衡条件的解与下述变分不等式问题等价:

VIP1:确定一个f*rsmp (t) ∈Ω, 使得∀frsmp∈Ω (这里Ω是满足模型约束条件的可行集) , 不等式

$\begin{array}{l}{\displaystyle \sum _{rs}{\displaystyle \sum _p{\displaystyle \sum _{m=1}^{{\rm M}}\beta }}}{}_m\{c{}_1({\displaystyle \sum _{p}f}{}_{mp}^{*rs}(t)\\ +\frac{1}{\theta }[\ln {\displaystyle \sum _{p}f}{}_{mp}^{*rs}(t)-\text{l}\text{n}D{}^{rs}({\rm T})]\\ -S(c{}_1({\displaystyle \sum _{p}f}{}_{mp}^{*rs}(t)))+c{}_2(f{}_{mp}^{*rs}(t)\\ +\frac{1}{\theta }[\text{l}\text{n}f{}_{mp}^{*rs}(t)-\text{l}\text{n}f{}_m^{*rs}(t)]\\ -S(c{}_2(g{}_m^{*rs}(t)))\}(f{}_{mp}^{rs}(t)-f{}_{mp}^{*rs}(t))\ge 0\end{array}(3)$

成立。

限于篇幅, 这里不给出具体证明, 证明方法与文献[16]中的证明类似。

3.2 算法

常用的求解变分不等式问题的算法有投影方法、对角化方法、增广拉格朗日方法、分解方法和混沌优化算法等几种, 对于变分不等式问题VIP1, 这里采用投影方法, 求得出发率和流量速率后, 可以根据约束条件计算得出其他几个决策控制变量ursma (k) , vrsma (k) , xrsma (k) 。对于实际旅行阻抗τma (t) , 按照文献[18]的公式计算:

$\tau {}_{ma}(t)=\tau {}_{ma}^0[1+\alpha (\frac{{\displaystyle \sum _m\gamma }{}_{m}x{}_{ma}^{rs}(t)}{C{}_a}){}^{\beta }](4)$

式中: τ${}_{ma}^0$为路段a上第m种出行方式的零流时间, Ca为路段a上的最大车辆通过能力; α, β为待定参数, 一般取α=0.15, β=4.0。${\displaystyle \sum _m\gamma }{}_{m}x{}_{ma}^{rs}(t)$为路段上的折合总流量, γm为第m种出行方式的流量折算系数。

将时间段[0, T]进行分段, 分为K个小时段, 每个小时段记为k, 投影方法在第n步迭代中需要求解如下子问题SQP:

$\min \frac{1}{2}z{}^{{\rm T}}(k)z(k)+[\rho F{}^{n-1}(z(k))-z{}^{n-1}(k)]{}^{{\rm T}}z(k),\forall k$, 这里, z (t) = (x (t) , y (t) ) T, x (t) = (frs (t) :rs∈W) T, y (t) = (grs (t) :rs∈W) T, ρ是满足0<ρ<1/L的任一正数, L是满足c1 (frs (t) ) 和c2 (grsm (t) ) 的Lipschitz常数。具体步骤如下:

第0步: 令出行方式变量m=1;

第1步: 初始化, 使用随机加载得到0时刻的决策控制变量{z0 (0) }, 并计算出初始的函数值F0 (z (0) ) , 初始的成本向量c01 (frs (0) ) , c02 (grsm (0) ) , 根据约束条件分别计算得出初始的决策控制变量{urs, 0ma (0) }, {vrs, 0ma (0) }, {xrs, 0ma (0) }, 并令n=1;

第2步: 令k=0;

第3步: 迭代, 求解子问题SQP, 得到决策控制变量{zn (k) };

第4步: 更新, 可根据约束条件分别计算得出决策控制变量{urs, nma (k) }, {vrs, nma (k) }, {xrs, nma (k) }, 根据式 (4) , 计算出路段实际旅行阻抗τnma (k) ;

第5步: 计算终止检查, 若k=K, 转第6步;否则令k=k+1, 转第3步;

第6步: 收敛性检验, 若‖zn (k) -zn-1 (k) ‖≤ε (ε潍设定的迭代精度) , 停止迭代;否则, 令n=n+1, 转第2步;

第7步: 若m=|M|, 停止计算;否则, 令m=m+1, 转第1步。

3.3 算例

考虑如图1所示的Papageorgiou网络, 有4个OD对, 8条路段, 可供选择的出行方式有2种, 每条梅段有2种交通方式混合行驶, 可供选择的出发时间有2种, 分别为b1, b2.假设用户从OD对1→5之间进行动态出行选择。首先, 用户需要在起节点1进行出行方私和出发时间的选择, 然后, 用户在连接间OD对1→5之间的3条路径上进行出行路径的选择, 每到一个中间节点, 用户将根据当时估计的出行成本选择下一条前进路段。取阻抗和效用转换参数θ=1.5, 式 (3) 中参数α1=α2=1, μ1=2, μ2=1, 两种方式的折算系数分别为γ1=1, γ2=3, 要求到达时间T1, 5=1200秒, 迭代精度ε=0.001。

利用5.1节给出的投影算法得到如表2所示的解。这里仅列出了路段1和路段7这两条路段上的计算结果。

① 假设两种方式下的自由流时间相等。

通过前面给出的算法, 可以得到路段上每个时段、每种出行方式下对于不同出发时间的流出率、流入率、车辆数目和瞬时路段阻抗。从计算结果可以看出, 在每个时段, 对于每种出行方式、每个出发时间, 得到的路段瞬时阻抗是相等的, 从而每个时刻的均衡流量满足出行方式、出发时间、出行路径联合选择的动态随机用户最优均衡条件, 说明前面提出的模型和算法是有效的。

4 小结

本文针对动态交通流分配问题, 在个体用户不能掌握完全路况信息做出完全理性决策, 而只能按照个人理解出行成本进行出行决策的前提下, 建立了同时考虑出行方式、出发时间、出行路径的动态随机用户最优出行选择的变分不等式模型, 证明了变分不等式模型和动态随机用户最优均衡条件的等价性, 并且提出了一个可行的投影算法。该模型的优点在于:一是将出行方案制定和出行行为实施作为一个连续的决策过程进行考虑, 使得模型更加符合客观实际;二是将出行方式、出发时间、出行路径选择问题纳入一体化的框架中分析, 考察动态的交通流在这三个方面取得一致的均衡性, 这种综合性的考虑对于实时的交通控制与优化, 对于推动智能交通系统更快的发展无疑具有十分重要的理论意义。下一步需要研究的问题是, 对于大型的城市交通网络, 如何开发高效率的更加实用的算法, 使之能够满足智能交通系统工程化的需要。

摘要：针对个体用户进行出行方式、出发时间、出行路径联合选择问题, 在个体用户基于log it模式进行出行决策的假设下, 建立了满足动态随机用户最优均衡条件的变分不等式模型, 该模型将用户的出行方案制定和实施作为一个整体进行考虑, 说明了该变分不等式模型解的存在性和唯一性, 并且在此基础上使用投影算法, 通过一个简单算例验证了算法的合理性和有效性。

随机用户平衡 篇4

1.1 UE平衡配流模型发展研究

Wardrop (1952) 提出了用户平衡 (UE) 和系统最优 (SO) 的概念, 标志着交通网络平衡概念从描述转为严格的数学模型。然而, 直到1956年Beckman等人提出了用于描述UE原理的一种数学规划 (MP) 模型;20年后在1975年才由Le Blanc等将F—W算法用于求解这个模型获得成功, 从而形成了现在的使用解法。

Be ckm an提出的描述UE问题的模型, 通常称为Be ckm an变换式, 具体模型公式如下:

该模型基于以下假设:1) 网络是强连通的;2) 路段特性函数正的、连续且分离。

而实际中, 道路特性及出行者选择行为特性并不是确定和统一的, 是时刻在变化的。因此, 后续研究者将出行者对路径旅行时间估计作为随机性变量考虑, 出现了如基于logit分布的随机用户平衡配流模型 (Che n和Alfa, 1991;Davis 1994) , 考虑路网OD点之间交通需求与时间的相关性的动态交通分配模型, 考虑路网能力可靠性的PUE (probability us e r e quilibrium) 配流模型 (许良和高自友, 2003) , 综合考虑了路网需求弹性、路网用户选择随机性的多类型弹性需求随机用户平衡分配模型等 (刘海旭等, 2003) 。

此外, 在路阻函数方面, 刘海旭、蒲云等 (2003) 做出了基于出行质量的随机用户平衡分配模型 (综合考虑了出行时间最小和出行时间可靠性最大之间的平衡) 。随着智能交通技术的发展, 先进的出行者信息系统 (ATIS) , 给出行者提供了实时、可靠的信息。张玺 (2013) 等, 考虑了路网需求的随机性和出行者基于信息系统的认知更新过程, 提出一个基于认知更新的随机动态分配模型。

1.2 UE平衡配流模型算法

1.2.1 启发式算法

在将F—W算法用于求解Beckmann变换式之前, 许多学者一直在探讨用模拟和近似的方法求解交通平衡分配问题, 这些方法通常称为非平衡分配算法, 包括:全无网络分配法 (Allor Nothing) , 也称为最短路径法, 运用AON网络加载机制进行平衡分配模拟;容量限制分配法, 相对最短路径分配法来说, 更多的考虑了路段上流量与路段阻抗的关系, 通过不断更新路段阻抗, 反复调用AON网络加载过程, 试图达到平衡状态的一种分配方法;增量加载分配法, 主体思想是将OD量分成n等分, 利用全有全无加载机制, 逐次加载每份流量, 并在每次加载完后, 重新修改路段阻抗;逐次平均分配法, 是一种界于增量加载法和平衡分配法之间的一种迭代算法, 其基本思想是不断调整已分配到各路段上的交通量而组件达到或接近平衡解。

1.2.2 F—W算法

Frank和Wolfe于1956年首先提出用于求解线性约束的二次规划问题的一种线性化算法。该方法属于可行方向法的一种。由于F-W法在每次迭代都必须求解一个线性规划 (LP) 问题, 在一般的实际问题中会因为计算量过大而不实用。但是, 由于交通分配问题的特殊性, 这个LP问题能变换为一次AON网络加载, 因此F-W法特别适合于UE规划求解, 在其基础上最终形成了目前较为广泛适用的一种严格又实用的解法。

F-W算法理论上的最大缺陷是收敛性不好, 特别是在最优解附近可行方向逐渐与目标函数的最速下降方向 (即负梯度方向) 正交, 这样导致收敛的缓慢。为此许多研究都致力于改进F-W算法的收敛特性, 大致改进思路分为3类:方向加速策略、步长加速策略、流量更新策略。

2 UE平衡配流模型拓展及平衡分配算法

2.1 弹性需求模型及算法

弹性需求模型:认为OD量在分配过程中是可变的, 与OD对之间的最小阻抗有关。

当网络中出行起讫点之间的拥挤程度增加时, 出行量会相应减少。可用一个函数来描述这种关系:

式中, Ds (·) 是出行需求函数, urs是起讫点rs之间的路径最小阻抗。

弹性需求分配模型目标函数:

弹性需求状态的约束条件:

2.2随机平衡分配SUE模型及算法

SUE分配模型:认为出行者在不拥有完备的交通信息下对路段阻抗有着不同的估计, 该阻抗可被视为分布于出行者群体上的一个随机变量, 这修正UE分配的基本假设, 即出行者拥有完备的交通信息, 而且能够依据这些信息做出正确的决策。

2.2.1 SUE分配模型

(1) SUE分配模型

SUE模型是由She ffi和Pow e ll (1982) 提出的, 具体数学形式如下:

2.2.2 SUE分配模型的计算算法MSA算法

SUE分配是无约束极小值问题, 对于一般的无约束极小值问题可以用下降方向沾求解。但足对于SUE模型确定下降方向和迭代步长不是容易之事, 原因在于:1) 在每次选代中都需要执行一次随机网络加载得到一组附加的路段流量来确定目标函数的下降方向, 但路段流量有时并不能被精确计算 (如导致由此取得的下降方向可能不是真正的下降方向) 尽管在总体上是下降的;2) 由于目标函数相当复杂, 使得迭代步长不可能如一般问题那样利用一维搜索求最优值。但是MSA算法可以避免上述困难, 结合随机网络加载机制, 成功求解SUE问题。

2.3 一般化的UE模型及算法

一般化的UE模型:认为路段阻抗函数以及需求函数是不可分离的, 修正UE规划及其弹性需求形式中路段阻抗函数和需求函数可分离的条件。

由此, Prager (1954) 在建模中考虑了双向道路中对交通流之间的相互影响。Dafermos (1971, 1972) 提出研究基于不分离的一般化特性函数的交通分配模型, 这种模型也适用于多模式、多车种或者多类别用户等多类别平衡分配问题。Roth (1965) 第一个研究了多类别用户分配问题。针对我国机非混行的特点, 陈森发等 (1993) 、刘安等 (1996) 、四兵峰等 (1999) 、刘法胜 (1999) 等均讨论了多种交通方式的混合平衡分配问题, 这些研究基本上都是对国外已有成果的拓展研究。

2.3.1 一般UE模型

以下为一个具有代表性的一般UE模型Dafermos (1982) :

约束条件:

其中Ω是由弹性UE模型相同约束条件决定的, 一般UE模型即使弹性UE的一般化。

2.3.2 对角化算法

一般化UE模型最有效的算法是对角化算法来。对角化算法也叫非线性Jacobi算法、松弛算法。对角化算法在整体框架上是迭代的, 每次迭代需要求解一个完整的UE规划, 而求解UE规划的算法一般也是一个迭代过程, 因此它具有迭代嵌套结构, 对于大型的交通网络需求需要付出巨大的计算量, 尽管相对于同类算法它是较优的。

3 结论

随着智能交通技术的发展, 乘客获得道路信息的渠道越来越多越来越全面, 深刻影响了乘客的选择行为。因此, 除上文介绍的用户平衡分配模型之外, 除了应该考虑交通需求的是随机变化性, 还应考虑路网上需求与时间的相关性, 因此还发展除了动态平衡分配模。由此可见, 用户平衡配流模型会发展得越来越全面, 配流结果更加的符合实际情况;另外由于交通技术在发展, 出行者行为影响因素越来越复杂, 模型因此需要不断更新。

摘要：用户平衡分配模型在交通规划及城市交通网络设计中占据重要作用, 网络上流量分配结果的准确性对交通决策问题起着关键性作用。用户平衡分配模型的关键部分是对路网用户的行为选择描述的准确性, 因此在基本的用户平衡模型上, 发展出了较多更能描述实际情况的用户平衡拓展模型。因此本文重点介绍了用户平衡分配模型、其拓展模型及其算法。

关键词：用户平衡分配模型,用户平衡分配拓展模型,算法

参考文献

[1]任刚著.交通管理措施下的交通分配模型及算法.东南大学出版社[M].2007.

[2]刘海旭, 蒲云.基于行程质量的用户平衡分配模型[J].中国公路学报, 2004.