交通分配

交通分配（精选9篇）

交通分配 篇1

1 引言

在城市及区域交通规划中, 交通分配作为一个重要环节起了关键的作用。随着人工智能、数学规划等方法的发展, 对交通分配模型的研究与应用也日趋成熟。国际上按照worddrop提出的第1和第2原则, 将交通分配模型划分为均衡模型和非均衡模型[1]。均衡交通分配理论在近几年发展较快, 与非均衡交通分配模型相比, 这类模型具有思路明确、结构严谨、结果合理、有利于宏观研究等优点。

近几年, 对均衡分配问题的求解出现许多新的算法, 虽然这些算法的运算复杂度在一定程度上降低了, 但处理大规模复杂的交通网络问题仍比较困难。这都迫切需要一种新的算法使之能建立易于编程的、计算能力快的、更贴近实际交通状况的预测模型。因此, 本文尝试将易于计算机编程, 且具有全局搜索功能以及并行运算特点的遗传算法应用于求解均衡交通分配模型。

2 遗传算法的一般理论

遗传算法 (Genetic Algorithm) 是一种模拟生物在自然界环境中遗传和进化过程而形成的一种全新的全局搜索和优化方法。它从任一初始群体出发, 通过随机选择、交叉和变异等遗传算子, 使种群一代代进行到空间中最好的区域, 直至达到最优点。其主要特点包括直接对结构对象进行操作, 不要求函数连续性以及求导;全局寻优能力更强;有内在的并行性。遗传算法已成为当今影响最广泛的进化方法之一, 是现代有关智能计算问题中的关键技术, 被人们广泛地应用于不同的领域, 如信号处理、自适应控制、组合优化、人工生命和机器学习。

2.1 编码

编码实际上就是从解空间把问题的可行解转换到遗传算法的搜索空间。编码一般有3种方式, 即符号编码方式、浮点数编码方式以及二进制编码方式。二进制编码方式中, 每个自变量用s位二进制的子串表示, n个问题用s×n表达, 假设 的取值范围在ximin～ximax, 则编码的区间为[0, 2s] 。

2.2 遗传操作

2.2.1 选择

选择就是以适应度高的个体为依据, 从群体中把父个体选择出来, 并令其产生相应的后代, 淘汰适应度低的个体。常用的选择方法主要有以下几种:比例的变换, 竞争的选择, 轮盘赌的选择, 稳态复制, 排序, 共享等。Holland提出的轮盘赌选择法 (roulette wheel selection) 是诸多选择方法中最有名、最常用的方法。

2.2.2 交叉

交叉是依照交叉概率, 将种群中的2个能够相互配对的父个体的部分结构按照某种特定的方式替换和重组形成2个新的个体。交叉的方法可以根据编码方法不同而变化, 例如二进制编码进行的二进制交叉, 实值编码进行的实值交叉等。在二进制交叉中又可以分为均匀交叉、单点交叉以及多点交叉。实值交叉通常有中间交叉、离散交叉、算术交叉等。

2.2.3 变异

变异是根据某一个很小的概率随机地改变群体中个体的某些基因。依据个体编码表示方法的不同, 变异方法也不同, 如二进制编码中的1变成0, 0变成1。变异算法有2个重要作用, 包括使遗传算法具有较强的局部随机搜索能力;使遗传算法能维持群体多样性, 防止未成熟收敛的现象出现。

2.3 终止条件

算法终止, 即最优个体的适应度达到设定的阀值;最优个体的适应度以及群体适应度不再变化时;迭代次数达到预先设定的次数。

2.4 遗传算法在约束优化问题上的处理方法

遗传算法用于约束优化问题的求解常用的有几种方法, 包括可行域、混合法、算子修正法、罚函数法[2]。采用线性约束的等式消除某些变量, 用其他的线性组合代替变量, 并修改线性不等式;采用专门设计的修正算子, 对不可行染色体进行修复, 保证后代一直是可行的;采用罚函数法, 通过惩罚不可行解将有约束的问题转化为无约束的问题, 使得遗传算法可以在可行域和不可行域中搜索到最优解。

3 基于遗传算法的用户均衡分配模型

3.1 用户均衡模型

交通分配就是将OD矩阵q中的交通需求量安排到路网中, 从而形成路段流量x, 该过程按照Wardrop第一原则 (UE原则) 进行, 用求解数学规划的问题算出符合UE条件的流量分布, 公式如下:

$\min \text{Ζ}(x)={\displaystyle \sum _{a\in A}}f{}_0^{x{}_a}t{}_a(\omega )\text{d}w(1)$

约束条件:

$\begin{array}{l}{\displaystyle \sum _{k\in {\rm P}{}_{rs}}}f{}_{rs}^k=q{}_{rs},r\in R,s\in S(2)\\ f{}_{rs}^k\ge 0,r\in R,s\in S,k\in {\rm P}\end{array}$

路段流量由公式计算:

$x{}_a={\displaystyle \sum _{r\in R}}{\displaystyle \sum _{s\in S}}{\displaystyle \sum _{k\in {\rm P}}}f{}_{rs}^k\delta {}_{\text{r}\text{s}}^{\text{a}\text{k}},a\in A(3)$

其中, 路段时间函数被假定成路段交通流量的单调、连续上升函数, 只与自身的路段流量有关。目标函数是路段时间函数的积分。约束条件令每个OD对之间所有路径流量的和等于相应的OD需求, 约束条件描述了路径流与路段流之间的关系。

3.2 模型的设计

3.2.1 算例

某一简化的交通网络见图1。

其中, OD量为300, 3个路段的时间阻抗函数为:

t1=50[1+α (x1/100) β], t2=30[1+α (x1/200) β], t3=40[1+α (x1/150) β]

α、β是调教系数, 建议α=0.15, β=4。

3.2.2 模型分析及求解过程

该交通网络的用户均衡, 交通分配问题可以表示成数学规划模型。

$\begin{array}{l}\text{m}\text{i}\text{n}\text{z}(X)={\displaystyle \sum }{\displaystyle \underset{0}{\overset{x{}_0}{\int }}}t{}_a(w)\text{d}w={\displaystyle \underset{0}{\overset{x{}_4}{\int }}}t{}_1(w)\text{d}w+{\displaystyle \underset{0}{\overset{x{}_2}{\int }}}t{}_2(w)\text{d}w+{\displaystyle \underset{0}{\overset{x{}_3}{\int }}}t{}_3(w)\text{d}w(4)\\ s.t.\left\{\begin{array}{l}{\displaystyle \sum _k}f{}_k^{r{}^3}=q{}_{rs}\forall r,s\\ f{}_k^{rs}\ge 0\forall k,r,s\end{array}\right\}\end{array}$

其中ta为路段的阻抗函数, a=1, 2, 3;qrs为OD流量;f${}_k^s$为r、s间第k条路段的流量, 即f${}_1^s$=X1, f${}_2^s$=X2, f${}_3^s$=X3。将OD流量qrs、路阻函数ta带入优化模型, 得到公式如下:

$\begin{array}{l}\min z(X)=50X{}_1+150\left(\frac{X{}_1}{100}\right){}^5+30X{}_2+180(X{}_2/200){}^5+40X{}_3+180(X{}_3/150){}^5,\\ s.t.\left\{\begin{array}{l}X{}_1+X{}_2+X{}_3=300\\ X{}_1\ge 0,X{}_2\ge 0,X{}_3\ge 0\end{array}\right\}(5)\end{array}$

采用罚函数法将目标函数转换成增广目标函数p (X, u) , 公式如下:

$\begin{array}{l}{\rm T}(X,u)=z(X)+u(X{}_1+X{}_2+X{}_3-300){}^2+u\left\{(\min (0,X{}_1)){}^2+(\min (0,X{}_2)){}^2+(\min (0,X{}_3)){}^2\right\}\\ (6)\end{array}$

式中T (X, u) 为增广目标函数;z (X) 同上;u为惩罚因子, 且u>0, 当u→∞时, 目标函数逼近最优解。通过遗传算法求解。

(1) 可行解采用二进制编码, 每个自变量的取值范围在[0, 300], 用8位二进制数表示, 染色体串的长度为8×3=24。

(2) 个体适应度函数:

F (X) =1/z (X) (7)

(3) 解码方法:

$\begin{array}{l}\tilde{x}{}_i={\displaystyle \sum _{i=1}^i}b{}_{ij}2{}^{i-j},(8)\\ x{}_i=x{}_{i\text{m}\text{i}\text{n}}+\frac{\tilde{x}{}_i(x{}_{i\text{m}\text{a}\text{x}}-x{}_{i\text{m}\text{i}\text{n}})}{2{}^{/}-1}(9)\end{array}$

得到结果:$x{}_1=0+\tilde{x}{}_i(300-0)/(2{}^8-1)$。

(4) 遗传算子为比例遗传算子, 种群适应度之和F的计算公式如下:

$\text{F}={\displaystyle \sum _{i=1}^{popsize}}F(X{}_i)(10)$

对染色体选择的概率计算使用公式如下:

pi, pi=F (Xi) /F, i=1, 2, …, popsize

对染色体累加的概率计算使用公式如下:

$q{}_i,q{}_i={\displaystyle \sum _{j=1}^i}p{}_j,j=1,2,\cdots ,popsize$

对于产生一个位于[0, 1]区间的长度为popsize随机数的序列, 其中的任意的一个数r若满足qi-1<r<qi, 则选第i染色体 (i=1, 2, …, popsize) , 这样就得到新的种群。运算交叉, 单点交叉算子;运算变异, 基本位变异算子。遗传算法的运行参数。设定群体的规模 (popsize) 为100, 交叉概率为0.95, 变异概率为0.001。经过计算, 得到结果如下:X1=118.309 2, X2=122.535 3, X3=59.154 6;t1=40.154 1, t2=40.145, t3=40.1451最优值:z (X) =11 028.385。从最后的运行结果可知, 所有路径的交通时间趋于相等, 即t1=t2=t3=40.145 1, 系统朝着均衡方向发展, 整个路网达到用户最优状态。

4 结语

从实例分析可见采用遗传算法解决用户最优的均衡交通分配模型是可行的。由于遗传算法模型简单, 易于计算机编程且求解速度快, 对函数的可微性或连续行等没有要求, 只要所要求解的问题的目标函数是可计算的便可, 在计算机的帮助下, 可灵活的处理许多交通网络问题, 方便了使用者的具体操作。

参考文献

[1]陆化普, 黄海军.交通规划理论研究前沿[M].北京:清华大学出版社, 2007.

[2]玄光男, 程润伟.遗传算法与工程优化[M].北京:清华大学出版社, 2006.

[3]姜友华, 王新生.遗传算法用于产生可供选择的城市规划方案[J].武汉大学学报, 2002, 35 (3) , 63~65.

[4]雷英杰, 张善文, 李续文, 等.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社, 2005.

[5]Booker, Goldberg L B, Holland J H.Classififier Systems andGenetic Algorithms[J].Artificial Intelligence, 1989 (40) :235~280.

[6]Feng C, Lin J.Using a genetic algorithm to generative sketchmaps for urban planning[J].Computers Environment and Urbansystem, 199, 23 (2) :92~100.

[7]Richad J B, John T T, Michael R B.Multiobjective urban plan-ning using genetic Algorithm[J].Journal of Urban and Develop-ment, 1999, 125 (2) :86~99.

交通分配 篇2

3.1动态模型的约束条件

本模型服从先进先出规则，设一辆在ti时段进入路段a。路段a上的行驶时间近似认为ta（ea（ti））（因为行驶时间ta（q）是随q的变化而变化，若ti时段很小，则可以认为a上的交通量ea（ti）为不变的）[5]，则在ti+ta（ea（ti））时刻离开a路段。为简便起见，若取每个小时为单位时间（或相等时间），则

这里假设第ti时段的交通流量a在本时段内不流出，即

说明ti时段a路段上的流出量必为前面某时段ti的流入量。

在ti时段末，路段a上的交通流量不仅与前一时段的交通量有关，还与本时段的流出量有关，应为

即ti时段a路段上现有交通量等于前一段交通量加上该时段交通分配量减去该时段交通流出量，设ea（0）=0。

考虑任一O-D对r-d，在起点r，ti时段的交通分配量，应为该节点的生成量与其它节点经过该节点流向s的交通量之和，即

3.2 动态模型的目标函数

为简便起见将所考虑的时段（0，T）分为m个相等的时期t1，t2，t3，……tm，因为每个时段相等，可将小时段记为1，2，……，m，则第i个时段的.均衡模型为

3.3 模型的求解方法

Frank-Wolfe算法用线性回归逐步逼近非线性规划的方法来求解UE模型，该方法是迭代算法[6]。此方法的前提条件是模型的约束条件必须都是线性的。均衡分配法的步骤可归纳如下：

Step0：初始化。

按照织 tao=ta（0），va 实行一次0-1分配，得到{xa1}，令n=1

Stepl：更新时间

tan=ta（xan）.va

Step2：找方向。

按照{tan}实行一次0-1分配得到一组辅助变流{yan}：

Step3：确定步长

求下式∑a（yan-xan）ta（xan+λ（yan-xan））=0；

0QλQ1

Step4： 移动。

Xan1=Xan+λa（yan-xan），Va.

Step5 ：收敛检验。如果{Xan1}已满足规定的收敛准则，停止计算。

{Xn+1}即为解，否则令n=n+1. 返回Stepl 1.

3.4 模型的求解步骤

为了求解本模型，关键就是求解规划问题，与UE问题没有本质区别，也是用求解非线性规划的方法即可解决。求解本模型步骤如下：

步骤0 首先将所考虑的大段[0，T]分为m个相同的单位时段1，2，…M。已知每个小段的O-D：q～（t1），V k， r， sea（0）=0：

步骤1 利用一种非线性规划的方法（F-W算法）求解规划问题（p1）“

步骤2 若求出了（p1）的最优解，由上式就可算出ea（t1-1）及oa（t1）；

步骤3 按非线性规划方法（F-W算法）来求解规划问题（p1）直至（pm）为止；

显然，若能寻找一种有效的方法来求解非线性规划问题（p1）（i=1，2，....，m），则本模型就有有效的求解方法，这属于非线性规划问题求解方法的研究。

4 结论

本文动态模型考虑了路段上的原有交通量，对实时的路段交通量配流进行了优化，路网得到了较充分的利用，比静态的交通量分配的路径诱导结果优势明显。

参考文献：

[1]杨兆升.城市交通流诱导系统理论与模型[M].北京：人民交通出版社，2000.

[2]黄海军.城市交通网络平衡分析理论与实践[M].北京：人民交通出版社，1994.

[3]陆化普，史其信，殷亚峰.动态交通分配模型理论的回顾与展望[J].公路交通科技，1996，13（1）：78-81

[4]杨清华，贺国光.对动态交通分配的反思[J].系统工程，2000，97（1）：49-52.

[5]袁振洲，李巍屹，刘海东.动态交通分配理论与方法研究简介[J].综合运输，2008（9）：23-25.

交通分配 篇3

交通分配问题主要是根据路网的出行成本和OD间的交通分布量计算出各条路段、路径的流量。Daganzo和Sheffi (1977) 提出了第一个随机用户均衡交通流分配模型[1], 之后研究人员基于不同的研究点提出了各种随机均衡分配模型。李志纯和黄海军 (2004) 假设出行方式选择满足随机均衡, 建立多方式换乘交通分配模型[2];lam和吴子啸 (2003) 假设出行方式和路径选择都满足随机均衡, 建立考虑步行与公共交通换乘的交通分配模型[3]。目前大多数满足随机均衡交通分配模型都是以logit模型来刻画出行者路径选择概率并计算相应路径流量, 但是logit模型只考虑到路径通行时间之间的绝对差别, 而不考虑相对差别。虽然利用基于Probit加载分配模型也能够解决这个问题, 但是前提是要知道路径出行时间的协方差矩阵, 而且目前尚无法构建基于Probit加载路径选择概率或路径流量的封闭表达式, 在求解算法上只能通过蒙特卡洛模拟进行求解, 计算量较大[4], 因此未能在交通分配模型中得到广泛使用。Kirchhoff方程不但在一定程度上能够说明路径出行时间相对差对出行者路径选择的变化, 而且不需要知道路径的协方差矩阵, 计算简单。VIS-SUIM交通仿真软件在模拟出行者路径选择时也提出了用Kirchhoff分布方程来计算出行者路径选择概率[5], 但是没有给出具体的模型表达式, 也没有对最后的求解做收敛处理, 并且该算法主要用于交通仿真模型中, 没有在交通分配模型中作推广。本文根据VISSUIM交通仿真软件说明书中的Kirchhoff分布方程表达式建立相应交通分配变分不等式模型, 用连续平均算法求得模型的收敛解, 并与基于logit加载随机均衡交通分配模型对同一个实验路网求得的解作比较。

2 问题描述

2.1 随机平衡交通分配问题

在实际出行中, 出行者对于路网状况以及交通现状不可能完全了解, 即使在ITS环境下, 出行者也只能间隔一段时间收到路况信息, 而路网中往往存在一些难以量化的因素, 因此可以将路径阻抗看成是一个随机变量。假定O-D对i-j之间第K条路径上出行者的实际出行阻抗为ckij, 出行者感知出行阻抗为Ckij, 其中Ckij=ckij+ξkij。ξkij为第K条路径出行阻抗的随机误差项。

每条路径的估计阻抗是随机变量, 具有相应的概率密度, 因此对于某一特定的出行者, 每条路径均有一个被选择的概率。随机均衡交通分配问题就是计算在路径阻抗分布函数的基础上, 有多少出行者选择每一条路径。假定O-D对i-j之间第K条路径被选择的概率是Pkij, 也就是其估计阻抗在i-j之间所有可能路径的估计阻抗中为最小值的概率, 即:

由随机均衡交通分配问题的定义可知, 在这种平衡状态下, 某个OD对之间所有已被选用的路径上不一定具有相同的实际阻抗值, 而满足下述条件:

在交通分配问题中满足式2的就可以认为满足SUE随机路径选择均衡[7]。

2.2 Kirchhoff分布方程与logit随机选择概率表达式比较

基于Kirchhoff分布方程路径选择概率表达如下[5]:

假设OD对i-j之间存在n条路径, ck表示路径k的出行时间, 则出行者对路径k的选择概率满足以下关系:

其中α表示敏感系数, α决定了驾驶员选择不同效用路径的概率分布。如果敏感系数低, 则驾驶员对不同效用路径的选择概率基本一致;如果敏感系数高, 则几乎所有的驾驶员都将只选择最优路径。

目前大多数考虑出行者随机路径选择交通模型都是基于logit随机加载, 其路径选择概率表达式如下[7]:

如图1所示, 假设OD对AB之间存在两条路径P1、P2, 考虑以下两种情况:

情况一:路径P1、P2出行时间分别为5分钟和10分钟, 分别根据Kirchhoff分布方程与logit模型计算出两条路径的选择比例如下表所示:

情况二:路径P1、P2出行时间分别为200分钟和205分, 分别根据Kirchhoff分布方程与logit模型计算出两条路径的选择比例如下表所示:

在情况一的条件下, 大部分出行者会选择路径P1, 因此P1的选择概率及分配流量都会比P2大很多, 而在情况二的条件下, 两条路径的出行时间都增加了195分钟, 这时两条路径的成本对出行者来说别就没有情况一时差别大, 两条路径的选择概率之差应该比情况一时的概率差小, 但是从计算结果可以看出, logit模型在两种情况计算出的概率完全一样;而Kirchhoff分布方程在第二种情况下计算出的路径选择概率差别很小, 而且从模型的表达式中容易看出, 随着路径出行时间的增大, 两条路径通行时间的相对差别逐渐减小, 其概率差还将进一步减少。因此考虑基于Kirchhoff分布方程能够考虑出行时间的绝对值变化对路径选择的影响, 相对logit模型更符合实际情况。

3 基于Kirchhoff分布方程交通分配模型建立

考虑网络G= (N, L) , 其中N表示网络中的节点集合, L表示网络中连接两个节点之间的路段集合。

W表示路网所有OD对集合

R表示起讫点集合。

S表示终点的集合。

fpw表示OD对w之间第p条路径的流量。

Pw表示OD对w之间的路径集合。

Ppw表示OD对w之间第p条路径。

C (fwp) 表示路径Pwp的通行时间, 其表达式如下:

其中xa表示路段a上的流量, , fwp为上的流量, 当路段a在路径p上时δa, p=1, 反之δa, p=0

假设出行者路径选择概率表达形式为Kirchhoff分布方程, 参考文献[5]中Kirchhoff分布方程概率表达式, 构建以下模型:

约束条件如下:

fwp*为模型求得的最优解, 对模型进行K-T条件分析可以得到以下结果[8]:

根据模型的表达式可知fwp>0, 因此根据式 (8) 可得

根据式 (10) 可知

根据式 (6) 可知

根据式 (11) 可知

将式 (13) 带入式 (11) 得到

从式 (14) 可知模型得到的解满足Kirchhoff分布方程形式。

4 求解算法

参考文献[9]第五章中提到的连续平均 (MSA) 求解算法对模型求解, 设计算法具体步骤如下:

步骤1:初始化, 设n=0, 所有路径流量为0, 计算各路径成本C (fwp*) ) (0) , n=n+1。

步骤2:根据式 (11) 计算所有OD对之间各条路径流量 (fwp*) ) (0) 。

步骤3:根据 (fwp*) ) (0) 及路段BPR函数更新所有OD对之间各路径成本C (fwp*) ) (0) 。

步骤4:根据C (fwp*) ) (0) 根据式 (11) 计算路径附加流量 (ywp*) ) (0) 。

步骤5:根据MSA算法对路径流量更新

步骤6:判断是否达到收敛标准: (fwp*) ) (n+1) - (fwp*) ) (0) <ε, 若满足该收敛标准则计算结束, 否则n=n+1返回步骤3。

5 算例分析

通过以下的虚拟路网对所建模型进行算例分析, 路网结构如图2所示, 该路网包括9个节点和12条路段。路段的通行时间函数采用BPR函数, 即

式中:ta (0) 为路段零流量通行时间, ca为路段a的通行能力。各路段自由流通行时间及路段的通行能力如表3所示

设敏感系数α=2, 收敛标准ε=0.05。将文献[10]中基于logit加载随机用户均衡模型 (以下称为模型1) 与本文所建模型 (以下称为模型2) 计算结果做比较, 当各条路段的零流量通行时间均增大50分钟时, 观察两个模型求得的解, 得到以下的结果:

Logit (1) 与k (1) 表示路段零流量通行时间增大前分别用模型1和模型2计算得到的路径选择概率, Logit (2) 与k (2) 则表示零流量时间增大后模型1和模型2计算得的路径选择概率。可以看出当每条路段零流量通行时间都增大50分钟后, 各条路径的零流量通行时间都在200分钟以上, 而各条路径出行时间的差值都在10分钟以内, 这对出行者来说相对差别很小, 因此对出行者来说各条路经的选择概率应该相差不大。观察到模型1计算得到的结果中P1的选择概率仍然要比其他的路径选择概率大很多, 而P6的选择概率仍旧很小, 而且其余几条路径的选择概率分布也很不均匀。而模型2计算出的路径选择概率就比较平均, 大都在16.6%上下, 相较模型1的结果更加符合实际情况。从迭代次数也容易看出模型2在两种情况下的迭代次数都远远小于模型1的迭代次数。这样便使得模型2在求解实际交通规划问题中能够大大减少计算量, 或者在同样计算强度的基础上能够对更大规模的路网进行求解。

6 结语

本文考虑路径出行时间相对差对出行者路径选择行为的影响, 构建了基于Kirchhoff分布交通分配模型, 并用MSA算法进行求解。对同一个实验路网, 将本文所建模型与基于logit随机加载交通分配模型计算结果作对比, 结果显示前者能够考虑路径出行时间相对差别对路径选择概率的影响, 当路经出行时间增大时前者计算结果更加符合实际情况, 而且迭代次数明显少于后者。

摘要：利用变分不等式建立基于Kirchhoff分布交通分配模型, 并证明模型的解满足Kirchhoff分布路径选择概率表达式, 基于K最短路算法和连续平均法, 设计求解模型算法。并与基于logit加载随机用户均衡交通分配模型作比较, 对同一个虚拟路网进行求解, 结果表明基于Kirchhoff分布分配模型不仅能够较好地考虑路径成本相对差对出行者路径选择行为的影响, 并且模型达到收敛标准所需的迭代次数大大减少。

关键词：Kirchhoff分布,随机用户均衡,路径出行时间,相对差

参考文献

[1]DAGANZO C F, SHEFFI Y.On stochastic models of traffic assignment[J].Transportation Science, 1977, 11:253-274

[2]LI ZHI-CHUN, LAM WILLIAM H K, WONG S C, et al.Modeling Park&Ride services in a multi-modal transportation network with elastic demand[C].Transportation Research Board 86th annual meeting, January 21-25, 2007, Washington D.C

[3]WU Z X, LAM W H K.A combined modal split and stochastic assignment model for congested networks with motorized and non-motorized transport modes[C].Transportation Research Board 81st annual meeting, December 13-17, 2002, Washington D.C

[4]PATRIKSSON M.Traffic Assignment Problem—Models and Methods[M].Sweden, Linkoping Institute of Technology, 2002

[5]PTV公司.VISSIUM交通仿真软件用户说明书[M].北京:人民交通出版社, 2003

[6]黄海军.城市交通网络平衡分析理论与实践[M].北京:人民交通出版社, 1994

[7]高自友, 宋一凡, 四兵锋.城市交通连续平衡网络设计理论与方法[M].北京:中国铁道出版社, 2000

[8]陈宝林.最优化理论与算法[M].北京:清华大学出版社, 2005

[9]陆化普, 黄海军.交通规划理论研究前沿[M].北京:清华大学出版社, 2007

交通分配 篇4

摘要：介绍了一个在分布式计算环境下可以实时运行的动态交通分配系统。该系统基于CORBA技术，可进行动态起迄点出行分布矩阵的估计和预测，还可以进行系统一致性控制。

关键词：动态交通分配 CORBA 并行计算

随着经济发展，交通拥挤、道路阻塞、交通事故和交通污染等问题越来越严重地困扰着世界各国的城市。应运而生的智能交通系统ITS（Intelligent Transportation Systems）通过使用先进的计算机技术、电子技术和通信技术以提高现有交通系统的效率，给人类带来了新的希望。根据美国智能交通协会ITS AMERICA（Intelligent Transportation Society of America）的定义，ITS的两个基本组成部分是先进交通信息系统ATIS(本网网收集整理)（Advanced Traveler Information Systems）和先进交通管理系统ATMS（Advanced Traffic Management Systems）。ATIS使用视觉和听觉设备搜集相关交通信息，然后分析、传递和提供信息，从而在起点到终点的旅行过程中，向出行者提供实时帮助，使整个旅行过程舒适、方便、高效；ATMS将车辆作为管理系统的一部分，利用它感知并预测未来交通拥挤堵塞，并且给出交通管理最佳策略。

保证ITS（尤其是ATMS）运行的核心方法是动态交通分配DTA（Dynamic Traffic Assignment）。所谓动态交通分配，就是将实时交通流量在路网各路段上进行合理分配，为旅行者提供出发时间与方式选择，为车辆提供道路诱导系统，引导车辆行驶在最佳线路上，并提供诱导系统与交通控制系统的相互联系。

美国德克萨斯州奥斯汀大学于2001年开发出了一套实时DTA系统――DYNASMART－X。本文基于其研究成果，提出了一个CORBA分布式实时DTA系统的框架。

1 CORBA技术

从1989年成立起?熏对象管理组织OMG（Object Management Group）一直致力于使用面向对象技术，使基于对象的软件在分布异构环境中可重用、可移植、可互操作。公共对象请求代理体系结构CORBA（Common Object Request Broker Architecture）即是由OMG提出的应用软件体系结构和对象技术规范。其核心是一套标准的语言、接口和协议，以支持异构分布应用程序间的互操作性及独立于平台和编程语言的对象重用。

CORBA技术是一个重大革新，它解决了系统集成中两大著名问题：（1）开发客户机／服务器应用的困难；（2）快速集成新老系统的问题。它被认为是新出现的分布式对象管理DOM（Distributed Object Management）技术的规范。DOM技术在基本的分布式计算服务上提供了一个更高层次的面向对象接口。最高层次的规范叫做对象管理体系结构OMA（Object Management Architecture），见图1。其中，ORB的作用是对其他部件间的请求进行传递；CORBA服务提供了一些基本的.系统服务，如命名、持久性和事件通知等；CORBA设施包括用户界面、信息管理等设施；CORBA域对应于特定的应用域，如财政、制造和远程通信技术等。

集成应用对象的关键是使用接口定义语言IDL（Interface Definition Language）定义的标准规范。一旦所有应用和数据有了一个与IDL兼容的接口，通信就会独立于物理位置、平台类型、网络协议和程序语言。一个使用CORBA创建的信息系统仲裁这些软件对象间的控制和信息流。

广泛使用的CORBA2．0 ORB是在对象间建立客户机／服务器关系的中间件。使用一个ORB，一个客户机对象可以透明地调用一个服务器对象的一个方法，这个服务器对象可以在同一台机器上，也可以在一个网络上。ORB截听调用请求，并负责找到一个对象，执行这个请求，传递参数，调用方法并返回结果。此客户机不需要知道对象的位置、编程语言、操作系统或其他任何不属于对象接口的方面。注意到客户机／服务器作用只是协调两个对象之间的相互作用非常重要。

2 动态交通分配

DTA系统是一个复杂的系统，在保证对交通系统中周期性和非周期性的事件进行实时响应的同时，还需要对数以万计的路段、控制器和车辆的历史、当前及预测数据进行管理。DTA系统的实时运行要求系统同时满足两个条件：（1）系统响应避免系统故障；（2）系统响应及时，如果不能及时响应，系统也不致停止运行。计算环境和软件工具是保证一个复杂系统实时响应的两个主要因素。

2．1 实时运行机制

为了满足实时运行的要求，需要一个机制，使DTA系统实时接收测量值，并启动相应的算法单元，传递结果到相应的外部设备。图2给出了这种实时运行机制。在当前运行时段Ti的起点，DTA系统接收

并评价刚刚过去的运行时段Ti－1的测量值。基于这些测量值，整个系统及其中的算法单元在当前时段响应和作用。每个算法单元和整个集成系统在逻辑内部和功能设计上均使用上述机制，从而通过运行时段的一致定义，即可方便地增减算法步骤和功能，大大提高了灵活性。

2．2 实时DTA框架

实时DTA系统由以下功能单元组成：（1）一致性检查；（2）一致性更新；（3）O－D估计（O即Origin，D即Destination，O－D估计即起迄点出行分布矩阵估计）；（4）O－D预测；（5）状态估计；（6）状态预测；（7）交通分配；（8）用户界面；（9）数据库：（10）管理。这些功能单元之间相互作用并与ATMS数据库相互作用。其中（1）负责检查真实系统和DTA仿真器与（3）之间的一致性，主要是比较预测的状态变量和实际的状态变量，一旦超过事先规定的阈值，即向（2）报告；（2）基于（1）的报告更新DTA仿真器和（4）；（3）基于监视系统的实时测量值和历史O－D数据，估计当前道路网络的起迄点出行矩阵；（4）基于当前O－D估计结果、当前网络状态和历史O－D数据，产生未来时段的O－D预测；（5）把给定的非常短的仿真间隔（几秒钟）的路径决策与（2）产生的调节结合来仿真交通流的类型；（6）仿真更长时间的交通流的类型并提供未来时段（20～30min）的路径决策；（7）根据系统最优和用户平衡等不同用户要求提供路径决策：（8）提供用户接口；（9）最小化其他单元请求的等待时间和最大化吞吐量；（10）提供所有单元间的控制以维持系统稳定并防止故障，同时保证系统同步。显然，实时DTA系统的设计应基于层次结构。最高层，即管理单元，其他单元各自被映射到一个不同的专用处理器，见图3。

3 基于CORBA的DTA系统

3．1 AMH框架下的DTA系统

多处理机／并行计算对实时DTA系统相当重要。在实时DTA系统中，一些功能周期性执行；另一些功能非周期性地被其他功能触发。因此，设计时，最根本的一点是把握每个功能单元的执行周期。

可以把所有循环集成在一个异步多层次AMH（Asynchronous Multi－Horizon）框架中。在AMH框架中，各功能在不同层次的分布式处理器上实现。每个功能以周期性模式、非周期性模式或联合活动模式运行。周期性活动模式下，基于执行循环定时执行；非周期性活动模式下，只有当其他功能发出一个事件调用请求时才执行；联合活动模式下，一个功能定时执行，同时允许其他功能触发以启动一个新功能的运行。也就是说，在当前执行循环中，当接收到一个调用请求时，将从下一个执行循环的起点开始新功能的运行。这个策略非常重要，保证系统对环境变化实时响应，同时维持整个DTA系统的可靠和稳定。

3．2 ILU框架下的DTA系统

在CORBA环境下实现实时DTA系统最好使用中间语言统一体ILU（Inter Language Unification），因为ILU是共享的，可用性更好。ILU支持创建新的对象、远程过程调用和异步调用。一旦一个ILU对象被创建，它就通知ILU服务器其已经存在。通过这个服务器，每个对象都能获得其他对象的信息。此后，每个对象均能远程访问其他任何对象，就像在同一台机器上。

实时DTA系统可以由三个主要对象组成：操作对象、GUI和ATMS数据库，见图4。CORBA中的对象需要被指定为服务器或客户机。服务器定义为一个接收客户机请求并执行这个请求的对象；客户机定义为一个向服务器发送请求的对象。一个对象也可以同时被指定为客户机和服务器。它既能发送也能接收请求。

在实时DTA系统中，三个对象均被指定为客户机和服务器。在操作对象下设计六个子操作对象。每个子操作对象在一个运行周期工作。在状态估计对象下设计一致性检查和一致性更新两个对象，是因为这两个对象与状态估计对象直接作用。GUI负责输入指令输出结果。ATMS数据库包括实时监视数据、系统输出、历史数据及其中的相互作用。

交通分配 篇5

关键词：城市交通,线路类型,客运周转量,分配优化模型

一般在现代大城市中的线路类型是:城市轨道交通、快速路、主干路、次干路和支路, 各类型线路所占的比例不同, 城市交通网络的总通行能力就不同。本文假设城市规划修建一条城市轨道交通线路, 政府部门可以控制综合交通网络修建和改造的总投资、总用地, 以最大高峰小时客运周转量为目标函数, 进行城市交通线路类型分配优化分析。

1线路类型特征分析

城市轨道交通是城市客运交通系统的骨干, 能够有效缓解整个城市的交通压力, 并对城市的发展具有引导性的作用, 但由于其投资金额巨大, 对城市的发展布局有着直接影响。快速路是城市客货流快速运输的动脉, 是快速到达城市各主要区域的通道, 但投资巨大;主干路是联系全市公共活动场所、主要交通枢纽和工矿企业及生活区的主要通道, 也有很大的交通容量, 但造价也很高;次干路是联系主干路之间的辅助性干道, 建设资金要低一些;支路主要是居住区街道和街区内部的街道, 单位长度的耗资最少, 在路网中所占的比例也最大。

2高峰小时客运周转量及计算方法

城市道路网的机动车高峰小时通行能力计算公式如下:

${{\rm N}}^{\prime }=\left({\displaystyle \sum _{i=2}^{5}L}{}_i\alpha {}_{1i}\alpha {}_{2i}\eta \right){\rm T}\times \frac{1000v}{l{}_p\left(\frac{v}{3.6}t{}_1+\frac{k{}_2-k{}_1}{254(\Phi +i)}v{}^2+l{}_s+l{}_v\right)}$。

其中, v为汽车的平均行车速度, km/h;t1为驾驶员反应时间, s, 可取t1=1.2～1.8;ls为汽车长度, m;lv为汽车安全间距, m, 可取lv=2 m～5 m;lp为机动车的平均出行距离, km;k2, k1均为制动使用系数, k2=1.7, k1=1.0;Φ为附着系数, 通常可取0.7;i为道路坡度系数;Li为城市轨道交通单线长度, 以及城市快速路、主干路、次干路、支路的单车道有效长度, km;α1i为道路综合利用系数;α2i为道路的交叉口利用系数;η为城市道路网的饱和度系数, 路段可取0.75;T为城市道路机动车道的高峰服务时间, h。

城市道路网机动车高峰小时客运周转量计算公式如下:

Pd=N′beL=N′×5×85%×L。

其中, b为每辆当量小客车的载客量, 人/pcu, 可以取5;e为满载率, 高峰小时时一般可以取85%;L为规划城市道路网的单车道总长度, km。

城市轨道交通列车高峰小时客运周转量, 人·km/h, 计算公式如下:

Pg=P′×L1×T=40 000L1×T。

其中, P′为一列车高峰小时运量, 可以取40 000人/h;L1为规划的城市轨道交通线路长度, km。

综合交通高峰小时客运周转量公式如下:

P=Pd+Pg。

3线路类型分配的线性规划优化模型

3.1 线路类型分配的线性规划计算方法

3.1.1 目标函数

$C={\rm T}\times L\times \frac{1000v}{l{}_p\left(\frac{v}{3.6}t{}_1+\frac{k{}_2-k{}_1}{254(\Phi +i)}v{}^2+l{}_s+l{}_v\right)}$。

c2=α12α22η;c3=α13α23η;c4=α14α24η;c5=α15α25η。

则目标函数为:

$F(X)=40000\times {\rm T}\times x{}_1+4.25C\times {\displaystyle \sum _{\begin{array}{l}i=2\\ j=2\end{array}}^{5}c}{}_{i}x{}_j$。

3.1.2 设计变量

高峰时段城市综合交通网络客运周转量的大小主要由各种线路类型长度Li决定, 所以, 选择参数Li为设计变量:

X= (x1, x2, x3, x4, x5) T= (L1, L2, L3, L4, L5) T。

3.2 约束条件

1) 城市轨道交通线路长度L1的约束。

约束条件为:

0≤L1≤[L1]U。

其中, [L1]U根据不同城市的规模与布局而取值。

2) 快速路线路长度L2的约束。

0.05L≤L2≤0.08L。

3) 主干路线路长度L3的约束。

0.128L≤L3≤0.192L。

4) 次干路线路长度L4的约束。

0.2L≤L4≤0.224L。

5) 支路线路长度L5的约束。

0.48L≤L5≤0.64L。

6) 资金 (万元) 约束。

设城市轨道交通每千米造价为b1、快速路每千米造价为b2、主干路每千米造价为b3、次干路每千米造价为b4、支路每千米造价为b5, 而一个城市在某个时期用于交通网的总资金数为B时, 有:

b1L1+ (L2b2) /n2+ (L3b3) /n3+ (L4b4) /n4+ (L5b5) /n5≤B。

其中, n2, n3, n4, n5分别为城市快速路、主干路、次干路、支路的车道数。

b1=w地下b地下+w地面b地面+w高架b高架。

式中:w——各种敷设方式在全线所占比例;

b——各种敷设方式的每千米造价, 万元/km。

7) 占用城市土地面积 (m2) 的约束。

道路路基宽度为di, 城市道路应占土地总面积为D, 则:

S1L1+ (L2d2) /n2+ (L3d3) /n3+ (L4d4) /n4+ (L5d5) /n5≤D。

S1=w地下s地下+w地面s地面+w高架s高架。

式中:s——各种敷设方式每千米占地面积, m2;

S1——城市轨道交通所占土地面积, m2。

8) 线路长度总约束。

L2+L3+L4+L5=L。

3.3 数学优化模型

根据以上分析, 可知本问题是一个线性规划问题, 对大城市其数学模型是:

maxF (X) =80 000x1+4.25C (c2x2+c3x3+c4x4+c5x5) 。

$\text{s}.\text{t}.\{\begin{array}{l}x{}_1\ge 0‚x{}_1\le [L{}_1]{}_U\\ x{}_2\ge [L{}_2]{}_L‚x{}_2\le [L{}_2]{}_U\\ x{}_3\ge [L{}_3]{}_L‚x{}_3\le [L{}_3]{}_U\\ x{}_4\ge [L{}_4]{}_L‚x{}_4\le [L{}_4]{}_U\\ x{}_5\ge [L{}_5]{}_L‚x{}_5\le [L{}_5]{}_U\\ b{}_{1}x{}_1+(x{}_{2}b{}_2)/n{}_2+(x{}_{3}b{}_3)/n{}_3+(x{}_{4}b{}_4)/n{}_4+(x{}_{5}b{}_5)/n{}_5\le B\\ S{}_{1}x{}_1+(x{}_{2}d{}_2)/n{}_2+(x{}_{3}d{}_3)/n{}_3+(x{}_{4}d{}_4)/n{}_4+(x{}_{5}d{}_5)/n{}_5\le D\\ (x{}_2+x{}_3+x{}_4+x{}_5)/L=1.0\end{array}$

。

4算例分析

某市对城市交通进行规划, 并已经筹划在五年内建成一条城市轨道交通线路, 现根据某市的抽样调查可得:高峰小时数T=2 h;汽车在城市道路中的平均行驶速度v=40 km/h;规划城市道路网的单车道总长度L=4 000 km;机动车平均出行距离lp=30 km。

4.1 确定目标函数的系数

C=1 334 720, c2=0.648, c3=0.432, c4=0.36, c5=0.4。

就道路交通而言, 取各种道路每千米造价为:

b2=3 000万元, b3=2 000万元, b4=1 000万元, b5=600万元。

路基宽度分别为:

d2=40 m, d3=40 m, d4=25 m, d5=12 m。

快速路、主干路、次干路、支路的车道数分别为6, 6, 4, 2, 该市综合交通线网允许总投资为250亿元, 交通允许占地总面积为26 km2。

4.2 单纯形法解线性规划问题

对于有城市轨道交通的城市, 将式中的数据代入模型, 单纯形法程序解得:

maxF (X) =80 000x1+5 672 560 (0.648x2+

0.432x3+0.36x4+0.4x5) 。

$\text{s}.\text{t}.\{\begin{array}{l}x{}_1\ge 0‚x{}_1\le 22\\ x{}_2\ge 200‚x{}_2\le 320\\ x{}_3\ge 512‚x{}_3\le 768\\ x{}_4\ge 800‚x{}_4\le 896\\ x{}_5\ge 1920‚x{}_5\le 2560\\ 500x{}_1+30x{}_2/6+20x{}_3/6+10x{}_4/4+6x{}_5/5\le 25000\\ 0.45x{}_1+4x{}_2/6+4x{}_3/6+2.5x{}_4/4+1.2x{}_5/2\le 2600\\ x{}_2+x{}_3+x{}_4+x{}_5\approx 4000\end{array}$

。

运用单纯形法程序解得:

maxF=9 282 895 770;

L1=21, L2=320, L3=760, L4=808, L5=2 024。

5结语

本文试探性地用城市高峰小时客运周转量将道路和城市轨道交通结合, 并在此思想上建立了线性规划的模型, 希望能够达到合理分配各种类型交通线路长度的目的。如果将本文模型的约束条件考虑得更复杂、更全面, 则更可以显出本方法的优越性。

参考文献

[1]沈建武, 吴瑞麟.城市交通分析与道路设计[M].武汉:武汉测绘科技大学出版社, 1996.

[2]陈光辉.城市道路网现状的模糊评价[J].中南公路工程, 2001 (4) :34-35.

[3]王炜.城市交通规划[M].南京:东南大学出版社, 1999.

[4]邵正宇, 郑安文.城市道路网通行能力最大的道路类型优化分配[J].中南公路工程, 2004 (4) :19-21.

西直门交通枢纽的行人流分配研究 篇6

西直门地铁站是北京地铁交通中的重要换乘站。西直门车站客流量巨大, 换乘较为繁琐, 同时也是整个北京交通命脉的关键节点之一。现在西直门地铁站由2号线, 4号线和13号线组成。并且彼此之间都可以换乘, 其中13号线和2号线与四号线2条线路的换乘距离很长, 2号线和4号线换乘距离较近。2号线和4号线为地下车站, 而13号线为高架车站。

2 对早高峰每条线路的人流量分析

我们将西直门划分为33个站点进行人流量统计, 其中1-14站点是13号线的统计点, 28、26、24为B、C、D三个站口的统计点, 13号线往2、4号线方向的衔接点为16、18、19、20、30站点, 13号线换乘2号线为22站点, 13号线换乘4号线为21站点, 2号线两端为25、29站点, 4号线两端为23、27站点。

2.1 对13号线早高峰人流量分析

2.1.1 分析1-6号站点、9-10号站点的数据, 其结果如下

(1) 7∶30—8∶30人流量高, 这是早高峰人流最集中的时段, 7∶00—7∶30人流量开始上升, 8∶30以后人流量呈曲折下降, 人流量集中于200—300人次之间; (2) 13号线下车乘客经1号口的人流有两个流向, 往7号出站和往12号口换乘2/4号线, 人流整体上大部分去往换乘, 高于出站人流量一倍之多。

2.1.2 对13号线人流分配是否拥挤的分析总结

地铁13号线现有车辆:北京地铁DKZ5型和DKZ6型。其中DKZ5型共有6节车厢, 第一节和第六节车厢座位数为36, 合计72, 载客数为226人, 其余四节车厢座位数为42人, 合计168个座位, 总计240。DKZ6座位数与载客数同DKZ5, 也为240, 每5分钟内13号线疏散32182/24=1341人, 列车每2分钟来一趟, 5分钟内共有2.5辆, 两边对流, 故有5辆, 可以运输1200人, 因为车上可以站立的人数是座位数的3倍左右, 13号线的车在5分钟内输送1341人不会拥堵。

2.2 对2、4号线早高峰人流量的分析

人流进入2号线的站点有18、19、20、22、24、25、26、28、29、30、33, 其中24、26、28为BCD进站口的标记。高峰段的一小时内, 人流总量为70394人。两个方向各来了29趟列车, 列车频率相同, 假设两边疏散的人流相同, 对这58趟列车作平均值计算。说明, “缓冲”在通道里的人流和2号线离开的人流, 合计70394人。

“缓冲”在正八边形通道里的平均步行速度为1.135m/s, 早高峰乘客行走密度一般取2.2人/m2。单向行走时楼梯通过能力一般取70人/min (下行) 、63人/min (上行) 及53人/min (混行) 计算。通道通行能力则按照每米88人/min (单向) 、70人/min (双向) 计算。即1min内, 在长262.5m、宽3.6m的空间内, 每分钟平均缓冲人流量262.5*3.6*2.2=2079人。

同理可得, BCD口和13号往2号线方向1小时内平均缓冲人数为2486人, 三个入口合计为7458人。即在7:30~8:30, 2号线两个方向的58趟列车需要疏散旅客70394- (2079+7458) =60857人。此外, 还有缓冲在2号线换乘大厅的人数乘以0.75予以调整为60857*0.75/58=787人, 2号线每趟列车有256个座位, 因此, 我们推测这样的列车分流有很大压力。

非拥挤数据是拥挤数据的1/2, 得到非高峰时段一辆车要疏散人流787*1/2=393人。再假设列车到站时256个座位已坐满, 根据分析13号线时的思路, 得到可以站立的人数为256*2=512>393。说明非高峰时段, 2号线的换乘通道和列车安排是可行的。

对4号线客流的分析与2号线一样, 4号线的运载压力远远小于2号线, 15959105591所以, 4号线在早高峰时并不存在疏散乘客的压力。

3 结论

上述对西直门13、2、4号线三条地铁线的数据分析论证可知, 在早高峰时段, 疏散乘客有压力的是2号线。同时, 早高峰的黄金时段是7∶30-8∶30, 了解这一信息后, 对于车站根据时间安排管理出行具有指导性意义。最后, 地铁站内在标识、闸机布置等细节服务方面还有很大的改善空间。

摘要：地铁西直门站是地铁2号线、4号线和13号线的换乘车站, 是北京最繁忙的地铁枢纽站点之一, 如何安全疏散客流, 减轻换乘压力以及提高换乘效率, 成为西直门交通枢纽研究的重点和难点。为此, 研究将西直门站划分了33个站点, 采集早高峰的人流数据并分析论证西直门交通存在的压力和问题。

关键词：地铁西直门,早晚高峰,33个站点,交通压力

参考文献

[1]张蓁.城市轨道交通转换点内部换乘和外部衔接[D].上海:同济大学建筑与城市规划学院, 2007.

[2]于海霞.北京地铁西直门车站换乘方案研究[D].北京:北京交通大学, 2009.

交通分配 篇7

1.1路网分层划分方法

在传统的分配方法中,路网不需要分层。人们常常通过道路的属性(设计车速、通行能力)来区分不同功能的道路。路网分层划分方法存在2个缺点:①没有考虑出行者的心理,出行者一般依据自己对道路的直观感受来选择路径,而不会去精确比较;②把不同的道路放在一起分配会增加运算成本,使分配算法的时间复杂度增加。在基于道路功能的分配方法中,道路网必须按照道路功能分层次建立,因为这更符合实际。一般来说,组团间出行会选择城市的快速路;组团内部出行往往会选择城市的主干道;而更小范围内的出行会选择次干路、支路。按道路功能分层分配的目的就是宏观把握各组团、大区之间的出行规律,保证干线道路分配精度,提高支线道路分配数据的精度。所以路网模型建立的第1步为对组团间出行的快速路建模,图1为路网分层模型建立的示意图。

1.2小区分层划分方法

在传统的交通预测方法中,首先就需要进行小区的划分,因为之后的四阶段全部依赖于此[1]。在基于道路功能分层预测方法中,小区划分要根据不同层次的路网来进行。例如,快速路路网将城市划分为不同组团,那么这些组团就是这个层次的小区。因为这一层的交通分配要围绕这些组团进行,目的是得到组团间出行在快速路网上的分配数据。接着将每个组团内部通过主干道划分成若干小区,然后再将每个小区通过次干路和支路划分成更细的小区,等等。

2 分层交通分配方法

2.1分层交通分配的意义

分层交通分配的意义在于它利用宏观层面上的约束条件干预交通分配,使之更符合实际。 居民出行选择路径具有强烈的层次性,不同层次的路网承担的功能不同。快速路和支路就不应采用同一算法在同一个层面上进行分配, 尽管可以设置参数,如路阻、容量来区分。出行者会根据自己的出行目的和道路的功能来大致决定自己的出行路径, 而不会精确地计算它们的差别,然后再选择路径。这样的考虑更符合人们的心理。

分层交通分配的意义还在于它的工程性。分层可以降低搜索最短路径的复杂度,层数越多,运算速度越快,宏观把握得越好。 交通分配的时间复杂度的主要组成部分是多路径最短路径的搜索复杂度。 常用的最短路径搜索算法(非数值算法)主要有Floyd-Warshall算法、Johnson算法和Dijkstra算法。它们计算阻抗矩阵的复杂度分别为O(V3)、O(VElogV) 和O(V0·V2)。 其中:V、E分别为顶点数(vertex)和边数(edge);V0为小区数。通过分层,其复杂度可降为${\rm O}((\frac{V}{mn}){}^3\cdot mn)$、${\rm O}(\frac{V}{mn}\cdot \frac{E}{mn}\log \frac{V}{mn}\cdot mn)$和${\rm O}(n\cdot (\frac{V}{mn}){}^2)$。其中: m为层数;n为每层的所含小区数的平均值。

2.2数据准备

在每一层交通分配之前,需要计算该层各小区之间的交通需求分布。每层的交通分布规律不尽相同,例如城市大区组团间的公交出行比例要大于组团内部,而步行的出行比例要远远低于组团内部;同一层的交通分布规律也各不相同,例如工业区和住宅区之间的交通量就要比住宅区和住宅区之间的交通量大。通过道路功能的分层需求预测,可以宏观地把握各区之间的出行规律,道路功能的分层需求预测比单一的重力模型预测准确。

通过道路功能的分层需求预测中小区划分的大小直接决定该层的人均出行次数,因为每个层次的人均出行次数有不同的含义。

每个层次的需求预测都要考虑内部、对外、过境出行需求。把周边道路的出口设置为外部小区,就是该区的对外出行需求。考虑涉外出行需求的原因是该层的涉外需求并不一定完全能由上一层的内部需求来体现。例如,组团间出行大多数人会考虑选择快速路,但是并非每个人都如此,还有少数人会选择距离更短的主干道。

2.3分配算法

基于道路功能的分配算法应该采用多路径增量算法。该算法的基本思路是在STOCH算法的基础上放松对“合理路径”的定义,因为不合理路径在实际中并非真正的不可能,只是因为工程上的数据缺失或者路网建模导致的。如果忽略了这些路段流量,分配结果可能会失真。

在多路径算法上进行增量分配,动态地考虑路阻,可以在道路接近拥堵的情况下消弱Logit模型的弱点[2,3]。

该算法步骤为

第1步 获取最短路径矩阵。

采用Johnson算法,以长度或时间或广义费用权重,得到每个路段节点之间的最短路径矩阵。这里的路段节点包括交叉口、小区形心。

传统的分配方法,如用户平衡(user equilibrium, UE)的启发式分配方法需要用Dijkstra算法在每一个OD对之间搜索最短路, 时间复杂度为O(V${}_0^3$),由于小区形心在所有节点中占的比例较小,约为1/10,所以该算法的速度很快; STOCH分配方法需要在每个OD对之间搜索所有节点到形心节点的最短路,时间复杂度为O(V0·V2)。 而该算法通过Johnson算法搜索所有节点之间的最短路, Johnson算法在计算稀疏矩阵(如交通网络)时速度要优于Floyd-Warshall算法, 时间复杂度为O(VElogV)[4]。

第2步 将交通需求分配到路段上。

1)依次以每个OD对为研究对象,以起点到这些节点的长度与这些节点到终点的最短路径之和为权重[5,6]。 如图2所示,起点到节点①、②、③的长度分别为3、5、6, 节点①、②、③到终点的最短路径长度为28、22、24, 则这3条路径的权重就分别为31,27,30。

2)路径的权重单位化。

$W{}_i=\frac{w{}_i}{{\displaystyle \sum w}{}_i/n}$

式中:wi为单位化前的权重;Wi为单位化后的权重;n为路径个数。

3)将交通需求按每条路径的权重分配到路段上,并将交通需求向后传递。

$f{}_i=x{}_{rs}\frac{\text{e}{}^{\theta W{}_i}}{{\displaystyle \sum _j^n\text{e}}{}^{\theta W{}_i}}$

式中:xrs为起点r至终点s的部分OD量;fi为第i条路段分配流量;n为路径个数;θ为调整系数,它取决于权重的单位。

如图2,设起点到终点的交通需求为100 pcu/h,而节点①、②、③ 到终点没有交通需求,路段上均未分配交通量。则经过这一轮分配,起点到①、②、③的路段上分别分配了35、31、34 pcu/h的交通量,起点到终点100 pcu/h的交通需求也转化为①、②、③到终点的35、31、34 pcu/h的交通需求。 如果该段分配的交通量小于1 pcu/h或者交通需求的起点等于终点时,停止转化这条路上的交通需求。重复这一过程直到所有路段上的交通需求都为零。

第3步 根据当前的路段流量可以得到新的路阻,将更新的路阻作为权重返回第1步,直到增量加载完毕。增量的比例可以取50%、30%、10%、10%。 其中,按照美国公路局模型,路段流量与行驶时间的关系如下:

$t=t{}_0[1+\alpha (V/C){}^{\beta }]$

式中:t为路段行驶时间;t0为交通量为零时路段行驶时间;V为路段机动车交通量;C为路段实用通行能力;α,β为参数,建议取α=0.15,β=4。

3 应用实例

在城市道路交通建设的各项前期工作中,客流预测是最重要的内容,而道路交通客流预测的难点在于客流分配。本文的算例采用一个虚拟的路网,它由3个级别的路网组成:快速路、主干路、次干路。 使用上述分配模型编制程序,实现交通分配,如图3所示。

1) 按照快速路路网将城市分为若干大区,如图4所示。充分考虑大区间的出行规律,进行交通生成、分布和方式划分预测,得到大区间的机动车OD,如表1所列。

2) 假设已有的交通调查数据,可得经过快速路和经过主干路的大区区间出行比例是1:0.43。计算出通过快速路的机动车出行OD。

3) 在快速路网上进行交通分配,采用多路径增量算法,如图5所示。

4) 同理,在主干路和次干路路网上进行分配,结果如图6,图7所示。

最后将各层的交通量叠加,所得即为道路交通量的分配结果。笔者同时采用TransCAD软件的STOCH分配方法进行了一次分配,结果如图8所示。由于没有分层,没有从宏观到微观干预分配,道路交通量出现了许多极端的情况,有的为零,有的却超饱和。分配结果证明了基于道路功能的分层交通分配是合理、可行的,小区内部的交通量更贴近实际;尤其在基础数据不足时能充分发挥其优势。

4 结 语

基于道路功能的分层交通分配方法以道路功能作为分层的依据,通过分层实现了从宏观到微观的交通分配,分层可以宏观把握、校核,还可以极大地降低时间复杂度,又因此可以采用更多高时间复杂度的算法得到更高的精度和更好的效果,这种方法具有很强的工程意义。

随着计算机技术的发展,人们逐渐将交通分配任务交由软件自动完成。计算机软件的主要任务有:①划分小区;②建立形心连杆;③完成交通分配。笔者已经用python、C++(Boost Graph Library)、Ant、Metapost联合编程实现了交通分配的自动化。

参考文献

[1]Yosef Sheffi.Urban Transportation Networks:E-quilibrium Analysis with Mathematical Program-ming Methods[M],Prentice-Hall.INC,1984

[2]黄海军.城市交通网络平衡分析理论与实践[M].北京:人民交通出版社,1994

[3]李旭宏.道路交通规划[M].南京:东南大学出版社,1997

[4]Chris Godsil G,R,.Algebraic Graph Theory[M].Springer-Verlag,2004

[5]王炜.多路径交通分配模型的改进及节点分配算法[J].东南大学学报,1994,24(6):21-261

交通分配 篇8

关键词：交通分配,容量约束,变分不等式,仿真算法

交通分配可分为均衡分配与随机均衡分配两类,Beckman最早研究了离散网络路段无容量约束的交通分配问题,提出了满足Wardrop用户均衡的分配模型,Frank-Wolfe算法是求解这个模型的最有效方法。但这个模型常使很多路段的流量异常高,这不符合实际情形,当对每条路段加一个容量约束时,又会导致Frank-Wolfe算法的优势丧失。许多学者采用内罚函数法、外罚函数法或广义拉格朗日乘子法将路段容量约束问题转化为一系列无容量约束子问题[1,2,3],通过对惩罚因子的不断调节,反复采用Frank-Wolfe算法求解,由于Frank-Wolfe算法收敛速度慢,妨碍了容量约束模型在大型路网上的应用。随后Dagazno和Sheffi给出了随机用户均衡(SUE)概念[4],此后许多学者对随机用户均衡问题也进行了深入研究[5,6,7,8],在随机均衡交通分配模型中,Logit分配模型是最重要的模型之一,但该分配模型需要首先对各O-D对之间的所有路径进行枚举,这同样导致了其在复杂大型路网上应用的困难。文献[9]提出一种拟Frank-Wolfe迭代算法,提高了分配效率。以上算法主要针对离散网络,而对于非对称网络中的交通分配问题,对应算法却比较少见[8]。

首先通过图表分析了实际路段行驶时间与无路段容量约束的函数近似行驶时间的差异,指出后者低估了实际路段行驶时间,从而可以通过不断校正排队延误因子和误差因子来模拟实际路段行驶时间。基于仿真思想,对非对称网络,提出了一种带路段容易约束的用户均衡交通分配仿真算法,它基于O-D对间最短路的动态生成,不需要路径枚举,在每轮迭代中,将按全有全无方法进行流量分配,并与前一轮迭代所得到的流量进行加权得到新一轮的路径流量,而各O-D对的加权系数则依据Logit模型来确定,通过不断自适应调节排队延误因子和误差因子,使路段流量逐步低于路段容量,最终达到广义用户均衡。一方面该算法不需要在每轮迭代中求解无约束交通分配模型,另一方面,它又避免了随机均衡分配法在各O-D对之间进行路径枚举。随后证明了算法的收敛性。通过一个交通分配问题算例,说明了算法的可行性。

1容量约束交通均衡分配问题

给定一个交通网络G=(N,A),N为节点集,A为路段集,R为起点集,S为终点集,R与S可以有公共元素;网络中共有|A|条路段;(r,s)是以r为起点,s为终点的O-D对;Prs为O-D对(r,s)间所有路径集合。容量约束交通均衡问题考虑了路段的容量,使该问题更加符合实际路网情形,在非对称网络,容量约束交通均衡模型具有如下变分不等式形式:

t(x*)T(x-x*)≥0; ∀x∈Ω (1)

式(1)中:

式(2)中:x*为均衡路段流量解;f${}_p^{rs}$是O-D对(r,s)间路径p上的流量,组成的向量为f=(…,f,…)T;xa为路段a的流量,组成的向量为x=(…,xa,…)T;ta(x)为路段a的行驶时间函数,t(x)=(…,ta(x),…)T为路段行驶时间函数向量,假定是严格单调可微且雅克比矩阵∇t(x)是严格对角占优的;Ca为路段a的容量,C=(…,Ca,…)T;qrs是O-D对(r,s)间的需求量;如果O-D对(r,s)间路径p经过路段a则δ=1,否则为0。上述模型式(1)—式(2)当可行域Ω非空(Ω≠∅)时,具有唯一路段流量解[10]。

模型式(1)—式(2)的均衡条件为:

$\{\begin{array}{l}{\displaystyle \sum _{a\in A}\tilde{t}}{}_a(x{}^{*})\delta {}_{ap}^{rs}-u{}_{rs})f{}_p^{rs}{}^{*}=0,\\ {\displaystyle \sum _{a\in A}\tilde{t}}{}_a(x{}^{*})\delta {}_{ap}^{rs}-u{}_{rs}\ge 0,f{}_p^{rs}{}^{*}\ge 0\\ d{}_a(x{}_a^{*}-C{}_a)=0；x{}_a^{*}\le C{}_a,d{}_a\ge 0\end{array}(3)$

式(3)中:$\tilde{t}{}_a(x)=t{}_a(x)+d{}_a$称为广义路段行驶时间,Lagrange乘子urs,da分别代表O-D对(r,s)间的最小行驶时间与路段a的排队延误时间,因此上述条件经常称为广义用户均衡条件。由于在拥挤网络中,da并不是可以忽略的[10],如图1(a)所示,在容量Ca附近时间函数近似曲线与实际时间曲线误差较大;从图1(b)可以看出,在无路段容量约束模型中,由于t(x)是严格对角占优的,当xa>Ca时,实际延误da要高于函数近似延误d′a,其误差因子Δda=da-d′a>0,因此仅用t(x)并不能模拟路段的实际行驶时间。需要注意的是,虽然在实际路网均衡条件下,排队延误是唯一的,但Lagrange乘子da并不唯一。

2路段容量约束用户均衡交通分配仿真算法

模型式(1)—式(2)是一个约束变分不等式问题,因具有容量约束,相应算法比较少见,因此现设计仿真算法来求解该模型。

2.1算法的迭代步骤

STEP0:输入O-D表及网络信息;设O-D对个数为N,令i表示第i 个O-D对;置各路段初始流量为0,置迭代次数k=1,第i个O-D对最短路径集Ai=∅;取允许误差ε>0,在0流下求各O-D对最短路p,(i=1,2,…,N),按全有全无分配各O-D对流量并计算路段行驶时间tk,令,随机产生Δd>0,∀a∈A;将产生的最短路归入各O-D对的最短路径集A(i=1,2,…,N)中,置mpki=1。

STEP1:确定各路段行驶时间t${}_a^{k+1}$=t${}_a^k$+d${}_a^k$,计算各个O-D对最短路p${}_i^{k+1}$,(i=1,2,…,N)。如果p∉Ai,置Ai:=Ai∪p${}_i^{k+1}$,路径p的出现次数mpk+1i=1;否则Ai中路径不发生变化,置mpk+1i=mpki+1。将每个O-D对的需求量按全有全无分配法全部分配到这批新产生的路径上,记所得到的各路径上的流量向量为。按一定规则选取流量加权组合系数α(0≤α≤1),对第i个O-D对,在其最短路径集Ai中分配流量为:。

STEP2:计算输出路段流量xk+1及路行驶时间t${}_a^{k+1}$,如果$\underset{a\in A}{{\displaystyle \max }}|x{}_a^{k+1}-x{}_a^k|+\underset{a\in A}{{\displaystyle \max }}\{0,x{}_a^{k+1}-C{}_a\}\le \epsilon$,停止;否则转STEP3。

STEP3:令延误因子:

;误差因子:,置k:=k+1,转STEP1。

2.2α${}_i^k$的选取方法

由于现实路网中各个O-D对的路径集和交通需求都存在一定差异,不同于Frank-Wolfe算法中各O-D对共用一个加权系数,本算法在迭代过程中各O-D对可选取不同的加权系数。选取方式如下:

计算第k次迭代时新产生的路径p${}_i^k$的初始行驶时间tpki及A${}_i^k$中各条路径的初始行驶时间,取:

$\alpha {}_i^k=\max \left\{\frac{\exp (-\theta t{}_{p{}_i^k})}{{\displaystyle \sum _{q{}_i\in A{}_i^k}m}{}_{q{}_i}\exp (-\theta t{}_{q{}_i})},\zeta {}_i\right\}(4)$

式(4)中,θ>0为Logit模型中的分布参数;A为第k次迭代后,已经求出的第i个O-D对的最短路集合;tqi是路径qi的初始行驶时间;mqi表示到目前为止,路径qi作为最短路而被重复选中的次数。式(4)中ζi是一个与算法迭代误差ε有关的充分小的正数,其作用是既要保证算法能够收敛,又要使每一步迭代路径流量都有适当的调整。

2.3算法的收敛性

定理:当Ω≠∅且qi<∞(i=1,2,…,N)时,则对任意给定的迭代误差ε>0,适当选取ζi(i=1,2,…,N),上述迭代算法是有限终止的。

证明:由于路网中只有有限条路段,要证明上述定理,只需证明对路网中任意一条路段a,有

$|x{}_a^k-x{}_a^{k-1}|\le \frac{\epsilon }{2},\max \left\{0,x{}_a^k-C{}_a\right\}\le \frac{\epsilon }{2},k\to \infty$即可。

先证。

考察第i个O-D对,取:

及

其中P为各O-D对所有可能路径的集合。 有:

$\frac{\exp (-\theta t{}_{p{}_i^k})}{{\displaystyle \sum _{q{}_i\in A{}_i}m}{}_{q{}_i}\exp (-\theta t{}_{q{}_i})}\le \frac{{\rm M}{}_i^k}{{\displaystyle \sum _{q{}_i\in A{}_i}m}{}_{q{}_i}m{}_i^k}=\frac{{\rm M}{}_i^k}{m{}_i^k}\frac{1}{k}\le \frac{{\rm M}}{m}\frac{1}{k}\to 0,k\to \infty 。$可以看出,若取$\zeta {}_i=\frac{\epsilon }{2{\rm N}|A{}_i|q{}_i}$,那么当k充分大时,总有α${}_i^k$=ζi,因此对A${}_i^{}$中任一条路径pi,由

知$|f{}_{p{}_i}^k-f{}_{p{}_i}^{k-1}|=|\alpha {}_i^k||\tilde{f}{}_{p{}_i}^k-f{}_{p{}_i}^{k-1}|\le q{}_i\alpha {}_i^k=q{}_i\zeta {}_i,k\to \infty 。$

其中:qi第i个O-D对的交通需求量。 由于交通网络中每个O-D对路径是有限的,即当k→∞时Ai中路径不再产生变化,从而对路网中任意一条路段a,其路段流量为$x{}_a^k={\displaystyle \sum _{i=1,2,\cdots {\rm N}}{\displaystyle \sum _{p\in A{}_i}\delta }}{}_{ap}f{}_p^k$,即有

$\begin{array}{l}|x{}_a^k-x{}_a^{k-1}|\le {\displaystyle \sum _{i=1,2,\cdots {\rm N}}{\displaystyle \sum _{p\in A{}_i}\delta }}{}_{ap}|f{}_p^k-f{}_p^{k-1}|\le \\ {\displaystyle \sum _{i=1,2,\cdots {\rm N}}|}A{}_i|q{}_i\zeta {}_i\le \frac{\epsilon }{2};k\to \infty 。\end{array}$

再证。

$\begin{array}{l}f{}_p^k=\alpha {}_i^k\tilde{f}{}_p{}^k+(1-\alpha {}_i^k)f{}_p{}^{k-1}=(1-\alpha {}_i^k)f{}_p{}^{k-1}=\\ (1-\zeta {}_i)f{}_p{}^{k-1}\to 0,k\to \infty 。\end{array}$

既有$x{}_a^k={\displaystyle \sum _{p\in {\rm P}}\delta }{}_{ap}f{}_p^k\to 0‚k\to \infty$。与$x{}_a^k-C{}_a>\frac{\epsilon }{2}>0$, 矛盾。

本算法是通过最短路算法来产生新路径,且总是在最短路上进行流量分配,而一些较差路径不能被选择或分配交通流量,这符合用户均衡交通分配的原则。随着迭代次数的增加,算法将不会产生新路径,并且通过流量的不断调节,最终达到广义的用户均衡。在STEP1与STEP3中,路段行驶时间采用仿真形式得到,因此该算法为仿真算法。 在STEP3中,误差因子更新方式和Lagrange乘子更新方式相似,但算法不需要在每次迭代中进行无约束交通分配运算,并且每次迭代都更新已产生的所有路径流量,更重要的是算法可以求解非对称网络。由于算法虽然不能直接得到准确延误因子,但却是非对称网络交通分配的快速算法。由均衡条件式(3)可知延误因子可在多面体式(5)中得到。

$\{\begin{array}{cc}f{}_p^{rs}{}^{*}{\displaystyle \sum _{a\in A}t}{}_a(x{}^{*})\delta {}_{ap}^{rs}+f{}_p^{rs}{}^{*}{\displaystyle \sum _{a\in A}d}{}_a\delta {}_{ap}^{rs}=\hfill & \hfill \\ u{}_{rs}f{}_p^{rs}{}^{*},\hfill & \forall r,s,p\hfill \\ {\displaystyle \sum _{a\in A}t}{}_a(x{}^{*})\delta {}_{ap}^{rs}+{\displaystyle \sum _{a\in A}d}{}_a\delta {}_{ap}^{rs}\ge u{}_{rs},\hfill & \forall r,s,p\hfill \\ d{}_a(x{}_a^{*}-C{}_a)=0,\hfill & \forall a\hfill \\ d{}_a\ge 0,\hfill & \forall a\hfill \end{array}(5)$

虽然多面体式(5)中只含有一组变量da,∀a,但da并不唯一,这与Lagrange乘子的不唯一性是一致的。

3计算实例

下面通过一个实例来检验本文提出的分配算法,采用文献[12]的初始数据和道路交通网络:

在如图2所示的网络中有4个O-D对:1-12、 9-4、12-1、4-9,O-D需求量分别为q1,12=460、q9,4=400、q12,1=440、q4,9=420,网络共有34条路段; 路段旁数字表示路段流量为0时的行驶时间, 设每条路段的容量均为300,采用非对称路段行驶时间函数:$t{}_a(x)=t{}_a(0)\left[1+0.5\left(\frac{x{}_a+0.2x{}_{\widehat{a}}}{1.2C{}_a}\right){}^4\right]$。 Ca为路段a的容量,$x{}_{\widehat{a}}$为路段a的反向路段$\widehat{a}$的流量。

x${}_a^C$表示算法所得到的路段流量, 表1给出了相应的分配结果(取ε=1, 保留小数点后两位)。

从表1可以发现,算法所得的结果中,最高路段流量仅为300.06,是允许范围内的误差,意味着该路段达到饱和。图3给出了算法的收敛曲线,可以看出本算法收敛的速度非常快;

图4、图5分别给出了路段(3,2)与路段(7,6)在算法迭代过程中流量的变化趋势,在100次迭代以后趋于稳定。

4结论

对非对称网络,提出了一种带路段容量约束的用户均衡交通分配仿真迭代算法,通过不断修正排队延误因子和误差因子来模拟实际路段行驶时间,再利用最短路算法产生有效路径,在当前迭代过程中,将全有全无分配法得到的各路径流量与上一轮迭代后各路径分配流量进行加权组合,得到新的路径分配流量,各O-D对加权组合系数通过Logit模型得到,随后给出了算法的基本思想与迭代步骤,并证明了算法的收敛性。计算实例还显示:该算法所得分配结果在误差范围内均不超过路段容量,收敛速度非常快,各路段流量在有限次迭代后便趋于稳定。由于分配流量的路径均是各O-D当前迭代下的最优路径,而未被选中的路径(相对较差的路径)不分配流量,这恰好符合用户均衡交通分

配原则,因此算法收敛时可达到广义用户均衡。本算法不需要路径枚举,而比求解容量约束下均衡交通分配模型计算量又小得多。因而它是一个有效的容量约束交通分配算法,适合在非对称道路交通网络中应用。

参考文献

[1] Larsson T,Patriksson M.An augmented lagrangian dual algorithm forlink capacity side constrained traffic assignment problems.Transpor-tation Research,1995;29:433—455

[2] Nie Y,Zhang H M.Models and algorithms for the traffic assignmentProblem with link capacity constraints.Transportation Research,2004;38:285—312

[3] Xu Y D,Li S J,Teo K L.Vector network equilibrium problems withcapacity constraints of arcs.Transportation Research Part E,2012;48:567—577

[4] Sheffi Y.Urban transportation networks:Equilibrium analysis withmathematical program methods.New Jersey,Prentice-Hall,INC,En-glewood Cliffs,1985

[5] Chiou Suh-wen.A novel algorithm for area traffic capacity control withelastic travel demands.Applied Mathematical Model,2011;35:650—666

[6] Meng Qiang,Khoo Hooiling.A computational model for the probit-based dynamic stochastic user optimal traffic assignment problem.JAdv Transp,2012;46:80—94

[7] Szeto W Y,Solayappan M,Yu Jiang.Reliability-Based transit as-signment for congested stochastic transit networks.Computer-AidedCivil and Infrastructure Engineering,2011;26:311—326

[8] D’Acierno L,Gallo M,Montella B.An ant colony optimisation algo-rithm for solving the asymmetric traffic assignment problem.EuropeanJournal of Operational Research,2012;217:459—469

[9]黄崇超,刘炳全.非平衡交通分配的Frank-Wolfe迭代算法.数学的实践与认识,2009;39(8):19—26

交通分配 篇9

传统的交通规划所采用的模型主要是20世纪50年代起源于美国的“四阶段”模型。基于出行的“四阶段”模型把出行分成发生、分布、方式选择以及交通分配四个步骤,然后以交通小区为单位,用集计数据进行模拟。“四阶段”模型在以交通基础设施建设为主的城市交通规划中发挥了重要的作用。然而,随着交通需求管理政策的日益广泛应用,“四阶段”模型暴露出明显的不足。针对“四阶段”方法的局限性,交通研究人员提出了基于活动的方法,该方法认为居民一天出行的需求源于居民一天的各种活动所构成的出行链[1]。相对于基于出行的“四阶段”法,基于活动的方法具有如下优点[2]:(1)考虑了时间维因素,活动和出行决策都是动态的;(2)以活动和出行模式为研究对象而不是以单个出行为研究对象;(3)考虑各种活动-出行之间的相互联系,一次决策受过去和预期事件的影响;(4)考虑了时空约束对活动和出行的影响。

近二十年,基于活动的出行行为建模方法在国内外已做了大量的分析研究。如荷兰开发了基于往返行程的系统[3],Ben-Akiva和Bowman开发了日活动计划系统[4],Gliebe和Koppelman开发了基于效用的日时间比例参与模型[5],另外,比较典型的还有基于活动的仿真系统STARCHILD[6]、基于规则的多代理系统Albatross[7]、基于微观仿真的综合计量系统CEMDAP[8]。然而,这些研究在进行交通分配时大多忽视了出行链行为,而认为出行链中的每次出行是独立的。William等[9]提出了一个基于活动的时间相关的交通分配模型,然而该模型中路径选择行为并没有考虑到预先确定的相关活动,另外,求解算法烦琐,计算量大,不适用于实际交通网络。Maruyama等[10,11]提出了一个基于出行链的静态模型,该模型假设用户对路网信息有完全的了解,用户不能改变路径来减少整个出行链上的成本,但忽略了停驻点及停驻时间的影响。Abdelghany[12]等提出了一个基于活动/出行的仿真分配模型,模型仿真出行者如何选择路径以最小化他们的总出行成本,该模型假设出行者对路网信息有完全的了解,然而现实中,出行者对路段的出行成本只能是估计,而且不同出行者的估计值也会不同,因此本文放松出行者对整个出行链路径信息完全了解的假设,提出了一个基于出行链的随机动态交通分配模型。出行链模式由出发地点、出发时间、中间停驻点、停驻时间、目的地定义,定义的出行链输入到模型中,模型选择路径以最小化出行者整个出行链上的感知成本。针对所提出的模型,结合时间相关的K最短路算法和连续平均法,设计了一个基于仿真的迭代求解算法,最后通过一个算例验证了模型和算法的有效性。

1基于出行链的动态随机用户均衡

传统的基于出行的四阶段模型在进行交通分配时常采用用户均衡的假设,即在静态条件下用户对路网信息有完全的了解,当用户不能改变自己的出行路径而减少其出行成本时达到用户均衡状态。后来,学者放松了出行者对路网信息完全了解的假设,提出了随机用户均衡,即当达到均衡时,出行者不能通过改变自己的路径来减少他们感知的出行成本。静态模型(确定性和随机性)适用于长期的规划分析,但由于它不能描述网络中的拥挤情况,认为整个规划时期路段交通流量和OD需求是常量,显然这和实际交通情况是不相符的。如果时变的OD需求是已知的,就可以分析各个时间段的路网状况,这就导致了时间相关的用户均衡问题[12]:即在任何出发时间间隔,没有出行者能通过改变出行路径来减少他们所感知的成本。

为避免基于出行的四阶段模型的缺点,越来越多的交通规划人员开始采用基于活动的模型进行交通需求分析与预测。活动链可以描述一个人一段时间内不同活动的顺序,也可以反映一个人在空间上的活动规律。为满足相应的活动所经过的路径常称为基于出行链的路径,如图1所示,假设一个人的一天的活动顺序为:家-单位-商店-家。设p为2个连续停驻点之间的一条路径,该出行链对应的路径为:p1→p2→p4;p1→p2→p5;p1→p3→p4;p1→p3→p5。

扩展基于出行的用户均衡到出行链的情况下,可得到基于出行链的时间相关的随机动态用户均衡:即在任何出发时间间隔,没有出行者能通过改变出行路径来减少他们所感知的整个出行链上的成本。

2 模型系统结构

研究动态交通分配通常有两类方法:解析法和仿真法。解析法有严格的数学定义,对动态交通分配有很精确的描述,可以研究解的存在性、唯一性、稳定性。但由于交通系统动态性能的复杂性,对其进行精确的建模很难求解。采用仿真方法能克服解析模型的缺点,再现交通流在交通网络中运行的复杂动态特性。因此,采用仿真的方法求解基于出行链的动态随机交通分配问题。求解基于出行链的动态随机交通分配问题,本质上是求解每个发车间隔分配到各条路径的交通量,所选择的路径能满足出行者完成其相应的活动。模型系统主要分三个模块:(1)交通/活动仿真模型;(2)出行者行为模块;(3)路径处理及交通分配模块。交通/活动仿真模型用于再现交通流在交通网络中运行的动态特征,描述交通流传播及时间-空间互动关系,评价交通网络相关特性;出行者行为模块在一个效用最大化框架下,描述出行者的路径选择决策;路径处理模块用于求解符合条件的路径选择集合。

2.1 交通/活动仿真模型

根据对交通系统描述细节的程度,交通仿真模型可以分为宏观、中观、微观三种。中观交通仿真模型适用于面向交通诱导系统的仿真开发与研究,实现在较大范围内模拟各种属性的特定车辆在路网中运行的状况,所以本文采用中观交通仿真模型。

交通仿真模块主要包括路段车辆行驶模块和交叉口处车辆行驶模块。在路段上,位置相近、交通流特性相似的车辆组成一个交通单位。计算交通单元内部的车辆速度时首先计算头车和尾车的速度,然后排列在中间的车辆分别根据其与头车尾车的位置采用线性加载的计算方法来计算各自的速度。

交通单元头车速度采用单元跟进计算公式来求得[13,14]:

公式中各参数含义如下所示:uij为向j方向行进的行车单元i的头车的单元跟进速度,即交通流ij头车速度;vj0为领导行车单元的尾车的速度;vmax为路段自由流速;λi=(dij/dupper);dij为头车ij距向方向j行进的领导行车单元尾车的距离;dupper预置极限距离。

交通单元尾车速度采用速度-密度函数来计算得到[13,14]:

$v{}_{i0}=V{}_{\min }+(V{}_{\max }-V{}_{\min })\left(1-\left[\frac{{\rm K}{}_i}{{\rm K}{}_{jam}}\right]{}^{\alpha }\right){}^{\beta }$ (2)

式(2)中各参数含义如下所示:vi0为交通单元尾车的速度;ki为交通单元的交通密度;kjam为路段的阻塞密度;vmax为路段的自由流速;vmin为路段的最小流速;α、β为待标定参数。

在每一个更新阶段中,仿真器依据路网中所有路段的通行能力计算平均车头时距。平均车头时距决定车辆被允许进入路段的时间,如下所示[13,14]:

tn=tn-1+1/Q (3)

式(3)中:tn表示下一辆车进入路段的最早时间;tn-1表示上一辆车进入路段的时间;Q表示交叉口的实际通行能力。

只有当系统的仿真时间大于等于式(3)中决定的tn时,车辆被允许进入此路段;否则,车辆在节点处形成排队。系统会在每一次更新中检查路网中的所有路段所含有的车辆数,如果路段上最后一个交通单元的尾部到达了此路段的边界,车辆也不被允许进入此路段。

当车辆到达中间停驻点时,车辆暂时驶离路网一段时间(等于车辆在中间停驻点的驻停时间),这段时间该车辆对路网中其他车辆不产生影响。当仿真时钟推进到停驻时间完成时,车辆重新驶入路网。

2.2 出行者行为模型

用一个有向图G(N,A)表示交通网络,N为所有节点集合,A为所有路段集合,I为所有出发节点的集合,h为每次出行对应的出行链,H为出行者可选择的出行链集合,h∈H,出行链由一系列中间停驻点表示:Qh={n1,n2,…,ns,…},其中,Qh为出行链h对应停驻点的集合;s为停驻点序号;令τ为出发时间间隔,l为一个出行链对应的一条路径,对于出行链h相应的路径l,C${}_{t,ihl}^{\tau }$为具有出行链h在时刻τ从i出发选择路径l的实际成本,总出行成本为:C${}_{t,ihl}^{\tau }$=∑C${}_{hl,p{}_k}^{\tau }$,Chl,pk为出行链h在时刻τ从i出发选择路径l中路径pk的实际成本。

每个出行方案由出发地点、出发时间、一系列活动停驻点及目的地构成,每次活动对应一个给定的活动持续时间。在该模型里,每个出发时间间隔,出行者选择路径以最小化他们整个出行链上的感知成本。

令C${}_{a,ihl}^{\tau }$为具有出行链h在时刻τ从i出发选择路径l的感知成本。则:

C${}_{a,ihl}^{\tau }$=C${}_{t,ihl}^{\tau }$+(1/θ)ε${}_{ihl}^{\tau }$∀i,j,τ (4)

式(4)中,ε${}_{ihl}^{\tau }$为出行链出行成本相关的误差项,假设Ε(ε${}_{ihl}^{\tau }$)=0或者E(C${}_{a,ihl}^{\tau }$)=σ${}_{ihl}^{\tau }$。换句话说,也就是平均感知成本等于实际的出行成本。θ为一常数,它起到将出行成本转换成效用的作用。

出行者在出发时刻τ选择路径l的概率为:

P${}_{ihl}^{\tau }$=P(C${}_{t,ihl}^{\tau *}$≤C${}_{t,ihl}^{\tau }$,∀l)∀i,j,τ (5)

换句话说,公式(5)表示在出发时刻τ某一路径被选择的概率等于该路径的交通时间被认为是最小值的概率。

根据ε${}_{ihl}^{\tau }$所服从分布的假设不同会产生不同的随机网络配流模型。当假设ε${}_{ihl}^{\tau }$服从正态分布时,可以得到probit模型;当假设ε${}_{ihl}^{\tau }$服从Gumbel分布时,可以得到logit模型。在确定了ε${}_{ihl}^{\tau }$的分布后就可以计算出路径选择的概率,从而可以计算出路径的分配流量:

f${}_{ihl}^{\tau }$=q${}_{ij}^{\tau }$P${}_{ihl}^{\tau }$,∀i,j,τ (6)

式(6)中:

q${}_{ij}^{\tau }$:从i出发具有出行链h的出行者数量;

f${}_{ihl}^{\tau }$:具有出行链h,在τ时刻从节点i出发选择路径l的出行者数量。

2.3 路径处理模块

基于从仿真器得到的路段出行时间,路径处理模块求解路径相关特性(如路径出行时间等)。每个出行链对应多条路径,由于出行者对路径成本感知的不同,他们并不都是选择最优的路径出行,也可能选择非最优的路径出行,因此,这涉及到出行链可选路径集的确定问题。出行链可选路径集的确定分两步,第一步计算两个停驻点之间的最短路径集,第二步组合第一步得到的子路径集从而得到该出行链对应的可选路径集。在进行路径选择时,路径集中每条路径分配给特定的选择概率,路径集之外的路径不被选择。第一步中两个停驻点之间的可选路径集的求解采用K最短路算法,K路算法[15]是在Dijkstra最短路算法的基础上进一步扩展得到的,其优点在于每次的计算都能够得到不止一条的最短路,并且能够根据用户不同需求得到不同的最短路个数。为提高模型计算效率,不是在每个仿真间隔重新计算K最短路路径,而是在预先设定的较长时段进行K最短路的计算。在设定的更新间隔内,K路径的出行时间通过每个仿真间隔的所得到的当前路段时间进行更新。

3 基于仿真的迭代算法

通过一个启发式迭代仿真程序来求解模型,该算法集成了连续平均法(MSA)和基于仿真的随机网络卸载方法。

算法主要步骤如下:

步骤1:初始化:设置迭代计数器n=1。基于初始的路段和节点出行特性,为每个出行方案找到一个初始的可行路径集,分配基于活动的初始需求到一个初始的可行路径集上。相应地,初始解由f${}_{ihl}^{\tau ,0}$表示。

步骤2:在给定路径分配模式下,运行交通/活动仿真器得到路段出行时间等相关信息。

步骤3:根据从仿真器得到的路段出行时间,调用路径处理模块分别计算每个出行方案的前K条最短路径集合。同时计算集合中每条路径的总出行成本。

步骤4:根据上一步计算的最短费用路径集合,计算每个选择肢的效用,基于多项logit模型计算每条路径的选择概率,得到每个分配间隔路段的辅助车辆数y${}_{ihl}^{\tau ,n+1}$。

步骤5:使用连续平均法更新路段流量:

$f{}_{ihl}^{\tau ,n+1}=f{}_{ihl}^{\tau ,n}+\frac{1}{n}(y{}_{ihl}^{\tau ,n}-f{}_{ihl}^{\tau ,n})$。

步骤6:判断f${}_{ihl}^{\tau ,n+1}$与f${}_{ihl}^{\tau ,n}$差值:$\left|f{}_{ihl}^{\tau ,n+1}-f{}_{ihl}^{\tau ,n}\right|\le \epsilon$,满足,停止循环,否则,执行步骤2。

4 数值算例

出行方案由每个出行者的出发时间、出发地点、一系列进行活动的中间停驻点、最终目的地构成。每个活动对应一个活动持续时间。在仿真实验中,对于每个出行者,每个活动持续时间是外生的并预先确定的。

出发节点为1和4,目的地节点为2和3,中间停驻点为6和10。

假设平均发车流率为2 000辆/小时,即平均每小时2 000辆车从节点1出发前往目的地2,有25%的出行者要在节点6处驻停5 min,另75%出行者直接前往目的地2;2 000出行者从节点1出发直接前往目的地3;2 000出行者从节点4前往节点3,25%出行者在节点10驻停5 min,其余75%出行者直接前往目的地3;2 000出行者从节点4直接前往节点2。

传统的基于出行的方法常忽略中间停驻点的行为或者认为出行链中的每次出行是独立的。为和基于出行链的方法对比起见,以出行链方法、传统基于出行的方法分别求出平均出行时间如表1所示。在以基于出行方法求解时,在进行交通分配时忽略中间停驻点的情况,即在进行交通分配时,仅考虑出行链中最终目的地对交通分配解结果的影响。举例说明,如果一个人从家出发,先送孩子去学校,然后前往工作单位,在分配时认为是一个从家到单位的单一出行。

分别以基于出行链方法和基于出行方法求出,平均发车流率为1 000、1 500、2 000、2 500辆/小时出行者的平均出行时间。从表1可以看出,当忽略停驻点仅考虑出行链中的最终目的地时,所求平均出行时间小于实际平均出行时间,这是因为,当忽略出行链中的中间停驻点时,减少了相应的总出行,路段变得更通畅。

5 结语

传统的基于出行的交通分配模型在进行交通分配时忽略了出行链中各出行之间的相互关系。本文提出的基于出行的动态随机交通分配模型考虑了出行链中各出行之间的相互关系,能更好的反映出行者的实际选择行为。基于所开发的仿真器,结合K最短路算法和MSA算法,设计了模型的求解算法,并通过算例比较了传统的基于出行的分配模型忽略停驻点时对分配结果的影响。