交通网络平衡配流模型算法研究★

杨 海 飞

(河海大学土木与交通学院，江苏 南京 210098)

1 交通配流基本原理与常用模型

1.1 交通配流问题的基本原理

交通网络分配问题是将实测或预测的交通分布量按照特定的出行规则分配加载至具体的道路网中，并根据相应算法求解得到各道路路段与交叉口节点的交通流量。交通分布量，即OD交通量，是出行起讫点小区重心之间的交通量，即从出发起点至出发目的地之间的交通流量。通常情况下，对于特定城市或区域，任意出行端点之间具有多条出行路径，因而，通过科学的原则和高效的算法将OD交通量合理的分配在出行起讫点之间的各条路径上(包括路段与节点)是交通配流需要解决的核心问题。

1952年，Wardrop首次提出了道路网平衡的概念和定义[1]，即Wardrop第一原理和Wardrop第二原理。

Wardrop第一原理亦称为用户平衡原理(简称UE)，其定义是指：在道路网上行驶的车辆驾驶员都明确清楚当前道路网络的交通运行状态，并在选择最短出行路径过程中使得道路网络达到平衡状态。所谓平衡状态是指路网中每个OD对之间所有被使用的通行路径具有最短的出行时间或最小的出行阻抗，而没有被使用的路径通行时间一定不小于被使用路径的最小出行时间。满足以上原理的交通配流模型即称为用户平衡模型(UE模型)。

Wardrop第二原理亦称为系统最优原理(简称SO)，其定义是指：考虑交通拥堵水平对出行阻抗的影响，道路网络中的交通流量应当以特定规律加载分配，从而使得网络整体的总出行时间达到最小。系统最优化模型为交通规划管理人员提供了一种决策方法。

进行交通配流的前提条件是已知OD交通量、网络图和网络中各路段的走行时间函数。而走行时间—交通流量函数可表达为：

ta=f(qa)

(1)

其中，ta为路段a的走行时间;qa为路段a的交通流量。被广泛应用的走行时间函数的是由美国公路局开发的BPR函数，其形式为：

(2)

1.2 交通网络配流模型

1.2.1非平衡配流模型

非平衡配流模型结构形式简单、参数标定明确、求解算法快速，在满足精度要求的情况下，是交通规划与交通管理等工程实践的重要配流方法。

1)“全有全无”配流法。“全有全无”法[2]是最简单最基本的配流方法。该方法具有以下两个特点：首先在配流过程中不考虑交通拥堵情况对道路出行阻抗的影响，即认为路网范围内所有路段的出行阻抗为常数，不会随着道路交通量的变化而变化；其次是认为驾驶员对道路路径的选择具有同质性，即同一OD对之间所有驾驶员都将选择相同的路径行驶。该配流模型的求解过程相当简便快速，计算效率高，然而所面临的主要问题是交通量在路网上的分配极度不均，全部集中在初始最短路，造成不同路段间的交通量差异悬殊，与实际的道路交通状况显著不符。通常城市交通网络的配流问题不宜直接采用“全有全无”法，但该方法可作为多种复杂配流模型的基础算法。

2)增量配流法。增量配流法[3]是一种模拟平衡的配流方法。该方法的基本思想是将OD交通量按照特定的比例循环分批加载至路网当中(加载运用“全有全无”算法)，并且每次加载循环结束后，根据当前各路段的交通量情况重新计算路网的出行阻抗或出行时间，在接下来的循环中将下一批交通量加载至当前最短路径上。增量配流算法的计算过程简单，计算精度可根据OD量的加载循环数进行控制，因此在工程实践中得以广泛应用。该方法仍然是一种近似方法，一般情况下，得不到平衡解。

3)连续平均法。连续平均法[4]是在增量配流法基础上对平衡配流原理的进一步模拟，其基本思路是反复优化已加载至路网上的交通量，使之在迭代过程中逐渐接近或达到平衡交通量。在每一阶段的循环过程中，根据增量分配法已加载的各路段交通流量，应用“全有全无”算法额外进行一次配流得到附加交通量，随后将上次循环得到的配流交通量与附加交通量进行加权平均处理，从而得到本次循环的加载交通量。算法结束的依据是相邻循环的分配结果误差应小于一定阈值。连续平均法是简单实用却又最接近于平衡配流法的配流方法。

1.2.2交通网络平衡分析模型

平衡配流模型通常被分为用户平衡模型(UE)，随机用户平衡模型(SEU)以及动态用户平衡模型(DUE)三类。本文重点研究用户平衡模型(UE)。

用户平衡模型(UE)中，OD矩阵在整个交通量加载过程下保持恒定。通常情况下，UE问题的求解需要抽象出一个高维凸优化模型，可运用遗传算法等现代化智能化算法求解。Bechman提出了经典的固定需求式用户平衡模型，其数学表达式如下：

(3)

平衡交通流配流模型具有明确的理论意义，模型结构严谨，参数含义明确，比较适用于理论和宏观层面的研究。然而，这类模型通常具有较多的优化变量，导致数学模型维数高，约束条件苛刻，求解算法十分复杂，运算效率较低，尽管当前学者提出了一系列智能算法，但计算理念和过程较为复杂，在工程实践应用中具有一定难度。

2 改进的平衡配流算法

Beckman提出了关于交通配流的数学规划模型，但在整整20年后LeBlanc 等学者才开始用Frank-Wolfe算法求解Beckman模型，形成了目前广泛应用的F-W法。F-W法是用线性规划逐步逼近非线性规划的方法来求解平衡模型的。其主要算法步骤如下所示：

Step3：计算迭代步长，按照下式求参数αn。

(4)

从上面的算法步骤可以看出，F-W法是一种迭代算法。影响迭代算法的解最后能否收敛到平衡解的因素很多，其中，初始解的选取很大程度上决定了F-W算法最后能否收敛到平衡解以及收敛速度的快慢，初始解越接近平衡解计算就越容易收敛，迭代步骤也就越少。本文就从计算初始解的方法上来改进平衡配流算法。

由以上步骤，传统的F-W算法是通过应用“全有全无”配流的方法来获得初始各路段的交通量的，然后进行迭代计算。“全有全无”配流法是一种十分粗糙的算法，最后配流的交通量与实际的路网交通流状态相差甚远，自然用这种方法求得的初始解与平衡解也就相差很多。

本文研究提出的改进平衡配流法中的初始解拟采用连续平均法来代替“全有全无”最短路配流。

连续平均法是非平衡算法中最接近于平衡算法的一种方法，可以很快的接近平衡解，所以可以用来代替“全有全无”配流法来求解平衡解的初始解。连续平均算法的计算步骤如下：

Step2：按照上一步Step1计算的各路段出行阻抗和OD量，并进行一次“全有全无”分配，得到各路段的附加交通量Fa。

(5)

连续平均法和F-W法相比，核心区别在于如何确定移动步长αn/φ(相关平衡分配模型是以严谨的数学原理为基础的，因此可以求出平衡解；而连续平均法是由计算者自己定，可以取常数，也可以定为变数。定为常数时，一般取0.5，定为变数时一般取1/n(n为循环次数)。由于连续平均法只是用来求初始解，为了减少计算时间，故可以将其收敛准则适当放宽，通过预先规定迭代循环次数的方法来命令求解过程停止。

改进的平衡配流算法计算步骤：

Step3：计算迭代步长，按照下式求参数αn。

3 实例计算与结论

根据张家港市交通规划资料，应用改进平衡配流算法对早高峰交通量进行分配。结果分析：经过计算，应用改进平衡配流算法对路网进行配流所需时间为传统方向搜索算法的(即F-W算法)60%左右，迭代次数是7次，而改进平衡配流算法的配流结果与传统算法的配流结果相差无几，交通量相差在5%以内的路段占到路段总数比例的91.5%，超过10%的仅占1.9%。经过上述的评测分析，本文把交通非平衡配流方法运用到交通平衡配流中的改进平衡配流法，迭代次数减少，在一定程度上减少了运算时间，提高了计算精度，进一步优化了求解平衡配流问题的传统算法。

本文在总结传统平衡与非平衡分配算法原理的基础上，提出将非平衡算法与平衡算法进行结合，以提高算法的运行效率。结合实例发现，本文提出的改进平衡分配算法能够显著提升交通分配计算速度，为相关交通规划的实践应用提供了一种高效的交通需求预测方法。