程 琳，孫 超,邵 娟

（東南大學(xué) 交通學(xué)院，南京210096）

快速收斂的牛頓路徑算法在交通分配中的應(yīng)用

程 琳*，孫 超,邵 娟

（東南大學(xué) 交通學(xué)院，南京210096）

以確定性交通網(wǎng)絡(luò)用戶均衡問題為研究對象，從理論上推導(dǎo)出以路徑費用函數(shù)為基礎(chǔ)的用戶均衡模型，在這基礎(chǔ)上，提出快速收斂的牛頓路徑算法.該算法每次僅對一OD對進行牛頓型流量轉(zhuǎn)移，轉(zhuǎn)移完再更新道路流量，提出“更快速度接近均衡解原則”，運用這一原則來簡化Hessian陣，從而得到迭代方向，并通過對原函數(shù)二階泰勒展開式進行一維搜索，尋找出最優(yōu)步長.將該算法運用于實際交通分配問題，分別對小、中、大三種網(wǎng)絡(luò)類型進行測試.結(jié)果表明，相比于傳統(tǒng)的梯度投影算法，快速收斂的牛頓路徑算法具有更快的收斂速度和更高的精度，在迭代前期尤為明顯.

交通工程；牛頓路徑算法；優(yōu)化步長；交通分配；簡化方向

1 引 言

交通分配是城市交通建模系統(tǒng)四階段中最后一個階段，它是將每一個OD點對間預(yù)測的交通量分配到實際道路網(wǎng)中，并且要滿足Wardrop第一原則（用戶均衡準則）[1].在達到用戶均衡狀態(tài)時，同一OD對之間，所有使用路徑的旅行時間相等且最小，所有非使用路徑的旅行時間均大于等于使用路徑的旅行時間，沒用人能夠通過單方面改變自己行駛路徑的行為，來減少自己的旅行時間[2].

求解用戶均衡交通分配問題，既可以用路段流量為變量，也可以用路徑流量為變量來構(gòu)建數(shù)學(xué)模型并求解算法.可行域為路段流量的算法稱為路段算法，這類算法以直接求解路段交通量為目的，常用的算法有Frank-Wlofe算法[3]和限制單純分解算法（RSD）[4].可行域為路徑流量的算法稱為路徑算法，該類算法以直接求解路徑交通量為目的，常用的算法有非集計單純分解算法（DSD）[5]、梯度投影算法（GP）[6-8]、共軛梯度投影算法（CGP）[9]和投影梯度算法（PG）[10].除上述求解兩類算法之外還存在另外一種交通流量分配方法，即起點算法（OBA）[11-12]，它的直接變量是從路段流入結(jié)點的流量比例，算法以求解起點通路比例為直接目的來間接獲得使用路徑的選擇率和路徑交通量，從這個方面看來，起點算法具有路徑算法的特征.表1對比了三種算法，以便更好地理解三種算法之間的異同.

表1 路段算法、路徑算法和起點算法的比較Table 1 The comparison of link-based algorithm,path-based algorithm and origin-based algorithm

1994年Jayakrishnan等人在求解交通分配問題時，提出了梯度投影（GP）算法[6].GP算法是一種快速收斂的路徑算法，Chen A等研究發(fā)現(xiàn)GP算法的計算效率和收斂速度明顯優(yōu)于路段算法和DSD算法[13].但當(dāng)GP算法接近最優(yōu)值時，會產(chǎn)生震蕩現(xiàn)象，這種現(xiàn)象造成該算法很難得到高精度的路徑解[9].路段算法收斂精度較低，且不提供路徑信息，起點算法原理復(fù)雜，應(yīng)用性較差，路徑信息需要后期的回溯，而路徑算法收斂精度高，原理簡單，路徑信息完整，最具有應(yīng)用前景，因而本文主要研究這類路徑算法.

如果單獨對算法的某一步驟進行優(yōu)化，有兩個方法可以解決上面的問題，第一是尋找更精確的迭代方向，即對Hessian陣的逆進行優(yōu)化；另一種方法是尋找更精確的步長.目前GP算法中的Hessian陣假設(shè)路徑之間相互獨立，即Hessian陣為對角陣，顯然這是不合理的，因為路徑之間可能共享某個或某些路段，路徑之間必然具有相關(guān)性.在GP算法中，步長的確定是從單位步長開始，按一個固定的系數(shù)進行遞減，這樣很容易產(chǎn)生剛開始步長太大，以致收斂過程中最優(yōu)路徑頻繁進出使用路徑集，產(chǎn)生許多重復(fù)、無效地計算過程；而在迭代后期，步長又過小，使得路徑解不能快速收斂.本文所提出的快速收斂牛頓（RCN）算法同時解決了GP算法中存在的這兩種問題.

GP算法在一次迭代循環(huán)過程中，同時計算所有OD對間的方向和步長，從而確定各OD對使用路徑的轉(zhuǎn)移交通量，然后同時進行交通量的轉(zhuǎn)移.每個OD對都獨立朝著自己使總目標(biāo)函數(shù)減少的方向移動，這一過程會出現(xiàn)事與愿違的現(xiàn)象，總的目標(biāo)函數(shù)并未減少，算法不收斂于最優(yōu)解（比如步長取固定的牛頓經(jīng)典步1）.這種整體轉(zhuǎn)移流量方式不便于方向和步長的優(yōu)化，因而GP算法需要進行整體優(yōu)化來得到更快收斂、更高精度的路徑解.因而本文的RCN算法采用了局部轉(zhuǎn)移流量方式，提高了流量更新效率.

2 交通網(wǎng)絡(luò)均衡模型

目前交通分配遵循用戶均衡(UE)原則（沒有用戶能夠通過改變自己的路徑來獲得更短的旅行時間）或者系統(tǒng)最優(yōu)(SO)原則（路網(wǎng)總旅行時間最小）.以路段費用函數(shù)為基礎(chǔ)，這兩種分配原則下的目標(biāo)函數(shù)可用式（1）、式（2）來表達.

式中 xa表示路段a上的流量；ta(xa)表示路段旅行費用函數(shù).

類比于路段費用函數(shù)SO模型，以路徑費用函數(shù)為基礎(chǔ)的SO模型是很容易表示的：.但至今學(xué)者們并沒有提出以路徑費用函數(shù)為基礎(chǔ)的UE模型.從式(1)出發(fā)推導(dǎo)出UE原則下以路徑費用函數(shù)為基礎(chǔ)的目標(biāo)函數(shù).

aa非常直觀的物理意義：它對路徑求偏導(dǎo)即為路徑費用，這對我們加強UE模型的理解很有幫助.孫超等[14]證明了式(4)與Wardrop第一原則等價性.

綜上交通網(wǎng)絡(luò)均衡數(shù)學(xué)模型的目標(biāo)函數(shù)如表2所示.

表2 均衡網(wǎng)絡(luò)流數(shù)學(xué)模型目標(biāo)函數(shù)Table 2 Objective functions of equilibrium network model

3 快速收斂牛頓（RCN）算法

3.1 RCN算法原理

RCN算法把網(wǎng)絡(luò)

上的交通流按OD對的不同分成不同的層，每次更新一個層上的流量而將來自于其他OD對上的出行看成是背景流量.每次迭代更新的目標(biāo)是：在當(dāng)前背景流量條件下，使來自當(dāng)前OD對的用戶路徑選擇趨于Wardrop原則，即就某個OD對而言，所有使用路徑的出行費用不高于非使用路徑的出行費用.圖1形象地給出了RCN算法分層疊加的原理.RCN算法將交通分配過程按照出行分布的OD對分解成若干個子過程，若干個子過程在網(wǎng)絡(luò)空間中疊加，就形成了交通網(wǎng)絡(luò)上的路徑流量.每個子過程只含有一個OD對，因而這些子過程的求解相對比較簡單，牛頓法就是一個很好方法.

圖1 快速收斂牛頓算法原理示意圖Fig.1 The principle of RCN algorithm

算法的流程可以分成兩個部分，即初始化和主循環(huán).初始化操作的目的是先將OD交通量粗略地分配到交通網(wǎng)絡(luò)中，為接下來的路徑交通量轉(zhuǎn)移奠定基礎(chǔ).進入主循環(huán)后，算法的主要工作是反復(fù)地進行使用路徑集的更新和路徑流量的轉(zhuǎn)移，直到滿足規(guī)定的精度條件或者達到最大循環(huán)次數(shù).在每次循環(huán)的最后，需要對該OD對影響的路段流量進行更新，這一過程運用了最新的信息，使得方向和步長確定更加精確，從而大大提高了算法的精度；再通過選用簡化的牛頓方向和優(yōu)化步長，使得算法的迭代步數(shù)大幅度降低，從而整體上提高算法的運算速度.

正因為采用了每次僅對一OD對進行牛頓型流量轉(zhuǎn)移，轉(zhuǎn)移完就更新道路流量的方式，所以才可以使用更為精確的牛頓簡化方向和優(yōu)化步長.

（1）牛頓方向簡化（Hessian陣的處理）.

根據(jù)最優(yōu)化理論可以計算出牛頓下降方向為

提出“更快速度接近均衡解原則”.在均衡狀態(tài)下，對每個OD對ω而言路徑費用是相等且等于路徑最小旅行費用.在多次迭代后，每個OD對ω中，非最短路徑費用的數(shù)值相差不大，因而負梯度方向的數(shù)值也幾乎相等.為了更快地達到均衡狀態(tài)（即)還是相等且等于路徑最小旅行費用），非最短路徑流量的增量（實際為負值）的大小應(yīng)與路徑費用增量有關(guān)，最終使得對每一OD對ω上，任意非最短路徑費用增量相等.

根據(jù)上面提出的原則，運用式（8）可推出速度更快、更簡潔的Hessian陣.

（2）優(yōu)化步長.

由于前面Hessian陣的近似處理，因而需要一個優(yōu)化的步長來進一步調(diào)整方向，以使算法能夠更快、更好地收斂于最優(yōu)點.目前所有路徑算法步長均為在每次迭代過程中，所有OD點對使用同一步長.顯然在一次迭代過程中，不可能每個OD點對的最優(yōu)步長λω是一樣的，最優(yōu)步長總有差別.如果我們每次選擇λω較小的，那么會使得收斂速度變慢；如果選擇λω較大的，那么搜索范圍會超出可行域，雖然可以用投影算法拉回來，但這種取法帶來許多不必要的計算量.正因為如此，本文提出了多步長梯度投影算法，該算法可以大大降低原問題的迭代步數(shù)，使得算法能夠更快、更好地收斂.

對式(4)以 fω為自變量進行二階泰勒展開：

當(dāng)然也可以對式(4)以x為自變量進行二階泰勒展開，同樣可以得到優(yōu)化步長為：

式(15)與式(16)是等價的，雖然后者比較簡單，計算速度快，但需要將Δf轉(zhuǎn)換為Δx，這樣需要給Δx分配新的內(nèi)存空間.優(yōu)化步長的尋找相當(dāng)于一維搜索過程，關(guān)鍵在于用二階泰勒展開式來代替原目標(biāo)函數(shù).經(jīng)過測試發(fā)現(xiàn)，實際道路網(wǎng)絡(luò)中每個OD對的使用路徑絕大部分為一條，大于三條的非常少，式(15)就是對這有限的幾條路徑進行運算，運算量非常小.

（3）更新路徑流量.

根據(jù)式(10)、式(15)中的方向和步長對路徑流量進行更新.

3.2 RCN算法步驟

RCN算法由初始化、列生成、求均衡解及收斂檢驗三個部分組成.初始化是為了生成每一OD對間的初始使用路徑集合；列生成是為了在當(dāng)前路段費用ta的基礎(chǔ)上生成最短路徑，若該路徑是新生成的，則將之添加到使用路徑集合中；求均衡解及收斂檢驗是為了在當(dāng)前受限路徑集中運用RCN方法求解主問題，并建議是否滿足收斂條件，滿足則停止計算，不滿足則進入下一次循環(huán)當(dāng)中.RCN算法的詳細步驟如下.

（1）初始化.

Step 1xa=0,ta=ta(xa),?a；Kω=?；確定精度ε的值；計數(shù)器n=0.

Step 2選擇一個未被選擇過的OD對ω.

Step 3找出OD對ω的最短路kω?(0)；確定初始使用路徑集合Kω=Kω?kω?(0).

Step 4全有全無加載，確定路徑流量

Step 5更新路段流量

Step 6更新路段旅行時間ta(0)=ta[xa(0)],?a.

Step 7如果已完成所有OD對的迭代更新，轉(zhuǎn)至Step8；否則轉(zhuǎn)至Step2.

（2）列生成、求均衡解、收斂檢驗.

Step 8計數(shù)器n=n+1.

Step 9選擇一個未被選擇過的OD對ω.

Step 10更新使用路徑旅行時間(n),?k.

Step 11找出最短路 kω?(n).更新使用路徑集合，如果Kω中不存在kω?(n)，則Kω=Kω?kω?(n)；否則將Kω中的最短路徑標(biāo)記為kω?(n).

Step 12根據(jù)式(10)、式(15)計算方向和步長

Step 13計算旅行時間誤差：

Step 14更新原使用路徑流量

Step 15更新最短路徑流量

Step 16如果=0，則Kω=Kωk.

Step 17更新路段流量 xa(n),?a.

Step 18更新路段旅行時間 ta(n),?a.

Step 19如果已完成所有OD對的迭代更新，轉(zhuǎn)至Step 20；否則轉(zhuǎn)至Step 9.

Step 20收斂檢驗，如果E≤ε,停止計算；否則轉(zhuǎn)至（2）列生成、求均衡解、收斂檢驗過程.

4 計算實例及數(shù)據(jù)分析

本節(jié)采用三個交通網(wǎng)絡(luò)（Nguyen[15]、Sioux Falls[16]、淮南市[17]）作為實例來比較GP算法和RCN算法的收斂速度和精度，三個交通網(wǎng)絡(luò)的規(guī)模如表3所示.在一臺Intel(R)Core(TM)2 Duo CPU E7500 2.93GHz的計算機上分別編制了GP算法和RCN算法的C#程序，以便更好地比較以上兩個算法.公平起見，兩個算法都盡可能使用相同的數(shù)據(jù)結(jié)構(gòu)和子程序，如使用路徑集都采用嵌套的泛型集合Dictionary和List來存儲，最短路的尋找都采用Dijkstra算法來實現(xiàn).本文編制的GP算法步長從1遞減至0.08，縮小比例為0.95.

表3 三個交通網(wǎng)絡(luò)的規(guī)模Table 3 The size of used traffic networks

圖2、圖4、圖6分別給出了三個網(wǎng)絡(luò)的旅行時間誤差隨迭代次數(shù)的變化情況.從圖中可以發(fā)現(xiàn)RCN算法在很少的迭代次數(shù)下就能快速收斂，而且精度也非常高.

圖3、圖5、圖7分別給出了三個網(wǎng)絡(luò)的旅行時間誤差隨CPU運行時間的變化情況.從圖中可以發(fā)現(xiàn)Nguyen和淮南市網(wǎng)絡(luò)下，RCN算法收斂速度非常快，精度也非常高，但在Sioux Falls網(wǎng)絡(luò)下，RCN算法的優(yōu)勢并不明顯.原因是Sioux Falls網(wǎng)絡(luò)每個起訖點之間均有交通發(fā)生和吸引量，這樣每次主循環(huán)下，需要運算的OD對非常多，大大增加了數(shù)據(jù)的更新次數(shù)，從而增加了運行時間.

圖2 Nguyen旅行時間誤差-迭代次數(shù)Fig.2 Travel time deviation-iterations of Nguyen

圖3 Nguyen旅行時間誤差-運行時間Fig.3 Travel time deviation-computing time of Nguyen

圖4 Sioux Falls旅行時間誤差-迭代次數(shù)Fig.4 Travel time deviation-iterations of Sioux Falls

圖5 Sioux Falls旅行時間誤差-運行時間Fig.5 Travel time deviation-computing time of Sioux Falls

圖6 淮南市旅行時間誤差-迭代次數(shù)Fig.6 Travel time deviation-iterations of HuaiNan

圖7 淮南市旅行時間誤差-運行時間Fig.7 Travel time deviation-computing time of Sioux Falls

計算實例表明，雖然RCN算法在每次循環(huán)過程中不停更新數(shù)據(jù)，增加了計算時間，但通過使用更為精確的牛頓簡化方向和優(yōu)化步長，使得在很少的迭代步數(shù)下，算法就能達到很高的精度，所以不管是在收斂速度還是精度上，RCN算法明顯優(yōu)于GP算法，尤其是在迭代前期，RCN算法成指數(shù)速度收斂.

5 研究結(jié)論

本文首先運用偏導(dǎo)、積分等數(shù)學(xué)轉(zhuǎn)換關(guān)系得到了以路徑費用函數(shù)為基礎(chǔ)的交通UE模型，該模型的提出為交通流分配算法提供新思路、新方法.進而提出了RCN算法，該算法每次僅對一OD對進行牛頓型流量轉(zhuǎn)移，轉(zhuǎn)移完就更新道路流量，在這基礎(chǔ)上，根據(jù)“更快速度接近均衡解原則”，計算出牛頓簡化方向，并且找到更為精確的優(yōu)化步長.經(jīng)過計算實例發(fā)現(xiàn)，RCN具有更快的收斂速度和更高的精度，尤其在迭代前期.

經(jīng)過對RCN算法和GP算法長時間的運算測試，發(fā)現(xiàn)RCN算法在前期收斂非?？?，但在后期（如淮南市網(wǎng)絡(luò)精度達到1E-12），RCN并沒有什么優(yōu)勢，相反GP這種占內(nèi)存少、每次循環(huán)時間短的算法能穩(wěn)健到達所需的精度.對RCN算法進行完善、將RCN算法和其他交通分配算法結(jié)合使用是進一步的研究工作.

[1] Meyer M D,Miller E J.Urban transportation planning:a decision-oriented approach[M].Second Edition.McGraw-Hill Companies,New York,2001.

[2] Sheffi Y.Urban transportation networks[M].Englewood Cliffs,New Jersey:Prentice-Hall,1985.

[3] LeBlanc L J,Morlok E K,Pierskalla W P.An efficient approach to solving equilibrium traffic assignment problem[J].Transportation Research,1975,9:309-318.

[4] Hearn D W,Lawphongpanich S,Vebtura J A.Restricted simplicial decomposition: Computation and extensions[J]. Mathematical Programming Study, 1987,31:99-118.

[5] Larsson T,Patriksson M.Simplicial decomposition with disaggregated representation for the traffic ssignment problem[J].Transportation Science,1992,26:4-17.

[6] Jayakrishnan R,Tsai W K,Prashker J N,et al.A faster path-based algorithm for traffic assignment[J]. Transportation Research Record,1994,1443:75-83.

[7] Chen A,Jayakrishnan R.A path-based gradient projection algorithm:Effects of equilibration with a restricted path set under two flow update policies[C]. Preprint#981560,in:Proceedings of the Transportation Research Board Annual Meeting,Washington,D.C., 1998.

[8] Cheng L,Xu X D,Qiu S L.Constrained newton methods for transport network equilibrium analysis[J].Tsinghua Science and Technology,2009,14(6):765-775.

[9] Lee D,Nie Y,Chen A.A conjugate gradient projection algorithm for the traffic assignment problem[J]. Mathematical and Computer Modelling,2003,37:863-878.

[10] Florian M,Constantin I,Florian D.A new lood at projected gradient method for equilibrium assignment[J].Transportation Research Record:Journal of the Transportation Research Board,Transportation Research Board of the National Academies,2009, 2090：10-16.

[11] Bar-Gera H.Origin-based algorithms for transportation network modeling[D].Chicago：University of Illinois, 1999.

[12] Bar-Gera H.Origin-based algorithm for the traffic assignment problem[J].Transportation Science,2002, 36:398-417.

[13] Chen A,Lee D,Jayakrishnan R.Computational study of state-of-the-art path-based traffic assignment algorithms[J]. Mathematics and Computers in Simulation,2002,59:509-518.

[14] 孫超，王欣，童蔚蘋，等.用戶均衡與系統(tǒng)最優(yōu)原則下交通分配模型的建立與分析[J].中國科技論文，2013，8（11）：1073-1077.[SUN C,WANG X,TONG W P,et al.Establishment and analysis of traffic assignment model under the user equilibrium and system optimization principle[J].China Science Paper,2013,8 (11):1073-1077.]

[15] Nguyen S,Dupuis C.An efficient method for computing traffic equilibria in networks with asymmetric transportation costs[J].Transportation Science,1984, 18:185-202.

[16] LeBlanc L J,Morlok E K,Pierskalla W P.An efficient approach tosolvingequilibrium trafficassignment problem[J].Transportation Research,1975,9:309-318.

[17] 鄭中元.城市道路交通網(wǎng)絡(luò)空間擁堵瓶頸識別[D].南京:東南大學(xué),2009.[ZHENG Z Y.Identification of bottlenecks in urban road network[D].Nanjing: Southeast University,2009.]

Path-based Rapid Convergent Newton Algorithm in Traffic Assignment

CHENG Lin,SUN Chao,SHAO Juan
(School of Transportation,Southeast University,Nanjing 210096,China)

This paper proposes a method for solving the deterministic user equilibrium assignment problem. The UE model based on route cost function is established.Base on this model,path-based rapid convergent Newton(RCN)algorithm is proposed.Each time the traffic flow is diverted for only one OD,and then the flow is updated.We propose the principle of faster speeds approaching equilibrium.Then we simplify the Hessian matrix which can deduce the iterative direction.And through the second-order Taylor expansion,the optimal step size is found.The algorithm is applied to the real traffic assignment problem.Three types (small,medium,large)of traffic networks are tested respectively.Compared to the traditional gradient projection algorithm,path-based rapid convergent Newton algorithm has faster convergence and higher precision,especially in the early iterations.

traffic engineering;path-based Newton algorithm;optimal step size;traffic assignment; simplified direction

2014-04-13

2014-09-14錄用日期：2014-10-08

國家自然科學(xué)基金（51078085，51178110，51378119）.

程琳（1963-），男，江蘇泰州人，教授.

*通訊作者：gist@seu.edu.cn

1009-6744（2014）06-0101-06

U491

A