改进的交通分配起点用户均衡算法

摘  要：对起点用户均衡算法的流量转移、起点限制子网(Bush)的更新、成本更新策略及计算流程等关键问题进行了分析改进。探讨了Bush的最长最短路径对查找方法，提出了流量转移的步长搜索方法及加速算法收敛的Bush更新方法，优化了适合多线程开发的算法流程。使用不同规模的城市交通网络模型进行了算法效率测试，并和其他算法进行了对比，结果表明算法效率有较大的提高，可满足大规模城市交通网络模型计算速度和精度的要求。

关键词：用户均衡交通分配，起点用户均衡算法，无环网络

研究背景

交通分配是交通需求模型的重要构成部分，它描述的是出行者如何在交通网络上选择出行路径。假定在信息完全的情况下，出行者会选择成本最小的路径。Wardrop[1]早在1952年给出了用户均衡（UE）的定义，1Beckmann[2]随后构建了用户均衡交通分配的数学模型，但这一理论直到1975年Leblanc[3]将Frank-Wolfe 算法（简称FW算法）应用到交通分配问题，才得到了广泛地应用。从模型应用的角度，交通规划师和软件工作者面临两个实际问题：交通分配达到什么样的精确度才能满足定量分析的要求？是否有更为高效的算法在最短的时间内达到所要的精度？Boyce等[4]以费城的两条快速路间的一对匝道建设方案使用交通分配模型进行影响范围分析为例，指出相对误差至少要小于1.0e-4，交通分配解的结果才比较可靠。Slavin等[5]等对华盛顿都市规划区路网进行分析，也发现相对误差达到1.0e-4以后，路段的流量解才能和算法高度收敛后得出的精确解基本一致，否则不能满足规划分析的需要。最近Slavin等又用交通分配模型对华盛顿的交通改善项目进行评估，例如增加一个路段的车道数目、新建一座桥梁等。结果表明，相对误差在1.0e-2和1.0e-3的时候，项目的影响范围杂乱无章，毫不相干的某些地区的局部道路的交通量也会有很大的变化，这明显不符合实际情况。而同样的模型输入，当相对误差达到1.0e-4或1.0e-5后，项目的影响主要结果主要集中其周边地区和相关路段，给出的评价结果是可信的。由此可见交通分配求解精确度的需要达到一定程度的重要性。众所周知，FW算法的一个很大的缺点是算法后期收敛很慢，特别是针对大型交通网络，很难在短时间内收敛到理想的精确度。例如上海的多车种分配模型，即使是性能很好的工作站，用FW算法大约需要3个小时才能得到上述相对满意的精度。随着交通网络拥挤程度的增加，收敛速度将变得更慢。交通分配模型需要对不同的需求状态、基础设施供给方案及其他模型参数进行调试运算，大量的运算时间已经成为有效应用交通模型的一个瓶颈。

半个多世纪以来，国际范围内的学者们一直在寻求更为高效和高精度的算法，并形成了基于路段、路径和起点三大类算法。1999年以色列学者Bar-Gera[6]和美国学者Dial[7]提出的起点用户均衡算法，使得寻求快速而精确的交通分配算法成为新的研究热点。Bar-Gera的算法结果表明其OBA(Origin Based Assignment)算法相比F-W算法效率有了明显改进。Daneva、Saïda Arrache等人也试图对FW算法进行改进，前者的测试表明收敛速度稍逊于Bar-Gera的OBA算法。Cube软件对Daneva的改进FW算法进行了开发。Dial在单个起点收费模型的研究基础上，提出了B算法，效率相比Bar-Gera又有了明显地提高。同时，TransCAD软件以B算法为原型，开发了OUE(Origin User Equilibrium)算法；SATURN软件则开发了Bar-Gera的OBA算法，Florain[8]随后也改进了基于路径的投影算法[9]，并在EMME软件中开发了新的模块，指出其计算速度和起点用户均衡算法相当。罗马的Gentile[10]又提出了基于终点的LUCE算法，并开发到VISUM软件中。Bar-Gera新近又提出了TAPAS算法，相比他的OBA算法有了更高的效率。不同商业软件开发者和学者的测试结果都表明实现的算法速度较快，但算法自身的特点、实现的代码编写过程、测试用的输入数据和计算机硬件平台的不同，使得这些算法很难有一个公平的平台进行比较。鉴于此，Marco[11] [12]最近分别编写了OBA算法（以及他的改进OBA算法）和OUE算法的代码并对多个路网在同一台计算机上进行了测试，结果表明OUE算法比较优秀。尽管上述算法的基本原理在相关文献中都有介绍，但算法的具体实现往往属商业秘密，很多关键细节问题尚未有公开的讨论。本文中总结上述算法的优点的基础上，提出OUE算法的改进方法，讨论算法实现的关键问题，并在大规模交通网络上来测试算法的效率。

2 起点用户均衡模型及算法

起点用户均衡算法的基本思想是将整个均衡分配问题分解为一个起点到所有讫点的均衡分配问题。Bar-Gera指出Beckmann的变换式可以改写成基于起点路段流量的形式：

起点用户均衡算法的基本思想有两个要点：

（1）一个起点到所有讫点的出行所使用到的路网是一个无环网络，Bar-Gera称之为限制子网（Restricting Sub-Network），Dial则称之为Bush。利用无环网络的节点拓扑排序，可以十分高效地同时计算最短和最长路径（交通网络一般是有环的，最长路径的求解尚未有成熟的算法，这也就是Dafermos很早就提出交通分配可以将流量在最短和最长路径之间转移的思想但无法实现的原因）。

（2）流量从成本大的路径转移到成本小的路径，并在保证Bush无环的基础上，更新Bush以求找到成本更小的路径。Dial与Bar-Gera的算法具有相同的构思，不同之处在于前者只将最长路径的流量转移到最短路径，后者则将所有路径的流量转移到最短路径。Dial的方法比较简洁，它在最长路径和最短路径之间实现均衡。LUCE算法是基于讫点的，其本质和基于起点是相同的，也是保证有一个无环的Bush，另外，流量转移量是将路径成本线性化后计算得到的，这也是其算法名称的由来，和Dial思想基本一致，只是增加了寻找最优流量转移步长的步骤。

图1 最长路径和最短路径之间的流量转移方法

算法主程序：

Step1 流量转移内循环（Bush得到稳定后，流量转移内循环是必要的）。

Step1.1 对每个起点的Bush进行流量转移：计算起点的最长最短路径，反拓扑顺序方向扫描所有节点，如果进入节点的最长路径和最短路径的路段相同，跳到下一个节点。否则，寻找该节点上游最近的最长、最短路径共同节点，得到两条路径段并转移流量。

Step1.2 更新路段的成本和成本导数值。满足内循环收敛条件则转Step2，否则转Step1.1。

Step2 对所有起点的Bush进行更新。先计算流量转移后Bush的最短和最长路径，删除Bush中无流量的路段，将新的路段加入Bush中，以产生成本更小的路径。如果Bush得到更新则要重新拓扑排序。满足收敛条件则退出，否则转Step1。

从计算流程来看，起点用户均衡算法的思路相当清晰，容易理解。然而，要高效地实现这个算法，却有很多具体问题值得改进和探讨。

3 算法实现的关键问题分析及效率测试

3.1 流量和成本更新策略

（1）流量更新流程。起点用户均衡算法的是将整个均衡分配问题分解为一个起点到所有讫点的均衡分配问题。有两种计算流程值得讨论：

方法一：一个起点Bush进行流量转移，接着更新Bush，循环操作直至起点Bush到达设定的均衡解，更新成本和导数值后，再对下一个起点的Bush进行均衡分配，直至所有起点的Bush执行完毕。由于成本更新，先执行的起点Bush均衡会受到破坏，因此上述流程需要多次循环（即外循环）才能达到所有起点Bush达到均衡。Dial建议迭代到一个起点的Bush不再更新为止，再进入下一个起点。

方法二：即本文节2提出的方法。

一个起点Bush的均衡解是整个交通分配的子问题，方法一在每次内循环中求解一个起点Bush的精确值解对整个算法的收敛效果并不明显。在四阶段组合模型中，Boyce，Zhang等的算法测试发现，交通分配在每次主循环计算中得到最短路径分配解和精确的均衡解两种方法想比较，整个组合模型的收敛速度前者要快得多。这两个算法，子问题和模型整体的收敛特性的关系具有相似性。因此方法二是可以比较快速收敛的，这和Marco的研究结论也是一致的。不过Marco建议起点Bush的流量转移需要设置内循环，只有当一个起点Bush的流量转移内循环使得局部均衡达到较高程度时，才进行Bush的网络更新。Bar-Gera则指出他的OBA算法中，起点的限制子网（即Bush）能够很快稳定，因此增加流量转移的内循环是高效的。笔者的OUE算法测试中，只对一个起点Bush的流量转移循环两次，并不考虑其收敛精度。因为Bush更新要比流量转移的计算开销小得多，使用较长的时间来计算精确的局部均衡解，对整个算法的收敛并没有好处。笔者也测试了不同内循环次数下的算法总体收敛情况，发现同一网络并不是内循环的次数越多收敛越快；次数相同的内循环，在不同网络中相对于两次内循环的收敛速度有快有慢。因此留给我们的问题是，为了提高算法的总体收敛速度，起点Bush的流量转移相对误差达到什么样的精度时，内循环就可以结束？

（2）成本和成本导数更新流程。在什么时候更新成本能够加速收敛是各种交通分配算法中遇到的普遍性问题。例如FW算法中，一个起点到所有讫点的所有流量加载完后立即进行成本更新，相对于整个最短路径分配完成后进行成本更新，从理论上说会加速收敛，这也就是常见的Gauss-Seidel方法。但是在程序执行过程中，额外地增加成本更新计算量也增加了很多开销，FW收敛速度受到了抵消，并不能加快多少。因此Gauss-Seidel方法是否有利于加速收敛可能因算法的特性而异，要根据实际网络的测试才能得出结论。起点用户均衡算法的流量更新步骤Step1.1中，笔者经过多个大型交通网络测试发现，每个起点Bush流量更新后，立即更新路段的成本有利于收敛加速。另外，笔者的测试也发现，每个起点Bush流量更新后，更新路段成本的导数值，反而会使收敛大大减慢，这可能和笔者所用的流量更新量计算方法有关。当然，为了给Bush的网络更新做准备，Step1.2的成本和成本导数值更新是必需的。这是因为Bush网络更新需要准确的最长最短路径成本值以保证在更新过程中，Bush网络保持无环特性。

（4）最长最短路径段成对节点的查找方法。在流量转移过程中，首先要找到最长最短路径中路段组成不同的路径对，反拓扑顺序首先找到进入的最长路径和最短路径路段不同的节点，称为路径段头节点Head，然后找到两条路径的上游共同节点，称为路径段尾节点Tail。流量是在Head和Tail之间转移的。路径段尾节点Tail的查找方法有两种。方法一：定义数组MinTree[|N|]，初始化为0，找到Head后，沿着最短路径回溯到起点，记录所有节点的对应数组值为1，然后从Head开始沿最长路径回溯，如果遇到数组值为1的节点，则找到了路径段尾节点Tail。方法二：找到Head后，最长路径向起点回溯一个节点，最短路径回溯到，循环进行，直至两条路径找到相同的节点Tail。方法一需要分配额外的内存，但最短路径只要回溯一遍，相比方法二，算法复杂度应该要小一些。但笔者在实际测试过程中，发现两种方法对收敛速度并没有明显的差别。

流量转移算法的完整过程如下：

流量转移最后要说明的两个技巧：一是最长路径必须在流量大于0的路段上构建，这样对流量转移才有意义，能加速收敛。二是路段残余流量会影响Bush的更新。由于计算机浮点数计算存在误差，路段流量可能在转移后会产生一个很小数值，因此程序必须设定路段流量的精度值，根据多个网络的计算测试经验，一般来说1.0e-12是比较合理的。另外，如果流量转移中不是浮点数计算误差造成，而是流量转移后确实存在一个很小的流量，那么在流量转移的时候需要事先把它完全转移干净。这两个因素都会影响Bush的更新，导致算法无法进一步收敛。Florain的投影算法中，建议去除OD对流量较小的交通需求（例如小于0.1），以提高算法收敛速度，笔者认为这种方法并不合适，即使是很小的OD对流量，大量的OD对可能会累加成较大的路段流量，和本文谈到的路段流量的微小流量去除本质上是不同的。

3.2 Bush构建和更新策略

3.3 收敛指标相关问题

交通分配的收敛指标一般用相对误差来表示，形式较多，常见的有两次迭代的目标函数变化相对值和路段流量差相对值。Dial指出可以用OD对之间的最长路径和最短路径之差来衡量，这个方法比较形象地表述了用户均衡分配的概念，不过FW算法没有最长路径计算，得不到这个指标。为了对比不同算法的效率，本次测试的收敛指标和TransCAD所用指标相同：

1.png

 式(9)表示当前解与当前流量状态下最短路径解的所有路段成本的相对差异，如果这个数值很小，说明出行者几乎无法通过改变路径来降低自己的出行成本，描述的是一种用户均衡状态。

值得一提的是，起点Bush的最短路径是在限定的Bush中计算出来的，如果Bush还可以优化而没有很好地优化，程序计算后期就变成在非最优的Bush中进行流量转移，此时式(9)的相对误差值仍然可以不断减小，从而造成了算法收敛的假象。因此，在确定程序计算结果之前应进行检验，若在整个网络中计算OD对的最短路