交通規(guī)劃8課件

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

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

①首先從起點(diǎn)O開(kāi)始，給每個(gè)節(jié)點(diǎn)一個(gè)標(biāo)號(hào),分為T(mén)標(biāo)號(hào)和P標(biāo)號(hào)兩類(lèi)；

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

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

②標(biāo)號(hào)過(guò)程中，T標(biāo)號(hào)一直在改變，P標(biāo)號(hào)不再改變，凡是沒(méi)有標(biāo)上P標(biāo)號(hào)的點(diǎn)，都標(biāo)上T標(biāo)號(hào)。

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

Step1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

t1=t2

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

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

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

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

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