第九章-基本交通分配模型1

9.1平衡和非平衡分配9.2非平衡分配法9.3平衡分配法9.4隨機(jī)分配(StochasticAssignment)方法第九章基本交通分配模型【例題9-1】設(shè)OD之間交通量為q=2000輛，有兩條徑路a與b。徑路a行駛時(shí)間短，但是通行能力小，徑路b行駛時(shí)間長(zhǎng)，但通行能力大。假設(shè)各自的行駛時(shí)間（min）與流量的關(guān)系如下式所示，求徑路

a與b上分配的交通量。9.1平衡和非平衡分配根據(jù)

Wardrop平衡第一原理的定義，很容易建立下列的方程組：則有：顯然

qb只有在非負(fù)解時(shí)才有意義，即：也就是說，當(dāng)OD交通量小于250時(shí)，，則當(dāng)OD交通量大于250時(shí)，兩條徑路上都有一定數(shù)量的車輛行駛.當(dāng)q=2000時(shí)，平衡流量為:目前，在交通流分配理論的中，以

Wardrop第一原理為基本指導(dǎo)思想的分配方法比較多。國(guó)際上通常將交通分配方法分為平衡分配和非平衡分配兩大類。對(duì)于完全滿足Wardrop原理定義的平衡狀態(tài)，則稱為平衡分配方法；對(duì)于采用啟發(fā)式方法或其他近似方法的分配模型，則稱為非平衡分配方法。交通分配模型的分類非平衡分配方法按其分配方式可分為變化路阻和固定路阻兩類；按分配形態(tài)可分為單徑路與多徑路兩類。9.2非平衡分配法分配形態(tài)分配方式固定路阻變化路阻單徑徑路全有全無方法容量限制方法多徑徑路靜態(tài)多徑徑路方法容量限制多徑徑路方法表9-1非平衡分配模型分類算法思想：將OD交通量q加載到路網(wǎng)的最短徑路上，從而得到路網(wǎng)中各路段流量的過程。計(jì)算步驟：步驟0初始化，使路網(wǎng)中所有路段的流量為0，并求出各路段自由流狀態(tài)時(shí)的阻抗。步驟1計(jì)算路網(wǎng)中每個(gè)出發(fā)地O到每個(gè)目的地D的最短徑路。步驟2將O、D間的OD交通量全部分配到相應(yīng)的最短徑路上。一、全有全無分配方法（all-or-nothingassignmentmethod）0-1分配法的特點(diǎn)計(jì)算簡(jiǎn)單；是其它交通分配的基礎(chǔ)；出行量分布不均勻，全部集中在最短路上；未考慮路段上的容量限制，有時(shí)分配到的路段交通量大于道路的通行能力；有時(shí)某些路段上分配到的交通量為0，與實(shí)際情況不符；隨著交通量的增加，未考慮到行程時(shí)間的改變。增量分配法是容量限制最短路交通分配法的進(jìn)一步推廣，又稱為比例配流方法。分配原則將原OD矩陣分成N

等份，對(duì)每一個(gè)小矩陣用最短路分配方法分配，完成以后，根據(jù)阻抗函數(shù)重新計(jì)算各條邊的阻抗（時(shí)間），然后再對(duì)下一個(gè)小矩陣進(jìn)行分配，直到N個(gè)矩陣分配完畢。二、增量分配法（incrementalassignmentmethod）Step0：初始化。將每組OD交通量平分成N等份，即使

。同時(shí)令

。Step1：更新路段行駛時(shí)間

。Step2：增量分配。按Step1計(jì)算出的路段時(shí)間

，用最短路分配法將

分配到網(wǎng)絡(luò)中去，得到一組附加交通流量

。Step3：累加交通流量，即

Step4：判斷終止條件。如果n=N，停止計(jì)算，當(dāng)前路段流量即是最終分配結(jié)果；如果n<N，令n=n+1，返回Step1。

增量分配法的特點(diǎn)當(dāng)N=1時(shí)為0—1分配；當(dāng)N→∞時(shí)，趨向均衡分配。該方法簡(jiǎn)單，精度可以根據(jù)N

的大小來調(diào)節(jié)，因而在實(shí)際中常被采用。該方法仍然是近似算法，有時(shí)會(huì)將過多的流量分配到容量小的路段。N越大，配流結(jié)果越接近均衡解，但計(jì)算工作量相應(yīng)增加。另外，非常大的N值也不能完全保證配流結(jié)果一定滿足用戶均衡條件。介于增量分配法和平衡分配法之間的一種循環(huán)分配方法算法思想：不斷調(diào)整各路段分配的流量而逐漸接近平衡分配結(jié)果。每步循環(huán)中，根據(jù)各路段分配到的流量進(jìn)行一次全有全無分配，得到一組各路段的附加流量；三、連續(xù)平均法（

methodofsuccessiveaverages）Step0初始化。根據(jù)各路段自由行駛時(shí)間進(jìn)行

0-1全有全無分配，得到初始解。令迭代次數(shù)

n=0，路阻函數(shù)Step1令n=n+1，按照當(dāng)前各路段的交通量計(jì)算各路段的路阻

。Step2按照

Step1求得的行駛時(shí)間和OD交通量進(jìn)行全有全無

0-1分配。得到各路段的附加交通量。Step3用加權(quán)平均法計(jì)算各路段當(dāng)前交通量（8-1）Step4如果相差不大，則停止計(jì)算。即為最終分配結(jié)果。否則返回

Step1。實(shí)踐中

Step4停止計(jì)算的判斷即可用誤差大小，也可以用循環(huán)次數(shù)的多少來進(jìn)行運(yùn)算的控制；用的比較多的是循環(huán)次數(shù)。在Step3中權(quán)重系數(shù)

a由計(jì)算者給定。a即可定為常數(shù)，也可定為變數(shù)。通常定為常數(shù)時(shí)a=0.5；定為變數(shù)時(shí)a=1/n，n是循環(huán)次數(shù)?！纠}

9-2】:設(shè)下圖

所示交通網(wǎng)絡(luò)的

OD交通量為200輛，各徑路的交通費(fèi)用函數(shù)分別為：試用全有全無分配法、增量分配法、連續(xù)平均法求出分配結(jié)果，并進(jìn)行比較。

【解】：1.全有全無分配法由路段費(fèi)用函數(shù)可知，在路段交通量為零時(shí)，徑路1最短。根據(jù)全有全無原則，交通量全部分配到徑路1上，得到以下結(jié)果：因?yàn)?，，根?jù)

Wardrop原理，網(wǎng)絡(luò)沒有達(dá)到平衡狀態(tài)，沒有得到均衡解。此時(shí)路網(wǎng)總費(fèi)用為：

2.增量分配法采用

2等分。(1)第

1次分配與全有全無分配法相同，徑路

1最短。(2)第

2次分配，此時(shí)最短徑路變?yōu)閺铰?這時(shí)，根據(jù)

Wardrop原理，各條徑路的費(fèi)用接近相等，路網(wǎng)接近平衡狀態(tài)，結(jié)果接近于平衡解。此時(shí)路網(wǎng)總費(fèi)用為：3.連續(xù)平均法（相對(duì)誤差取5%）(1)初始化，全有全無分配

令迭代次數(shù)n=0，路段阻抗：

(2)令n=n+1=1，按照

(1)中求得的行駛時(shí)間和OD交通量進(jìn)行全有全無

0-1分配。得到各路段的附加交通量：用加權(quán)平均法（式8-1）計(jì)算各路段當(dāng)前交通量，取a=1/n=1，則得：(3)計(jì)算間的相對(duì)誤差δi1(i=1,2,3，計(jì)算時(shí)除數(shù)值若為0，則δi0變?yōu)?.1)重新計(jì)算路段阻抗：(4)令n=n+1=2，按照

(3)中求得的行駛時(shí)間對(duì)OD交通量重新進(jìn)行

0-1分配。得到各路段的附加交通量：取a=1/n=0.5用加權(quán)平均法（式8-1）計(jì)算各路段當(dāng)前交通量:(5)計(jì)算間的相對(duì)誤差δi2重新計(jì)算路段阻抗：(6)令n=n+1=3，重新計(jì)算(7)……不斷迭代直至n=23，求得

，

，計(jì)算結(jié)束，即上述分配結(jié)果為最終結(jié)果。此時(shí)路網(wǎng)總費(fèi)用為：

9-1、已知交通需求和網(wǎng)絡(luò)模型如下，試用0-1分配法配流，q19=1000輛/日；q29=500輛/日。第九章作業(yè)9-2、分為10份進(jìn)行增量分配9-3、用連續(xù)平均分配法求解下面的固定需求交通分配問題（迭代2次）9.3平衡分配法發(fā)展歷程從

1952年Wardrop提出道路網(wǎng)平衡的概念和定義之后，如何求解Wardrop平衡成了研究者的重要課題。1956年，Beckmann等提出了描述平衡交通分配的一個(gè)數(shù)學(xué)規(guī)劃模型。經(jīng)過20年之后，即到1975年才由LeBlanc等學(xué)者設(shè)計(jì)出了求解Beckmann模型的算法（將Frank-Wolfe算法用于求解該模型），從而形成了現(xiàn)在的實(shí)用解法。9.3.1用戶優(yōu)化均衡交通分配模型UserEquilibrium（用戶均衡）的基本假設(shè)有：假設(shè)出行者都力圖選擇阻抗最小的路徑；假設(shè)出行者能隨時(shí)掌握整個(gè)網(wǎng)絡(luò)的狀態(tài)，即能精確計(jì)算每條路徑的阻抗從而做出完全正確的路徑選擇決策；假設(shè)出行者的計(jì)算能力和計(jì)算水平是相同的。UE的定義：當(dāng)不存在出行者能單方面改變其出行路徑并能降低其阻抗時(shí)，達(dá)到了UE狀態(tài)。一、用戶平衡分配模型及其求解算法（1）模型化其中，hkrs：OD對(duì)rs間第k條徑路的交通量。

tkrs：OD對(duì)rs間第k條徑路的行駛時(shí)間。trs：OD對(duì)rs間最短徑路的行駛時(shí)間。qrs：OD對(duì)rs的分布交通量。路段阻抗：ta=ta(xa)【例9-3】如圖表示了一對(duì)由兩條可選路徑連接的起終點(diǎn)，t1,t2分別表示路段1,2上的交通時(shí)間，用x1,x2表示相應(yīng)的交通流量，q表示總的OD流量，則q=x1+x2。分析：當(dāng)q非常小時(shí)，所有用戶都選擇路段1，也即：

當(dāng)q<q’時(shí)，

x1=q,x2=0;

當(dāng)q>=q’時(shí)，

x1>0,x2>0;此時(shí)，若已知t=t1=t2則

x1=t1-1

(t)，x2=t2-1(t)q’tx2x1(2)Wardrop第一平衡原理的等價(jià)最優(yōu)化問題原理理論上合理，實(shí)際求解非常困難。Beckmann（1956）等價(jià)數(shù)理最優(yōu)化模型（有約束非線性最優(yōu)化問題）其中：

，表示路段a上的交通流量；：路段

-徑路相關(guān)變量，即

0-1變量。如果路段a屬于從出發(fā)地為r目的地為s的OD間的第k

徑路，則其值為1，否則為0；fkrs：出發(fā)地為r，目的地為s的

OD間的第k條徑路上的流量；qrs：出發(fā)地r和目的地s之間的

OD交通量。【例題

9-4】：如圖所示，為一個(gè)只有兩條徑路（同時(shí)也是路段）、連接一個(gè)出發(fā)地和一個(gè)目的地的簡(jiǎn)單交通網(wǎng)絡(luò)，兩個(gè)路段的阻抗函數(shù)分別是：

t1=2+x1

，

t2=1+2x2

OD量為

q=5，分別求該網(wǎng)絡(luò)的

Beckmann模型的解和均衡平衡狀態(tài)的解。

【解】：

先求

Beckmann模型的解。將阻抗函數(shù)帶入模型，得：將

x2=5-x1帶入目標(biāo)函數(shù)并進(jìn)行積分，轉(zhuǎn)換為無約束的極小值問題：

min:Z(X)=1.5x12-9x1+30另

dZ/dx1=0，解得

x1*=3，

x2*=2。

下面求平衡狀態(tài)的解，根據(jù)

Wardrop用戶平衡原理，網(wǎng)絡(luò)達(dá)到平衡是應(yīng)該有：

t1=t2和

x1+x2=5。聯(lián)立求解這個(gè)方程組，很容易求得

x1=3，

x2=2。此時(shí)，t1=t2=5。

可見，對(duì)于該路網(wǎng)，Beckmann模型的解和平衡狀態(tài)的解完全相同。

（3）Beckmann模型等價(jià)于

Wardrop原理的證明證明：對(duì)Bechmann的模型構(gòu)造拉格朗日方程如下：（9-1）其中，urs是拉格朗日乘子。根據(jù)非線性規(guī)劃理論中的庫(kù)恩

-塔克（

Kuhn-Tucher）條件，拉格朗日函數(shù)在極值點(diǎn)必須滿足下列條件：（9-2）另外，對(duì)拉格朗日乘子求偏導(dǎo)，可得到：（9-3）通過對(duì)拉格朗日函數(shù)求偏導(dǎo)可以得到式（9-2）和式（9-3）中各項(xiàng)的具體結(jié)果，過程如下：（9-4）其中，

(L：網(wǎng)絡(luò)中路段的集合)又因?yàn)椋?/p>

以及，所以，（9-5）其中clmn：出發(fā)地為m，目的地為n的

OD

間的第l條徑路的阻抗；

另外，在式（9-4）的第二項(xiàng)中，。因此，第二項(xiàng)可以簡(jiǎn)化為：

（9-6）將式（9-5）和式（9-6）代回式（9-4），得:因此式（9-2）的庫(kù)恩-塔克條件可以簡(jiǎn)化表式示為：

（9-7a）（9-7b）?式（9-7）對(duì)任意的k，r，s都成立，即對(duì)任意的OD對(duì)都成立。進(jìn)一步分析其實(shí)際意義可知，對(duì)于某個(gè)特定的連接r和s的徑路，某徑路k的流量fkrs由兩種可能：

①如果fkrs>0，由式（9-7a），得ckrs=urs

；

②如果fkrs=0，由式（9-7b），得ckrs≥urs。

因此，任何情況下，徑路k的阻抗總是不小于拉格朗日乘子urs。據(jù)此推斷，就是(r,s)間的最小阻抗。當(dāng)徑路k上有從(r,s)的流量時(shí)，徑路k的阻抗必等于(r,s)間最短徑路的阻抗；當(dāng)徑路k上沒有從(r,s)的流量時(shí)，徑路k的阻抗必大于或等于(r,s)間最短徑路的阻抗。而這正是

Wardrop平衡原理所描述的，因此，

Beckmann模型的解滿足

Wardrop的平衡準(zhǔn)則。（4）解的唯一性證明模型具有唯一解的條件：約束條件式形成凸領(lǐng)域，并且目標(biāo)函數(shù)為狹義凸函數(shù)。補(bǔ)充知識(shí)：

對(duì)于區(qū)間I,設(shè)f(x)為定義在區(qū)間I上的函數(shù)，若對(duì)I上的任意兩點(diǎn)x1，x2和任意的實(shí)數(shù)λ∈(0,1)，總有

f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2),則f(x)稱為I上的凸函數(shù)。

判定方法可利用定義法、已知結(jié)論法以及函數(shù)的二階導(dǎo)數(shù)Beckmann模型的約束條件均為線性函數(shù)，所以形成的領(lǐng)域?yàn)橥诡I(lǐng)域。Z函數(shù)為凸函數(shù)的條件為：?2Z/?xa2>0由目標(biāo)函數(shù)知，?Z/?xa=ta(xa),因?yàn)?/p>

Beckmann模型建立的假設(shè)前提是路段的阻抗只和自身的流量有關(guān)，與別的路段的流量無關(guān)，所以：所以，目標(biāo)函數(shù)Z海賽矩陣為：當(dāng)所有路段的阻抗函數(shù)都是單調(diào)遞增函數(shù)時(shí)，，則目標(biāo)函數(shù)

Z

的海賽矩陣是正定的，目標(biāo)函數(shù)是嚴(yán)格凸的。根據(jù)

Beckmann模型建立時(shí)對(duì)阻抗函數(shù)要求是單調(diào)遞增函數(shù)的前提，所以說

Beckmann模型有唯一的最小點(diǎn)

x*。也就是說，當(dāng)達(dá)到分配平衡時(shí)，分配到各路段上的流量是唯一的。

二、用戶平衡分配模型求解算法1975年由

LeBlanc等學(xué)者將

Frank-Wolfe算法（F-W算法）用于求解

Beckmann模型F-W算法是用線性規(guī)劃逐步逼近非線性規(guī)劃的方法來求解UE模型的。思路如下：從某一初始點(diǎn)出發(fā)，進(jìn)行迭代，每步迭代中，先找到一個(gè)最速下降的方向，然后再找到一個(gè)最優(yōu)步長(zhǎng)，在最速下降方向上截取最優(yōu)步長(zhǎng)得到下一步迭代的起點(diǎn)。重復(fù)此過程，直到找到最優(yōu)解。此法的前提條件是模型的約束條件必須都是線性的。梯度法(最速下降法

steepestdescentmethod)（1）F-W算法簡(jiǎn)介設(shè)有非線性規(guī)劃模型：

min：Z=f(X)s.t.AX=B

，X≥0式中：X、B：向量；A：矩陣。對(duì)目標(biāo)函數(shù)f(X)進(jìn)行在X0處的一階泰勒展開，得：

f(X)=f(X0)+▽f(X0)(X-X0)（

9-8）

此展開式將目標(biāo)函數(shù)f(X)近似地表達(dá)成線性函數(shù)，則上述的非線性規(guī)劃模型可以近似轉(zhuǎn)化為下列線性規(guī)劃模型：

min：

Z=f(X0)+▽f(X0)(X-X0) （

9-9）

s.t.AX=B

，X≥0 去掉目標(biāo)函數(shù)中的常數(shù)項(xiàng)，簡(jiǎn)化成如下等價(jià)的線性規(guī)劃：

min：

Z=▽f(X0)X

（

9-10）s.t.AX=B

，X≥0 解（

9-10）線性規(guī)劃問題，可以得到一組最優(yōu)解。

F-W方法認(rèn)為和的連線為目標(biāo)函數(shù)的最速下降方向。然后把根據(jù)線性極值問題：求得的

λ

作為最優(yōu)步長(zhǎng)。令，從而得到下一步迭代的起點(diǎn)。如此循環(huán)，直到和十分接近為止。

由于該方法在每一步迭代中都必須求解一組線性規(guī)劃問題，在一般的非線性規(guī)劃模型中，該方法由于計(jì)算量過大而不適用。只是在近似線性規(guī)劃模型易于求解時(shí)，該方法才有應(yīng)用價(jià)值，而交通分配模型正好具有這一特點(diǎn)。（2）Beckmann模型的搜索方向問題已知迭代起點(diǎn)，求下一步迭代方向，即求解以下式為目標(biāo)函數(shù)的線性規(guī)劃：s.t.

；

；式中，

表示目標(biāo)函數(shù)的梯度，X,Y表示矩陣；

ya為輔助路段流；分析：為已知數(shù)，求一系列ya，使網(wǎng)絡(luò)的總行駛時(shí)間最小的交通分配問題。解法：0-1分配即可實(shí)現(xiàn)，即每一OD對(duì)均沿最短路分配，以獲取輔助路段流ya。求出的xn與yn的連線即為下一步迭代的方向，即dn=yn-xn

（3）最優(yōu)步長(zhǎng)的確定問題迭代步長(zhǎng)由下面的一維極值問題決定：

s.t.令

，有：可用許多一維搜索方法求得最優(yōu)步長(zhǎng)

（如二分法、0.618法等）。（4）Beckmann模型的F-W算法求解方法:步驟

1：初始化。按照，進(jìn)行

0-1交通分配，得到各路段的流量；令

n=1。

步驟

2：更新各路段的阻抗：

。

步驟

3：尋找下一步迭代方向：按照更新后的{tan}，再進(jìn)行一次

0-1交通分配，得到一組附加流量

{yan}。步驟

4：確定迭代步長(zhǎng)：用二分法求滿足下式的λ

。

步驟

5：確定新的迭代起點(diǎn)：

。

步驟

6：收斂性檢驗(yàn)。如果滿足：

其中ε是預(yù)先給定的誤差限值。如果條件滿足，則{}就是要求的平衡解，計(jì)算結(jié)束；否則，令n=n+1，返回

步驟

2。

【例9-5】UE分配算例：設(shè)圖所示交通網(wǎng)絡(luò)的OD交通量為200輛，各徑路的交通費(fèi)用函數(shù)分別如下式所示，試用F-W法求出分配結(jié)果?！窘狻浚航⒂脩艟饽Ｐ蜑椋海?）用全有全無分配法求解初始可行解：（2）求最佳搜索方向繼續(xù)用全有全無分配法求解，得：(3)求最佳步長(zhǎng)λ*將代入目標(biāo)函數(shù)中，得：這時(shí)，求滿足dZ/dλ=0的λ*，：所以，λ*=0.6這時(shí)，交通量：費(fèi)用（時(shí)間）：目標(biāo)函數(shù)：收斂判定：所以，滿足了Wardrop第一平衡原理F-W算法的缺陷F-W算法在迭代后期階段收斂很慢，原因是當(dāng)趨近于最優(yōu)解時(shí)，搜索方向?qū)⒋怪庇谀繕?biāo)函數(shù)在點(diǎn)的梯度。影響F-W算法收斂速度的因素還有：初始解、網(wǎng)絡(luò)結(jié)構(gòu)和擁擠程度。初始解離平衡點(diǎn)越近，則需要的迭代次數(shù)就越少；網(wǎng)絡(luò)結(jié)構(gòu)越復(fù)雜，或者說從起點(diǎn)到終點(diǎn)的可行路徑數(shù)越多，則需要的迭代次數(shù)就越多；擁擠程度越大的網(wǎng)絡(luò)，需要更多的迭代次數(shù)來達(dá)到平衡點(diǎn)。在實(shí)際應(yīng)用中，對(duì)于大規(guī)模網(wǎng)絡(luò)，通常4至6次迭代就夠了。確定迭代次數(shù)時(shí)，要綜合考慮原始數(shù)據(jù)的準(zhǔn)確性、財(cái)力約束和具體的網(wǎng)絡(luò)結(jié)構(gòu)。9.3.2系統(tǒng)最優(yōu)分配模型及其求解算法（一）系統(tǒng)最優(yōu)分配模型

（二）UE模型與SO模型解的比較Wardrop第二平衡原理：在系統(tǒng)平衡條件下，擁擠的路網(wǎng)上交通流應(yīng)該按照平均或總的出行成本最小為依據(jù)來分配。適用于最大限度地使用現(xiàn)有道路系統(tǒng)的場(chǎng)合（智能交通系統(tǒng)），出于交通管理者的角度考慮。從徑路選擇角度，該分配方法與用戶平衡分配法中用戶一直選擇時(shí)間上的最短徑路不同，它有必要讓用戶選擇最短徑路以外的徑路。（一）系統(tǒng)最優(yōu)分配模型系統(tǒng)最優(yōu)原理比較容易用數(shù)學(xué)模型來表述，其目標(biāo)函數(shù)是網(wǎng)絡(luò)中所有用戶總的阻抗最小，約束條件和用戶平衡分配模型一樣。因此，系統(tǒng)最優(yōu)分配模型是：其中：（二）UE模型與SO模型解的比較對(duì)阻抗函數(shù)進(jìn)行變換，令：則：因此，如果用作為阻抗函數(shù)，則此時(shí)用戶最優(yōu)分配模型完全可以轉(zhuǎn)換為系統(tǒng)最優(yōu)分配模型，所以進(jìn)行該阻抗函數(shù)下的用戶最優(yōu)分配，得到的解就是系統(tǒng)最優(yōu)分配的解。也就是說，對(duì)阻抗函數(shù)進(jìn)行變換后，可以按照用戶最優(yōu)模型的算法來求解系統(tǒng)最優(yōu)模型?！纠}

9-6】：試用系統(tǒng)最優(yōu)分配法求出例

9-5中分配結(jié)果，并與用戶均衡模型結(jié)果進(jìn)行比較?！窘狻浚航⑾到y(tǒng)最優(yōu)分配模型也即:（1）用全有全無分配法求解初始可行解：（2）求最佳搜索方向繼續(xù)用全有全無分配法求解，得：(3)求最佳步長(zhǎng)λ*將代入目標(biāo)函數(shù)中，得：代入上述目標(biāo)函數(shù)Z中，得：這時(shí)，求滿足dZ/dλ=0的λ*，所以，λ*=0.7。這時(shí)，交通量：費(fèi)用（時(shí)間）：目標(biāo)函數(shù)：(4)收斂判定：(5)第二次迭代，按照更新后的費(fèi)用進(jìn)行全有全無分配：(6)求最佳步長(zhǎng)λ*代入上述目標(biāo)函數(shù)Z中，得：這時(shí)，求滿足dZ/dλ=0的λ*，所以，λ*=0，這時(shí)，交通量：則知已得到最優(yōu)解。方法x1x2x3c1c2c3ZUE8012001313152100SO6014001113.5152550表9-2結(jié)果比較9.4隨機(jī)分配方法隨機(jī)分配(StochasticAssignment)由于交通網(wǎng)絡(luò)的復(fù)雜性和路段上交通狀況的多變性，以及各個(gè)出行者主觀判斷的多樣性，某OD點(diǎn)對(duì)之間不同出行者所感知的最短路徑將是不同的、隨機(jī)的，因此這些出行者所選擇的“最短路徑”不一定是同一條，從而出現(xiàn)多路徑選擇的現(xiàn)象。這種交通分配叫做“多路徑分配”，或“隨機(jī)加載”；單一徑路分配→多徑路分配9.4.1Logit型隨機(jī)配流的基本理論假定用戶對(duì)當(dāng)前路網(wǎng)信息的掌握不完全；同時(shí)出行者對(duì)阻抗的估計(jì)視為隨機(jī)變量。仍然用Wardrop第一原理選擇路徑，但這里的路徑為估計(jì)最短路徑，即OD對(duì)間存有多條路線，同一出行者對(duì)不同的路徑存在著不同的估計(jì)，不同的出行者對(duì)同一路徑也存在著不同的估計(jì)。對(duì)某一特定的出行者來說，他總是選擇估計(jì)阻抗最小的路徑。隨機(jī)分配模型就是在研究路徑估計(jì)阻抗分布函數(shù)的基礎(chǔ)上，計(jì)算有多少出行者選擇每一條路徑。設(shè)某OD對(duì)（r,s）之間每個(gè)道路利用者總是選擇自己認(rèn)為阻抗最小的徑路k，此時(shí)稱道路利用者主觀判斷的阻抗值為“感知阻抗”，用Ckrs表示；用ckrs表示徑路的實(shí)際阻抗，則有：式中：εkrs—隨機(jī)誤差項(xiàng)，有E[εkrs]=0。根據(jù)Wardrop徑路選擇原則，第k條徑路被選擇的概率為：根據(jù)效用理論中有關(guān)“效用”的定義，可以用徑路感知阻抗的負(fù)值來表示選擇的效用，即：此時(shí)，徑路的選擇就是一個(gè)多項(xiàng)選擇中挑選效用最大的選擇枝的問題。根據(jù)隨機(jī)效用理論，假定εkrs相互獨(dú)立，且服從相同的Gumbel分布（此時(shí)，可以用一個(gè)ε表示所有的εkrs）的條件下，徑路k的選擇概率為：式中：

b—參數(shù)，與ε的方差有關(guān)，可以證明

。上式即為第七章中講述的Logit模型。用該模型求徑路選擇概率需要把點(diǎn)對(duì)（r，s）之間所有的徑路都找出來，這在實(shí)際中是非常困難的。9.4.2Dial算法1971年Dial發(fā)明了一種算法，能夠在網(wǎng)絡(luò)上有效地實(shí)現(xiàn)Logit模型，但它并不需要求解連接OD點(diǎn)對(duì)的所有徑路的選擇概率和交通量。該算法具有下列特點(diǎn)：（1）認(rèn)為道路利用者不是在出發(fā)點(diǎn)就決定選擇哪條徑路，而是在出行過程中的每一個(gè)節(jié)點(diǎn)都做一次關(guān)于下一步選擇哪條路段走向目的地的選擇。即真正選擇的不是徑路，而是路段（2）道路利用者在一個(gè)節(jié)點(diǎn)處選擇路段時(shí)，并不是以該節(jié)點(diǎn)為起點(diǎn)的每個(gè)路段都考慮，只有并選擇“有效路段”。有效路段、有效徑路:有效路段的定義是：當(dāng)路段（i,j）的上游端點(diǎn)i比下游端點(diǎn)j離起點(diǎn)r近，而且i比j離終點(diǎn)s遠(yuǎn)，則該路段為有效路段。由有效路段組成的徑路稱為有效徑路。Dial算法可以確保出行量分配在使其有效地遠(yuǎn)離其起始節(jié)點(diǎn)的徑路上，那些“走回頭路”的徑路將被剔除掉。Dial算法與Logit模型的計(jì)算結(jié)果完全一致，二者是等價(jià)的。Dial算法步驟：Dial算法的具體步驟如下：步驟1初始化。確定有效路段和有效徑路。1）計(jì)算從起點(diǎn)r到所有節(jié)點(diǎn)的最小阻抗，記為r(i)；2）

計(jì)算從所有節(jié)點(diǎn)到終點(diǎn)s的最小阻抗，記為s(i)；3）

定義Qi為路段起點(diǎn)為i的路段終點(diǎn)的集合；4）定義Di為路段終點(diǎn)為i的路段起點(diǎn)的集合；5）對(duì)每個(gè)路段（i,j），根據(jù)下式計(jì)算“路段似然值（LinkLikelihood）”L(i,j)（此時(shí)通常假定參數(shù)b=1）：

步驟2從起點(diǎn)r開始按照r(i)上升的順序，向前計(jì)算路段權(quán)重。步驟3從終點(diǎn)s開始，按照s(j)上升的順序，向后計(jì)算路段交通量?！纠?-7】如圖a所示的交通網(wǎng)絡(luò)，圖中邊上的數(shù)值是路段的交通阻抗，起點(diǎn)r為①，終點(diǎn)s為⑨，設(shè)q19=1000，求該網(wǎng)絡(luò)的隨機(jī)分配結(jié)果。(a)交通網(wǎng)絡(luò)圖【解】

步驟1初始化。找出有效路段和有效徑路。（1）根據(jù)最短路算法，求出所有的r(i)和s(i)值，如圖(b)所示；(b)最短路權(quán)r(i)和s(i)值（2）根據(jù)路段似然值公式，求出所有路段的似然值（此時(shí)設(shè)b=1），如圖(c)所示。以L(5,8)為例說明如何計(jì)算：因?yàn)?/p>

，所以根據(jù)上述計(jì)算結(jié)果，可知從1到9并非6條徑路都是有效徑路，其中只有4條為有效徑路