第八章-交通流分配電子教案

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

網(wǎng)絡上相鄰兩個節(jié)點之間的交通線路。徑路

網(wǎng)絡上任意一OD點對之間，從發(fā)生點到吸引點一串連通的路段的有序排列叫做這一OD點對之間的徑路。一OD點對之間可有多條徑路。最短徑路

一對OD點之間的徑路中總阻抗最小的徑路叫“最短徑路”。1/8/2025鄧建華

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

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

T是臨時標號，表示從起點O到該點的最短路權上限；

P標號是固定標號，表示從起點O到該點的最短路權。

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

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

Step1

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

Step2設經(jīng)過了K-1）步標號，節(jié)點i是剛得到P標號的點，則對所有沒有得到P標號的點進行下一步新的標號（第K步）；考慮所有與節(jié)點i相鄰且沒有標上P標號的點{j}，修改它們的T標號：

式中dij—i到j的距離（路權）；T(j)—第K步標號前j點的T標號。1/8/2025鄧建華1．Dijkstra法（標號法）(2)算法步驟

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

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

①是借助距離（路權）矩陣的迭代運算來求解最短路權的算法。②該方法能一次獲得任意兩點之間的最短路權矩陣。1/8/2025鄧建華2．矩陣迭代法(2)算法步驟

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

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

1/8/2025鄧建華從節(jié)點1經(jīng)過兩步到達5的最短路權為3。其他元素按同樣方法計算，得到D2

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

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

（1）從起點r開始，尋找與r相鄰的一節(jié)點i，滿足： dri+Lmin(i,s)=Lmin(r,s) 式中：dri—路段r到i的距離； Lmin(i,s)—節(jié)點i到s的最短路權； Lmin(r,s)—節(jié)點r到s的最短路權。則路段[r，i]便是從r到s最短徑路上的一段。（2）尋找與i相鄰的一點j，使其滿足： dij+Lmin(j,s)=Lmin(i,s)則路段[i，j]便是從r到s最短徑路上的一段。（3）如此不斷反復，直到終點s。把節(jié)點r,i,j…s連接起來，便得到從r到s的最短路線。1/8/2025鄧建華【例題8-3】辨識出例題8.2-2所求得的從節(jié)點1到節(jié)點9的最短徑路?！窘狻浚簭钠瘘c1開始，因為d14+Lmin(4,9)=2+4=6=Lmin(1,9)所以[1,4]在最短徑路上。因為d45+Lmin(5,9)=1+3=4=Lmin(4,9)所以[4,5]在最短徑路上。因為d56+Lmin(6,9)=1+2=3=Lmin(5,9)所以[5,6]在最短徑路上。因為d69+Lmin(9,9)=2+0=2=Lmin(6,9)所以[6,9]在最短徑路上。則從節(jié)點1到節(jié)點9的最短徑路是：1-4-5-6-9。1/8/2025鄧建華四、交通平衡問題（一）Wardrop平衡原理:第一原理：在道路的利用者都確切知道網(wǎng)絡的交通狀態(tài)并試圖選擇最短徑路時，網(wǎng)絡將會達到平衡狀態(tài)。在考慮擁擠對行走行駛時間影響的網(wǎng)絡中，當網(wǎng)絡達到平衡狀態(tài)時，每個OD對的各條被使用的徑路具有相等而且最小的走行時間行駛時間；沒有被使用的徑路的走行時間行駛時間大于或等于最小走行時間行駛時間。1/8/2025鄧建華第一原理（用戶均衡(UserEquilibrium，UE)或用戶最優(yōu)）：在道路的利用者都確切知道網(wǎng)絡的交通狀態(tài)并試圖選擇最短徑路時，網(wǎng)絡將會達到平衡狀態(tài)。在考慮擁擠對行走行駛時間影響的網(wǎng)絡中，當網(wǎng)絡達到平衡狀態(tài)時，每個OD對的各條被使用的徑路具有相等而且最小的走行時間行駛時間；沒有被使用的徑路的走行時間行駛時間大于或等于最小走行時間行駛時間。1/8/2025鄧建華系統(tǒng)最優(yōu)原理（SystemOptimization，SO）在系統(tǒng)平衡條件下，在擁擠路網(wǎng)上交通流應該按照平均或總的出行成本最小為依據(jù)來分配。第二個原理作為一個設計原理，是面向交通管理運輸規(guī)劃師和工程師的。一般來說，這兩個原理下的平衡結果不會是一樣的，但是在實際交通中，人們更期望交通流能夠按照Wardrop第一原理，即用戶平衡的近似解來分配。

第二原理：1/8/2025鄧建華【例題8-4】設OD之間交通量為q=2000輛，有兩條徑路a與b。徑路a走行時間行駛時間短，但是通過通行能力小，徑路b走行時間行駛時間長，但通行過能力大。假設各自的走行時間行駛時間（min）與流量的關系是：（二）平衡和非平衡分配：1/8/2025鄧建華這時需要求徑路a與b上分配的交通量。根據(jù)Wardrop平衡第一原理的定義，很容易建立下列的方程組：

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

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

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

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

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

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

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

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

用戶平衡原理，網(wǎng)絡達到平衡是應該有：

t1=t2

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

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

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

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