吳超峰，龍建成，劉昊翔

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

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

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

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

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

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

(1)

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

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

(2)

2 多用戶均衡交通分配問(wèn)題的求解算法

我們把求解傳統(tǒng)靜態(tài)UE交通分配問(wèn)題的TAPAS算法推廣用于求解多用戶均衡交通分配問(wèn)題。為了比較分析算法的性能，我們還提出了對(duì)角化算法來(lái)求解多用戶均衡交通分配問(wèn)題。

2.1 基于可替換路徑對(duì)的求解算法

2.1.1 可替換路徑對(duì)算法的基本原理

2.1.2 可替換路徑對(duì)流量調(diào)整子算法

如果Δx=0，則算法終止。

Step3：收斂判斷。如果

則算法終止；否則，返回到Step1。

2.1.3 基于可替換路徑對(duì)的多用戶均衡交通分配問(wèn)題的求解算法

我們采用如下基于可替換路徑對(duì)的算法求解多用戶均衡交通分配問(wèn)題：

Step1：更新PAS集合。對(duì)每個(gè)起點(diǎn)r∈N和用戶群φ∈Φ進(jìn)行如下操作：

Step1.2：生成PAS。對(duì)最短路徑樹(shù)外的所有路段(i,j)，進(jìn)行如下操作：

Step3：收斂檢驗(yàn)。如果G(x)<ε，則算法終止；否則，返回到Step1。

算法Step1.2中第2步，可以采用Bar-Gera[5]提出的方法，也可以采用Xie等[6]提出的最大路段流量?jī)?yōu)先搜索法(Maximum-flow first search method, 簡(jiǎn)稱MFS)從路段(i,j)出發(fā)尋找PAS(s1,s2)。由于MFS能夠高效、準(zhǔn)確地搜索到PAS，且得到的PAS還具有更好的流量調(diào)整潛力，本文將采用MFS方法來(lái)更新PAS集合。MFS的具體步驟可以參見(jiàn)Xie等[6]。

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

2.2 基于用戶類別的對(duì)角化算法

采用對(duì)角化方法求解多用戶均衡交通分配問(wèn)題的算法流程如下：

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

Step1：對(duì)角化。

Step1.1：設(shè)φ=1。

Step1.2：求解如下變分不等式問(wèn)題：

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

，

(3)

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

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

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

2.3 基于起點(diǎn)或OD對(duì)的對(duì)角化算法

我們可以把同一用戶中同屬于一個(gè)起點(diǎn)或OD對(duì)的出行者看成單獨(dú)的一類用戶。于是，基于用戶類別的對(duì)角化算法可以直接推廣應(yīng)用于構(gòu)建基于起點(diǎn)或者基于OD對(duì)的對(duì)角化算法。

3 數(shù)值算例

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

表1 測(cè)試網(wǎng)絡(luò)Table 1 The test networks

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

3.1 算例設(shè)置

(4)

3.2 算法收斂效果對(duì)比

表2給出了4種算法在4個(gè)測(cè)試網(wǎng)絡(luò)中的收斂情況。可以發(fā)現(xiàn)UDA與ODA相比，ODA對(duì)網(wǎng)絡(luò)的規(guī)模更敏感，當(dāng)網(wǎng)絡(luò)較小時(shí)兩個(gè)算法效率相近，當(dāng)網(wǎng)絡(luò)規(guī)模變大時(shí)ODA效率明顯下降。而TAPAS在各種網(wǎng)絡(luò)、各種收斂水平下都具有非常好的計(jì)算效率。

3.3 交通需求水平對(duì)算法收斂時(shí)間的影響

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

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

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

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

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

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

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

3.5 交通需求水平對(duì)最優(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 結(jié)論

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

參考文獻(xiàn)：

[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]. 交通運(yùn)輸系統(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)科學(xué)與數(shù)學(xué), 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)絡(luò)系統(tǒng)優(yōu)化模型及其算法[J]. 中國(guó)公路學(xué)報(bào), 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.