多層次交通網絡的UE與SO混合均衡與效率損失

曾明華，肖 瑜，黃細燕

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

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

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

1 問題闡述及符號

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

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

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

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

2 多層次交通網絡混合均衡及其變分不等式

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

1）系統最優條件

2）層次均衡條件[9]

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

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

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

即為交通網絡混合平衡條件，故有結論。

3 多層次交通網絡混合均衡的效率損失上界

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

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

根據城市道路網絡中各層次道路子網絡即支路子網絡、次干路子網絡、主干路子網絡的比例構架呈現從底到頂的金字塔型式，因此，較低層次道路子網絡的車輛出行總費用在一般情況下會較高。于是，結合式（1），式（6）不等號右邊的式子

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

于是，（6）式變為

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

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

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

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

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

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

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

解之，即得

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

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

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

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

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

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

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

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

根據推論2，進一步假設λ=0，則

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

5 結論

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

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

[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]石超峰，徐寅峰.交通網絡效率損失上界的估計方法[J].系統工程理論與實踐，2010，30（5）：945-947.

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

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

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

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

[9]曾明華.區域交通網絡層次性與優化設計[M].北京：人民交通出版社，2011：77-92，101，116-131.

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