交通規(guī)劃8課件

第八章交通流分配第一節(jié)概述第二節(jié)交通流分配中的基本概念第三節(jié)非平衡分配方法第四節(jié)平衡分配方法第五節(jié)隨機(jī)分配方法第六節(jié)動態(tài)交通流分配本章內(nèi)容2/6/2023第一節(jié)概述城市交通網(wǎng)絡(luò)上形成的交通流量分布是兩種機(jī)制相互作用直至平衡的結(jié)果。實際中路阻是常量還是變量？路徑選擇的隨機(jī)性表現(xiàn)在哪些方面，在交通分配時將會有何思路解決。明確幾個問題：？2/6/2023鄧建華第二節(jié)交通流分配中的基本概念一、交通分配交通流分配涉及到以下幾個方面:可將現(xiàn)狀OD交通量分配到現(xiàn)狀交通網(wǎng)絡(luò)上，以分析目前交通網(wǎng)絡(luò)的運(yùn)行狀況。也可以是將規(guī)劃年OD交通量分布預(yù)測值分配到現(xiàn)狀交通網(wǎng)絡(luò)上，以得到規(guī)劃年交通需求，為交通網(wǎng)絡(luò)的規(guī)劃設(shè)計提供依據(jù)。還可以將規(guī)劃年OD交通量分布預(yù)測值分配到規(guī)劃交通網(wǎng)絡(luò)上，以評價交通網(wǎng)絡(luò)規(guī)劃方案合理性。2/6/2023鄧建華二、交通阻抗交通阻抗（或者稱為路阻）在交通流分配中通過路阻函數(shù)來描述，所謂路阻函數(shù)是指路段行駛時間與路段交通負(fù)荷，交叉口延誤與交叉口負(fù)荷之間的關(guān)系。在具體分配過程中，由路段行駛時間及交叉口延誤共同組成出行交通阻抗。2/6/2023鄧建華二、交通阻抗交通阻抗由兩部分組成：路段阻抗和節(jié)點阻抗。城市道路：1.路段阻抗公路：BPR公路行駛時間函數(shù)：2/6/2023鄧建華2.節(jié)點阻抗公路：因為路段比較長，路段延誤占絕大 多數(shù)，一般不計交叉口延誤。城市道路：可以計算分流向的、不分流的 交通流的延誤，但是在實際操 作中比較困難，所以也可忽略 不計，或簡單估計。2/6/2023鄧建華

（二）最短徑路算法最短徑路算法是交通流分配中最基本也最重要的算法，幾乎所有交通流分配方法都是以它作為一個基本子過程反復(fù)調(diào)用。最短路算法問題包含兩個子問題：兩點間最小阻抗的計算和兩點間最小阻抗徑路的辨識。在各類文獻(xiàn)中，有關(guān)交通流分配最短徑路的算法很多，如Dijkstra法、矩陣迭代法、Floyd-Warshall法等。2/6/2023鄧建華1．Dijkstra法（標(biāo)號法）(1)算法思想

①首先從起點O開始，給每個節(jié)點一個標(biāo)號,分為T標(biāo)號和P標(biāo)號兩類；

T是臨時標(biāo)號，表示從起點O到該點的最短路權(quán)上限；

P標(biāo)號是固定標(biāo)號，表示從起點O到該點的最短路權(quán)。

②標(biāo)號過程中，T標(biāo)號一直在改變，P標(biāo)號不再改變，凡是沒有標(biāo)上P標(biāo)號的點，都標(biāo)上T標(biāo)號。

③算法的每一步把某一點的T標(biāo)號改變?yōu)镻標(biāo)號，直到所有的T標(biāo)號都改變?yōu)镻標(biāo)號。即得到從始點O到其他各點的最短路權(quán)，標(biāo)號過程結(jié)束。2/6/2023鄧建華1．Dijkstra法（標(biāo)號法）(2)算法步驟

Step1

初始化：給起點1標(biāo)上P標(biāo)號P(1)=0，其余各點均表標(biāo)上T標(biāo)號T1(j)=∞，j=2,3…,.n。即表示從起點1到1的最短路權(quán)為0，到其他各點的最短路權(quán)的上限臨時定為∞。標(biāo)號中括號內(nèi)數(shù)字表示節(jié)點號，下標(biāo)表示第幾步標(biāo)號。經(jīng)過第一步標(biāo)號得到一個P標(biāo)號P(1)=0。2/6/2023鄧建華1．Dijkstra法（標(biāo)號法）(2)算法步驟

在所有的T標(biāo)號（包括沒有被修改的）中，比選出最小的T標(biāo)號Tk（j0）：

式中j0—最小T標(biāo)號所對應(yīng)的節(jié)點號；T(r)—與i點不相鄰點r的T標(biāo)號。給點j0標(biāo)上P標(biāo)號：P(j0)=Tk(j0)，第K步標(biāo)號結(jié)束。Step3當(dāng)所有節(jié)點中已經(jīng)沒有T標(biāo)號，算法結(jié)束，得到從起點1到其他各點的最短路權(quán)；否則返回Step2。2/6/2023鄧建華【例8－1】步驟1給定起點1的P標(biāo)號：P[1]=0，其他節(jié)點標(biāo)上T標(biāo)號：T1(2)=…=T1(9)=∞。步驟2節(jié)點1剛得到P標(biāo)號。節(jié)點2、4與1相鄰，且均為T標(biāo)號，修改這兩點的T標(biāo)號： T2(2)=min[T1(2),P(1)+d12]=min[∞,0+2]=2 T2(4)=min[T1(4),P(1)+d14]=min[∞,0+2]=2在所有（包括沒修改的）T標(biāo)號中，找出最小標(biāo)號。2、4為最小，任選其一，如節(jié)點2，即P[2]=T2(2)=2。步驟3節(jié)點2剛得到P標(biāo)號。節(jié)點3、5與2相鄰，且均為T標(biāo)號，修改這兩點的T標(biāo)號：T3(3)=min[T(3),P(2)+d23]=min[∞,2+2]=4T3(5)=min[T(5),P(2)+d25]=min[∞,2+2]=4在所有T標(biāo)號（點3,4,5…9）中，節(jié)點4為最小，給節(jié)點4標(biāo)上P標(biāo)號，即P[4]=T2(4)=2。2/6/2023鄧建華所有節(jié)點均標(biāo)上了P標(biāo)號，計算結(jié)束。得到節(jié)點1到其他各節(jié)點的最短路權(quán)（P標(biāo)號）表8.2-1例題8-1計算結(jié)果交通規(guī)劃實際中，需要求出路網(wǎng)中任意兩個節(jié)點之間的最短路權(quán)矩陣（n×n階）；盡管Dijkstra算法一次能夠算出從起點到其他各節(jié)點的最短路權(quán)，但仍不能滿足要求，用此方法求最短路權(quán)矩陣，需要反復(fù)運(yùn)算n次，導(dǎo)致計算效率不高，且速度較慢，所需存儲空間較多，在大規(guī)模交通規(guī)劃中應(yīng)用受到一定限制。節(jié)點1234567891024234456P標(biāo)號P(1)P(2)P(3)P(4)P(5)P(6)P(7)P(8)P(9)2/6/2023鄧建華2．矩陣迭代法(2)算法步驟

①首先構(gòu)造距離矩陣（以距離為權(quán)的權(quán)矩陣）。②矩陣給出了節(jié)點間只經(jīng)過一步（一條邊）到達(dá)某一點的最短距離。③對距離矩陣進(jìn)行如下的迭代運(yùn)算，便可以得到經(jīng)過兩步達(dá)到某一點的最短距離：2/6/2023鄧建華【例8－2】(1)距離矩陣如表（構(gòu)造矩陣）

2/6/2023鄧建華(2)矩陣給出了節(jié)點間只經(jīng)過一步（一條邊）到達(dá)某一點的最短距離。

2/6/2023鄧建華（3）進(jìn)行矩陣迭代運(yùn)算經(jīng)過三步到達(dá)某一節(jié)點的最短距離為：（4）再進(jìn)行矩陣迭代運(yùn)算，運(yùn)算方法同上2/6/2023鄧建華3．最短徑路辨識通過Dijkstra算法或矩陣迭代法得到最短路權(quán)矩陣后，還需要把每一個節(jié)點對之間具體的最短徑路尋找出來，將交通流分配上去，進(jìn)而進(jìn)行網(wǎng)絡(luò)的規(guī)劃。

最短徑路辨識采用追蹤法：從每條最短徑路的起點開始，根據(jù)起點到各節(jié)點的最短路權(quán)搜索最短徑路上的各個交通節(jié)點，直至徑路終點。2/6/2023鄧建華算法思想：設(shè)某最短徑路起點是r，終點是s。徑路辨識算法如下：

（1）從起點r開始，尋找與r相鄰的一節(jié)點i，滿足： dri+Lmin(i,s)=Lmin(r,s) 式中：dri—路段r到i的距離； Lmin(i,s)—節(jié)點i到s的最短路權(quán)； Lmin(r,s)—節(jié)點r到s的最短路權(quán)。則路段[r，i]便是從r到s最短徑路上的一段。（2）尋找與i相鄰的一點j，使其滿足： dij+Lmin(j,s)=Lmin(i,s)則路段[i，j]便是從r到s最短徑路上的一段。（3）如此不斷反復(fù)，直到終點s。把節(jié)點r,i,j…s連接起來，便得到從r到s的最短路線。2/6/2023鄧建華四、交通平衡問題（一）Wardrop平衡原理:第一原理：在道路的利用者都確切知道網(wǎng)絡(luò)的交通狀態(tài)并試圖選擇最短徑路時，網(wǎng)絡(luò)將會達(dá)到平衡狀態(tài)。在考慮擁擠對行走行駛時間影響的網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)達(dá)到平衡狀態(tài)時，每個OD對的各條被使用的徑路具有相等而且最小的走行時間行駛時間；沒有被使用的徑路的走行時間行駛時間大于或等于最小走行時間行駛時間。2/6/2023鄧建華第一原理（用戶均衡(UserEquilibrium，UE)或用戶最優(yōu)）：在道路的利用者都確切知道網(wǎng)絡(luò)的交通狀態(tài)并試圖選擇最短徑路時，網(wǎng)絡(luò)將會達(dá)到平衡狀態(tài)。在考慮擁擠對行走行駛時間影響的網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)達(dá)到平衡狀態(tài)時，每個OD對的各條被使用的徑路具有相等而且最小的走行時間行駛時間；沒有被使用的徑路的走行時間行駛時間大于或等于最小走行時間行駛時間。2/6/2023鄧建華這時需要求徑路a與b上分配的交通量。根據(jù)Wardrop平衡第一原理的定義，很容易建立下列的方程組：

2/6/2023鄧建華第三節(jié)非平衡分配方法非平衡分配方法按其分配方式可分為變化路阻和固定路阻兩類，按分配形態(tài)可分為單徑路徑徑路與多徑路徑徑路兩類2/6/2023鄧建華一、全有全無分配方法其優(yōu)點是計算相當(dāng)簡便，分配只需一次完成，其最大的弱點不足之處是出行量分布不均勻，出行量全部集中在最短徑路上。顯然這是與實際交通情況不符合的，因為當(dāng)最短路上車流逐漸增加時，它的路阻會隨之而增大，意味著這條路有可能不再是最短路，車流會轉(zhuǎn)移到其他可行徑路上行走，因此，其它路徑上也會有流量。2/6/2023鄧建華一、全有全無分配方法算法思想和計算步驟如下：算法思想

是將OD矩陣交通量T加載到路網(wǎng)的最短徑路樹上，從而得到路網(wǎng)中各路段流量的過程。計算步驟

Step0初始化，使路網(wǎng)中所有路段的流量為0，并求出各路段自由流狀態(tài)時的阻抗。Step1計算路網(wǎng)中每個出發(fā)地O到每個目的地D的最短徑路。Step2將O、D間的OD交通量全部分配到相應(yīng)的最短徑路上。2/6/2023鄧建華增量分配法是一種近似的平衡分配方法。該方法是在全有全無分配方法的基礎(chǔ)上，考慮了路段交通流量對阻抗的影響，進(jìn)而根據(jù)道路阻抗的變化來調(diào)整路網(wǎng)交通量的分配，是一種“變化路阻”的交通量分配方法。增量分配法有容量限制—增量分配、容量限制—迭代平衡分配兩種形式。二、增量分配法2/6/2023鄧建華采用容量限制—增量分配方式，首先需先將OD表分解成N個分表(N個分層)，然后分N次使用最短路分配方法，每次分配一個OD分表，并且每分配一次，路阻就根據(jù)路阻函數(shù)修正一次，直到把N個OD分表全部分配到路網(wǎng)上。算法思想

將OD交通量分成若干份；循環(huán)地分配每一份的OD交通量到網(wǎng)絡(luò)中；每次循環(huán)分配一份OD交通量到相應(yīng)的最短徑路上；每次循環(huán)均計算、更新各路段的走行行駛時間，然后按更新后的走行行駛行駛時間重新計算最短徑路；下一循環(huán)按更新后的最短徑路分配下一份OD量OD交通量。1.容量限制—增量分配2/6/2023鄧建華容量限制—增量分配計算步驟

Step0初始化。以適當(dāng)?shù)男问椒指頞D交通量，即，令Step1計算、更新路段費(fèi)用。Step2用全有全無分配法將第n個分割OD交通量 分配到最短經(jīng)路上。Step3如果n=N，則結(jié)束計算。反之，令n=n+1返回Step1。這里，N-為分割次數(shù)；n為-循環(huán)次數(shù)。2/6/2023鄧建華算法思想該法不需要將OD表分解，先假設(shè)路網(wǎng)中各路段上的流量為零，按零流量計算初始路阻，并分配這個OD表，然后按分配流量計算路阻，重新分配整個OD表，最后比較新分配的路段流量與原來分配的路段流量、新計算的路阻與原來計算的路阻，若分別比較接近，滿足迭代精度要求，則停止迭代，獲得最后的分配的交通量。否則，根據(jù)新計算的路權(quán)，再次分配，直到滿足精度為止。2.容量限制—迭代平衡分配2/6/2023鄧建華計算步驟

原理基本是相同的，分配過程中最主要的是確定路阻和計算最短路阻矩陣。理論上，若迭代精度控制得合理，迭代平衡分配的結(jié)果優(yōu)于增量分配的結(jié)果。但迭代平衡方法事先無法估計迭代次數(shù)及計算工作量，對于較復(fù)雜的網(wǎng)絡(luò)，可能會因為個別路段的迭代精度無法滿足要求而使迭代進(jìn)入死循環(huán)，出現(xiàn)算法不收斂的情況。為避免出現(xiàn)算法不收斂的情況，美國聯(lián)邦公路局（FHWA，U.S）對這一算法進(jìn)行了改進(jìn)。2/6/2023鄧建華迭代加權(quán)法（MethodofSuccessiveAverages，簡稱MSA法）是介于增量分配法和平衡分配法之間的一種循環(huán)分配方法。也稱連續(xù)平均法或二次加權(quán)平均法。三、迭代加權(quán)法2/6/2023鄧建華不斷調(diào)整各路段分配的流量而逐漸接近平衡分配結(jié)果。每步循環(huán)中，根據(jù)各路段分配到的流量進(jìn)行一次0-1全有全無分配，得到一組各路段的附加流量；然后用該循環(huán)中各路段已分配的交通量和該循環(huán)中得到的附加交通量進(jìn)行加權(quán)平均，得到下一循環(huán)中的分配交通量；當(dāng)相鄰兩次循環(huán)中分配的交通量十分接近時，即停止運(yùn)算，最后一次循環(huán)中得到的交通量即為最終結(jié)果。算法思想2/6/2023鄧建華計算步驟

Step0初始化。根據(jù)各路段自由行駛時間進(jìn)行全有全無分配，得到初始解。令迭代次數(shù)n=0，路阻函數(shù)。Step1令n=n+1，按照當(dāng)前各路段的交通量計算各路段的路阻。Step2按照Step1求得的行駛時間和OD交通量進(jìn)行全有全無分配。得到各路段的附加交通量。Step3用MSA方法計算各路段當(dāng)前交通量

Step4如果相差不大，則停止計算。即為最終分配結(jié)果。否則返回Step1。2/6/2023鄧建華第四節(jié)平衡分配方法本節(jié)中，討論講述描述Wardrop平衡分配原理的數(shù)學(xué)模型，并在數(shù)學(xué)模型的基礎(chǔ)上探討平衡分配模型的求解算法。如在Wardrop平衡原理基本概念中所介紹的，滿足Wardrop平衡分配原理的模型有用戶平衡分配模型和系統(tǒng)最優(yōu)平衡分配模型。2/6/2023鄧建華一、用戶平衡分配模型及其求解算法（一）用戶平衡分配模型－Beckmann模型數(shù)學(xué)語言直接表達(dá)Wardrop用戶平衡準(zhǔn)則：當(dāng)交通網(wǎng)絡(luò)達(dá)到平衡時，若有，必有，說明如果從r到s有兩條及其以上的徑路被選中，那么它們的行駛時間相等；若有，必有，說明如果某條從r到s的徑路流量等于零，那么該徑路行駛時間一定超過被選中的徑路的行駛時間。2/6/2023鄧建華1、模型基本約束條件的分析交通流守恒：徑路流量與路段流量關(guān)系：阻抗條件：2/6/2023鄧建華2、Beckmann交通平衡分配模型為驗證模型與理論的解的一致性，現(xiàn)舉例說明2/6/2023鄧建華【例8－6】已知：先用模型求解：具體模型如下將x1=5-x2代入目標(biāo)函數(shù)并積分，轉(zhuǎn)換為無約束極小值問題：2/6/2023鄧建華【例8－6】根據(jù)平衡原理求解：根據(jù)Wardrop

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

t1=t2

和x1+x2=5。聯(lián)立求解這個方程組，很容易求得x1=3，x2=2。此時，t1=t2=5?？梢?，對于該路網(wǎng)，Beckmann模型的解和平衡狀態(tài)的解完全相同。2/6/2023鄧建華（二）用戶平衡分配模型求解方法

Frank-Wolfe算法Beckmann模型是一個非線性規(guī)劃模型，F(xiàn)-W方法的前提是模型的約束條件必須都是線性的。該方法是用線性規(guī)劃逐步逼近非線性規(guī)劃的方法，它是一種迭代法。在每步迭代中，先找到目標(biāo)函數(shù)的一個最速下降方向，然后再找到一個最優(yōu)步長，在最速下降(梯度法)方向上截取最優(yōu)步長得到下一步迭代的起點，重復(fù)迭代直到找到最優(yōu)解為止。概括而言，該方法的基本思路就是根據(jù)一個線性規(guī)劃的最優(yōu)解而確定下一步的迭代方向，然后根據(jù)目標(biāo)函數(shù)的一維極值問題求最優(yōu)迭代步長。2/6/2023鄧建華（二）用戶平衡分配模型求解方法

Frank-Wolfe算法1.Frank-Wolfe算法的基本原理設(shè)有非線性規(guī)劃模型：min：Z(X)=f（X） s.t.AX=B，X≥0式中：X、B—向量；A—矩陣。對目標(biāo)函數(shù)f（X）進(jìn)行在X0處的一階泰勒展開，得： f（X）=f（X0）+▽f（X0）(X-X0)這樣將f（X）近似地表達(dá)成線性函數(shù)，則將其近似轉(zhuǎn)化為下列線性規(guī)劃模型： min：Z（X）=f（X0）+▽f（X0）(X-X0) s.t.AX=B，X≥02/6/2023鄧建華（二）用戶平衡分配模型求解方法

Frank-Wolfe算法1.Frank-Wolfe算法的基本原理再去掉目標(biāo)函數(shù)的常數(shù)項，簡化得：min：Z（X）=▽f（X0）Xs.t.AX=B，X≥0解此線性規(guī)劃問題，可以得到最優(yōu)解。F-W方法認(rèn)定X0和的連線為目標(biāo)函數(shù)的最速下降方向。然后由：求得λ為最優(yōu)步長。令，從而得到下一步迭代的起點。如此循環(huán)，直到為止。2/6/2023鄧建華（二）用戶平衡分配模型求解方法

Frank-Wolfe算法2.Frank-Wolfe求解方法首先，我們考慮已知迭代起點而求決定下一步迭代方向的線性規(guī)劃問題，該線性規(guī)劃的目