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

曾明華，肖 瑜，黃細(xì)燕

（1.華東交通大學(xué)軌道交通學(xué)院；2.華東交通大學(xué)基礎(chǔ)學(xué)院，南昌330013）

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

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

1 問題闡述及符號(hào)

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

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

出行費(fèi)用的選擇受到用戶學(xué)習(xí)和選擇行為的影響，可參考文獻(xiàn)[10]。

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

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

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

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

2）層次均衡條件[9]

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

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

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

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

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

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

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

根據(jù)城市道路網(wǎng)絡(luò)中各層次道路子網(wǎng)絡(luò)即支路子網(wǎng)絡(luò)、次干路子網(wǎng)絡(luò)、主干路子網(wǎng)絡(luò)的比例構(gòu)架呈現(xiàn)從底到頂?shù)慕鹱炙褪剑虼耍^低層次道路子網(wǎng)絡(luò)的車輛出行總費(fèi)用在一般情況下會(huì)較高。于是，結(jié)合式（1），式（6）不等號(hào)右邊的式子

而（6）式不等號(hào)左邊的式子

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

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

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

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

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

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

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

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

解之，即得

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

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

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

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

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

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

稍作說明，推論2與文獻(xiàn)[6]所得結(jié)果一致。

證明在交通網(wǎng)絡(luò)沒有層次結(jié)構(gòu)的情況下，所有路段處于同一層次，即 ||H=1。且因?yàn)闆]有層次性，路徑費(fèi)用函數(shù)不用層次因子加權(quán)，仍按通常的表達(dá)方式進(jìn)行計(jì)算，即（1）式變?yōu)椋瑥亩鶕?jù)定理2和定理4的推導(dǎo)過程，可知式（17）成立。式中，是在不考慮層次結(jié)構(gòu)情況下的表示 ，因?yàn)榇藭r(shí)已與層次結(jié)構(gòu)無關(guān) ，自然與層次結(jié)構(gòu)無關(guān) ，所以，

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

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

5 結(jié)論

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

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

[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)絡(luò)效率損失上界的估計(jì)方法[J].系統(tǒng)工程理論與實(shí)踐，2010，30（5）：945-947.

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

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

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

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

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

[10]賀振歡.用戶出行費(fèi)用綜合更新自學(xué)習(xí)模型的研究[J].華東交通大學(xué)學(xué)報(bào)，2010，27（1）：12-16.