蘇煥銀，史峰，徐光明

(中南大學(xué)交通運輸工程學(xué)院，湖南長沙410075)

用戶均衡(UE)交通分配模型在現(xiàn)實中被廣泛運用。當(dāng)前求解該模型的算法主要有3類:(1)基于路段的交通分配算法，如Frank－Wolfe算法［1］;(2)基于起點的交通分配算法，如Bar－Gera設(shè)計了起點算法［2］，Dial等提出了 B 算法［3］，Yu Nie 研究了 Bush算法［4］;(3)基于路徑的交通分配算法［5］，如梯度投影算法［6］。該模型主要有 2 個計算難題，一是獲取足夠精確的路段流量;二是確定符合現(xiàn)實情況的路徑流量。根據(jù)已有的研究可知，該模型可以確定唯一的路段流量，但無法確定唯一的路徑流量。目前的研究工作主要集中在第1個難題上。Bar－Gera設(shè)計的基于成對可替代子路徑(a pair of alternative segments，PAS)的交通分配算法(TAPAS)［7］能夠同時解決上述2個難題，首先建立UE模型和最大熵用戶均衡模型(MEUE)，提出成對可替代子路徑的概念，并將其作為算法的核心，通過實驗分析對比當(dāng)前的主流交通分配算法，證明了TAPAS算法在運行效率和解的精度方面都具有較強的優(yōu)勢。

TAPAS算法的核心操作是基于PAS，包括構(gòu)建PAS，管理PAS集合，基于有效的PAS在子路徑之間轉(zhuǎn)移流量以均衡子路徑費用，在相關(guān)起點之間均衡路徑流量比例。Bar－Gera［7］提到一個覆蓋的PAS集合對于實現(xiàn)PAS的相關(guān)起點之間的路徑流量的等比例非常重要，然而對于算法的收斂作用甚微。本文旨在提高算法的收斂速度，因此，從該角度出發(fā)，可以將算法的核心操作集中于新構(gòu)建的PAS，保證PAS的有效性，基于新構(gòu)建的PAS在子路徑之間轉(zhuǎn)移流量以均衡子路徑費用，在相關(guān)起點之間均衡路徑流量比例，減少PAS集合的相關(guān)操作。根據(jù)Bar－Gera［7］對算法收斂性的證明可知，基于有效的PAS進行流量轉(zhuǎn)移可以保證算法的收斂性，因此調(diào)整之后的算法仍然是收斂的。詳細設(shè)計各子模塊算法，最后可通過算例驗證改進策略對提高算法收斂速度的有效性。

1 符號及概念定義

將研究的區(qū)域劃分為若干小區(qū)，以小區(qū)的中心點為點，交通網(wǎng)絡(luò)可以表示為強連通的有向網(wǎng)絡(luò) G={N，A}，其中 N 為點集，A={［u，v］:u，v∈N}為有向弧集(也稱為路段集)，假設(shè)兩點之間最多只有一條路段，任何點到它自身不存在路段，網(wǎng)絡(luò)的強連通性表示網(wǎng)絡(luò)中任意2點之間都存在一條有向路徑。一條路徑是一些不同點構(gòu)成的序列［v1，…，vk］，并且［vl，vl+1］∈ A，1 ≤ l≤ k － 1，下面提到的路徑都是不包含有向圈的路徑。路徑r的起點記為rt，終點記為rh，特別地，a=［at，ah］∈ A。一條路段 a=［at，ah］和一個單點［v］也都是一條路。

記點i至點j的路徑集為Rij。對于子路徑s=［i=v1，…，vn=j］與子路徑 r=［j=u1，…，um=k］，子路徑的包含關(guān)系s?r表示s是r的子路徑，即s為r的一部分。路－弧關(guān)聯(lián)關(guān)系由δra表示，若a∈r，其值為1，否則為0。

記起點集為No，起點p∈No對應(yīng)的終點集為Nd(p)，起點p∈No至終點q∈Nd(p)的交通流(或需求)為dpq，O－D流數(shù)組為d，起點p至終點q的路徑r∈Rpq上的流量為hr，路徑流向量為h。從起點p出發(fā)、通過路段a、到達所有終點的路徑流量之和稱為基于起點的路段流量，|A|乘以|No|維路段流量記為f。所有起點的總路段流量為，總路段流向量為f·。本文對TAPAS算法的核心概念PAS作如下進一步的闡述。

子路徑:在一條路徑的某些節(jié)點處分割路徑，分割成的部分即為子路徑，一條子路徑可由若干相連的路段組成。

一對可替代子路徑(PAS):2條子路徑若有相同的起始節(jié)點和相同的終止節(jié)點，且中間節(jié)點不同，則稱為一對可替代子路徑，也稱可替代子路徑對。起始節(jié)點可稱為一對可替代子路徑的分叉點，終止節(jié)點可稱為一對可替代子路徑的結(jié)合點。

等比例就是對于不同起點(或不同終點)的流量在一對可替代子路徑上的分配比例是相等的。

2 交通分配模型

交通分配問題(traffic assignment problem，TAP)是根據(jù)一定的行為假設(shè)，將給定的O－D流分配到指定的路徑上。最常見的假設(shè)是Wardrop用戶均衡準(zhǔn)則，該準(zhǔn)則下出行者總選擇最小費用路徑出行。

上述問題的前提假設(shè):O－D流相對于時間是靜態(tài)的、相對于出行費用是固定不變的。所有出行者的時間價值、貨幣費用和其它路徑貢獻度都是等同的，出行者都完全掌握出行決策的相關(guān)信息。路徑費用為路徑上路段費用之和，即 cs=，其中 t=(ta)a∈A表示路段費用向量，依賴于總路段流量反映的擁擠程度。TAP問題能夠描述為如下路徑流量模型［TAP］(Patriksson［9］):

通過上述模型可以確定用戶均衡交通分配的唯一路段流量解f*·，但不能確定唯一的路徑流量解 hr，r∈ Rpq。Rossi等［10］證明了最大熵路徑流量解卻是唯一的。Bar－Gera等［11］提出等比例假設(shè)(對于不同起點(或不同終點)的流量在一對可替代子路徑上的分配比例是相等的)，解釋了按照最大熵原理求出路徑流量解的最優(yōu)條件。Bar－Gera［12］在理論上證明了等比例條件下的路徑流量解并不唯一，最大熵原理是等比例的充分不必要條件，即最大熵原理和等比例并不等價。但同時。Bar－Gera［12］在一個現(xiàn)實網(wǎng)絡(luò)中證明了這2個條件之間的不同點是非常小的。所以可以通過等比例條件求出一組路徑流量解，近似的代表最大熵原理下唯一的路徑流量解。

建立最大熵用戶均衡模型［MEUE］(Bar－Gera［7］):

3 算法設(shè)計

3.1 TAPAS 算法

TAPAS算法可以同時求解上述2個模型，該算法的主體思想源于網(wǎng)絡(luò)流模型(固定路段費用、線性目標(biāo)函數(shù))的負費用圈優(yōu)化算法，在用戶均衡交通分配問題中，PAS與負費用圈相對應(yīng)，算法TAPAS關(guān)鍵通過PAS上的操作實施，包括新建、刪除PAS及修正PAS的相關(guān)起點列表;在當(dāng)前PAS的子路徑之間轉(zhuǎn)移流量，均衡子路徑費用;在PAS的相關(guān)起點之間均衡路徑流量比例。算法過程中存儲了PAS，構(gòu)建了PAS集合。

TAPAS算法的核心操作是在存儲的大量PAS中選擇PAS集，進而在此PAS集上進行流量轉(zhuǎn)移。雖然在PAS集上的流量轉(zhuǎn)移對相關(guān)起點之間的路徑流量的等比例分配非常重要，但對于算法的收斂作用卻是有限的。

3.2 TAPAS 改進算法

由于很多交通分配問題更加專注于算法的收斂速度，可以考慮僅限于在當(dāng)前有效的PAS上進行流量轉(zhuǎn)移，減少PAS集合的相關(guān)操作。將調(diào)整后的算法稱為MTAPAS算法。

Bar－Gera構(gòu)建的算法強調(diào)基于PAS集合，認為構(gòu)建適量的PAS即可，通過不斷地在集合內(nèi)的PAS上進行流量轉(zhuǎn)移以達到費用均衡，然而隨著迭代次數(shù)的增加，集合中PAS的有效性會降低。注意到當(dāng)前有效的單一PAS是基于實時的路網(wǎng)流量分布信息獲取的，可以實現(xiàn)將非最短路上的流量轉(zhuǎn)移到最短路上，是單次流量轉(zhuǎn)移效率較高的PAS。如果將算法的核心操作僅限于當(dāng)前有效的單一PAS，可以提高單次流量轉(zhuǎn)移的效率，當(dāng)然也減小了轉(zhuǎn)移范圍。同時，算法結(jié)構(gòu)更簡單，編程工作量更小，也有其有利的一面。

基于上述分析，給出MTAPAS算法的具體設(shè)計，如算法1。

算法1 MTAPAS算法

開始

賦初值fpa=0，a∈A，PASs={};

進行全有全無分配;

當(dāng)不滿足終止條件時，循環(huán)執(zhí)行。

開始1

對于每個起點p，p∈No，分別執(zhí)行。

開始2

構(gòu)建基于起點的非零流路段子網(wǎng)絡(luò);

檢測子網(wǎng)絡(luò)中是否有圈流，若有則刪除;

構(gòu)建基于該起點的最短路樹Ap;

對于路段a∈A，如果fpa＞0且a?Ap，執(zhí)行。

開始3

構(gòu)造一個有效的PAS;

構(gòu)建相關(guān)起點列表;

執(zhí)行流量轉(zhuǎn)移操作，以均衡路徑費用;

調(diào)整相關(guān)起點之間路徑流量，以滿足比例條件。

返回3

返回2

返回1

結(jié)束

3.3 關(guān)鍵子算法設(shè)計

下面對MTAPAS算法的子算法操作給出詳細設(shè)計過程。

算法2 有效PAS的構(gòu)建子算法

輸入 路段b=(bt，bh)，起點P，最短路樹AP，基于起點的路段流量

輸出 PAS=［s1，s2］;

開始

獲取路段a，滿足ah=bh，a∈AP;

確定從起點P到點bh的最短路徑rpbh=［p=u1，u2，…，ul=bh］;

從節(jié)點bt沿有流量的路段逆向采用廣度優(yōu)先搜索法搜尋rpbh中的節(jié)點;

確定第一個搜索到的節(jié)點uk;

從uk沿搜索路徑逆向追溯獲取uk到bt路徑

PAS 的第1 條子路徑 s1=［uk，uk+1…，ul］;

PAS的第2 條子路徑 s2=［rukbt，bh］;

結(jié)束

新構(gòu)建的PAS都可以保證費用的有效性。流量有效性需要在搜索路徑時附加限制條件，即只對流量滿足一定條件的路段搜索。假設(shè)搜索的路段為c，則要求 fpc≥ k*fpb，k為0到1之間的數(shù)值，取值越大可轉(zhuǎn)移的流量越多，因此為了提高流量轉(zhuǎn)移的效率可以取值大一些，但是取值過大時會出現(xiàn)搜索不成功的現(xiàn)象，所以要根據(jù)具體實例適當(dāng)?shù)恼{(diào)整取值。

算法3 基于PAS的流量轉(zhuǎn)移子算法

輸入 PAS=［s1，s2］，PAS的相關(guān)起點列表LPAS;f=［fpa］，p∈ No，a ∈ A;

開始

從s2上可轉(zhuǎn)移到s1上的最大流量為δmax=

對于p∈LPAS，循環(huán)執(zhí)行，

開始1

δp=k·mina?s2fpa;

fpa=fpa+ δp，a ? s1;

fpa=fpa－ δp，a ? s2;

結(jié)束1

結(jié)束

因為在構(gòu)建PAS時就確定了s1在最短路樹上，所以流量確定從s2上轉(zhuǎn)移到s1上，然而TAPAS算法中轉(zhuǎn)移流量之前需要確定流量轉(zhuǎn)移的方向。所以該算法中的流量轉(zhuǎn)移要簡單許多，且本算法采用二分法計算轉(zhuǎn)移流量的最佳取值，分化的次數(shù)可以根據(jù)算法當(dāng)前收斂的精度動態(tài)確定。

算法4 基于PAS的相關(guān)起點之間均衡路徑流量等比例分配子算法

輸入 PAS=［s1，s2］，PAS的相關(guān)起點列表LPAS，基于起點的路段流量矩陣f=［fpa］，p∈No，a∈A

輸出 基于起點的路段流量矩陣f=［fpa］，p∈ No，a ∈ A

開始

k1=0，k2=0;

對于p∈LPAS，循環(huán)執(zhí)行

開始1

結(jié)束1

計算方程k1ρ2－k2ρ+k2=0的根ρ;

對于p∈LPAS，循環(huán)執(zhí)行，

開始2

結(jié)束2

結(jié)束

up為基于起點 p需要調(diào)整的流量，Bar－Gera［7］建議采取 up的二次逼近函數(shù)，推導(dǎo)出 U(ρ)的二次函數(shù)形式，因為，所以本文設(shè)計，滿足上述2個條件。所有的流量調(diào)整之和為0，所以只需求解U(ρ)=0的根即可。

4 數(shù)值試驗分析

以常用的Sioux Falls測試網(wǎng)絡(luò)為示例進行數(shù)值試驗，該網(wǎng)絡(luò)劃分了24個小區(qū)，共包含24個節(jié)點，76個路段，528個OD對，具體結(jié)構(gòu)如圖1所示，詳細的數(shù)據(jù)可以從 Bar－ Gera(2001)［13］獲取。采用Matlab編程，并與 TAPAS算法進行比較分析，結(jié)果見圖2。

圖1 Sioux Falls測試網(wǎng)絡(luò)Fig.1 Sioux Falls test network

圖2 相應(yīng)收斂水平下CPU時間Fig.2 CPU time required to achieve desired levels of convergence

由圖2可知，對于Sioux Falls測試網(wǎng)絡(luò)，相比TAPAS算法，MTAPAS算法的收斂速度有一定的提高，當(dāng)收斂精度在10－12以內(nèi)時優(yōu)勢明顯，特別是當(dāng)精度在10－8以內(nèi)時的收斂速度比TAPAS算法快2倍左右。

Sioux Falls測試網(wǎng)絡(luò)是比較典型的交通測試網(wǎng)絡(luò)，在該網(wǎng)絡(luò)上驗證了算法僅僅在當(dāng)前PAS上轉(zhuǎn)移流量具有更高的效率，只說明存在這種可能，在部分例子中僅僅在當(dāng)前PAS上轉(zhuǎn)移流量不會降低其效率。

5 結(jié)論

(1)對TAPAS算法的主體算法結(jié)構(gòu)做出調(diào)整，將算法的核心操作僅限于當(dāng)前有效的單一PAS上，減少PAS集合的相關(guān)操作。

(2)詳細設(shè)計了包括有效PAS構(gòu)建子算法、基于PAS的流量轉(zhuǎn)移子算法和基于PAS在相關(guān)起點之間均衡路徑流量等比例分配子算法。

(3)通過對Sioux Falls測試網(wǎng)絡(luò)計算分析，我們認為，在部分例子中僅僅在當(dāng)前PAS上轉(zhuǎn)移流量不會降低算法的效率。

(4)由于避免了大量PAS的存儲、管理以及PAS集上的流量轉(zhuǎn)移，算法結(jié)構(gòu)更簡單，編程工作量更小。

［1］張歡，盧毅，朱東鐵.基于用戶均衡分析的公路超限車輛補償費率優(yōu)化模型［J］.鐵道科學(xué)與工程學(xué)報，2012，9(6):84 －89.

ZHANG Huan，LU Yi，ZHU Dongtie.Optimization model on highway reimbursement rate of oversize vehicles with user equilibrium analysis［J］.Journal of Railway Science and Engineering，2012，9(6):84 －89.

［2］史峰，王英姿，徐光明，等.考慮支路路段雙向車流相互影響的單向交通組織優(yōu)化［J］.鐵道科學(xué)與工程學(xué)報，2012，9(2):66 －71.

SHI Feng，WANG Yingzi，XU Guangming，et al.Optimization approach for one－way traffic organization with bi－directional flow’s effect of local road［J］.Journal of Railway Science and Engineering，2012，9(2):66 －71.

［3］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.

［4］周和平，胡列格，晏克非.基于模糊路段流量的OD反推的不確定規(guī)劃模型與算法研究［J］.鐵道科學(xué)與工程學(xué)報，2005，43(1):68 －74.

ZHOU Heping，HU Liege，YAN Kefei.Uncertain programming model and algorithm for estimating origindestination matrices based on fuzzy link flow［J］.Journal of Railway Science and Engineering，2005，43(1):68 －74.

［5］Bar－Gera H.Origin－based algorithm for the traffic assignment problem［J］.Transportation Science ，2002，36(4):398－417.

［6］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.

［7］許項東，程琳，邱松林.交通分配自適應(yīng)梯度投影算法的敏感性分析［J］.東南大學(xué)學(xué)報(自然科學(xué)版)，2013，43(1):226 －230.

XU Xiangdong，CHENG Lin，QIU Songlin.Sensitivity analysis of self－adaptive gradient projection traffic assignment algorithm［J］.Journal of Southeast University(Natural Science Edition)，2013，43(1):226－230.

［8］Bar－Gera H.Traffic assignment by paired alternative segments［J］.Transportation Research Part B，2010，44:1022－1046.

［9］Patriksson M.The traffic assignment problem models and methods［R］.VSP，Utrecht，Netherlands，1994.

［10］Rossi T F，McNeil S，Hendrickson C.Entropy model for consistent impact fee assessment［J］.Journal of Urban Planning and Development/ASCE ，1989，115(2):51－63.

［11］Bar－Gera H，Boyce D.Route flow entropy maximization in origin － based traffic assignment［C］//Ceder，A.(Ed.).Proceedings of the 14th International Symposium on Transportation and Traffic Theory，Jerusalem，Israel，Elsevier Science，Oxford，UK，1999:397 －415.

［12］Bar－Gera，H.Primal method for determining the most likely route flows in large road networks［J］.Transportation Science，2006，40(3):269 －286.

［13］Bar－Gera H.Transportation network test problems［EB/OL］.2001.ww.bgu.ac.il/～ bargera/tntp ＞.