雙交通模式隨機(jī)用戶平衡問(wèn)題的一種求解方法*

度 巍 王先甲 黃崇超 肖海燕

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

2 問(wèn)題求解

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

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

以θ1為L(zhǎng)ogit比例參數(shù),ˉDw為交通需求的單模式隨機(jī)用戶平衡(SUE)問(wèn)題的平衡路徑流,與雙模式隨機(jī)用戶平衡交通流相同.

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

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

即

化簡(jiǎn)得

進(jìn)一步有

即

最后得

由式(16),可得

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

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

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

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

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

整理式(21),得

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

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

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

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

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

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

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

4 算 例

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

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

表1 路徑列表

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

式中:ˉA k=AD k,A為式對(duì)應(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)點(diǎn)Fk+1.

算法迭代步驟如下.

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

步驟2 由Fk構(gòu)造對(duì)角陣Dk=diag,…,fwnm,k),計(jì)算▽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為一維搜索得到的最佳步長(zhǎng),令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].求得的雙模式隨機(jī)用戶最優(yōu)配流結(jié)果如表2所列.

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

5 結(jié) 束 語(yǔ)

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

[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ī)用戶平衡問(wèn)題的新方法[J].上海交通大學(xué)學(xué)報(bào),2009,43(2)230-234.

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

[8]陳森發(fā),周 晶,朱玉全.城市交通均衡流分配的多模式模型及算法[J].自動(dòng)化學(xué)報(bào),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ī)用戶平衡分配模型[J].系統(tǒng)工程理論方法應(yīng)用,2005,14(2):159-165.