《解决组合分布和分配问题的改进起点算法》由会员分享，可在线阅读，更多相关《解决组合分布和分配问题的改进起点算法（8页珍藏版）》请在金锄头文库上搜索。
1、解决组合分布和分配问题的改进起点算法徐猛 a，*,Anthony Chen b,高自友 a（a北京交通大学交通运输学院系统科学研究所，中国北京海淀区100044b犹他州立大学，美国犹他州843224110 ）摘要：本文研究的是出行分布为重力模型和交通分配为用户均衡模型的条件下， 进一步研究用起点算法解决组合分布和分配（CDA）问题。近来，起点算法显得优于 F-W算法在交通分配（TA）问题上；在解决组合分布和分配（CDA）问题时， 在计算时间上和解决问题的精度上起点算法要优于Evans的算法。在本文中，借 助Evans算法由Huang和Lam运输系统研究B 26（4）,1992,325 - 33
2、7提出的一 种修正后的OD流量更新方法被应用于改进起点算法解决组合分布和分配（CDA） 问题。改进的起点算法的收敛性证明是通过初步的计算结果来说明这种修正后的 OD流量更新方法在起点算法中影响。关键词：组合交通分布和分配；Evans算法；起点（OB）算法；出行分布；交通分配1.引言运输系统可以当作是各种不同元素以及它们之间的相互作用的组合，这种组合产生了出 行需求，从而通过提供运输服务的需求来满足这种需求。当一个运输系统有了研究改进，就 会有多种可供选择的方式。考虑各种出行的目的预测了出行方式。在运输领域，出行预测是 一个复杂的问题而且越来越受到人们的关注。一般地，这个问题可以简化为一系列的步
3、骤或 者阶段：出行产生（出行选择），出行分布（目的选择），方式划分（模型选择），交通分配 （路径选择）。这个简化的模型应用于交通规划研究已经几十年了，而且将被继续用于现在 的实践中（Boyce 和 Xiong ， 2007）。正如许多研究者（如Oppenheim,Garret和Wachs;McNally,Boyce所提出的,在这个连续的4步骤程序中的许多步都受到不一致的出行时间和拥挤因素的影响。作为补救，一种反馈机 制常常被用于解决这种矛盾；但是通常这种方法不能完全严格的实现（Boyce,2002）。一种解 决这个问题的可供选择的方法是采用一种数学模型用行为假设（来源于典型的实际效用理 论）作
4、为数学条件来寻找满足这种情况的解决方法。这些模型通常被称为“组合”或者“综 合”模型。对于那种综合了多种交通选择在一起的模型的研究已经有几十年了。有弹性需求的用户均衡模型的第一个有约束的凸优化构想首先是由Beckmann在1956年提出的。它把每个OD 对之间的出行者当作是这个OD对出行系统的一项功能。Florian （1975）和Evans（1976）通过 一个组合的CDA模型来考虑目的选择扩展了这一凸优化构想。在这个模型中，出行分布服 从负指数分布的重力模型，而交通分配服从一个用户均衡模型。1993Oppenheim在CDA模 型中增加了多变的目的地因素来探究在目的地的交通拥堵的影响。在1
5、992年Lam和 Huang ,Boyce和Bar-Gera在2004年以及Ho在2006年拓展了 CDA模型以解释多用户问题， 而Florian和Nguyen在1978研究了 CDA模型中的交通方式划分。1981年针对组合的分布、 分配和方式划分,Friesz提出了一个等价的最优化问题,这一问题排除了对称性限制。在2004 年Wong提出了一个最优化模型，该模型用来解决组合分布，层次选择模型以及多用户和 模式的网络分配。1988年Safwat和Magnanti基于随机效用理论集成了一系列交通需求和 预测4个步骤发展了一种组合模型。1995年Oppenheim同时考虑了出行-目的地-方式-路线
6、 选择对该模型进一步延伸，这种延伸是基于多元Logit模型在多层次结构中假设每个出行者 是城市出行中的一个顾客，这些出行者的选择通过效用和预算限制反映出来。以上讨论的所有组合模型中，CDA模型在许多交通规划中的应用极为重要，因为它可 以帮助交通规划者了解土地利用和交通规划间的相互作用，并由此决定城市未来的发展方向 和交通系统改善计划。例如，许多研究者已经采用CDA模型作为在一个两层规划框架中的 低级别问题，用来模拟不同的土地利用和运输问题。2004年Yang等利用CDA模型模拟了 城市运输网络的通行能力和服务水平等级；2000年Tam和Lam利用CDA模型来决定在路 网的通行能力限制下最大的小
7、汽车数量和可用的停车车位；2003年Lin and Feng将CDA模 型应用于土地利用网络设计问题，该问题是为了分析土地利用、公共设施、运输网络和出行 需求的综合布局；2006年Lee证明了均衡OD出行费用的改变与土地利用的发展有关系； 2005年Yim用CDA模型作为一个规划来规划土地利用方式，路网中的路径负担方式，考 了居民、就业分配和网络加强，优化路网的可靠性；2007年Ho和Wong把CDA模型用于 居住区位和交通均衡以追求在一个联系运输系统中优化住房供给模式。对于解决问题的方法，著作中多种算法作为一个约束凸优化问题被用于解决CDA模型。 1976年Evans题出了一种局部线性规划方
8、法，这种方法是一种解联系优化问题的下降算法。 1975年Florian和Florian ，1978年Nguyen三人基于Frank和 Wolfe的方法提出了另一种 算法。然而，根据Boyce和LeBlanc和Farhangian的研究，Evans的算法有较好的收敛特 性。基于两种未经证实的猜测，1989年Horowitz提出了 Evans算法的一种改进算法，目的 是为了减少计算次数和降低内存需求。然而，正女口Huang和Lam1992年所指出的Horowitz 的改进算法不一定经常都能够收敛于最优解。为了改正这个问题，1992年Huang和Lam在 Horowitz的改进算法基础上提出来一个进
9、一步改进算法，并且给出了一个严格的收敛性证 明。另一方面，1998年Lundgren和Patriksson提出了一种解决算法，这种算法融合了 Evans 的算法和单形分解法(DSD), DSD方法是由Larsson和Patriksson在1992年提出的。自从 该算法被用于路径流量领域人们期望这种算法与Evans的算法相比有更好的计算效率和更 高的计算精度。然而，融合Evans的算法和二次分配后的DSD算法会导致不收敛。近来，Bar-Gera 和 Boyce 在 2003 年,Bar-Gera 和 Boyce 在 2006 年拓展了解决 CDA 模 型的OB算法作为一个不动点问题。与Evans
10、的算法相比，OB算法在获得高精度方法方面 具有更高的效率。当实施OB算法后，人们发现在OD流量更新步骤的步长的确定对于该算 法的计算效果有明显的影响。作为一种提高OB算法进计算效率的方法，本文采用由Huang 和Lam提出的改进线性研究方法，该方法的改进源于Evans算法。人们期望这种方法能够 提高OB算法在解决CDA模型中有更好的效率。本文的余下部分是按照下面的安排组织起来的。在下一部分，总结Evans CDA模型和 OB算法。在一个改进的OD流更新方法下，用于解决双约束CDA问题的改进OB算法将 会在第三部分论述。第四部分则是改进OB算法的收敛性证明。第五部分则是为了说明改进 OD流更新策
11、略在OB算法中的影响的一些初步计算结果。一些总结的评论将会在第六部分 讨论。2. Evans算法和OB算法的总结这一部分对于求解CDA模型的Evans模式和OB算法做了总结。总结部分的陈述内容 来自于 Evans(1976),Huang 和 Lam(1992),Bar-Gera、Boyce(2003)和 Yim(2005)。符号首先是 为了便利才提出来的，后来被用于CDA模型的凸优化模型和OB算法。2.1.符号N网络中的节点A网络中的路径Z网络中的某个区域Z起点P的讫点pZ讫点q的起点qA起点p的一个局部网络pah路径a的起始节点hat路径a的结尾节点lcn.jNBjdpqOpDq最终到节点j
12、的相同的节点到节点j的非基本路径从起点p到讫点q的OD流量；d=（，d ，）pq在起点p处开始，单位时间内的出行者数目在讫点q处结束，单位时间内的出行者数目rp起点p的平衡系数sq讫点p的平衡系数Xa路径a上的父通流量；x=（.，x，.）aC （X ）路径a上交通流量为x时的出行费用假定它是连续的、严格递增的函数；c=aaa(，C(x ),.)aaXap起点为p的路径a上交通流量aap路径a占所有以p为起点的路径的比例；a= （.， ap， .）， 0 W a Wl,1ap工a = 1, Vi e N, p e Z心apahgjp从起点p到节点j的交通流量o. ip从起点p到节点i的最大费用u
13、. ui从节点i到节点j的最小费用1 a路径a的平均费用va路径a上考虑流量时，卩的近似导数1 aOj到节点j的平均费用pj至忡点j上的流量，O.的近似导数IMax主循环的次数I内部循环的次数Inner卩阻抗系数0算法映射2.2凸优化模型给出出行分布和分配问题的约束条件如下:x 0 Va e A, p e Z,apx =乙 x,Va e AaappeZd 0Vp e Z, q e Z ,pp乙x -乙x = OVp e Z,apappaeAaeAEx 一为x = dVp e Z,q e ZapappqPaeAaeAEx一 x = 0 Vp e Z, i e N, i 电 Z u papapae
14、AaeAat=iE d = Opq p乙d= DpqpeZqu = 0ppu0, a e A,+ ca+ ca a ( ap 0（2）（3）（4）（5）（6）（7 ）（8）（9）（10）61）（12）s D exp匕 B u 丿Vp e P, q e Z .p q qpqp如果Op, Dq和0已经给定那么式（3）, （7）,，（12）定义了出行分布问题。这个问题也被称作带有负指数的双约束重力模型，采用Fratar的迭代法可以从双约束重力模型中获得一个独一无二的最优解（d * ）。出行分布问题的一个等效最小化优化模型可以表示如下: pqMin G（d）= E E d （n d + B u 一 1
15、）pq pq pqs.t.6）（71和&（13）因为G（d）是关于d的严格单调凸函数,所以这个问题的解法是独一无二的（Evans第一定理）。如果d和c（x）已知，那么式（1）、（2）、（4）、（5）、（6）、（9）、（10）和（11）定义了交通分配pqa a问题。这些等式替代了 Wardrop第一原理，同时等价于KuhnTucker必要条件，也是以下最Min H(x)=EJxac (xxs.t.0,（2：（4 ）（5）和（6）(14)小化凸优化程序的必须满足的等式约束:函数H（x）是一个关于x的严格的凸函数，而对于所有aUA,函数c（x ）是一个严格的递增 函数。在路网流量方面，这个问题的该种解法是独一无二的，但是对于路
