基于终点的用户均衡交通分配模型求解算法

摘 要：用户均衡分配模型是更接近实际交通状态的分配模型，它是建立在出行者总选择起迄点间交通时间最短的路径作为出行路线的行为假设基础上的。分析基于终点的用户均衡交通分配模型,指出该模型与基于路径均衡配流模型是等价的,在选择美国BPR路阻函数后,模型可以转化为带线性约束的非线性规划问题,并给出模型的矩阵表示。对这类问题,采用简便实用的仿射尺度算法求解,给出算法的基本思想及详细的实现过程。仿真结果显示,所得最优解满足Wardrop第一准则,表明该算法是有效的,可用于大型路网的配流计算。

关键词：交通分配;Wardrop准则;基于终点模型;仿射尺度算法

中图分类号：U491;TP274文献标识码：B

文章编号：1004-373X(2008)22-145-03

Algorithm for User Equilibrium Traffic Assignment Model Based on Destination

LIU Bingquan,WANG Mingjun

(Weinan Teachers University,Weinan,714000,China)

Abstract：User equilibrium assignment model is the one that is closer to actual traffic situation.It is established on the fact that the travellers are apt to choose the shortest paths as travel routes between OD(origin destination).The paper analyzes user equilibrium traffic assignment model based on destination,and points out that the model and traffic assignment model based on path are equivalent.By using BPR link travel time function,the model can be translated into nonlinear programming problem with linear constraints and represented in matrix form.To solve the problem,affine scaling algorithm is adopted and the general idea and detailed implementation process of the algorithm are given.Simulation demonstrates that the optimal solution observes Wardrop first principle and the method is effective,so it is suitable to solve the traffic assignment problem in large scale road network.

Keywords：traffic assignment;Wardrop principle;destination-based model;affine scaling algorithm

交通分配就是把各种出行方式的空间OD量分配到具体的交通路网上,它是城市交通规划的一个重要环节。依据Wardrop第一、第二准则,通常把交通分配划分为均衡分配与非均衡分配。Beckman最早提出了满足Wardrop第一准则的用户均衡交通分配模型,常采用Frank-wolfe算法进行求解［1-3］。由于该模型以各OD对之间的路径流量为变量,需要枚举OD对间的所有路径,因此对大型路网,模型求解相对比较困难。

近年来,许多学者对这类问题进行了多方面研究［4-6］,提出许多新的模型与算法,如基于路段模型与算法［7］,基于起点和终点的模型与算法［8,9］等。这些模型与算法都是以路段流量为变量,并发现基于路段的交通分配模型同样满足Wardrop第一准则。选择路段流量为变量,避免路径枚举,减少计算的复杂程度。

基于终点的用户均衡交通分配模型可以归结为一个具有线性约束的非线性规划问题，本文采用简单实用的仿射尺度算法［10］求解这类问题。首先给出基于终点的用户均衡交通分配模型,指出该模型与基于路径均衡配流模型是等价的,当选择适当路阻函数后,模型可以归结为带线性约束的非线性规划问题,并转化为仿射尺度算法的处理形式;最后采用该算法求解一个小型路网的交通配流问题,仿真结果显示,该算法是有效的,可用于大型路网的配流计算.

1 交通分配模型

1.1 用户均衡交通分配模型

用户均衡分配模型是更接近实际交通状态的分配模型。在均衡状态时，在同一OD对间所有被使用的路径上，其路径行驶时间相等且该行驶时间小于或等于未被使用路径上的行驶时间，此时网络处于平衡状态，任何出行者均无法通过变更选择路径达到减少出行时间的目的。对于一个给定交通网络G＝（N,A），N为节点集，A为边集，R为起点集，S为终点集，R与S可以有公共元素；A(i)为以i为起点的有向路段集合;B(i)为以i为终点的有向路段集合;(r,s)为以r为起点，s为终点的OD对；xsa表示路段a上到终点s,(s∈S)的流量;Prs为OD对(r,s)间所有路径集合。对应于Wardrop第一准则的用户均衡交通分配模型（1）:

min z(x)=∑a∈A∫xa0ta(ω)dω(1)

s.t.∑p∈Prsfrsp=qrs,r,s(2)

frsp≥0,p,r,s(3)

xa=∑r∈R∑s∈S∑p∈Prsδrsap・frsp,a(4)

式中：frsp是O-D对（r，s）间路径p上的交通量；qrs是OD对(r,s)间的交通需求量；

δrsap=1，OD对(r,s)间路径p经过路段a

0，否则

上面模型是基于路径用户均衡交通分配模型,求解该模型需要枚举OD对间的所有路径,因此在大型路网上应用比较困难。下面给出的基于终点的用户均衡交通分配模型(2):

min z(x)=∑a∈A∫xa0ta(ω)dω（5）

s.t. ∑a∈A(i)xsa－∑b∈B(i)xsb=qis,i∈R,s∈S,i≠s（6）

∑a∈A(i)xsa－∑b∈B(i)xsb=0,iR,s∈S,i≠s（7）

xsa≥0（8）

xa=∑s∈Sxsa（9）

该优化模型以路段到终点的流量xsa为变量,避免了路径枚举,从而适用于大型路网的配流计算。

1.2 模型分析

模型(1) 中目标函数是路段行驶时间函数积分之和，该目标函数在交通上的含义并不直观，但它的K-K-T条件却正好与Wardrop第一准则一致。并且可以证明,模型(2)与模型(1)是等价的。事实上,令xrsa为路段a从起点r到终点s的流量,则有xrsa=∑p∈Prsfrsp・δrspa,对i≠r,i≠s,有∑a∈A(i)∑p∈Prsfrsp・δrsap－∑b∈B(i)∑p∈Prsfrsp・δrsbp=0,即OD对(r,s)中,当节点i为中间点时进入i的流量等于流出流量。从而有：

∑a∈A(i)xsa－∑b∈B(i)xsb=∑a∈A(i)∑r∈Rxrsa－∑b∈B(i)∑r∈Rxrsb

=∑a∈A(i)∑r∈R∑p∈Prsfrsp・δrsap－∑b∈B(i)∑r∈R∑p∈Prsfrsp・δrsbp

=∑r∈R(∑a∈A(i)∑p∈Prsfrsp・δrsap－∑b∈B(i)∑p∈Prsfrsp・δrsbp)=0

即为式(7)。同样对i∈R,i≠s时有:

∑a∈A(i)xsa－∑b∈B(i)xsb

=∑a∈A(i)∑r∈R∑p∈Posfrsp・δrsap－∑b∈B(i)∑r∈R∑p∈Prsfrsp・δrsbp

=∑a∈A(i)∑p∈Pisfisp・δisap+∑a∈A(e)∑r∈R{i}∑p∈Prsfrsp・δrsap－

∑b∈B(i)∑p∈Pisfisp・δisbp－∑b∈B(i)∑r∈R{i}∑p∈Prsfrsp・δrsbp

=∑a∈A(i)∑p∈Pisfisp・δisap+∑r∈R{i}(∑a∈A(i)∑p∈Prsfrsp・δrsap－

∑b∈B(i)∑p∈Pisfisp・δisbp)

=∑a∈A(i)∑p∈Pisfisp・δisap=∑p∈Pisfisp=qis

与式(2)一致,所以模型(1)与(2)是等价的。

1.3 模型的矩阵表示

令x=(…,x1a…x|S|a,…)T(|A|×|S|)×1表示路网中各路段基于终点的流量向量;ei(s)=(…,eia(s),…)1×|A|表示s为OD对终点时节点i的点弧关联向量;其中:

eia(s)=1，s为OD终点时,i为a的起点

－1，s为OD终点时,i为a的终点

0，否则

设：

E(s)=e1(s)e2(s) …e|N|(s)〗|N|×|A|

E=E(1)0…0

0E(2)…0

… … … …

00…E(|S|)〗(|N|×|S|)×(|A|×|S|)

b=(…,bsi,…)T(|N|×|S|)×1,

bsi=qis,i∈R,s∈S且i≠s

0,否则

采用矩阵表示模型(2)转化为式(10):

min z(x)=∑a∈A∫xa0ta(ω)dω

s.t.Ex=b

x≥0（10）

2 仿射尺度算法

2.1 算法的基本思想

设模型（3）的内可行域Q+={x|Ex=b,x>0}，当前迭代点为xk=(xk1,…,xk|A|×|S|)T，xk∈Q+，构造对角阵Dk=diag(xk1,xk2,…,xk|A|×|S|)，做仿射尺度变换Tk：g=D－1kx，在此变换下，式(10)变为：

min Gk(g)

s.tEkg=b，g≥0（11）

其中，Ek=EDk,并且xk被变换到式(11)约束区域的中心e=(1，1，…,1)T(|A|×|S|)×1。从e出发沿式(11)的目标函数在gk＝e处的负梯度在矩阵Ek的核空间的投影方向：qk=－(Gk(e)－Ek′(EkEk′)－1EkGk(e))做一维搜索，这里Gk(e)=Dkz(xk)。若qk＝0，则可证xk是式(11)一个K-T点；若qk≠0，则记pk=qkqk，做一维搜索min0≤λ≤θ F(xk+λDkpk)，（0

2.2 算法的迭代步骤

Step 1: 给定初始点x0∈Q+，x0＝(x01,x02,…,x0|A|×|S|)T，允许误差ε，σ>0，置k =1；

Step 2: 令Dk=diag(xk1,xk2,…,xk|A|×|S|)，计算qk=－(Gk(e)－Ek′(EkEk′)－1EkGk(e))，其中Gk(e)=Dkz(xk),Ak=ADk；

Step 3: 若qk

Step 4: 计算pk=qkqk，进行一维搜索min0≤λ≤θ z(xk+λDkpk)，θ∈（0，1）；

Step 5: 设λk是Step4中最优解，若λkDkpk

Step 6: 令xk+1=xk+λkDkpk，置k=k+1，转Step2；

3 仿真实验

考虑如图1所示的交通路网，有14条路段,变量xsa有28个;有2个OD对1-9和3-7，OD需求量分别为q1,9=q3,7=55;路阻函数采用美国公路局1964年提出的BPR函数,具体可取ta(xa)=ta(0)(1+0.15xaca4),ta(0)为路段自由流行驶时间,设每条路段饱和容量为40;路段自由流行驶时间见表1。

图1 交通路网图

采用仿射尺度算法，使用Matlab软件编程对这个实例进行求解。求解中所取允许误为ε=0.01,σ=0.1时，各路段分配流量见表2。表3给出分配流量路径的行驶时间,可以看到,同一OD对路径行驶时间基本相同,从而满足Wardrop 第一准则。图2给出了仿射尺度算法的收敛曲线图,可以发现,本算法收敛速度快,算法迭代528步后误差降为0.01。

表1 路段自由流行驶时间

路段1234567891011121314

ta(0)54.54544.54.56654.54.555

表2 各路段分配流量

路段1234567

xa9.6628.4545.3438.1026.5545.3437.83

路段891011121314

xa26.5526.7237.8345.4426.7217.1728.28

表3 各OD对路径行驶时间

OD对路径(按节点)行驶时间

(1,9)

1-4-5-8-921.4181

1-2-5-6-921.4336

1-4-5-6-921.4191

1-2-5-8-921.4326

(3,7)

3-2-5-4-720.9307

3-6-5-8-720.9417

3-6-5-4-720.9317

3-2-5-8-720.9407

图2 算法的收敛曲线

4 结 语

本文给出了基于终点的用户平衡交通分配模型的仿射尺度算法，模型以基于OD对终点的路段流量作为变量，避免了路径枚举，减少计算量。仿真计算结果显示，本文采用的仿射尺度算法是有效的，分配到各路段的流量满足Wardrop 第一准则。

参考文献

［1］Lee Der-Horng,Nie Yu.Accelerating Strategies and Computational Studies of the Frank-Wolfe Algorithm for the Traffic Assignment Problem［J］.Trans.Research Record,2001,1 771:97-105.

［2］Gao Ziyou,Lam W H K,Wong S C.The Convergence of Equilibrium Algorithms with Non-monotone Line Search Technique［J］.Applied Mathematic and Computation,2004,148:1-13.

［3］Michael Patriksson.Algorithm for Comuting Traffic Equilibria［J］.Network and Spatial Economics,2004,4:242-250.

［4］Yu Nie,Zhang H M.Models and Algorithms for the Traffic Assignment Problem with Link Capacity Constraints［J］.Transportation Research Part B,2004,38:285-312.

［5］Lee Der-Horng,Nie Yu,Chen Anthony.A Conjugate Gradient Projection Algorithm for Traffic Assignment Problem［J］.Mathematical and Computer Modeling,2003,37:863-878.

［6］芦群,刘灿齐.城市公共交通网络均衡分配模型与算法［J］.交通与计算机,2004,22(4):3-6.

［7］肖海燕.基于路段流量的交通分配模型的算法［J］.武汉科技大学学报:自然科学版,2007,30(3):274-277.

［8］Bar-Gera H.Origin-based Algorithm for the TrafficAssignemnt Problem［J］.Trans.Science,2002,36:398-417.

［9］李峰,王书宁.基于终点的路径交通量求解算法［J］.清华大学学报:自然科学版,2006,46(1):149-152.

［10］Huang Chong-Chao.Gradient Projection Method with Affine Scaling for Nonlinear Programming［J］.Advances in Modelling and Analysis(A),AM SE Press,1994,22:43-48.

作者简介 刘炳全 男，渭南师范学院数学与信息科学系，讲师。主要研究方向为系统优化建模与算法。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文