基于 Darl 算法的动态交通分配初探 http://www.paper.edu.cn 刘道君 河海大学交通学院，江苏南京（210098） E-mail：anda_paper@163.com 摘 要: 本文提出了一种基于 Darl 算法的交通分配模型，该模型是动态出发时间选择和随 机用户平衡的联合模型。在交通分配的路径选择上,运用了 Darl 算法的“有效路径”搜索原 理来确定路径上所有路段的权重，并根据这些权重求出每条路径的选择概率。最后利用总的 交通出发量和路径选择概率求出每条路径上的驶入量。 关键词：Darl 算法；交通分配；有效路径 0 引言 动态交通分配（DTA）是智能运输系统（ITS）的重要部分，其作用是在给定的交通需 求和条件下实时决定交通模式，主要应用在 2 个方面：①实时交通控制和管理；②离线网络 规划和政策评估。DTA 有两个主要组成部分：出行选择法则和交通流传播。笔者基于 Darl 算法初探一种新的出行选择法则，包括对出发时间和路线的选择。 在 DTA 中，交通阻抗是一项非常重要的指标，在实际应用中，人们感知的道路阻抗只 是对实际阻抗的估计，估计值和实际值之间存在着一个随机变量，相应地存在随机用户平衡 问题，即任何一个道路利用者均不可能通过单方面改变起路径来降低其所估计的行驶时间来 达到随机用户平衡（SUE）。假设所给出的 OD 出行需求总量是固定的，在静态情况下，每 个时间段的出发量是固定值。若每个时间段的出发量不是固定的，而需根据当前的道路情况 来确定每个时间段的出发量，这种情况就是动态出发时间的选择问题（dynamic departure time）。同时考虑动态路径选择（dynamic route choice）和动态出发时间选择的随机用户平衡。 1 Darl算法[1] 思想：搜索（走一步，看一步）确定路径： 出行不是在起点时就决定通过哪条路径，而是从上一个节点选择下一个节点，根据路 段变化选择下一个接点； 选择的路段只从“有效路段”中选择。 注：“有效路径”就是上游节点比下游节点靠近起点，下游节点比上游节点更靠近终点。 Step 1:初始化 计算由起点i 到所有节点的最小阻抗，记 ； )(ir )(is 。 O i = i 计算从所有节点到终点 的最小阻抗，记 s i 设 为离开节点 的路段的另一端点的集合， I iO iI 为进入节点 的路段的另一端点的集合， i i j ),( 计算路段“似然值” ： 对每一条路段 [ { jrb )( exp ⎧ ⎨ 0 ⎩ LLLLLLLLLLLLLLLLL ] } LL j iL ),( j it ),( jr )( ir )( i { o oo , , = 1 L i }yi { i i , 2 1 L i 2 , i i − ir )( − is )( > 其它 且 = 若 < }ix ； ； js )( （1） -1- 

http://www.paper.edu.cn 有效路径 最短路径 无效路径 = ⎧ ⎪ ⎨ ⎪ ⎩ j iL ),( 1,0 ≠> LLLL 1 = LLLLL 0 = LLLLL j it ),( 式中：b 是待定系数， Step 2 向前计算路段的权重 从 r 开始，按 j i ),( i )(ir （2） j i ),( 的实际阻抗。 为路段 上升顺序，依次考虑每个节点，计算离开它的所有路段的权重，对 节点 ，路段 的权重为： j iL ),( LLLLLLLLLL ∑ iL imWj ),( ), LLLLLL ( 若 i i 若 = ≠ r r ∈ IIm iW j ),( = ⎧ ⎪ ⎨ ⎪⎩ 式中： irW ),( j iW ),( irL ),( = 为路段 iW j ),( = j i ),( 的权重， 式，从 作为初始值开始迭代运算，可依次得到所有 （3） ∑ imWj ), ( iL ),( iIm ∈ 是一个循环替代公 j ),( 的值。 iW 2. DDSUE 模型与 Darl 算法的综合研究 该综合研究包括动态出发时间的选择和动态出行路线的选择，以及运用 Darl 算法确定 出有效路段、有效路径，通过路段选择概率的搜寻确定出该路径的交通分配量。具体研究如 下： ① 首先列举出每 OD 对之间所有的有效路径，确定每条路径的通行能力，假设第 条 k 路径包括 个路段，每条路段的通行能力为 （ m iq i ,2,1 L= , m ) 在该条路径上最小的路段通 行能力将决定整条路径的通行能力，因此取其中最小的路段通行能力作为路径的通行能力 [2] Q rs k = { qq min , 1 L , , q }m ,∀ srk , 2 （4） x rs ② 计算每条路径在当前时刻的行程花费。设 aΦ 为每个路段的自由流行程时间； k )(t 为每条路径在t 时刻的总车辆数，则第 条路径在 时刻的行程花费[2]为 k t tC )( rs k +Φ= ∑ a ka ∈ x rs k Q t )( ,∀ srk , k （5） kA k ③ 记 为第 条路径，根据上面的路径行程花费和 Darl 算法计算车辆在t 时刻选择 ji ),( ji ∈),( 路段 的选择概率，其中 ),( rs iCj ,( rs iP ,( tj ), = 。 kA tj ), ,∀ srk , （6） 是路段 ),( ni 所在的路径l 在 时刻的行程 t iW o ix ∑ 1 on = i ni ∈),( tniCniW ), ),( ,( rs rs tniC ,( ), = i i l , ,2,1 L = rs tC )( ix ； lA o ， ix ， -2- 式中：路段 oo , 1 L i jn , = , 2 i , 花费， 

④ 根据上一个节点的下游有效路段的路段选择概率确定出最大的路段选择概率。 P { }), tniP max （7） srk , tj ),( ,∀ ,( = rs rs http://www.paper.edu.cn 选择下一个节点作为下一步寻找路径的其始点，直到找出一条 { r ),1,( t ),1( ， 每 条 路 段 对 应 的 选 择 概 率 为 ： tsP rs ),( k }), sw i ,(, (, ), j k = P rs k r → 的路径 ， k s 。 tj ),( P rs 、、 L k }),( tsP rs k 、、 L ,∀ srk , （8） L L tj P rs ),( 、、 L k { tP P rs rs )( max k k = 、、 L t ),1( )(tP rs k 式中： t 是 时刻路径 的路径选择概率。 k ⑤ 利用确定的路径 求得出发交通量 k f rs k t )( = tQ rs ∆ k tP rs )( k ,∀ srk , （9） s srk , ,∀ （10） rs = { max 则t 时间段中，OD 点对从 r 到 的交通出发量为 tF )( OD 点对从 r 到 的第 条路径的驶入量[3]为 e rs k })( t k tPtF )( f rs k s srk , ,∀ t )( )( rs k = rs （11） ⑥ 式（11）为最后的分配结果，经过有限次迭代后，使用公式（12）判断是否收敛[2] ∑∑∫ t )( t )( n )( k dt − e e )1 − ( k T = n t 0 rs k T ∑∑∫ t rs k = 0 e rs k t )( dt δ< （12） 式中：δ是收敛判断参数。如果满足上式，则分配过程完成，否则，继续进行下一步 迭代。 3 算法步骤 Step 1 初始化 列举出每 OD 对之间所有的有效路径，确定每条路径的通行能力； 根据式（4）确定每条路径的通行能力； 设置开始时间每条路径上的驶入量为 0； 确定开始时间段每 OD 点对之间的出发交通量，设定迭代收敛判断参数δ和迭代次数 1=N 1=M ； ，时间段 Step 2 动态随机网络加载 确定每条路径在第 M 时间段的行程花费，式（5）； 由式（6）、（7）计算出路段选择概率，并选择出最大路段选择概率的路段，依次找到 r → 的路径 ； 根据式（9）、（10）、（11）得到第 M 时间段中每条路径的分配结果（驶入量）； k s 一条 判断，如果 [ ( tM ) <∆× ]T ，则 = MM 1+ ，转 Step 2； -3- 

Step 3 收敛判断 如果式（12）成立，算法结束；否则，令 NN = + ,1 M = 1 ，转到 Step 2。 http://www.paper.edu.cn 4 结束语 本文初探性的运用了 Darl 算法建立了一个动态交通分配模型，该模型的运行实现并不 很复杂，可以尝试作为城市道路交通动态分配的方法予以深入研究。限于笔者学术水平，没 有深入探讨 DDSUE 模型和 Darl 算法的结合关系。论文尚缺有效的实例分析，笔者将在接 下来的深入研究中对该模型进行充分的修改和必要的实例分析，在次期间诚恳广大交通同仁 提供宝贵的建议和学术支持。 参考文献 [1] 吴中.《交通模型》笔记.河海大学内部资料.江苏 南京（2006）. [2] 温凯歌，曲仕茹.基于 Logit 模型的动态交通分配研究.交通与计算机.2006 年第一期，第 24 卷. [3] 李硕，范炳全.动态与随即交通网络模型与应用.上海：同济大学出版社，2005.44～48. Original research for dynamic traffic assignment based on Darl arithmetic Abstract This paper mentioned a model of dynamic traffic assignment based no Darl arithmetic, the model combined departure time with dynamic stochastic user equilibrium assignment problem (DDSUE). In route choice of traffic assignment, it computed the proportion of each link, which had been chosen by using the theory of Darl arithmetic’s “efficiency path”, and calculated the proportion of each path by using the one of link. Finally, each path flow had been calculated by using the path capacity multiplying the proportion of each path which had been chosen. Keywords: Darl arithmetic; traffic assignment; efficiency path -4-