多層次交通網(wǎng)絡的UE與SO混合均衡與效率損失

曾明華，肖 瑜，黃細燕

（1.華東交通大學軌道交通學院；2.華東交通大學基礎學院，南昌330013）

自由市場中所有出行者從個人角度考慮選擇出行成本最小化的路徑，出行者之間只有自私的博弈。在沒有誘導的條件下，依靠自由市場競爭所達到的用戶均衡（UE）一般不能使有限資源分配達到系統(tǒng)最優(yōu)（SO）。如果部分出行者受控于交通誘導與控制中心，在系統(tǒng)最優(yōu)的前提下用戶出行路徑選擇，則系統(tǒng)最終會趨向于一種介于系統(tǒng)最優(yōu)和用戶最優(yōu)之間的狀態(tài)。因此，系統(tǒng)中存在效率損失，但一直沒有得到定量界定。文獻[1]最早提出了合作系數(shù)或無政府的代價來界定交通網(wǎng)絡中由于用戶的非合作行為而導致的效率損失問題。在此基礎上，文獻[2]完成了一項具有代表性的工作，即，假設具有非負系數(shù)的線性阻抗函數(shù)，發(fā)現(xiàn)用戶均衡效率損失最多為系統(tǒng)最優(yōu)的1/3。之后，許多學者為尋找用戶平衡更小的效率損失上界而進行了一系列拓展研究[3-5]?？紤]到交通網(wǎng)絡中部分出行者接受誘導中心的指揮、按照系統(tǒng)最優(yōu)的原則選擇路徑，而其他出行者根據(jù)個人成本最小的原則擇路，文獻[6]以及文獻[7]建立了刻畫這種混合交通行為的變分不等式模型，推導了混合交通行為網(wǎng)絡的效率損失上界。研究表明一般情況下的效率損失上界與具體被研究的網(wǎng)絡結構和交通需求水平等有關。

現(xiàn)實中交通網(wǎng)絡是多模式的，多層次是多模式的伴生特征，并且已有研究表明多層次交通網(wǎng)絡具有比非層次網(wǎng)絡更好的性能[8-9]。本文研究了具有多層次結構的交通網(wǎng)絡中系統(tǒng)最優(yōu)與用戶均衡所構成的混合均衡情況下效率損失問題，建立了混合均衡的等價變分不等式，并分析了多層次交通網(wǎng)絡混合均衡的效率損失上界。該研究結果表明效率損失上界與交通網(wǎng)絡層次結構、道路路況、交通需求水平、交通誘導信息滲透率等因素直接相關，若不考慮層次性可得文獻[6]與文獻[2]的分析結果。

1 問題闡述及符號

考慮交通網(wǎng)絡G=(V，E)，V為節(jié)點集合，E為區(qū)域所有路段集合。記W={w}為所有起訖點(OD對)的集合，Rw為OD對w∈W之間的所有路徑構成的集合。va為路段a∈E的交通流量,為相應向量；設為路徑OD對w間r∈Rw上的交通流量，記為路徑流量向量。記為交通網(wǎng)絡中邊-路徑關聯(lián)矩陣，當邊a在路徑r上時，否則，；記為交通網(wǎng)絡中OD-路徑關聯(lián)矩陣，若路徑r∈Rw，則，否則。設路段a上的可分離的路段成本函數(shù)為ca(va)是非負可微的，并且是關于路段流量va的單調遞增凸函數(shù)；ca(va)∈C，C是給定的路段成本函數(shù)類，比如C是一簇多項式函數(shù)。

假設對區(qū)域交通網(wǎng)絡中所有路段按照功能和技術等級分為不同層次，其中代表區(qū)域中交通模式的層次集合。設X為實數(shù)集合，對每個層次賦予一個度量用以指示其對出行者的相對吸引強度，且滿足，則將l?稱為層次因子[8]。利用交通網(wǎng)絡層次因子給出OD對w間路徑r上的廣義路徑費用

出行費用的選擇受到用戶學習和選擇行為的影響，可參考文獻[10]。

由于交通系統(tǒng)中存在安裝有先進交通信息系統(tǒng)（ATIS）和無ATIS裝置的兩類出行者，他們各自遵循SO和UE兩種不同的路徑選擇原則，這種混合交通行為將導致混合均衡。假設OD對w上的市場滲透率皆為滿足某種分布，本文采用常用的均勻形式，即。若OD對w之間的交通需求量為qw（記為相應向量），則有裝置用戶的OD需求量為λqw，無裝置用戶的OD需求量為。下文用標記“”和“”分別表示有裝置和無裝置用戶的相關變量，例如，表示有裝置用戶的路徑流量和路段流量，和表示有裝置用戶的路徑流量向量和路段流量向量。不妨記路段a上混合交通流為，記路徑r∈Rw上的混合交通流為，并記為相應的向量。

2 多層次交通網(wǎng)絡混合均衡及其變分不等式

層次交通網(wǎng)絡混合均衡，是具有多層次結構交通網(wǎng)絡中部分用戶追求系統(tǒng)最優(yōu)而其他用戶追求用戶平衡所達到的一種均衡狀態(tài)；滿足系統(tǒng)最優(yōu)條件的出行者內部，沒有任何出行者可以通過單方面改變出行路徑來降低其最小綜合出行費用，而對于滿足層次均衡條件的出行者而言，都不能通過單方面改變出行路徑來減少其最小出行費用。其中，系統(tǒng)最優(yōu)條件和層次均衡條件如下

1）系統(tǒng)最優(yōu)條件

2）層次均衡條件[9]

該條件的解釋：若OD對w間路徑r上沒有交通流，則路徑r的層次路徑費用不小于最小層次路徑費用；若OD對w間路徑r上有交通流，則路徑r的層次路徑費用等于最小層次路徑費用，且交通流選擇盡可能多包含較高層次路段的路徑。

定理1設路段費用函數(shù)是關于的單調遞增凸函數(shù)，則多層次交通網(wǎng)絡混合均衡等價于：求，使下述變分不等式成立

證明由變分不等式模型的Karush-Kuhn-Tucker條件，知

即為交通網(wǎng)絡混合平衡條件，故有結論。

3 多層次交通網(wǎng)絡混合均衡的效率損失上界

以下分析多層次交通網(wǎng)絡混合均衡的效率損失上界。

將fS分解為，則代入定理1中的變分不等式并整理，可得

根據(jù)城市道路網(wǎng)絡中各層次道路子網(wǎng)絡即支路子網(wǎng)絡、次干路子網(wǎng)絡、主干路子網(wǎng)絡的比例構架呈現(xiàn)從底到頂?shù)慕鹱炙褪?，因此，較低層次道路子網(wǎng)絡的車輛出行總費用在一般情況下會較高。于是，結合式（1），式（6）不等號右邊的式子

而（6）式不等號左邊的式子

于是，（6）式變?yōu)?/p>

對某個層次，對屬于該層次的每條路段定義參數(shù)

于是，得到下述混合均衡效率損失上界定理如下。

定理2假設可分離的路段費用函數(shù)ca(va)是單調遞增的凸函數(shù)，所有ca構成一個函數(shù)類C；設受控于交通誘導中心的用戶占交通網(wǎng)絡總需求的比例為λ∈(0，1)，系統(tǒng)最優(yōu)與用戶平衡行為共同作用下的混合均衡的路徑（路段）流量解分別為；并設交通網(wǎng)絡系統(tǒng)最優(yōu)的路徑（路段）流量解為。那么混合均衡的效率損失存在如式（11）所示的上界。

效率損失上界與交通網(wǎng)絡層次性結構、受控于交通誘導信息的出行者比例、路段成本函數(shù)類型等因素相關。上述效率損失上界界定了在最壞情況下交通網(wǎng)絡的性能，由于現(xiàn)實交通網(wǎng)絡中路段零流成本ca(0)＞0，考慮到這一點[3]，現(xiàn)實交通網(wǎng)絡的效率損失要更小一些。沿用定理2的符號，類似于文獻[6]，下述定理給出了一個更精確的上界。

定理3對，假設存在依賴于混合均衡流量的，使得零流成本滿足。那么混合均衡與系統(tǒng)最優(yōu)的網(wǎng)絡總成本之比ρM存在如下上界

4 多項式路段費用函數(shù)情形下的效率損失上界

沿用定理2的符號和定理3中假設，定理4將給出采用常用的BPR路段費用函數(shù)情況下更吻合實際的上界。

解之，即得

從而，將va的解代入（9）和（10）式，有

，都依賴于混合均衡流量解，且該解是與交通網(wǎng)絡層次性結構直接相關，為了顯性地表達此含義，令。從而，得到路段費用采用BPR函數(shù)時的交通網(wǎng)絡混合均衡效率損失上界

定理4取BPR函數(shù)即（自然數(shù)集），那么交通網(wǎng)絡混合均衡的效率損失上界如上面的式（15）所示。

推論1在多層次交通網(wǎng)絡中，假定不存在交通誘導與控制中心以保證網(wǎng)絡中部分車輛按系統(tǒng)最優(yōu)方式選擇出行路徑，則在該類交通網(wǎng)絡中效率損失上界為

證 明由 推 論 中 的 假 定 知λ=0 ，則。 于 是 ，，故有效率損失上界如（16）式。

推論2若不考慮交通網(wǎng)絡層次性，則交通網(wǎng)絡混合均衡的效率損失為

稍作說明，推論2與文獻[6]所得結果一致。

證明在交通網(wǎng)絡沒有層次結構的情況下，所有路段處于同一層次，即 ||H=1。且因為沒有層次性，路徑費用函數(shù)不用層次因子加權，仍按通常的表達方式進行計算，即（1）式變?yōu)?，從而根?jù)定理2和定理4的推導過程，可知式（17）成立。式中，是在不考慮層次結構情況下的表示 ，因為此時已與層次結構無關 ，自然與層次結構無關 ，所以，

根據(jù)推論2，進一步假設λ=0，則

若還不考慮定理中關于零流成本ca(0)的假設，即，那么可得當n=1時，即有，這與文獻[2]的結果一致。

5 結論

交通誘導信息在某種程度上提高了交通效率，降低了交通擁堵，但人們自私的出行行為使得交通網(wǎng)絡無法達到理想的系統(tǒng)最優(yōu)狀態(tài)。給出了多層次交通網(wǎng)絡中混合均衡的等價變分不等式及效率損失上界，交通網(wǎng)絡效率損失上界與層次結構、交通需求水平、交通誘導信息滲透率、道路狀況等多種因素有關，研究方法具有較強的現(xiàn)實意義。此外，流量分布還受交通需求的分布形態(tài)、交通信息的分布形態(tài)、用戶出行偏好特點、交通管理政策等諸多因素的影響，因此，交通網(wǎng)絡效率損失上界也受到這些現(xiàn)實因素的影響。

有研究表明多層次交通網(wǎng)絡的性能會比傳統(tǒng)不考慮層次性情況下所優(yōu)化設計出交通網(wǎng)絡的性能大幅提升[8-9]，因此，本文融合層次性這一反映客觀實際的結構形式對交通網(wǎng)絡的效率損失進行研究，對設計效率更高、性能更優(yōu)的交通網(wǎng)絡具有重要意義。相較于通常研究中采用的非層次交通網(wǎng)絡，多層次交通網(wǎng)絡究竟在多大程度上降低混合均衡的效率損失，這將是下一步的工作。

[1]KOUTSOUPIAS E,PAPADIMITRIOU C.Worst-case equilibria[C]//Proceedings of the 16th Annual Conference on TheoreticalAspects of Computer Science，Springer-Verlag，1999：404-413.

[2]ROUGHGARDEN T，TARDOS é.How bad is selfish routing[J].Journal of theACM，2002，49（2）：236-259.

[3]CORREA J R，SCHULZ A S，Stier-Moses N E.On the inefficiency of equilibria in congestion games[C]//Proceedings of the 11th International Integer Programming and Combinatorial Optimization Conference，Berlin，Germany.In：Lecture Notes in Computer Science，Heidelberg：Springer，2005，3509：167-181.

[4]石超峰，徐寅峰.交通網(wǎng)絡效率損失上界的估計方法[J].系統(tǒng)工程理論與實踐，2010，30（5）：945-947.

[5]黃海軍，歐陽戀群，劉天亮.交通網(wǎng)絡中用戶均衡行為的效率損失[J].北京航空航天大學學報，2006，32（10）：1215-1219.

[6]劉天亮，歐陽戀群，黃海軍.ATIS作用下的混合交通行為網(wǎng)絡與效率損失上界[J].系統(tǒng)工程理論與實踐，2007，（4）：154-159.

[7]羅文昌.界定用戶平衡及Logit型隨機用戶平衡下的混合平衡交通網(wǎng)絡效率損失[J].運籌學學報，2010，14（2）：79-86.

[8]曾明華，李夏苗.基于層次性的交通網(wǎng)絡資源優(yōu)化配置方法[J].中南大學學報：自然科學版，2011，42（1）：247-253.

[9]曾明華.區(qū)域交通網(wǎng)絡層次性與優(yōu)化設計[M].北京：人民交通出版社，2011：77-92，101，116-131.

[10]賀振歡.用戶出行費用綜合更新自學習模型的研究[J].華東交通大學學報，2010，27（1）：12-16.