程 琳 紀 魁 蒲自源 王 悅

(東南大學交通學院，南京 210096)

路段型隨機用戶均衡敏感度分析

程 琳 紀 魁 蒲自源 王 悅

(東南大學交通學院，南京 210096)

摘 要:為了設計基于Logit的隨機用戶均衡問題的高效算法，對傳統(tǒng)的隨機用戶均衡模型熵項進行分解，得到路段型隨機用戶均衡模型.在分析路段型隨機均衡模型及其優(yōu)化條件的基礎上，以數(shù)學規(guī)劃的方法推導其敏感度方程，這相對于變分不等式的方法更加容易接受，同時因為確定型均衡模型是隨機用戶均衡模型的一種特例，所以此方法同樣適用于確定型用戶均衡的敏感度分析.以相繼平均算法和敏感度矩陣對算例進行求解，兩者結果基本吻合.同時對實際遇到的秩虧問題，提出“分段求解”的方法，有效地解決了矩陣無法求逆的現(xiàn)象.

關鍵詞:路段型隨機用戶均衡模型;敏感度分析;數(shù)學規(guī)劃;Logit

在交通網(wǎng)絡流理論中，分析模型的輸入變量(如道路容量、自由流旅行時間、OD需求等“外部變量”)對輸出變量(如路段流量、路段通行時間等“內部變量”)的影響程度就是“敏感度分析”或者“靈敏度分析”［1］.對于確定型用戶(user equilibrium，UE)均衡，Tobin等［2］以變分不等式的方法推導了其敏感度方程.Ying等［3］在2001年用數(shù)學規(guī)劃的方法，對基于Logit的隨機用戶均衡(stochastic user equilibrium，SUE)的對偶模型進行敏感度方程的推導，得到了滿足精度要求的結果.Clark等［4］也用數(shù)學規(guī)劃的方法對基于Probit的SUE模型進行了敏感度的分析.相對于變分不等式，數(shù)學規(guī)劃的方法更加簡單.本文以數(shù)學規(guī)劃的方法對路段型SUE模型進行敏感度分析，推導其敏感度方程;提出的數(shù)學規(guī)劃方法相對于其他數(shù)學規(guī)劃方法［3，5］更加簡單，具有普遍適用性.

1 路段型隨機均衡模型

傳統(tǒng)的基于Logit的SUE模型，含有一個有路徑信息的熵項，在評價函數(shù)時需要對路徑信息列舉，這就制約了高效算法的設計.Akamatsu［6］對含有路徑信息的熵項進行了分解，使得熵項只含有路段信息，得到了基于Logit的路段型SUE模型:

式中，xoij表示在起點o的流量;θ為常數(shù);δok，δkd為開關函數(shù)，k=o(k=d)時，δok=1(δkd=1)，否則為0;HL，HN分別表示SUE模型熵項的前后兩項，以為變量;tij(xij)為路段阻抗函數(shù)，一般以BPR形式表示，即

式中，t0ij為路段自由流旅行時間;Cij為路段容量.

可以發(fā)現(xiàn)，路段型隨機均衡模型含有2項:第1項為路段阻抗的一個積分函數(shù);第2項為只含有路段流量信息的熵項，通過θ控制其大小.θ表示旅行者對路網(wǎng)的熟悉程度，對路網(wǎng)越熟悉，θ值越大.當θ→∞時，就轉化為UE問題，所以UE問題實際上是SUE問題的一種特殊形式.

2 路段型隨機均衡模型敏感度方程推導

定義wn為約束條件式(2)的拉格朗日乘子，n表示從1開始的整數(shù)，用以計數(shù);ε為擾動常數(shù)，則模型的拉格朗日函數(shù)為

在最優(yōu)解時，▽L=0.綜合其約束條件，定義如下方程組［7］

在均衡時，得到等式

定義向量矩陣

變換得到▽εy為

根據(jù)式(14)，結合泰勒公式，可得

式中，o(‖ε‖)→0.根據(jù)以上公式，可以在獲得一組均衡解的前提下，根據(jù)敏感度方程，獲得擾動后的均衡解.

向量矩陣M由四項組成，關鍵在于求得Hessian矩陣的▽2L和▽h.對式(8)的求二次偏導，得

式中，δij，gh為開關函數(shù)，路段(i，j)與路段(g，h)相同時為1，否則為0.

向量矩陣N與所求輸入變量攏動有關.

2.1 對起終點流量求敏感度方程

當OD對之間的qod需求發(fā)生變化時，路段上的流量也將會發(fā)生相應的變化.設初始流量為qod，則

式中，γod為OD對o，d需求的擾動，是一個常數(shù).對于N含有兩項，分別對γod求導，得

易知，本模型中，式(19)等于0，根據(jù)式(13)，可以推得N.

2.2 對自由流旅行時間求敏感度方程

在車道暢通時，車輛以設計車速行駛的時間稱之為自由流旅行時間.由于道路改造等原因，經(jīng)常會導致自由流旅行時間發(fā)生變化，對其求敏感度將方便對變化后的路段流量進行估計，從而為規(guī)劃工作提供參考.以BPR函數(shù)為阻抗函數(shù)，如式(7)所示，εij作為零流旅行時間的擾動參數(shù)，可以得到

矩陣N的元素為

3 敏感度算法實現(xiàn)

對于路段型SUE模型，可以按傳統(tǒng)的相繼平均算法(method of successive averages，MSA)求解［8］，設計敏感度算法如下:

① 根據(jù)Bell第二算法加載流量［9］，根據(jù)MSA算法求解出路網(wǎng)基于起點的路段流量和路段流量xij;

②計算式(16)和(17)，得到矩陣M;

③分別計算出式(19)、(20)和式(22)、(23)，得到對應于起終點流量和對應于自由流時間矩陣N;

④由式(14)求得敏感度矩陣.

通過以上算法，可以求得基于起點的路段流量對OD需求和零流時間擾動的敏感度，從而可以預測擾動之后的新均衡解，為規(guī)劃決策提供參考.

4 算例分析

本節(jié)首先對Ying等［3］的算例進行敏感度方程的推導，比較其結果.算例1由5個節(jié)點和6個路段組成，如圖1所示.根據(jù)Bell加載的MSA算法的基本要求［10］設節(jié)點4和節(jié)點5為虛擬節(jié)點，這樣可以避免2條路段連接2個相同的節(jié)點.

圖1 算例1路網(wǎng)

采用如下路段阻抗函數(shù)［3］:

各個路段屬性定義為

OD需求定義為

由于只有一個起點，所以=xij.在 θ=0.001的條件下，各路段流量為

計算Hessian矩陣和▽h，得

可以發(fā)現(xiàn)，矩陣的秩為4，出現(xiàn)秩虧，因此矩陣 M也將出現(xiàn)秩虧，從而導致無法求逆.

分析路網(wǎng)中，添加的虛擬節(jié)點4、節(jié)點5對應的約束條件為

式(25)和(26)表示流入流量等于流出流量.本文針對以上2個約束提出“分段求解”的方法，以解決秩虧問題.已知矩陣方程為

分段求解的思想就是:將矩陣M的第6行和第6列去除，同時將矩陣Y、N中的第6行去除，得到一組數(shù)據(jù)，然后將M中的第5行和第5列去除以及將矩陣Y、N中的第5行去除，得到另一組數(shù)據(jù)，將2組數(shù)據(jù)疊加求和.

1)對起終點流量求敏感度

當q13發(fā)生微小擾動γ13時的敏感度矩陣為

當OD之間的需求流量發(fā)生變化時，路段流量必然會發(fā)生變化，結果體現(xiàn)了很好的閉合性.可以發(fā)現(xiàn)路段(1，2)和(2，5)對OD的改變比較敏感，規(guī)劃部門可以通過規(guī)劃用地性質去改變居民的出行OD交通量，從而改善路網(wǎng)運行狀況.

2)對時間求敏感度

可見，擾動參數(shù)對流量轉移的影響較大.觀察路網(wǎng)可知，路段(1，2)減少的流量必然會增加到路段(1，4)上去，求得的結果也體現(xiàn)了流量守恒.規(guī)劃管理部門可以通過合理的調整路網(wǎng)的服務水平，去改變路網(wǎng)的交通量分配.

將以上結果與Ying等［3］結果相比，發(fā)現(xiàn)兩者結果一致，說明了本文方法的正確性.

路段型SUE模型也可以清晰地展示多起點的路網(wǎng)流量分配.算例2含有2個起點，13個節(jié)點，19條路段，4個OD對，如圖2所示.路段阻抗函數(shù)采用BPR 函數(shù)(21)，取 α =0.15，β=4，路網(wǎng)屬性見表1.定義 θ=0.01，其相應的擾動為

圖2 算例2路網(wǎng)

表1 算例2路網(wǎng)屬性

經(jīng)過一系列的擾動后，敏感度矩陣求得的結果()和相繼平均算法()求得的結果如表2所示.由表可知二者誤差很小，因此本文的敏感度矩陣方法滿足實際應用的要求.

表2 幾種擾動下的流量結果

5 結語

本文提出的以數(shù)學規(guī)劃方法對模型進行敏感度分析，經(jīng)驗證分析，滿足精度要求，同時提出的“分段求解”方法也在處理秩虧問題上有一定的借鑒意義.考慮到UE問題是SUE問題在θ→∞時的一種特例，所以本文中的數(shù)學規(guī)劃方法也同樣適用于UE問題.

［1］陸化普，黃海軍.交通規(guī)劃理論研究前沿［M］.北京:清華大學出版社，2007.

［2］Tobin R L，F(xiàn)riesz T L.Sensitivity analysis for equilibrium network flow［J］.Transportation Science，1988，22(4):242－250.

［3］Ying J Q，Miyagi T.Sensitivity analysis for stochastic user equilibrium network flows—a dual approach［J］.Transportation Science，2001，35(2):124 －133.

［4］Clark S D，Watling D P.Probit-based sensitivity analysis for general traffic network［J］.Journal of the Transportation Research Board，2000，1733:88－95.

［5］程琳，王煒，王京元，等，用戶均衡網(wǎng)絡中的敏感度分析方法［J］.系統(tǒng)工程理論與實踐，2004，24(11):116－121.

Cheng Lin，Wang Wei，Wang Jingyuan，et al.Solution to sensitivity analysis for the equilibrium network flow［J］.Systems Engineering—Theory＆Practice，2004，24(11):116 －121.(in Chinese)

［6］Akamatsu T.Decomposition of path choice entropy in general transport network ［J］.Transportation Science，1997，31(4):349－362.

［7］Fiacco A V.Introduction to sensitivity and stability analysis in nonlinear programming［M］.New York:Academic Press，1983.

［8］Lee D H，Meng Q，Deng W J.Origin-based partial linearization method for stochastic user equilibrium traffic assignment problem［J］.Journal of Transportation Engineering，2010，136(1):52 －60.

［9］Bell M G H.Alternatives to Dial's logit assignment algorithm［J］.Transportation Research，1995，29(4):287－295.

［10］Dial R B.A probabilistic multipath traffic assignment model which obviates path enumeration［J］.Transportation Research，1971，5(2):83－111.

Sensitivity analysis for link-based stochastic user equilibrium network flows

Cheng Lin Ji Kui Pu Ziyuan Wang Yue

(School of Transportation，Southeast University，Nanjing 210096，China)

Abstract:In order to explore an efficient algorithm for the Logit-based stochastic user equilibrium(SUE)problem，the conventional entropy of the SUE model was decomposed to get the link-based SUE model.In this paper，based on analysis of the Link-based SUE model and its optimizing conditions，a mathematical programming method of sensitivity analysis for the model is presented.The method is more likely to be accepted relative to the variational inequality method.Since user equilibrium in a traffic network is an extreme case of SUE，the method can be used for the Wardropian equilibrium also.Numerical examples are solved by the method of successive averages algorithm and the sensitivity matrixes，both results are consistent.The“segmented solution”method is given to deal with the rank defect，solving the phenomena of the matrixes which can't be inversed effectively.

Key words:link-based stochastic user equilibrium;sensitivity analysis;mathematical programming;Logit

中圖分類號:U491.1

A

1001－0505(2013)01-0221-05

doi:10.3969/j.issn.1001 －0505.2013.01.040

收稿日期:2012-04-29.

程琳(1963—)，男，博士，教授，博士生導師，gist@seu.edu.cn.

基金項目:國家自然科學基金資助項目(51078085，51178110).

引文格式:程琳，紀魁，蒲自源，等:路段型隨機均衡敏感度分析［J］.東南大學學報:自然科學版，2013，43(1):221－225.［doi:10.3969/j.issn.1001 －0505.2013.01.040］