基于可替换路径对的多用户均衡交通分配算法

吴超峰，龙建成，刘昊翔

(合肥工业大学汽车与交通工程学院，安徽 合肥 230009)

交通分配作为“四阶段”交通需求预测中最后一个阶段，其模型及算法在过去几十年中一直被广泛研究。随着城市规模的扩大以及交通需求预测准确性要求的提升，对交通分配的精度和效率的要求越来越高，传统基于Frank-Wolfe的交通分配算法[1]已经无法满足实际应用，高精度和高效率的交通分配算法逐步被开发出来。例如，Bar-Gera[2]基于方向比例的概念提出了基于起点的交通分配算法，很大程度上提升了静态交通分配问题的求解效率和精度。Dial[3]依据路径流量从费用最大的路径调整到费用最小的路径的原则，提出了另一种基于起点的交通分配算法。Nie[4]提出了改进的基于起点的交通分配算法。Bar-Gera[5]提出了基于可替换路径对的交通分配(traffic assignment by paired alternative segments，TAPAS)算法，把静态交通分配问题的求解效率提升到了新的高度。Xie等[6]提出了改进的TAPAS算法，进一步简化了算法的结构，并提高了算法的效率。目前，基于可替换路径对类的算法还只被用于求解传统的静态交通分配问题。

大多数交通分配问题的研究都假设路网中所有用户同质，即所有用户都遵循相同的出行选择准则，如用户均衡(user equilibrium，UE)，或者系统最优(system optimum，SO)[7]。然而，现实中用户出行选择准则异质普遍存在。近年来，随着路网中基于APP的电召车以及基于网上购物的货运车辆的逐渐增多，加上传统的出租车、货运车辆以及普通的私家车等，使得路网的用户成分逐渐复杂，多用户均衡交通分配问题的快速、精确求解对新形势下的交通规划与管理尤为重要[8]。当前，对于混合多用户均衡交通分配问题的研究还不多。Harker[9]建立了混合多用户均衡交通分配问题的变分不等式模型，但只给出了解存在的条件。黄海军等[10]提出了在换乘场景下的组合出行方式下混合均衡分配的变分不等式模型。Yang等[11]提出了对角化方法结合相继平均法的算法来求解均衡交通分配问题，但算法的求解效率和精度都不佳。四兵锋等[12]根据政府政策和措施对出行者路径选择行为的影响，构建了双层规划模型描述了城市混合交通网络的系统优化问题，并采用对角化算法求解了下层混合交通网络的交通分配问题。Yang等[13]、Ceng等[14]在小型人工网络中研究了路段通行能力限制、网络拥堵等广义约束对混合均衡分配求解的影响。

本文针对混合多用户均衡交通分配问题的变分不等式模型，分别设计了基于用户类型的对角化算法和基于起点或OD对的对角化算法来求解混合多用户均衡交通分配问题，将TAPAS算法应用于求解该问题，并采用大规模交通网络验证算法的性能。数值结果表明,论文设计的算法可以解决已有算法求解混合网络均衡问题效率较低且精度不高的问题。

1 多用户均衡交通分配模型

多用户均衡交通分配问题可以描述为一系列变分不等式问题[11]：寻找一个向量x*∈Ω，使得

(1)

其中，Ω=∏φ∈ΦΩφ，Ωφ={x|Λfφ=qφ,Δfφ=xφ,fφ≥0}。

我们采用如下间隙函数来衡量多用户均衡交通分配问题求解算法的收敛精度：

(2)

2 多用户均衡交通分配问题的求解算法

我们把求解传统静态UE交通分配问题的TAPAS算法推广用于求解多用户均衡交通分配问题。为了比较分析算法的性能，我们还提出了对角化算法来求解多用户均衡交通分配问题。

2.1 基于可替换路径对的求解算法

2.1.1 可替换路径对算法的基本原理

2.1.2 可替换路径对流量调整子算法

如果Δx=0，则算法终止。

Step3：收敛判断。如果

则算法终止；否则，返回到Step1。

2.1.3 基于可替换路径对的多用户均衡交通分配问题的求解算法

我们采用如下基于可替换路径对的算法求解多用户均衡交通分配问题：

Step1：更新PAS集合。对每个起点r∈N和用户群φ∈Φ进行如下操作：

Step1.2：生成PAS。对最短路径树外的所有路段(i,j)，进行如下操作：

Step3：收敛检验。如果G(x)<ε，则算法终止；否则，返回到Step1。

算法Step1.2中第2步，可以采用Bar-Gera[5]提出的方法，也可以采用Xie等[6]提出的最大路段流量优先搜索法(Maximum-flow first search method, 简称MFS)从路段(i,j)出发寻找PAS(s1,s2)。由于MFS能够高效、准确地搜索到PAS，且得到的PAS还具有更好的流量调整潜力，本文将采用MFS方法来更新PAS集合。MFS的具体步骤可以参见Xie等[6]。

Xie等[6]研究了TAPAS类算法的复杂度，发现复杂度与网络包含的PAS数相关，而网络中PAS的数量又与网络规模和结构相关，相似规模的网络可能因为网络结构的区别导致PAS数量有巨大差别，因此TAPAS类算法的复杂度无法简单与网络的节点数、小区数、路段数等信息关联。本文给出的基于可替换路径对的混合均衡分配算法本质上也属于TAPAS类算法的一种，因此其复杂度也与PAS数相关，其具体的相关性则需要进一步研究。

2.2 基于用户类别的对角化算法

采用对角化方法求解多用户均衡交通分配问题的算法流程如下：

Step0：初始化。采用全有全无分配得到初始路段流量x0，设迭代次数n=0，收敛精度ε>0。

Step1：对角化。

Step1.1：设φ=1。

Step1.2：求解如下变分不等式问题：

cφ(xφ*,xφ-n)T(xφ-xφ*)0,∀xφ∈Ωφ

，

(3)

得到最优解xφ*。

Step2：收敛判断。若G(xn+1)<ε，则算法终止；否则，令n=n+1，转Step1。

在变分不等式(3)中，由于除第φ类用户以外的其他类型用户的流量固定，该变分不等式是一个单一用户的网络均衡问题，可以直接采用Frank-Wolfe、外梯度投影算法、基于起点的交通分配算法、TAPAS类算法等进行求解。

2.3 基于起点或OD对的对角化算法

我们可以把同一用户中同属于一个起点或OD对的出行者看成单独的一类用户。于是，基于用户类别的对角化算法可以直接推广应用于构建基于起点或者基于OD对的对角化算法。

3 数值算例

我们采用不同规模的网络来检验提出的算法的有效性见表1。所有算例都在一台配置Intel Core i5 3.10 GHz处理器和8 GB内存的计算机上采用Visual Studio C#编程实现。

表1 测试网络Table 1 The test networks

注：测试网络数据来源于http://www.bgu.ac.il/～bargera/tntp/。

3.1 算例设置

(4)

3.2 算法收敛效果对比

表2给出了4种算法在4个测试网络中的收敛情况。可以发现UDA与ODA相比，ODA对网络的规模更敏感，当网络较小时两个算法效率相近，当网络规模变大时ODA效率明显下降。而TAPAS在各种网络、各种收敛水平下都具有非常好的计算效率。

3.3 交通需求水平对算法收敛时间的影响

路网的拥挤程度对于交通分配算法的收敛性具有一定的影响。我们把Chicago Sketch网络的OD需求从50%依此递增10%到150%，并采用ODA、UDA和TAPAS等4种算法求解相应的多用户均衡交通分配问题。图1给出了各算法收敛所需要的计算时间。可以发现TAPAS相比UDA和ODA具有更好的稳定性，且对交通需求水平的敏感性较低。在其他3个网络的测试中，发现提出的算法在不同网络上具有相似的特性。

表2 各个算法在不同网络下的收敛效率对比

图1 交通需求水平对算法收敛时间的影响Fig 1 The effect of traffic demand on convergence time for each algorithm

3.4 用户比例对系统总阻抗的影响

由于UE用户和CN用户在出行过程中都没有完全考虑其出行带来的外部性成本，当系统中存在UE用户群和CN用户群时，整个网络的系统总阻抗很难到达系统最优状态。系统中UE用户和CN用户越多，则整个网络偏离系统最优越远。当网络中SO用户群占比接近100%时，UE用户与CN用户出行带来的外部性成本趋于零，从而系统总阻抗也趋于最低。

Yang等[11]在小网络中的计算结果表明SO用户群占据一定比例以后，整个路网的系统总阻抗可以降到最小。这表明网络的结构和规模可能是影响实现系统总阻抗最小所需的SO用户群占比的重要因素。本文在多个不同规模的交通网络上的计算结果表明，在多用户混合交通系统中，SO用户群占比接近100%时系统总阻抗才能够降到最低的现象可能在较大规模的网络中普遍存在。

图2 不同网络不同SO用户比例下的系统总阻抗Fig.2 The effect of the proportion of SO user on total system travel cost under different networks

3.5 交通需求水平对最优系统总阻抗的影响

图3 不同需求水平下不同SO用户比例下的系统总阻抗Fig.3 The effect of the proportion of SO user on total system travel cost under different traffic demand

4 结论

本文针对多用户均衡交通分配问题的变分不等式模型，在基于可替换路径对的UE交通分配算法基础上，分别设计了基于用户类别的对角化算法和基于起点或OD对的对角化算法，并与外梯度算法进行了对比分析。结果表明基于可替换路径对的多用户均衡交通分配算法无论是在小网络还是大网络上都有较高的计算精度，并有很好的计算效率。通过求解不同需求水平下的多用户均衡交通分配问题，发现基于可替换路径对的多用户均衡交通分配算法能保持较好的稳定性。通过算例，发现在不同规模路网中不同交通需求水平下，SO用户比例越大多用户均衡交通分配状态下路网系统总阻抗越小。下一步研究中，可以将本文提出的基于可替换路径对的多用户均衡交通分配算法推广应用于网络设计问题、道路拥挤收费、网络交通控制等交通规划与管理问题中。

参考文献：

[1]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.

[2]BAR-GERA H. Origin-based algorithm for the traffic assignment problem[J]. Transportation Science, 2002, 36(4):398-417.

[3]DIAL R B. A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration[J]. Transportation Research Part B, 2006, 40(10):917-936.

[4]NIE Y. A class of bush-based algorithms for the traffic assignment problem[J]. Transportation Research Part B Methodological, 2010, 44(1):73-89.

[5]BAR-GERA H. Traffic assignment by paired alternative segments[J]. Transportation Research Part B, 2010, 44(8/9):1022-1046.

[6]XIE J, XIE C. New insights and improvements of using paired alternative segments for traffic assignment[J]. Transportation Research Part B, 2016, 93:406-424.

[7]WARDROP J G. Road paper: Some theoretical aspects of road traffic research[J]. Proceedings of the institution of civil engineers, 1952, 1(3), 325-362.

[8]罗端高, 史峰. 多用户多方式混合交通均衡变分模型及求解算法[J]. 交通运输系统工程与信息, 2010, 10(5):110-116.

[9]HARKER P T. Multiple equilibrium behaviors on networks[J]. Transportation Science, 1988, 22(1):39-46.

[10]黄海军, 李志纯. 组合出行方式下的混合均衡分配模型及求解算法[J]. 系统科学与数学, 2006, 26(3):352-361.

[11]YANG H, ZHANG X, MENG Q. Stackelberg games and multiple equilibrium behaviors on networks[J]. Transportation Research Part B Methodological, 2007, 41(8):841-861.

[12]四兵锋, 赵小梅, 孙壮志,等. 城市混合交通网络系统优化模型及其算法[J]. 中国公路学报, 2008, 21(1):77-82.

[13]YANG X, BAN X J, MA R. Mixed equilibria with common constraints on transportation networks[J]. Networks & Spatial Economics, 2017, 17(2):547-579.

[14]CENG L C, WEN C F. Generalized mixed equilibria, variational inequalities and constrained convex minimization[EB/OL].[2018-01-20].http://dx.doi.org/10.22436/jnsa.010.02.3.

[15]PANICUCCI B, PAPPALARDO M, PASSACANTANDO M. A path-based double projection method for solving the asymmetric traffic network equilibrium problem[J]. Optimization Letters, 2007, 1(2):171-185.