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

吳超峰，龍建成，劉昊翔

(合肥工業(yè)大學汽車與交通工程學院，安徽 合肥 230009)

交通分配作為“四階段”交通需求預測中最后一個階段，其模型及算法在過去幾十年中一直被廣泛研究。隨著城市規(guī)模的擴大以及交通需求預測準確性要求的提升，對交通分配的精度和效率的要求越來越高，傳統(tǒng)基于Frank-Wolfe的交通分配算法[1]已經(jīng)無法滿足實際應用，高精度和高效率的交通分配算法逐步被開發(fā)出來。例如，Bar-Gera[2]基于方向比例的概念提出了基于起點的交通分配算法，很大程度上提升了靜態(tài)交通分配問題的求解效率和精度。Dial[3]依據(jù)路徑流量從費用最大的路徑調整到費用最小的路徑的原則，提出了另一種基于起點的交通分配算法。Nie[4]提出了改進的基于起點的交通分配算法。Bar-Gera[5]提出了基于可替換路徑對的交通分配(traffic assignment by paired alternative segments，TAPAS)算法，把靜態(tài)交通分配問題的求解效率提升到了新的高度。Xie等[6]提出了改進的TAPAS算法，進一步簡化了算法的結構，并提高了算法的效率。目前，基于可替換路徑對類的算法還只被用于求解傳統(tǒng)的靜態(tài)交通分配問題。

大多數(shù)交通分配問題的研究都假設路網(wǎng)中所有用戶同質，即所有用戶都遵循相同的出行選擇準則，如用戶均衡(user equilibrium，UE)，或者系統(tǒng)最優(yōu)(system optimum，SO)[7]。然而，現(xiàn)實中用戶出行選擇準則異質普遍存在。近年來，隨著路網(wǎng)中基于APP的電召車以及基于網(wǎng)上購物的貨運車輛的逐漸增多，加上傳統(tǒng)的出租車、貨運車輛以及普通的私家車等，使得路網(wǎng)的用戶成分逐漸復雜，多用戶均衡交通分配問題的快速、精確求解對新形勢下的交通規(guī)劃與管理尤為重要[8]。當前，對于混合多用戶均衡交通分配問題的研究還不多。Harker[9]建立了混合多用戶均衡交通分配問題的變分不等式模型，但只給出了解存在的條件。黃海軍等[10]提出了在換乘場景下的組合出行方式下混合均衡分配的變分不等式模型。Yang等[11]提出了對角化方法結合相繼平均法的算法來求解均衡交通分配問題，但算法的求解效率和精度都不佳。四兵鋒等[12]根據(jù)政府政策和措施對出行者路徑選擇行為的影響，構建了雙層規(guī)劃模型描述了城市混合交通網(wǎng)絡的系統(tǒng)優(yōu)化問題，并采用對角化算法求解了下層混合交通網(wǎng)絡的交通分配問題。Yang等[13]、Ceng等[14]在小型人工網(wǎng)絡中研究了路段通行能力限制、網(wǎng)絡擁堵等廣義約束對混合均衡分配求解的影響。

本文針對混合多用戶均衡交通分配問題的變分不等式模型，分別設計了基于用戶類型的對角化算法和基于起點或OD對的對角化算法來求解混合多用戶均衡交通分配問題，將TAPAS算法應用于求解該問題，并采用大規(guī)模交通網(wǎng)絡驗證算法的性能。數(shù)值結果表明,論文設計的算法可以解決已有算法求解混合網(wǎng)絡均衡問題效率較低且精度不高的問題。

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

多用戶均衡交通分配問題可以描述為一系列變分不等式問題[11]：尋找一個向量x*∈Ω，使得

(1)

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

我們采用如下間隙函數(shù)來衡量多用戶均衡交通分配問題求解算法的收斂精度：

(2)

2 多用戶均衡交通分配問題的求解算法

我們把求解傳統(tǒng)靜態(tài)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]提出的最大路段流量優(yōu)先搜索法(Maximum-flow first search method, 簡稱MFS)從路段(i,j)出發(fā)尋找PAS(s1,s2)。由于MFS能夠高效、準確地搜索到PAS，且得到的PAS還具有更好的流量調整潛力，本文將采用MFS方法來更新PAS集合。MFS的具體步驟可以參見Xie等[6]。

Xie等[6]研究了TAPAS類算法的復雜度，發(fā)現(xiàn)復雜度與網(wǎng)絡包含的PAS數(shù)相關，而網(wǎng)絡中PAS的數(shù)量又與網(wǎng)絡規(guī)模和結構相關，相似規(guī)模的網(wǎng)絡可能因為網(wǎng)絡結構的區(qū)別導致PAS數(shù)量有巨大差別，因此TAPAS類算法的復雜度無法簡單與網(wǎng)絡的節(jié)點數(shù)、小區(qū)數(shù)、路段數(shù)等信息關聯(lián)。本文給出的基于可替換路徑對的混合均衡分配算法本質上也屬于TAPAS類算法的一種，因此其復雜度也與PAS數(shù)相關，其具體的相關性則需要進一步研究。

2.2 基于用戶類別的對角化算法

采用對角化方法求解多用戶均衡交通分配問題的算法流程如下：

Step0：初始化。采用全有全無分配得到初始路段流量x0，設迭代次數(shù)n=0，收斂精度ε>0。

Step1：對角化。

Step1.1：設φ=1。

Step1.2：求解如下變分不等式問題：

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

，

(3)

得到最優(yōu)解xφ*。

Step2：收斂判斷。若G(xn+1)<ε，則算法終止；否則，令n=n+1，轉Step1。

在變分不等式(3)中，由于除第φ類用戶以外的其他類型用戶的流量固定，該變分不等式是一個單一用戶的網(wǎng)絡均衡問題，可以直接采用Frank-Wolfe、外梯度投影算法、基于起點的交通分配算法、TAPAS類算法等進行求解。

2.3 基于起點或OD對的對角化算法

我們可以把同一用戶中同屬于一個起點或OD對的出行者看成單獨的一類用戶。于是，基于用戶類別的對角化算法可以直接推廣應用于構建基于起點或者基于OD對的對角化算法。

3 數(shù)值算例

我們采用不同規(guī)模的網(wǎng)絡來檢驗提出的算法的有效性見表1。所有算例都在一臺配置Intel Core i5 3.10 GHz處理器和8 GB內(nèi)存的計算機上采用Visual Studio C#編程實現(xiàn)。

表1 測試網(wǎng)絡Table 1 The test networks

注：測試網(wǎng)絡數(shù)據(jù)來源于http://www.bgu.ac.il/～bargera/tntp/。

3.1 算例設置

(4)

3.2 算法收斂效果對比

表2給出了4種算法在4個測試網(wǎng)絡中的收斂情況?？梢园l(fā)現(xiàn)UDA與ODA相比，ODA對網(wǎng)絡的規(guī)模更敏感，當網(wǎng)絡較小時兩個算法效率相近，當網(wǎng)絡規(guī)模變大時ODA效率明顯下降。而TAPAS在各種網(wǎng)絡、各種收斂水平下都具有非常好的計算效率。

3.3 交通需求水平對算法收斂時間的影響

路網(wǎng)的擁擠程度對于交通分配算法的收斂性具有一定的影響。我們把Chicago Sketch網(wǎng)絡的OD需求從50%依此遞增10%到150%，并采用ODA、UDA和TAPAS等4種算法求解相應的多用戶均衡交通分配問題。圖1給出了各算法收斂所需要的計算時間?？梢园l(fā)現(xiàn)TAPAS相比UDA和ODA具有更好的穩(wěn)定性，且對交通需求水平的敏感性較低。在其他3個網(wǎng)絡的測試中，發(fā)現(xiàn)提出的算法在不同網(wǎng)絡上具有相似的特性。

表2 各個算法在不同網(wǎng)絡下的收斂效率對比

圖1 交通需求水平對算法收斂時間的影響Fig 1 The effect of traffic demand on convergence time for each algorithm

3.4 用戶比例對系統(tǒng)總阻抗的影響

由于UE用戶和CN用戶在出行過程中都沒有完全考慮其出行帶來的外部性成本，當系統(tǒng)中存在UE用戶群和CN用戶群時，整個網(wǎng)絡的系統(tǒng)總阻抗很難到達系統(tǒng)最優(yōu)狀態(tài)。系統(tǒng)中UE用戶和CN用戶越多，則整個網(wǎng)絡偏離系統(tǒng)最優(yōu)越遠。當網(wǎng)絡中SO用戶群占比接近100%時，UE用戶與CN用戶出行帶來的外部性成本趨于零，從而系統(tǒng)總阻抗也趨于最低。

Yang等[11]在小網(wǎng)絡中的計算結果表明SO用戶群占據(jù)一定比例以后，整個路網(wǎng)的系統(tǒng)總阻抗可以降到最小。這表明網(wǎng)絡的結構和規(guī)?？赡苁怯绊憣崿F(xiàn)系統(tǒng)總阻抗最小所需的SO用戶群占比的重要因素。本文在多個不同規(guī)模的交通網(wǎng)絡上的計算結果表明，在多用戶混合交通系統(tǒng)中，SO用戶群占比接近100%時系統(tǒng)總阻抗才能夠降到最低的現(xiàn)象可能在較大規(guī)模的網(wǎng)絡中普遍存在。

圖2 不同網(wǎng)絡不同SO用戶比例下的系統(tǒng)總阻抗Fig.2 The effect of the proportion of SO user on total system travel cost under different networks

3.5 交通需求水平對最優(yōu)系統(tǒng)總阻抗的影響

圖3 不同需求水平下不同SO用戶比例下的系統(tǒng)總阻抗Fig.3 The effect of the proportion of SO user on total system travel cost under different traffic demand

4 結論

本文針對多用戶均衡交通分配問題的變分不等式模型，在基于可替換路徑對的UE交通分配算法基礎上，分別設計了基于用戶類別的對角化算法和基于起點或OD對的對角化算法，并與外梯度算法進行了對比分析。結果表明基于可替換路徑對的多用戶均衡交通分配算法無論是在小網(wǎng)絡還是大網(wǎng)絡上都有較高的計算精度，并有很好的計算效率。通過求解不同需求水平下的多用戶均衡交通分配問題，發(fā)現(xiàn)基于可替換路徑對的多用戶均衡交通分配算法能保持較好的穩(wěn)定性。通過算例，發(fā)現(xiàn)在不同規(guī)模路網(wǎng)中不同交通需求水平下，SO用戶比例越大多用戶均衡交通分配狀態(tài)下路網(wǎng)系統(tǒng)總阻抗越小。下一步研究中，可以將本文提出的基于可替換路徑對的多用戶均衡交通分配算法推廣應用于網(wǎng)絡設計問題、道路擁擠收費、網(wǎng)絡交通控制等交通規(guī)劃與管理問題中。

參考文獻：

[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]. 交通運輸系統(tǒng)工程與信息, 2010, 10(5):110-116.

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

[10]黃海軍, 李志純. 組合出行方式下的混合均衡分配模型及求解算法[J]. 系統(tǒng)科學與數(shù)學, 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]四兵鋒, 趙小梅, 孫壯志,等. 城市混合交通網(wǎng)絡系統(tǒng)優(yōu)化模型及其算法[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.