基于可替換路徑對的多用戶均衡交通分配算法

吳超峰，龍建成，劉昊翔

(合肥工業大學汽車與交通工程學院，安徽 合肥 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給出了各算法收斂所需要的計算時間?？梢园l現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用戶群占據一定比例以后，整個路網的系統總阻抗可以降到最小。這表明網絡的結構和規?？赡苁怯绊憣崿F系統總阻抗最小所需的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.