Frank_Wolfe算法求解交通分配问题_比较不同流量更新策略和线搜索技术

第8卷 第3期 2008 年 6 月 交通运输系统工程与信息 Journal of Transportation Systems Engineering and Information Technology Vol18 No13 Jun 2008 文章编号 : 100926744 (2008) 0320014209 智能交通系统与信息技术 Frank2Wolfe 算法求解交通分配问题 : 比较不同流量更新策略和线搜索技术 徐 　猛 3 a ,屈云超a ,高自友b (北京交通大学 : 　a. 交通运输学院系统科学所 ; b. 轨道交通控制与安全国家重点实验室 ,北京 100044) 摘要 : 　Frank2Wolfe (FW)算法是一类广泛应用于求解交通分配问题的算法. 它具有容 易编程实现 ,所需内存少的特点. 但是该算法收敛速度较慢 ,不能得到路径信息. 为了 提高算法的效率 ,本文研究三种流量更新策略 (all2at2once , one2origin2at2a2time , one2OD2 at2a2time)以及不同的步长搜索策略下的 FW 算法 ,其中步长搜索策略包括精确线性搜 索方法 (包括二分法、黄金分割法、成功失败法) 和不精确的线性搜索方法 (包括基于 Wolfe2Powell 收敛准则的搜索方法和 Gao 等提出的非单调线性搜索方法) . 最后 ,本文将 上述策略应用于四种不同规模的交通网络中 ,并给出较适合求解的组合. 关键词 : 　交通分配问题 ;Frank2Wolfe 算法 ;流量更新策略 ;线搜索 中图分类号 : 　U491 文献标志码 : 　A Implementing Frank2Wolfe Algorithm for Traffic Assignment Problem under Different Flow Update Strategies and Line Search Technologies XU Menga , QU Yun2chaoa , GAO Zi2youb (a. School of Traffic and Transportation ; b. State Key Laboratory of Rail Traffic Control and Safety , Beijing Jiaotong University , Beijing 100044 , China) Abstract : 　Frank2Wolfe (FW) algorithm is widely used to solve traffic equilibrium assignment problems. It has the characteristics of simple implementation and modest memory requirement. However , it also faces some prob2 lems such as slow convergence , no providing path information , and so on. In order to improve its implementation efficiency , the FW algorithm is furthermore studied from three flow update strategies (all2at2once , one2origin2at2a2 time , and one2OD2at2a2time) and different step search methods , which include deterministic line search methods (bisection method , golden2section method , and success2failure method) and nondeterministic line search methods (a search method on the basis of Wolfe2Powell convergent criterion and a nonmonotone line search method) . Four different scales of transportation networks are used to test the different update strategies finally. Key words : 　traffic assignment problem ; Frank2Wolfe algorithm ; flow update ; line search CLC number : 　U491 Document code : 　A 收稿日期 :2007212217 　　修回日期 :2008202226 　　录用日期 :2008203211 基金项目 :国家自然科学基金 (70771005) ; 国家重点基础研究发展 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 (973 计划 , 2006CB705503) ; 教育部博士点 新教师基金 (20070004045) . 作者简介 :徐猛 (1976 - ) , 男 , 湖北松滋人 ,博士.3 通讯作者 :xumeng @jtys. bjtu. edu. cn © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 1 　引 　　言 交通分配是研究许多交通问题 (例如城市交通 预测、交通网络设计问题、道路定价问题) 的基础. 交通分配是在假定用户出行行为准则下 ,将 OD 流 量分配到网络中的过程. 交通分配得到的数据可以 用来分析用户的路径选择行为 ,估计或预测汽车出 行总量Π公交系统的乘客出行量. 交通分配也是进行 城市和区域规划 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 的合理性 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 的基础. 此外 , 利用交通分配也可以检验现状路网的可靠性. 自从 Beckmann 等提出交通分配的凸优化描述 以来 ,设计求解交通分配问题的算法吸引了大批学 者[1 - 8 ] . Patriksson[9 ]对现有的交通分配问题以及求 解算法进行了详细的总结. 根据每次迭代存储信 息的不同 ,求解交通分配问题的算法主要分为三 类 :基于路段的求解算法、基于路径的求解算法和 基于起点的求解算法. 基于路段的算法具有需要 内存少的优点 ;基于路径的算法虽然具有较快的收 敛速度 ,但是内存需求量很大. 基于起点的算法[10 ] 所需内存少、收敛速度快、能够给出详细的路径信 息 ,而且能够用于大规模网络求解. 此外 ,求解交 通分配问题收敛准则的确定也是一个重要的问题 , Boyce 等[11 ]在研究从宾夕法尼亚东南部到新泽西 南部的两大高速公路匝道后提出 ,交通分配收敛准 则精度较低时 ,轻微的扰动会引起整个网络路段流 量的波动. Frank2Wolfe (FW) 算法是经典的求解交通分配 问题算法[12 ] . FW 算法主要由确定可行下降方向 和搜索步长两大部分组成. FW 算法将求解最小化 线性子问题过程 ,并将流量通过全有全无的分配到 最小费用的路径 ,路段费用通过当前路段流量求 得. 可行下降方向通过求解子过程得到的解与当 前解之差确定. FW 算法的特点是迭代早期收敛 快 , 后期较慢 ,因为在后期 (当迭代点接近最优解 时) ,搜索方向与目标函数的梯度趋于正交. 这样 的方向并非是最好的下降方向 ,很多学者改进此算 法的的出发点就是在下降方向的选取上[9 ,13 ] . 2 　流量更新策略 2. 1 　All2at2once 流量更新策略 All2at2once 是常用的流量更新策略 ,每次求解 所有 OD 对的最短路径 ,并且同时更新所有 OD 对 最短路径和其最短路径集间的流量. 图 1 是 All2at2 once 流量更新的示意图 ,符号定义如下 : x ———更新前的路段流量向量 ; y ———求解所有 OD 对的最短路径 ,经过全有 全无分配得到的路段流量向量 ; z ———更新后的路段流量向量. 图 1 　All2at2once 流量更新示意图 Fig. 1 　All2at2once flow updates strategy 　 　　从图 1 可以看出 ,这个流量更新策略下需要两 个路段向量变量 x 和 y ,所以主要的存储空间需求 为 2Na ,其中 Na 为存储路段流向量的所需的空间. 2. 2 　One2origin2at2a2time 流量更新策略 与 All2at2once 流量更新策略不同 ,one2origin2at2 a2time 流量更新策略每次只更新部分路段流量. 在 这个策略下求解时 ,每次迭代需要求解一个 O 点 下所有 OD 对的最短路径 ,并且每次更新这些 OD 对最短路径及其最短路径集间的流量. 图 2 是 one2origin2at2a2time 流量更新的示意图 ,其中符号的 定义如下 : xo ———以 O 为起点的所有 OD 对的最短路径 集的流量通过全有全无分配得到的路段流量向量 ; yo ———求解一个 O 点下所有 OD 对的最短路 径 (也就是以 O 点为起点的最短路径树) ,并通过 全有全无分配得到的路段流量向量 ; zo ———更新后的部分路段流量向量 ; uo ———原始路段流量向量除去 xo 得到的流 量 ,是流量更新时保持不变的流量向量. 图 2 　One2origin2at2a2time 流量更新示意图 Fig. 2 　One2origin2at2a2time flow updates strategy 　 　　图 2 表示一个起点的流量更新过程 ,一次完整 的流量更新应该包括 SUMO 次 (其中 SUMO 为 O 点 51第 3 期 Frank2Wolfe 算法求解交通分配问题 : 比较不同流量更新策略和线搜索技术 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 的个数) . 从图 2 可以看出 uo 的值并没有更新 ,但 是在平衡流量时需要 uo 用来进行线性搜索求解 α. xo 和 yo 都是路段向量变量 ,所需的存储空间都 是 N a , uo 是更新时不变的部分路段流量 (实际上 是存储的路径集的变量) ,与起点的个数和路径数 目有关 ,所需的存储空间为 NoN a ,所以这个策略 下总共需要的存储空间为 2 N a + NoN a . 2. 3 　One2OD2at2a2time 流量更新策略 与 one2origin2at2a2time 策略相似 , one2OD2at2a2 time 策略也是每次更新部分路段流量. 每次求解一 个OD 对的最短路径 ,并且每次更新这个 OD 对的最 短路径集和求解的最短路径的流量. 图 3 为 one2 OD2at2a2time 流量更新的示意图 ,其符号定义如下 : xOD ———以一个 OD 对的最短路径集的流量通 过全有全无分配得到的路段流量向量 ; yOD ———求解该 OD 对的最短路径 ,并通过全 有全无分配得到的路段流量向量 ; zOD ———更新后的路径集流量向量 ; uOD ———原始路段流量向量除去 xOD 得到的 流量 ,即流量更新时保持不变的流量向量. 图 3 　One2OD2at2a2time 流量更新的示意图 Fig. 3 　One2OD2at2a2time flow update strategy 　 　　图 3 描述了 OD 需求流量的更新过程. 每次迭 代都需要对路段流量进行更新 ,但是路段费用却不 需要每次随着路段流量的更新而更新. 费用是在 所有 OD 对的流量更新完成之后才进行更新的 ,也 就是图 3 中最后一步所表示的过程. 在此策略下 , 路径信息的存储为主要存储开销. 假设 N n 为每条 路径所包含的路段的条数 , N i 为达到平衡时迭代 的次数 , No 为网络中起点的个数. 如果用路径中 各条路段编号的先后顺序来描述每条路径 ,那么存 储路径所需的空间即为 N i ·No ·N n . 3 　线搜索 可行下降方向法是求解约束优化问题的重要 方法 ,搜索步长的确定是可行下降方向法的重要步 骤. 求解搜索步长的方法有很多. 线性搜索主要 包括两大类 :精确线搜索和不精确线搜索. 精确线 性搜索可以通过导数信息进行求解 ,例如二分法、 牛顿法和割线法 ,这类方法虽然收敛速度快 ,但是 有些问题的导数信息难以确定. 精确线性搜索可 以通过直接搜索目标函数的极值 ,如成功失败法、 黄金分割法. Miller[14 ]对各类精确搜索方法进行了 详细的描述. 不精确的步长搜索方法在某种程度上可以提 高算法的收敛速度. 本文主要将两种不精确搜索 方法运用到 FW 算法 ,一种是基于 Wolfe2Powell 收 敛准则的不精确搜索方法[15 ] ,一种是 Gao 等提出 的非单调线性搜索技术[16 ] . 下面给出这两种方法 的具体描述. 3. 1 　Wolfe2Powell 不精确搜索方法[10 ] 给定的常数 c1 和 c2 值并满足 0 < c1 < c2 < 1 时 ,如果搜索到的步长α满足式 (1) 和式 (2) ,则 可以看作目标函数有所下降 ,满足搜索要求 (本文 中取 c1 = 0. 1 , c2 = 0. 5) . f ( xk ) - f ( xk +1 ) ≥- c1 ·α·¨ f ( xk ) T dk (1)¨ f ( xk +1 ) T dk ≥ c2 ·¨ f ( xk ) T dk (2) 　　计算过程如下 : (1) 令 a = 0 , b = - ∞,α = 1 . (2) 令 xk +1 = xk + α·dk ,计算 f ( xk +1 ) ,¨ f ( xk +1 ) ,如果搜索步长满足式 (1) 和式 (2) ,那么 停止计算. 否则继续计算 ,如果不满足式 (1) ,则转 向第 (3)步 ;如果满足式 (1) 却不满足式 (2) 则转向 第 (4)步. (3) 令 b = α,α = (α+ a)Π2 ,返回第 (2)步继 续计算. (4) 令 a = α,α = min{2α, (α+ b)Π2} ,返回 第 (2)步继续计算. 3. 2 　Gao 等提出的非单调搜索方法[6 ] 给定 a0 > 0 ,0 < σ < 1 , 0 < γ < 12 ,每次迭 代的搜索步长为αk = σhk a0 . 其中 hk 是满足条件 (3)的最小正整数. 61 交通运输系统工程与信息 2008 年 6 月 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net f ( xk +σh a0 dk ) ≤ maxj = 0 ,1 , ⋯, M{ f ( x k - j ) } + γσh a0 ¨ f ( xk ) T dk (3) 　　在本文的计算中 ,式 (3)的各参数的取值如下 , σ = 0. 62 ,γ = 0. 001 , M = 3 . 4 　数值结果 本文运用 FW 算法求解四种不同规模的网络 , 并通过数值结果对流量更新策略和搜索步长方法 进行分析. 表 1 给出了网络的基本数据. 表 1 　网络信息 Table 1 　Test networks 网络 名称 起点 个数 节点 个数 路段 条数 OD 对 个数 Nguyen2Dupius 网络 2 13 19 4 Anaheim 网络 38 416 914 1 406 Barcelona 网络 97 3 1 020 2 522 7 922 ChicagoSketch 网络 386 933 2 950 142 890 注 :1. 数据均来自 http :ΠΠwww. bgu. ac. ilΠ～ bargeraΠtntp . 　 2.“3 ”表示比 http :ΠΠwww. bgu. ac. ilΠ～bargeraΠtntp 给出的起点个 数要少. 因为在 OD 对数据文件中 ,有些起点并没有任何迄点信 息 ,在起点的统计时没有考虑进去. 　　数值计算的运行环境为 Intel Ó PentiumÓ 4 CPU 1. 6 GHz ,768 MB RAM ,所用操作系统为 Microsoft Windows XP. 所有程序用 C 语言编写 ,通过 Visual C ++ 6. 1. 0 进行编译和调试. 所有算法采用相同 的网络数据、数据存储结构和相同的最短路径算 法 ,在初始化流量时均采用 All2at2once 策略进行 求解. 4. 1 　线性搜索 本节的数值结果是通过求解 Nguyen2Dupius 网 络 (实验网路) 得到的. 上文提到的三种线性搜索 技术和三种流量更新策略将用于求解该问题. 首 先我们将研究步长搜索精度对算法收敛速度的影 响. 为了描述方便 ,图 4～图 15 中三种流量更新策 略分别用 A、B、C 来表示 ,A 代表 all2at2once 流量更 新策略 ,B 代表 one2origin2at2a2time 流量更新策略 ,C 代表 one2OD2at2a2time 流量更新策略. 精确线性搜 索方法用 I、G、F 表示 , I代表二分法 ,G代表黄金分 割法 ,F 代表成功失败法. 线性搜索精度用数字 1、 2、3、4、5 表示 ,分别代表 10 - 1到 10 - 5五种精度. 图 例中的标注代表运用到 FW 算法的方案 ,其中第一 个字母表示流量更新策略 ,第二个字母表示步长搜 索方法 ,数字代表精确线性搜索的精度. 例如 “AI1”代表 FW 算法运用 all2at2once 流量更新策略、 二分法步长搜索方法 ,并且线性搜索精度为 10 - 1 . 4. 1. 1 　步长搜索精度分析 首先我们将研究步长搜索精度对 FW 算法的 影响. 图 4 (a) ～4 (c) 表示运用 AI、AG、AF 策略分 别在五种不同搜索精度下求解 Nguyen2Dupius 网络 前 50 次迭代的数据结果. 这里流量更新策略全部 采用 all2at2once 流量更新策略. 图 4 (a) 　AI策略下不同搜索精度的比较 Fig. 4 (a) 　Effects of different line search precisions with bisection method and all2at2once strategy　 图 4 (b) 　AG策略下不同搜索精度的比较 Fig. 4 (b) 　Effects of different line search precisions with golden section method and all2at2once strategy　 图 4 (c) 　AF策略下不同搜索精度的比较 Fig. 4 (c) 　Effects of different line search precisions with success2failure method and all2at2once strategy 　 　　图 5 (a) ～5 (c) 表示运用 BI、BG、BF 策略分别 71第 3 期 Frank2Wolfe 算法求解交通分配问题 : 比较不同流量更新策略和线搜索技术 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 在五种不同搜索精度下前 50 次迭代的数据结果. 这里流量更新策略全部采用 one2origin2at2a2time 流 量更新策略. 图 5 (a) 　BI策略下不同搜索精度的比较 Fig. 5 (a) 　Effects of different line search precisions with bisection method and one2origin2at2a2time strategy 　 图 5 (b) 　BG策略下不同搜索精度的比较 Fig. 5 (b) 　Effects of different line search precisions with golden section method and one2origin2at2a2time strategy 　 图 5 (c) 　BF策略下不同搜索精度的比较 Fig. 5 (c) 　Effects of different line search precisions with success2failure method and one2origin2at2a2time strategy 　 　　图 6 (a) ～6 (c) 表示运用 CI、CG、CF 策略分别 在五种不同搜索精度下前 50 次迭代的数据结果. 这里流量更新策略全部采用 one2OD2at2a2time 流量 更新策略. 　　通过图 4～图 6 可以看出 ,在求解 Nguyen2 图 6 (a) 　CI策略下不同搜索精度的比较 Fig. 6 (a) 　Effects of different line search precisions with bisection method and one2OD2at2a2time strategy 　 图 6 (b) 　CG策略下不同搜索精度的比较 Fig. 6 (b) 　Effects of different line search precisions with golden section method and one2OD2at2a2time strategy 　 图 6 (c) 　CF策略下不同搜索精度的比较 Fig. 6 (c) 　Effects of different line search precisions with success2failure method and one2OD2at2a2time strategy 　 Dupius 网络时 ,各种精确线性搜索方法在不同精度 下的结果相差不多 ,高搜索精度并没有加快整体的 收敛速度. 另外可以看出精度为 10 - 1时可能会出 现一些不收敛或者目标值振荡的情况 ,如 0. 618 法 和成功失败法 ,所以精度为 10 - 2时比较适合求解. 81 交通运输系统工程与信息 2008 年 6 月 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 4. 1. 2 　搜索方法分析 这一节的分析是基于搜索精度为 10 - 2的数据 进行的. 图 7 (a)比较了 all2at2once 流量更新策略下 各种线性搜索步长 (二分法、黄金分割法、成功失败 法)的数据结果. 图 7 (b)和图 7 (c)分别比较one2or2 图 7 (a) 　All2at2once 流量更新策略得到的结果 Fig. 7 (a) 　Effects of three line search methods with all2at2once strategy　 图 7 (b) 　One2origin2at2a2time 流量更新策略得到的结果 Fig. 7 (b) 　Effects of three line search methods with one2origin2at2a2time strategy　 图 7 (c) 　One2OD2at2a2time 流量更新策略得到的结果 Fig. 7 (c) 　Effects of three line search methods with one2OD2at2a2time strategy 　 igin2at2a2time 和 one2OD2at2a2time 流量更新策略. 从 图中我们可以看出 ,在三种流量更新策略下 ,黄金 分割法在迭代过程中收敛速度稍快 ,成功失败法次 之 ,二分法相对速度稍慢. 精确步长搜索方法应用 到 FW 算法求解时 ,不同的方法对整体算法的收敛 速度没有太大的影响. 4. 1. 3 　流量更新策略分析 通过 4. 1. 2 节的分析可以看出 ,运用黄金分割 法求解时收敛速度稍快. 图 8 描述的是基于黄金 分割步长搜索方法 ,运用三种流量更新策略得到的 数据结果. 从图中我们可以明显看出 ,运用 one2 OD2at2a2time 流策略收敛速度最快. 因为每次更新 一个 OD 对的流量 ,每次更新流量时都运用一次一 维搜索 ,而且更新后的流量都能及时被用于下次最 短路径的求解. 所以一次更新一个OD 对的这种流 量更新策略的收敛速度最好. 图 8 　黄金分割法下三种流量更新策略的比较 Fig. 8 　Comparing three flow update strategies with golden section search method 　 4. 1. 4 　流量更新策略进一步分析 图 9 比较了最优的线性搜索方法———黄金分割 法 (从收敛速度的角度来看)与第 3 节列举的两种不 精确线性搜索方法的数据结果. 其中 M 代表基于 Wolfe2Powell 收敛准则的方法 , N 代表 Gao 等提出的 非单调线性搜索方法. 图 9 表明N 方法比M方法的 收敛速度更好 ,且与黄金分割法得到的结果相似. 4. 2 　其他网络数据分析 4. 1 节的实验结果主要是基于试验网络得到 的 ,这一节将把上述方案运用到大网络进行求解并 进行检验. 图 10 描述了三种流量更新策略下 ,运 用黄金分割法以及五种精度下求解 Anaheim 网络 得到的数据结果 ,图 11 为求解 Barcelona 网络得到 91第 3 期 Frank2Wolfe 算法求解交通分配问题 : 比较不同流量更新策略和线搜索技术 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 图 9 　两种不精确搜索方法下三种流量更新策略的比较 Fig. 9 　Comparing three flow update strategies with two nondeterministic methods 　 的数据. 图 8 和图 11 同时表明 ,线搜索精度为 10 - 2就可以达到收敛 ,更高的精度对加速收敛没有 很大作用. 在搜索策略上看 ,one2OD2at2a2time 流量 更新策略相对于其他策略对整体收敛速度有了很 大的提高. 由于 Chicago Sketch 网络规模较大 ,所以 求解时运用二分法步长搜索策略. 图 12 为求解网 络的数据 ,结果同时表明 one2OD2at2a2time 流量更 新策略的收敛速度较快. 图 10 　Anaheim网络数值结果 Fig. 10 　Results for anaheim network 　 4. 3 　收敛性分析 前两节主要分析了收敛速度 ,即迭代次数和目 标函数值的关系 ,但是不同策略下每次迭代所需要 的时间是不同的. 虽然 one2OD2at2a2time 策略下达 到收敛所需的迭代次数要少于其他两种策略 ,但是 由于每次迭代需要更新所有 OD 对的信息 ,所以一 次迭代所需的时间较长. 因为每次迭代都需要存储大量的数据 ,所以程 序的运行时间需要更长. 程序运行时间跟系统有 关 ,为了使计算结果不出现大的偏差 ,每个方案的 程序都执行 5 次 ,然后取 5 次运行时间的平均值作 图 11 　Barcelona 网络数值结果 Fig. 11 　Results for barcelona network 　 为方案运行的时间. 图 12 　Chicago Sketch 网络数值结果 Fig. 12 　Results for chicago sketch network 　 由于 Nguyen2Dupius 网络规模较小 ,三种流量 更新策略时间相差不是很明显 ,所以这里选用 Bar2 celona 网络进行数据分析. 收敛性中相对精度的表 达式为式 (4) 的形式 ,其中 BLB 即当前目标函数的 最小值. 图 13 至图 15 给出了 Anaheim 网络、Barce2 lona 网络和 Chicago Sketch 网络的数据结果. 从图 中可以看出 ,one2origin2at2a2time 策略的收敛性较 好. 不过由于三种流量更新策略均是在 FW 算法 框架下进行 ,最终收敛精度只能达到 10 - 3到 10 - 4 . RG = Z ( xn ) - BLB n BLB n 　　表 2 为三种流量更新策略下算法的每次迭代 　　表 2 　各种策略的单步迭代平均运行时间 (单位 :秒) Table 2 　Average run time for three flow update strategies ( Unit : Sec) 二分法 成功失败法 黄金分割法 All2At2Once 7. 25 7. 25 7. 5 One2Origin2At2A2Time 8 7. 25 10. 75 One2OD2At2A2Time 58 55 72. 75 02 交通运输系统工程与信息 2008 年 6 月 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 的平均运行时间. 从表中可以看出 ,all2at2once 策 略下三种精确搜索方法步长搜索策略对整体的影 响不大 ,但是其他两种策略下各种方法影响较大. 同时实验数据表明 ,成功失败法的运算时间最少. 图 13 　Anaheim网络三种流量更新策略下的收敛情况 Fig. 13 　Comparison implementation times of three flow update strategies for anaheim network 　 图 14 　Barcelona 网络三种流量更新策略下的收敛情况 Fig. 14 　Comparison implementation times of three flow update strategies for barcelona network 　 图 15 　Chicago Sketch 网络三种流量更新策略下 的收敛情况 Fig. 15 　Comparison implementation times of the three flow update strategies for chicago sketch network 　 5 　研究结论 本文主要研究了三种流量更新模式和五种线 性搜索技术 (包括三种精确搜索方法和两种不精确 搜索方法)下 FW 算法求解四种不同规模网络的执 行效率. 数据结果表明 : 精确搜索方法中黄金分割法收敛速度较快 ,成 功失败法次之 ,二分法收敛速度稍慢 ; Gao 等提出 不精确搜索方法比 Wolfe2Powell 准则的方法收敛速 度快. 但是线性搜索对 FW 算法的影响不如流量 更新策略明显. 在步长搜索中二分法精度取 10 - 1即可满足收 敛要求 ,其他方法取 10 - 2可以满足精度要求. 总体 来看 ,10 - 2为最佳步长搜索精度. 大网络数据也证 明了上述观点. 在搜索策略来看 ,one2OD2at2a2time 策略和 one2 origin2at2a2time 策略均比 all2at2once 策略收敛速度 要快 ,但是 one2OD2at2a2time 策略每次迭代所需的 时间要比其他两种策略较长. 在大网络中 ,这种差 异比较明显. 进一步的研究 ,还可以讨论影响算法收敛速度 的其它因素 , 如 :初始解 ,网络结构 ,拥挤程度 (即 OD 需求) 等等. 参考文献 : [ 1 ] 　Chen A , Jayakrishnan R , Tsai W K. Accelerating the convergence of the frank2wolfe algorithm for the traffic as2 signment problem with one2at2a2time flow update strategy [J ] . Journal of Transportation Engineering , 2002 , 128 (1) : 31 - 39. [ 2 ] 　Chen A. Effects of flow update strategies on the implemen2 tation of the frank2wolfe algorithm for the traffic assignment problem [ R ] . Transportation Research Record , 2001 , 1771 : 132 - 139. [ 3 ] 　Jayakrishnan R , Tsai W K, Prashker J N , Rajadhyaksha S. A Faster Path2based Algorithm for Traffic Assignment [ R] . Transportation Research Record ,1994 , 1443 : 75 - 83. [ 4 ] 　Sheffi Y. Urban Traffic Networks : Equilibrium Analysis with Mathematical Programming Methods [ M ]. Prentice2 Hall , Englewood Cliffs , NJ , 1985. [ 5 ] 　王京元 ,程琳. 最短路拍卖算法在交通分配中的应 用[J ] . 交通运输系统工程与信息 , 2006 , 6 (6) :79 - 82. [WANGJin2yuan , CHEN Lin. Application of auction algorithm for shortest paths in traffic assignment[J ] . Jour2 nal of Transportation Systems Engineering and Information 12第 3 期 Frank2Wolfe 算法求解交通分配问题 : 比较不同流量更新策略和线搜索技术 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net Technology , 2006 , 6 (6) :79 - 82. ] [ 6 ] 　司徒惠源 ,罗康锦. 动态交通分配 :回顾及前瞻 [J ] . 交通运输系统工程与信息 , 2005 ,5 (5) :85 - 95. [ Sze2 to W Y, Lo H K. Dynamic traffic assignment : review and future research directions [ J ] . Journal of Transportation Systems Engineering and Information Technology , 2005 ,5 (5) :85 - 95. ] [ 7 ] 　李志纯 ,黄海军. 随机交通分配中有效路径的确定 方法[J ] . 交通运输系统工程与信息 , 2003 ,3 (1) :28 - 32. [LI Zhi2chun , HUANG Hai2jun. Determining the efficient paths in stochastic traffic assignment [J ] . Journal of Transportation Systems Engineering and Information Technology , 2003 ,3 (1) :28 - 32. ] [ 8 ] 　李峰 ,王 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 宁. 基于终点的路径交通量求解方法 [J ] . 清华大学学报 (自然科学版) ,2006 ,46 (1) :149 - 152. [ LI Feng , WANG Shu2ning. Destination2based approach for routing traffic flows in traffic assignment prob2 lems [J ] . Journal of Tsinghua University ( Science and Technology) , 2006 ,46 (1) :149 - 152. ] [ 9 ] 　Patriksson M. The Traffic Assignment Problem : Models and Methods [ M ]. VSP , Utrecht , The Netherlands , 1994. [10 ] 　Bar2Gera H. Origin2based algorithm for the traffic assign2 ment problem[J ] . Transportation Science , 2002 , 36 : 398 - 417. [11 ] 　Boyce D , Bar2Gera H. Convergence of traffic assign2 ments : how much is enough[J ] . Journal of Transportation Engineering , 2004 , 130 (1) :49 - 55. [12 ] 　Frank M , Wolfe P. An algorithm for quadratic program2 ming[J ] . Naval Research Logistics Quarterly , 1956 , 3 : 95 - 110. [13 ] 　黄海军. 城市交通网络平衡分析 ———理论与实践 [M] . 北京 :人民交通出版社 , 1994. [ HUANG Hai2 jun , Urban Transportation Network Equilibrium Analysis : Theory and Practice[M]. Beijing : China Communications Press , 1994. ] [14 ] 　Miller R E. Optimization[M]. Wiley , New York , 2000. [15 ] 　Wolfe P. Convergence Theory in Non2linear Programming , Integer and Non2linear Programming[M]. North Holland , Amsterdam , 1970. [16 ] 　Gao Z Y, Lam W H K, Wong S C , Yang H. The conver2 gence of equilibrium algorithm with non2monotone line search technique[J ] . Applied Mathematics and Computa2 tion , 2004 , 148 (1) : 1 - 13. 22 交通运输系统工程与信息 2008 年 6 月 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net