Computer Engineering and Applications 计算机工程与应用 2018，54（9） 213 用于求解路径交通流量的改进 Frank-Wolfe 算法 柴 获 1，2，何瑞春 2，马昌喜 2，代存杰 1，3 CHAI Huo1，2, HE Ruichun2, MA Changxi2, DAI Cunjie1，3 1. 兰州交通大学 机电技术研究所，兰州 730070 2. 兰州交通大学 交通运输学院，兰州 730070 3. 甘肃省物流及运输装备信息化工程技术研究中心，兰州 730070 1.Mechatronics Technology and Research Institute, Lanzhou Jiaotong University, Lanzhou 730070, China 2.School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China 3.Engineering Technology Center for Informatization of Logistics & Transport Equipment, Lanzhou 730070, China CHAI Huo, HE Ruichun, MA Changxi, et al. Improved Frank-Wolfe algorithm for path traffic flows in traffic assignment problems. Computer Engineering and Applications, 2018, 54（9）：213-217. Abstract：Frank-Wolfe algorithm is classic algorithm for traffic assignment problem, but cannot get the path traffic flow because it is a link- based algorithm, an improved algorithm is proposed for the path traffic flow computing based on Frank- Wolfe algorithm. The correspondent module for path traffic flow computing is added to the original algorithm, which is used to update traffic flow of all paths between source and destination（OD）by the traffic flow step size from all or nothing assignment procedure in each iteration, at the same time to obtain the results of path flow in the calculate process of link traffic flow. the experimental results show that the improved algorithm is an efficient algorithm for traffic flow assignment, can be used to solve the path traffic flow by a small amount of time and space costs increased in the Frank-Wolfe algorithm and avoid enumerating all path of the traffic network. Key words：systems engineering; path traffic flow; Frank-Wolfe algorithm; traffic assignment; user equilibrium 摘 要：Frank-Wolfe 算法是用于求解交通流量分配问题的经典算法，但该算法是基于路段（Link-Based）的交通流量 分配算法，无法用于求解路径交通流量。针对此问题，提出一种用于求解路径交通量的改进 Frank-Wolfe 算法。通 过在 Frank-Wolfe 原算法中增加求解路径交通流量的计算步骤，根据原算法中“全有全无”加载方法获得的步长，更 新源-目的（OD）间所有已配流的路径的交通流量，在原算法迭代计算路段流量的同时，同步计算路径流量。通过算 例表明，改进算法是一个有效的算法，在 Frank-Wolfe 原算法的基础上增加少量的时间和空间成本即可求解路径交 通流量，避免穷举交通网络中的所有路径，可以很好地用于用户均衡交通流量分配中。 关键词：系统工程 ；路径交通流量 ；Frank-Wolfe 算法 ；交通流量分配 ；用户均衡 文献标志码：A 中图分类号：U492.3 doi：10.3778/j.issn.1002-8331.1612-0102 1 引言 交通流量分配是城市交通需求预测与交通网络规 划的关键技术，Wardrop 平衡分配原则 [1]在交通流量分 配中被广泛应用，根据该原则的两个平衡原理可以将 交通分配问题分为用户均衡（User Equilibrium，UE）和 系统最优（System Optiminzation，SO）交通分配问题。 Beckmann 建立了平衡配流理论的凸数学规划模型 [2]， Leblanc 首先提出了 Frank-Wolfe 算法[3]，LeBlanc 等通过 基金项目：国家自然科学基金（No.61364026，No.51408288）；甘肃省科技计划（No.1610RJZA037，No.1610RJZA048）；兰州交通大 学校青年基金（No.2015026）。 作者简介：柴获（1982—），男，博士研究生，讲师，CCF 会员，研究领域为现代物流与交通运输系统，E-mail：chaihuo@mail.lzjtu.cn； 何瑞春（1970—），女，博士，教授，博导，研究领域为交通运输规划与管理；马昌喜（1979—），男，博士，副教授，研究领域 为交通系统优化与决策；代存杰（1982—），男，博士生，讲师，研究领域为交通运输规划与管理。 收稿日期：2016-12-07 修回日期：2017-01-24 文章编号：1002-8331（2018）09-0213-05 CNKI 网络出版：2017-04-19, http://kns.cnki.net/kcms/detail/11.2127.TP.20170419.1252.026.html 计算机工程与应用www.ceaj.org

214 2018，54（9） Computer Engineering and Applications 计算机工程与应用 实例验证了该算法用于交通流量分配的可行性[4]，该算 法被认为交通流量分配最经典的算法。Leblanc、Lee 和 高自友等分别通过搜索步长和搜索方向给出了各种不 同的改进 Frank-Wolfe 算法 [5-7]，弥补了原算法存在收敛 速度慢的缺陷，使得算法在效率上有了一定的提升。然 而，由于 Frank-Wolfe 算法是一种基于路段（link-based） 的方法，无法用于求解 OD 对间路径的流量。 Leventhal 首次提出了基于路径（path-based）的列生 成算法（CGA）[8]，认为在每个起终点对之间存在不止一 条的最短路径，提出用多条最短路径加载代替全有全无 加载，但该算法需要存储大量的路径信息，而且将随着 算法迭代次数的增加而变得越来越大，对于大规模交通 网络求解变得非常困难。Bar-Gera 提出的基于起点的 算法（OBA）[9]及 Dial 提出基于起点的 B 算法[10]等都是基 于路径的交通分配方法，可以求解路径交通量但是不要 求储存使用路径，从而不需要占用太多的存储资源，但 该算法的有效性还待检验。根据比例一致性条件[11]也 可确定路径交通流量，虽然在理论上得到了充分的探讨 和验证[12]，Gentile 将比例一致性嵌入到基于终点的算法 并在 VISUM 中进行实验可获得唯一路径流量 [13]，但目 前尚未在实际交通系统中得到验证，也无法证明求解得 到的唯一路径流量解是否与实际相符。 Frank-Wolfe 算法在每个起终点对之间，反复在最 短路径上使用“全有全无”（All Or Nothing，AON）加载 方法，不要求太大的存储容量，能将求解非线性规划问 题转化为求解一系列的线性规划问题，而且各线性规划 具有相同的约束条件，所以该方法具独特的优势。基于 Frank-Wolfe 算法进行改进用于求解路径交通量也不失 为一种有效的尝试。Chen 等[14]在 2002 年提出一种基于 OD 对的改进 Frank-Wolfe 算法（OD-Based Frank-Wolfe， ODBFW），在原算法的基础上，针对每个 OD 对求解相 应的下降方向和步长，获取路段流量的同时根据不同 OD 对的步长时行路段流量的更新，该方法能够有效地 求解路径流量值，但由于算法中针对所有 OD 对求不同 的下降方向和步长，对所有的 OD 间的路径流量要根据 新的步长进行更新，会导致计算量大大增加，同时也破 坏 了 Frank-Wolfe 原 算 法 的 结 构 ；李 峰 等 [15-16] 通 过 将 Beckmann 的模型进行修改先采用 Frank-Wolfe 算法计 算基于终点的路段交通量，再通过 Dijkstra 算法得到所 有 OD 对的最短路径集合，然后再根据所提算法确定一 组路径交通量，该方法能够有效求解路径交通量，并且 经过实例验证，但需要包括 Frank-Wolfe 算法在内的三 个步骤才能求解。 本文提出一种基于 Frank-Wolfe 算法的改进算法， 在不改变 Frank-Wolfe 原算法结构的前提下，根据每代 “全有全无”配流获得的步长更新 OD 对间所有已配流 的路径的交通量，获得路段交通量的同时获得唯一的路 径交通量。本文所提算法在不改变 Frank-Wolfe 原算法 结构的前提下，仅通过增加路径流量更新步骤，最终获 得路径流量。 2 Frank-Wolfe 算法 Beckmann 提出的具有固定需求的 UE 模型[2]如下： min Z(x) = ∑ s.t. ∑ hrs k = qrs,∀r ∈ R,s ∈ S xaca(ω) dω ∫ a 0 （1） （2） k hrs k ≥ 0, ∀r ∈ R,s ∈ S,k ∈ Krs xa = ∑ a,k, ∀a ∈ A hrs k δrs ∑ r,s k （3） （4） 其中 A 为交通网络中路段的集合，R 为产生交通量的 起始节点的集合，S 为吸引交通量的终讫节点集合，r 表示一个起始节点，r ∈ R ，s 表示一个终讫节点，s ∈ S ， Krs 为连接 OD 对 r - s 的所有路径的集合，qrs 为所研究 时间段内从 r 到 s 的交通需求量，hrs k 为 OD 对 r - s 之间 第 k 条路径上的流量，k ∈ Krs ，xa 为路段 a 上的交通流 量，a ∈ A ，ca 为路段 a 上的阻抗，δrs a,k 表示如果路段 a 在连接 OD 对 r - s 的第 k 条路径上，其值为 1，否则为 0。式（1）为目标函数，是所有网络中的路段阻抗函数积 分和，式（2）代表路径流量与 OD 间的交通需求量之间 的守衡关系，式（3）保证所有的路径流量一定是正值，式 （4）是路段流量与路径流量之间的关联关系。 以下为 Frank-Wolfe 算法求解步骤： 步骤 1 初始化。基于 {c0 OD 对 r,s ，求得的 r,s 间的最短路径 k 0 流量 qrs 全部分配到路径 k 0 rs 上，即 hrs k 0 rs 令 n = 1 。 a} ={ca(0)} ，依次检查每一个 rs ，并将 r,s 间交通 = qrs ，得到 {x1 a} ， 步骤 2 更新。令 cn a = ca(xn 步骤 3 下降方向。基于{ cn 对 r,s ，求得的 r,s 间的最短路径 k n 量 qrs 全部分配到路径 k n rs 上，即 hrs k n rs a),∀a ∈ A 。 a }，依次检查每一个 OD rs ，并将 r,s 间交通流 = qrs ，得到{ y n a }。 步骤 4 搜索步长。采用二分法等方法求解满足 Z[xn a + αn(y n a - xn min 0 ≤ αn ≤ 1 步骤 5 移动。令 xn + 1 步骤 6 结束条件。如果 ∑ a + αn(y n (xn + 1 a - xn a - xn a) 。 a)2 ∑ a)] 的 αn 。 a = xn a xn a ≤ ε， a 程序结束；否则 n = n + 1 ，转至步骤 2。 3 改进 Frank-Wolfe 算法 Frank-Wolfe 算法中的 k n 分别表示当迭代到 第 n 次时 r - s 间的最短路径及该路径上的交通流量，路 径 k n 在原算法 rs 只表示当前代的最短路径，因此 k n rs ，hrs k n rs rs ，hrs k n rs 计算机工程与应用www.ceaj.org

柴 获，何瑞春，马昌喜，等：用于求解路径交通流量的改进 Frank-Wolfe 算法 2018，54（9） 215 中作为临时变量并不保存，而且路径 k n rs 上可能在第 n 次迭代之前已经分配过流量，在迭代过程中存在多次向 路径 k n rs 上配流的可能，所以迭代 n 次仅表示在 r -s 间完 成了 n 次最短路径的查找，并不表示已配流的路径有 n 条。为了在迭代过程中始终保存已配流路径上的流量， 在改进的算法中，新增变量 hˉrs k 表示 r - s 间已配流路径 k 的流量，并增加集合 Kˉ rs 表示 r - s 间所有已配流路径集 合。在迭代过程中，当前代最短路径 k n rs 如果从未配流， 则按原算法中“全有全有”配流原则进行，该计算步骤已 经在初始化（步骤 1）和寻找下降方向（步骤 3）时完成， 只需将路径 k n rs 的流量 hˉrs rs 为 已 配 流 路 径 ，即 k n rs rs ∈ Kˉ k n rs 所经过的所有路段的流量， 无法更新该路径 k n rs 的流量。为此，通过对原算法步骤 进行改进，在更新路径 k n rs 所经过的所有路段的流量的 同时，根据路段流量的变化值更新路径 k n = qrs ；如 果 当 前 代 最 短 路 径 k n rs 时，只更新路径 k n rs ，并记录路径 k n rs 加入集合 Kˉ rs 上的流量。 rs 流量 hˉrs 在 Frank-Wolfe 原算法路段流量更新的基础上，对 路径流量采用以下方式更新。对于当前代最短路径 k n rs ，根据下降步长 αn 对路径 k n 进行修正，在原 流量的基础上增加流量 (qrs - hˉrs 径 k n 量 hˉrs k n rs 路径 k ，以 hˉrs 流量更新方式可采用式（5）表示： rs 中除路 rs 外的其他已配流路径，在原流量的基础上减少流 αn ，使 r - s 间总流量仍保持 qrs 。对于 Kˉ rs 中任意 k (n) 表示其经过 n 次迭代后的流量，则路径 )αn ，而对于 Kˉ k n rs k n rs hˉrs k (n + 1) = hˉrs k (n) +(qrs - hˉrs ì í hˉrs k (n) - hˉrs î k (n))αn, k = k n rs,k ∈ Kˉ k (n)αn, k ≠ k n rs rs,k ∈ Kˉ rs （5） 改进后的 Frank-Wolfe 算法主要在步骤 5 中增加路 径交通量更新步骤，算法步骤如下： 步骤 1 初始化。基于 {c0 a} ={ca(0)} ，依次检查每一个 rs ，并将 r,s 间交通 = qrs ，得到 {x1 a} ， rs ，其流 OD 对 r,s ，求得的 r,s 间的最短路径 k 0 流量 qrs 全部分配到路径 k 0 rs 上，即 hrs k 0 rs rs 加入已配流集合 Kˉ 令 n = 1 ，同时将最短路径 k 0 量 hˉrs = qrs 。 k 0 rs 步骤 2 更新。令 cn a = ca(xn 步骤 3 下降方向。基于 {cn a),∀a ∈ A 。 a} ，依次检查每一个 OD rs ，并将 r,s 间交通流 = qrs ，得到 {y n a} 。 对 r,s ，求得的 r,s 间的最短路径 k n rs 上，即 hrs 量 qrs 全部分配到路径 k n k n rs 步骤 4 搜索步长。采用二分法等方法求解满足 Z[xn a)] 的 αn 。 a + αn(y n a - xn min 0 ≤ αn ≤ 1 步骤 5 移动并更新路径流量。 步骤 5.1 移动。令 xn + 1 步骤 5.2 依次检查每一个 OD 对r ，s，更新路径流量。 rs ∈ Kˉ )αn ， rs 上的流量 hˉrs + (qrs - hˉrs rs ，路径 k n a + αn(y n a = xn a - xn a) 。 = hˉrs k n rs k n rs k n rs 如果 k n rs ，路径 k 上的流量 hˉrs k = rs ，路径 k n rs 上 rs 加入已配流集合 Kˉ 对于其他任意 k ∈ Kˉ ，且 k ≠ k n hˉrs k - hˉrs 的流量 hˉrs k n rs k αn ，否则，将 k n = qrsαn 。 步骤 6 结束条件。如果 ∑ (xn + 1 a - xn a)2 ∑ a xn a ≤ ε ， a 程序结束；否则 n = n + 1 ，转至步骤 2。 4 算法复杂度分析 算法中增加存储已配流路径集合及其交通流量的 变量 hˉrs k (k ∈ Kˉ rs) ，随着迭代次数的增加，r - s 间新的最 短路径的递增，集合 Kˉ rs 不断增大，尽管只有部分路径 会分配流量，但最坏的情况下，集合 Kˉ rs 中元素的数量 | Krs ，其对应的变量 可能会达到 r - s 间所有路径的个数 | hˉrs | Krs ，所以新增步 k 的元素个数随着迭代次数增加至 | | Krs 个元 骤在内存方面，对应每对 r - s 间增加最多至由 | 素组成的集合及其流量 hˉrs k 所占存储空间，但这些变量 为求解路径交通量必要的输出变量，所以求解路径交通 量算法无可避免。 在计算时间复杂度方面，假设交通网络节点个数为 n ，OD 对的个数为 g ，Frank-Wolfe 原算法在求解交通流 量分配时的迭代数为 l ，步骤 3 中要针对每个 OD 求最 短路径，目前求最短路径比较稳定的算法，如 Dijkstra 算 法，时间复杂度为 O(n2) ，其他步骤时间复杂度均不超过 步骤 3，所以对于给定的问题，原算法的时间复杂度为 O(gln2) 。修改后的步骤 5 由于要对所有 OD 已分配流 量的路径遍历进行比较，而 r - s 间所有路径的个数最大 为 n(n - 1) ，所以新增部分时间复杂度仍为 O(gln2) ，因 此，增加求解路径交通量步骤后，Frank-Wolfe 算法时间 复杂度仍为 O(gln2) 。 5 算例分析 为了验证改进算法的有效性，首先通过一个简单的 交通网络流量分配案例中路径交通量的求解来分析一 下。对于图 1 的交通网络（箭头上标示函数为阻抗函 数），其中 OD 间交通需求量为 1-4：20，1-3：15，2-4：10， 算法采用 MATLAB 编程实现，设置终止条件 ε = 0.005 ， 运行过程迭代 9 次，运行结果如表 1 所示，流量数据取小 数点后四位，交通流量分配结果正确。 c(x) = 1 + 2 x c(x)=1+3x ① ② ③ c ( x ) = 1 + x c(x)=1+4x c(x) = 1 + 2 x ④ 图 1 测试网络及阻抗函数 计算机工程与应用www.ceaj.org

216 2018，54（9） Computer Engineering and Applications 计算机工程与应用 表 1 通过改进算法计算所得的路径流量 OD 需求量 qrs 路径 k 交通量 hˉrs k 1-4 1-3 2-4 20 15 10 1-2-4 1-3-4 1-2-3-4 1-3 1-2-3 2-4 2-3-4 路段流量 xa 8.246 3 6.316 7 5.437 0 10.902 6 4.097 4 4.436 0 5.564 0 路径交通量分配到路段上的流量 1-2 8.246 3 — 5.437 0 — 4.097 4 — — 1-3 — 6.316 7 — 10.902 6 — — — 17.780 8 17.219 2 2-3 — — 5.437 0 — 4.097 4 — 5.564 0 15.098 4 2-4 8.246 3 — — — — 4.436 0 5.564 0 12.682 3 3-4 — 6.316 7 5.437 0 — — — — 路径阻抗 88.290 9 88.293 0 88.295 2 52.657 7 52.659 9 51.729 4 51.733 7 17.317 7 — 然后通过 MATLAB 编程生成较复杂的交通网络 （图 2）进行实验，采用美国联邦公路局阻抗函数 c(x) = t0(1 + α(x/c0)β) ，其中 t0 为自由流时的阻抗，c0 为路段通 行能力，α 、β 为回归系数。在编程时以上参数均采用 随 机 方 法 生 成 ，t0 取 值 范 围 [0.01，0.1]，c0 取 值 范 围 [700，800]，α 取值范围为[0.16，0.18]，β 取 4，设置终止 条件为 ε = 0.005 。 ① ③ ⑥ ② ④ … ⑤ … … … … n2-2 … n2-1 n2 … n × n 个节点构成的交通网络 图 2 采用改进后的算法，通过 MATLAB 编程进行以下 两组实验来求解路径交通量，Δt 表示同等网络结构和 O-D 对数目下“改进后的 Frank-Wolfe 算法”与“Frank- Wolfe 原算法”运行时间差。（1）n =50 时，网络共有 2 500 个节点和 9 800 条边，实验中分别随机选取 10 到 100（以 10 为单位递增）个 OD 对进行 10 次计算，获取每个 OD 各自的路径流量，通过程序运行观察 Δt 值的变化；（2） n 分别取 10 到 100（以 10 为单位递增），随机选取 50 个 OD 对进行 10 次计算，获取每个 OD 对各自路径的流量， ® 通过程序运行观察 Δt 值的变化 。运行平台为 Intel i5-3470 3.20 GHz CPU，4.0 GB 内存的个人计算 Core 机，程序运行时间如表 2 和表 3 所示。设置终止条件为 ε = 0.005 ，通过两组实验均能在有限时间内获取所有 OD 对间的路径流量，通过统计程序中各个步骤的运行 时间，改进后的算法较原算法 Δt 变化趋势如图 3 所示。 ™ 表 2 改进行后的算法与原算法运行时间比较 表 3 改进行后的算法与原算法运行时间比较 （n = 50 ，OD 数量从 10 到 100） （n 从 10 到 100，OD 数量 50） 节点数 n × n OD 对数 迭代 次数 Frank-Wolfe 原算法 运行时间/s 改进后的 Frank- Wolfe 算法 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 10 20 30 40 50 60 70 80 90 100 11 10 12 11 11 13 12 10 12 12 103.304 4 133.361 6 216.915 6 245.305 9 292.420 2 416.178 7 425.523 3 382.113 8 530.358 5 584.916 3 103.324 2 133.385 5 216.963 9 245.359 2 292.486 7 416.288 9 425.632 4 382.200 9 530.499 3 585.073 1 Δt 0.019 8 0.023 9 0.048 3 0.053 3 0.066 5 0.110 2 0.109 1 0.087 1 0.140 8 0.156 8 节点数 n × n OD 对数 迭代 次数 100 400 900 1 600 2 500 3 600 4 900 6 400 8 100 10 000 50 50 50 50 50 50 50 50 50 50 11 10 12 11 11 13 12 10 12 12 Frank-Wolfe 原算法 19.889 4 58.753 1 106.463 8 164.904 1 222.462 8 367.106 0 499.704 9 683.193 7 862.700 6 1 033.080 6 运行时间/s 改进后的 Frank- Wolfe 算法 19.977 4 58.847 1 106.570 5 164.997 6 222.531 9 367.185 5 499.788 3 683.274 6 862.802 7 1 033.179 7 Δt 0.088 0 0.094 0 0.106 7 0.093 5 0.069 1 0.079 5 0.083 4 0.080 9 0.102 1 0.099 1 步骤 5 运行时间 线性（步骤 5 运行时间） 0.20 0.15 0.10 s / t Δ 0.05 0.20 0.15 0.10 s / t Δ 0.05 步骤 5 运行时间 线性（步骤 5 运行时间） 0 1 2 3 4 5 6 O - D /10 7 8 9 10 （a）实验一 0 1 2 3 4 5 6 n /10 （b）实验二 7 8 9 10 图 3 两组实验中步骤 5 的运行时间 计算机工程与应用www.ceaj.org

柴 获，何瑞春，马昌喜，等：用于求解路径交通流量的改进 Frank-Wolfe 算法 2018，54（9） 217 实验结果表明，在交通网络结构不变的情况下，改 进后的算法运行时间与原 Frank-Wolfe 算法运行时间相 比，随着输入 OD 对数量的增加，Δt 随之增大，折线图 显示变化趋势接近线性（图 3（a））；在 OD 对的数量不 变，交通网络的节点和边的数量增加的情况下，Δt 变化 不明显，而且接近某个恒定值（图 3（b））。同时，由于已 配流路径的数量总是小于或等于迭代次数，通过对两组 实验中运行时迭代次数分析，已配流路径的数量与节点 个数及 OD 对数的变化关系不明显，改进过程中增加的 新变量所需内存的数量并不会随着节点个数及 OD 对 数的增加而大幅增加。 为进一步说明该方法的可行性及有效性，将采用实 际的城市交通网络 Sioux Falls[4]网络和兰州市主城区交 通网络，仍然采用上述实验计算机，分别使用本文所给 出的方法和文献[13]所提算法（目前在 VISUM 中验证过 的基于路径交通流量分配算法）对这些网络进行求解， 在相同的计算精度 (ε = 0.005) 要求下均能获得路径交通 流量，程序运行时间见表 4。 表 4 采用实例的计算结果 节点数/ 边数 24/76 OD 对数 10 运行时间/s 文献[13]算法 本文算法 59.236 0 18.365 2 623/1 357 50 365.857 4 173.382 0 网络 Sioux Falls 兰州市主城区 交通网络 6 结束语 本文在改进 Frank-Wolfe 算法的基础上，给出一种 路径交通量求解算法，与其他基于路径的交通流量分配 求解算法不同，是对基于路段算法的扩展，通过算法分 析和算例验证，得出以下结论： （1）该方法能够避免穷举交通网络中所有路径，利 用 Frank-Wolfe 算法在求解交通流量分配问题上独特的 优势，在增加有限的时间与空间成本情况下，计算路段 交通流量的同时能够获取路径交通流量。 （2）与 Frank-Wolfe 原算法相比，在节点及边的数不 变，OD 对的数量增加的情况时，改进部分的运行时间随 OD 对数量成线性增加；在 OD 对的数量不变，交通网络 的节点的数量增加的情况时，改进部分的运行时间接近 于某一固定值，不会随交通网络节点的增加而增加。 （3）文中算法步骤及算例均针对用户均衡的流量分 配，由于算法改进部分不涉及目标函数，所以改进算法 仅需修改目标函数后直接用于求解系统最优的流量分 配问题。 参考文献： [1] Wardrop J G.Some theoretical aspects of road traffic research[C]//Proceeding of the Institution of the Institu- tion of Civil Eng，1952：72-73. [2] Beckmann M J，Mcguire C B，Winston C B.Studies in the economics of transportation[J].Economic Journal，1955，26 （12）：820-821. [3] Frank M，Wolfe P.An algorithm for quadratic program- ming[J].Naval Research Logistics Quarterly，1956，3（1/2）： 95-110. [4] Leblanc L J，Morlok E K，Pierskalla W P.An efficient approach to solving the road network equilibrium traffic assignment problem[J].Transportation Research，1975，9（5）： 309-318. [5] Leblanc L J，Helgason R V，Boyce D E.Improved effi- ciency of the Frank-Wolfe algorithm forconvex network programs[J].Transportation Science，1985，19（4）：445-462. [6] Lee D H，Yu N.Accelerating strategies and computational studies of the traffic assignment problem[J].Transportation Research Record Journal of the Transportation Research Board，2001，1771 （1）：97-105. the Frank- Wolfe algorithm for [7] Gao Z Y，Lam W H K，Wong S C，et al.The conver- gence of equilibrium algorithms with non- monotone line search technique[J].Applied Mathematics & compu- tation，2004，148（1）：1-13. [8] Leventhal T L，Nemhauser G L，Trotter L E.A column traffic assignment[J]. generation algorithm for optimal Transportation Science，1973，7（2）：168-176. [9] Bar-Gera H.Origin-based algorithm for the traffic assign- ment problem[J].Transportation Science，2002，36（4）：398-417. [10] Dial R B.A path- based user- equilibrium traffic assign- ment algorithm that obviates path storage and enumer- ation[J].Transportation Research Part B：Methodological， 2006，40（10）：917-936. [11] Bar- Gera H，Boyce D.Route flow entropy maximiza- tion in origin-based traffic assignment[C]//14th Interna- tional Symposium on Transportation and Traffic Theory， 1999. [12] Boyce D，Xie J.Assigning user class link flows uniquely[J]. Transportation Research：Part A Policy & Practice， 2013，53（3）：22-35. [13] Gentile G.Local user cost equilibrium：A bush-based algorithm for traffic assignment[J].Transportmetrica，2014， 10（1）：1-40. [14] Chen A，Jayakrishnan R，Wei K T.Faster Frank-Wolfe traffic assignment with new flow update scheme[J]. Journal of Transportation Engineering，2002，128（1）：31-39. [15] 李峰，王书宁 . 基于 Frank-Wolfe 算法的路径交通量求解 方法[J]. 吉林大学学报：工学版，2005，35（6）：632-636. [16] 李峰，王书宁 . 基于终点的路径交通量求解方法[J]. 清华 大学学报：自然科学版，2006，46（1）：149-152. 计算机工程与应用www.ceaj.org