雙交通模式隨機用戶平衡問題的一種求解方法*

度 巍 王先甲 黃崇超 肖海燕

(上海金融學(xué)院應(yīng)用數(shù)學(xué)系1) 上海 201209) (武漢大學(xué)系統(tǒng)工程研究所2) 武漢 430072)

(武漢科技大學(xué)冶金工業(yè)過程系統(tǒng)科學(xué)重點實驗室3) 武漢 430081) (武漢大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院4) 武漢 430072)

(湖北第二師范學(xué)院數(shù)學(xué)與計量經(jīng)濟系5) 武漢 430205)

0 引 言

交通分配是交通規(guī)劃理論的基礎(chǔ),自20世紀(jì)50年代Wardrop[1]提出著名的平衡交通分配兩原則以來,國內(nèi)外眾多學(xué)者對于交通分配進(jìn)行了大量研究.在Ward rop的用戶平衡配流原則中,總是假設(shè)出行者精確地了解每條路徑的出行時間,從而始終能做出絕對正確的路徑選擇.而事實上,由于信息掌握得不充分,出行者只能對路徑出行成本作出大致估計,對同一路徑,不同的出行者會有不同的估計值.Dagazno和Sheffi[2]將出行者對路段出行成本的理解值與實際值之差視為隨機變量,給出了隨機用戶平衡(SUE)概念,此后許多學(xué)者對于隨機用戶平衡問題進(jìn)行了深入研究[3-5].文獻(xiàn)[4]首次將交通分配問題從以往的單交通模式擴展到更符合實際的雙交通模式,其中一種為主交通模式(通常為轎車,出租車),另外一種為次交通模式(通常為軌道交通),次交通模式上的行走阻抗為固定值.同時構(gòu)造了在模式分離情形下,一種求解雙交通模式確定性用戶平衡問題的方法.然而當(dāng)主要交通模式采用隨機用戶平衡分配時,尚無有效的求解方法,本文通過在次交通模式路徑上定義虛擬路阻函數(shù),將雙交通模式的交通分配問題轉(zhuǎn)化成為通常的單交通模式下的固定需求隨機用戶平衡問題求解,最后給出了一個算例.

1 基本網(wǎng)絡(luò)描述

定義交通網(wǎng)絡(luò)G=(N,A,M).式中:N為節(jié)點集合;A為有向路段的集合;M為交通模式數(shù),本文將考慮M=2時的情況.a為G中主交通模式的任意一條路段;xa為路段a上的主交通模式流量;ca(xa)為路段a的路阻函數(shù),為單調(diào)遞增函數(shù);W為G中的O-D對集合;w為W中的任一O-D對;Pw為主交通模式中O-D對w間的所有路徑集合;ˉDw為O-D對w間的交通需求;Dw為O-D對w間主交通模式的交通需求;k為主交通模式中屬于Pw的任意一條路徑為O-D對w間路徑k上的主交通模式流量;表示若路段a在連接O-D對w的路徑k上,則為1,否則為0;為O-D對w中,主交通模式出行者對路徑k的估計阻抗,ckw為w中主交通模式路徑k的實際阻抗.

由于次交通模式在各個O-D對w的每條路徑上,其行走阻抗為定值,所以可以認(rèn)為次交通模式在各個O-D上僅有一條路徑,該路徑只含一條路段直接連接各個O-D對,定義該路段為aw,其運行阻抗為定值cw,其路徑上的流量為 fw,圖1是一個4O-D對的雙交通模式路網(wǎng)圖.

圖1 雙交通模式網(wǎng)絡(luò)圖

圖1 中4個O-D對分別為1-8,1-9,2-8,2-9,其中直接連接各個O-D對的路徑為次交通模式的路徑,在雙交通模式下有以下條件成立

當(dāng)雙交通模式下的交通分配達(dá)到隨機用戶平衡時,對主交通模式,各個O-D對路徑交通流應(yīng)滿足如下Logit分配方式

在主交通模式與次交通模式之間,若移植固定需求下的雙模式交通需求分配模式,達(dá)到隨機用戶平衡時,應(yīng)滿足如下關(guān)系w

式中:θ2為交通模式之間的比例參數(shù).

2 問題求解

由于雙模式隨機用戶平衡問題不僅要在主交通模式內(nèi)部,而且還要在交通模式之間達(dá)到隨機用戶平衡,所以使得平衡交通流的求解變得復(fù)雜,下面的定理1將說明,通過對次交通模式路徑賦以適當(dāng)?shù)奶摂M路阻函數(shù),可以將雙模式隨機用戶平衡問題轉(zhuǎn)化成為通常的單模式固定需求隨機用戶平衡問題.

定理1 在路網(wǎng)中,若對次交通模式的路徑(即直接連接O-D對w的路段)賦以如下虛擬路阻函數(shù)

以θ1為Logit比例參數(shù),ˉDw為交通需求的單模式隨機用戶平衡(SUE)問題的平衡路徑流,與雙模式隨機用戶平衡交通流相同.

證明 令 fw*為交通路網(wǎng)在單模式、固定需求下達(dá)到隨機用戶平衡時,次交通模式的路徑流量 ,由式(6),有

將式(9)代入式(10)得

即

化簡得

進(jìn)一步有

即

最后得

由式(16),可得

由式(3)與式(17),可得

式(18)正好是雙模式彈性隨機用戶平衡時,兩模式之間的分配關(guān)系式(8).

對于原主交通模式的路徑,不失一般性,考慮O-D對w的路徑k.當(dāng)達(dá)到單模式、固定需求下的隨機用戶平衡時,其平衡流fw*k 應(yīng)滿足

將式(9)代入式(19)有

將式(17)代入式(20),化簡得

整理式(21),得

由式(18)知式(22)即為

式(23)表明,在網(wǎng)絡(luò)中,當(dāng)達(dá)到單模式、固定需求下的隨機用戶平衡時,原主交通模式的各個路徑平衡流也與雙模式隨機用戶平衡流相同,從而定理獲證.

3 雙模式隨機用戶平衡問題的數(shù)學(xué)規(guī)劃模型

由于定義的路阻函數(shù)是可分離的,該問題對應(yīng)的數(shù)學(xué)規(guī)劃模型可以證明數(shù)學(xué)規(guī)劃(24)的K-K-T條件滿足雙交通模式下的隨機用戶平衡條件,即式(6),式(8).

同時式(24)關(guān)于變量的Hessian矩陣為

對式(9)關(guān)于 fw求導(dǎo),得

由于次交通模式的運行阻抗為固定值,從而出行者對于交通模式之間運行阻抗的觀察誤差比例系數(shù)θ2不大于出行者在主交通模式中各O-D對路徑間的觀察誤差比例系數(shù)θ1,從而式(29)大于零,故H essian矩陣正定,從而數(shù)學(xué)規(guī)劃(24)為嚴(yán)格凸規(guī)劃,存在唯一解.

4 算 例

最后通過求解圖1所示的交通路網(wǎng)所對應(yīng)的雙模式隨機用戶平衡配流,檢驗本文提出方法的可行性.

交通網(wǎng)絡(luò)1中,各個O-D對交通需求量及有效路徑集合如表1所列,表中括號內(nèi)是路徑所包含的路段.

表1 路徑列表

對上述雙模式隨機用戶平衡交通分配問題所對應(yīng)的數(shù)學(xué)規(guī)劃模型,本文用仿射尺度內(nèi)點算法求解[8-11].該算法的思想是:對于當(dāng)前迭代點Fk=(,…,構(gòu)造對角陣 D k=diag(,…),作仿射尺度變換 Tk:g=D k-1Fk,在此變換下,式(24)變?yōu)槿缦滦问?/p>

式中:ˉA k=AD k,A為式對應(yīng)的約束矩陣;b為O-D需求向量.在仿射尺度變換下,Fk將被變換到(26 b)的約束區(qū)域的中心e=(1,1,…,1)T,從e出發(fā)沿式(26 a)的目標(biāo)函數(shù)在gk=e處的負(fù)梯度在矩陣ˉA k核空間的投影方向作一維搜索,得新的可行內(nèi)點Fk+1.

算法迭代步驟如下.

步驟1 取初始可行路徑配流F1=(fw1,11,…,fwnm,1)T,允許誤差ε＞0,置迭代數(shù)k=1.

步驟2 由Fk構(gòu)造對角陣Dk=diag,…,fwnm,k),計算▽G k(e)=D k▽F(fk),Aˉ k=ADk,

步驟3 若▽′G k(e)=0或者‖ ▽′Gk(e)‖＜ε,最優(yōu)配流為 Fmin,=Fk=Dke算法停止,否則轉(zhuǎn)步驟4.

步驟5 設(shè)λk為一維搜索得到的最佳步長,令Fk+1=Fk+λKDkdk,k:=k+1,轉(zhuǎn)步驟2.

在本算例中,取θ1=2,θ2=1,而各路段自由流阻抗分別為[5 6 5 3 3 4 4 6.5 6.5 7 7 16 21 16.5 22 5 5].求得的雙模式隨機用戶最優(yōu)配流結(jié)果如表2所列.

表2 雙模式隨機用戶最優(yōu)配流結(jié)果

5 結(jié) 束 語

本文通過對次交通模式上的路徑賦以虛擬路阻函數(shù),將雙交通模式隨機用戶平衡問題轉(zhuǎn)化成單模式隨機用戶平衡問題求解,并用仿射尺度內(nèi)點算法對一個小型路網(wǎng)進(jìn)行了數(shù)值實驗.當(dāng)次交通模式的出行路阻為變量時以及當(dāng)交通模式多于兩個時所對應(yīng)的隨機用戶平衡交通分配將是下一步的研究方向.

[1]Wardrop JG.Some theoretical aspects of road traffic research[J].Proceedings of the Institute of Civil Engineers,1952(2):325-378.

[2]Daganzo CF,SheffiY.On stochasticmodels of traffic assignment[J].Transportation Science,1977,11(3):253-274.

[3]Sheffi Y.U rban transportation netw orks:Equilibrium analysis w ith mathematical p rogram methods[M].New Jersey,Prentice-Hall,INC,Englewood Cliffs,1985.

[4]Florian M.A traffic equilibrium model of travel by car and pub lic transitmodes[J].Transportation Science,1977,11(2):166-179.

[5]Gartner N H.Op timal traffic assignment with elastic demands:A review;Part II:A lgorithmic approaches[J].Transportation Science,1980,14(2):192-208.

[6]度 巍,王先甲,黃崇超.一種求解彈性需求隨機用戶平衡問題的新方法[J].上海交通大學(xué)學(xué)報,2009,43(2)230-234.

[7]周 晶.隨機交通均衡配流模型及其等價的變分不等式問題[J].系統(tǒng)科學(xué)與數(shù)學(xué),2003,23(1):120-127.

[8]陳森發(fā),周 晶,朱玉全.城市交通均衡流分配的多模式模型及算法[J].自動化學(xué)報,1993,(12):190-196.

[9]Huang CC,JiC M.Gradient projectionmethod with affine scaling for non linear programm ing[J].Advances in Modeling&Analysis,1994,22(2):43-48.

[10]四兵鋒,高自友.多模式的城市混合交通均衡配流模型及算法[J].公路交通科技,1999,16(1):44-48.

[11]劉海旭,蒲 云.多類型彈性需求隨機用戶平衡分配模型[J].系統(tǒng)工程理論方法應(yīng)用,2005,14(2):159-165.