第八講交通流分配課件

第八講交通流分配課件1【本章主要內(nèi)容】8.5交通分配模型中存在的問題8.2交通網(wǎng)絡(luò)平衡與非平衡分配理論8.1概述交通流分配8.3非平衡分配法8.4平衡分配法【本章主要內(nèi)容】8.5交通分配模型中存在的問題8.2交通2重點問題：

1、Wardrop第一、第二原理

2、簡單平衡分配模型的求解

3、非平衡分配中的增量分配方法

4、簡單的隨機(jī)分配問題求解重點問題：38.1概述交通流分配是交通需求預(yù)測四階段法的第四階段，任務(wù)是將各種出行方式的OD矩陣按照一定的路徑選擇原則分配到交通網(wǎng)絡(luò)中的各條道路上，求出各路段上的流量及相關(guān)的交通指標(biāo)，從而為交通網(wǎng)絡(luò)的設(shè)計、評價等提供依據(jù)。一、交通流分配概述8.1概述交通流分配是交通需求預(yù)測四階段法的第四階段，任務(wù)48.1概述OD矩陣OD矩陣反映了各種方式的交通需求在不同時段的空間分布形態(tài)，這是需求預(yù)測前三個階段得到的結(jié)果。在進(jìn)行交通分配之前，需要將OD矩陣的單位轉(zhuǎn)換為交通量或運量的單位（如出行次數(shù)轉(zhuǎn)換為車輛數(shù)）。此外還需要進(jìn)行時段的轉(zhuǎn)換（如全日OD矩陣轉(zhuǎn)換為高峰小時OD矩陣）。8.1概述OD矩陣5交通量分配即是將已經(jīng)預(yù)測得出的OD交通量，根據(jù)已知的道路網(wǎng)描述，按照一定的規(guī)則符合實際地分配到道路網(wǎng)中的各條道路上，進(jìn)而求出路網(wǎng)中各路段的交通流量。一般的道路網(wǎng)中，O與D之間有很多條道路，如何將OD交通量正確合理地分配到O與D之間的各條道路上即是交通分配模型要解決的問題。交通量分配即是將已經(jīng)預(yù)測得出的OD交通量，根據(jù)已知的道路網(wǎng)描6交通分配涉及以下幾個方面1、將現(xiàn)狀OD交通量分配到現(xiàn)狀交通網(wǎng)絡(luò)上，以分析目前交通網(wǎng)絡(luò)的運行狀況。若有某些路段的交通量觀測值，還可以將觀測值與分配結(jié)果進(jìn)行比較，以檢驗?zāi)Ｐ途取?、將規(guī)劃年OD交通量預(yù)測值分配到現(xiàn)狀交通網(wǎng)絡(luò)上，以發(fā)現(xiàn)對規(guī)劃年的交通需求而言的現(xiàn)狀交通網(wǎng)絡(luò)的缺陷，為交通網(wǎng)絡(luò)的規(guī)劃設(shè)計提供依據(jù)。3、將規(guī)劃年OD交通量預(yù)測值分配到規(guī)劃交通網(wǎng)絡(luò)上，以評價交通網(wǎng)絡(luò)規(guī)劃方案的合理性。交通分配涉及以下幾個方面1、將現(xiàn)狀OD交通量分配到現(xiàn)狀7交通分配所需基本數(shù)據(jù)1、表示需求的OD交通量。在擁擠的城市道路交通網(wǎng)中通常采用高峰期OD交通量，在城市間公路網(wǎng)中通常采用年平均日交通量（AADT）的OD交通量。2、路網(wǎng)定義，即路段及交叉口特征和屬性數(shù)據(jù)，同時還包括其時間—流量函數(shù)。3、路徑選擇原則。運行線路固定類型、運行線路不固定類型。交通分配所需基本數(shù)據(jù)1、表示需求的OD交通量。在擁擠的8交通網(wǎng)絡(luò)8.1概述交通網(wǎng)絡(luò)是交通需求作用的載體。在交通分配前，需要將現(xiàn)狀（或規(guī)劃）的交通網(wǎng)絡(luò)抽象為數(shù)學(xué)中的有向圖模型，以表達(dá)交通網(wǎng)絡(luò)的拓?fù)潢P(guān)系和交通供給的各種特性。二、交通網(wǎng)絡(luò)概述交通網(wǎng)絡(luò)8.1概述交通網(wǎng)絡(luò)是交通需求作用的載9交通網(wǎng)絡(luò)的抽象與簡化

交通分配中所使用的網(wǎng)絡(luò)是圖論中抽象的網(wǎng)絡(luò)圖，由節(jié)點和連線組成。節(jié)點一般代表道路網(wǎng)中道路的交叉點以及交通小區(qū)的重心，連線則代表在兩點之間存在一條道路。交通網(wǎng)絡(luò)的抽象與簡化交通分配中所使用的網(wǎng)絡(luò)是圖10交通網(wǎng)絡(luò)的抽象與簡化簡化時主要考慮以下幾點：

①窄而容量小的道路可不予考慮；②小的道路交叉點不作節(jié)點考慮，而在與之相關(guān)的道路的行駛時間函數(shù)中恰當(dāng)?shù)乜紤]其影響；③可將幾條平行道路合并成一條道路，并修改其容量；④分級構(gòu)成網(wǎng)絡(luò)。交通網(wǎng)的抽象與簡化是由分析費用與分析精度的平衡決定的。

交通網(wǎng)絡(luò)的抽象與簡化簡化時主要考慮以下幾點：交通網(wǎng)的抽象11

交通阻抗（或者稱為路阻）直接影響到交通流路徑的選擇和流量的分配。道路阻抗在交通分配中可以通過路阻函數(shù)來描述。

路阻函數(shù)是指路段行駛時間與路段交通負(fù)荷、交叉口延誤與交叉口負(fù)荷之間的關(guān)系。在具體分配過程中，由路段行駛時間及交叉口延誤共同組成出行交通阻抗。三、交通阻抗交通阻抗（或者稱為路阻）直接影響到交通流路徑12交通阻抗交通網(wǎng)絡(luò)上的路阻，應(yīng)包含反映交通時間、交通安全、交通成本、舒適程度、便捷性和準(zhǔn)時性等等許多因素。交通時間常常被作為計算路阻的主要標(biāo)準(zhǔn)：

（1）理論研究和實際觀測表明，交通時間是出行者所考慮的首要因素，尤其在城市道路交通中；（2）幾乎所有的影響路阻的其它因素都與交通時間密切相關(guān)，且呈現(xiàn)出與交通時間相同的變化趨勢；（3）交通時間比其它因素更易于測量，即使有必要考慮到其它因素，也常常是將其轉(zhuǎn)換為時間來度量。

交通阻抗交通網(wǎng)絡(luò)上的路阻，應(yīng)包含反映交通時間、交13路段阻抗

對于單種交通網(wǎng)絡(luò)，出行者在進(jìn)行路徑選擇時，一般都是以時間最短為目標(biāo)。有些交通網(wǎng)絡(luò)，路段上的行駛時間與距離成正比，與路段上的流量無關(guān)，如城市軌道交通網(wǎng)絡(luò)，可選距離為阻抗。有些交通網(wǎng)絡(luò)，如公路網(wǎng)、城市道路網(wǎng)，路段上的行駛時間與距離不一定成正比，而與路段上的交通流量有關(guān)，選用時間作為阻抗，可表達(dá)為：：路段a的所需時間；

：路段a上通過的交通流量。路段阻抗對于單種交通網(wǎng)絡(luò)，出行者在進(jìn)行路徑選14路段阻抗美國道路局BPR函數(shù)：

：路段a的交通容量，即單位時間內(nèi)路段a可通過的最大車輛數(shù)；

：阻滯系數(shù)；

：零流阻抗，即路段a上為空靜狀態(tài)時車輛自由行駛所需時間。最早的BPR函數(shù)中，，，指實用交通容量；后來經(jīng)過改進(jìn)的BPR函數(shù)為，。指穩(wěn)定交通容量。路段阻抗美國道路局BPR函數(shù)：：路段a的交通容量，即單位時15路段阻抗理想的路段阻抗函數(shù)應(yīng)該具備下列的性質(zhì)：1、真實性，用它計算出來的行駛時間應(yīng)具有足夠的真實性。2、函數(shù)應(yīng)該是單調(diào)調(diào)遞增與連續(xù)可導(dǎo)的。3、函數(shù)應(yīng)該允許一定的“超載”，即當(dāng)流量等于或超過通過能力時，行駛時間不應(yīng)該為無窮大。應(yīng)該反饋一個行駛時間，否則一個無窮大的數(shù)可能會導(dǎo)致計算機(jī)死機(jī)。。4、從實際應(yīng)用的角度出發(fā)，阻抗函數(shù)應(yīng)該具有很強(qiáng)的移植性，所以采用工程參數(shù)如自由流車速、通過能力等就比使用通過標(biāo)定而得到的參數(shù)要好些。

路段阻抗理想的路段阻抗函數(shù)應(yīng)該具備下列的性質(zhì)：16節(jié)點阻抗

節(jié)點阻抗——指車輛在交通網(wǎng)絡(luò)節(jié)點處（主要指在交叉口處）的阻抗。交叉口阻抗與交叉口的形式、信號控制系統(tǒng)的配時、交叉口的通過能力等因素有關(guān)。在城市交通網(wǎng)絡(luò)的實際出行時間中，除路段行駛時間外，交叉口延誤占有很大的比重。高峰期間交叉口延誤可能會超過路段行駛時間。由于不同流向車輛在交叉口的不同延誤在最短路徑算法中的表達(dá)沒能得到很好的解決，已有的城市道路交通流分配中一直忽略節(jié)點阻抗問題。節(jié)點阻抗節(jié)點阻抗——指車輛在交通網(wǎng)絡(luò)節(jié)點處（17四、最短路徑的計算方法交通網(wǎng)絡(luò)上任意一OD點對之間，從發(fā)生點到吸引點一串連通的路段的有序排列叫做這一OD點對之間的路徑。一OD點對之間可以有多條路徑，總阻抗最小的路徑叫“最短路徑”。

最短路徑的計算是交通量分配中最基本也是最重要的計算：

任何一種交通量分配法都是建立在最短路徑的基礎(chǔ)上；幾乎所有交通量分配方法中都是以它作為一個基本子過程反復(fù)調(diào)用，最短路徑的計算占據(jù)了全部計算時間的主要部分。四、最短路徑的計算方法交通網(wǎng)絡(luò)上任意一OD點對之間，18最短路徑算法問題包含兩個子問題：1、兩點間最小阻抗的計算；2、兩點間最小阻抗路徑的辨識。前者是解決后者的前提。許多算法都是將這兩個子問題分開考慮，設(shè)計出來的算法是分別單獨求出最小阻抗和最短路徑。

交通流分配最短路徑的算法有:(1)Dijkstra法、(2)矩陣迭代法、(2)Floyd-Warshall法。最短路徑算法問題包含兩個子問題：19（一）Dijkstra法

Dijkstra法也稱標(biāo)號法。常用于計算從某一指定點（起點）到另一指定點（終點）之間的最小阻抗。Dijkstra法可以同時求出網(wǎng)絡(luò)中所有節(jié)點到某一個節(jié)點的全部最短路徑或最短路徑樹。

標(biāo)號的基本特點是：從網(wǎng)絡(luò)中的某一個目的地節(jié)點開始，同時尋找網(wǎng)絡(luò)中所有節(jié)點到該目的地節(jié)點的最短路徑樹，算法以一種循環(huán)的方式檢查網(wǎng)絡(luò)中所有的節(jié)點。在每一步循環(huán)中，總試圖找到一條從被檢查節(jié)點到目的地節(jié)點的更短路線。直到?jīng)]有更短的路線可能被發(fā)現(xiàn)為止。（一）Dijkstra法Dijkstra法也201、Dijkstra法—算法思想

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

T標(biāo)號是臨時標(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é)束。1、Dijkstra法—算法思想①首212、Dijkstra法—算法步驟步驟1初始化。給起點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設(shè)經(jīng)過了（K-1）步標(biāo)號，節(jié)點i是剛得到P標(biāo)號的點，則對所有沒有得到P標(biāo)號的點進(jìn)行下一步新的標(biāo)號（第K步）；考慮所有與節(jié)點i相鄰且沒有標(biāo)上P標(biāo)號的點｛j｝，修改它們的T標(biāo)號：Tk（j）=min[T（j），P（i）+dij]式中，dij——i到j(luò)的距離（路權(quán)）；

T（j）——第K步標(biāo)號前j點的T標(biāo)號。在所有的T標(biāo)號（包括沒有被修改的）中，比選出最小的T標(biāo)號Tk（j0）：

Tk（j0）=min[Tk（j），T（r）]式中，j0——最小T標(biāo)號所對應(yīng)的節(jié)點；

T（γ）——與i點不相鄰點r的T標(biāo)號。給點j0標(biāo)上P標(biāo)號：P（j0）=Tk（j0），第K步標(biāo)號結(jié)束。步驟3當(dāng)所有節(jié)點中已經(jīng)沒有T標(biāo)號，算法結(jié)束，得到從起點1到其它各點的最短路權(quán)；否則返回第二步。2、Dijkstra法—算法步驟步驟122例題8.1

用Dijkstra法計算圖7-1所示路網(wǎng)從節(jié)點1到各節(jié)點的最短路權(quán)。22①②③112222④2⑤⑥2⑦⑧⑨22圖7-1交通網(wǎng)絡(luò)示意圖例題8.1

用Dijkstra法計算圖7-123步驟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]=2T2(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?！窘狻坎襟E1：給定起點1的P標(biāo)號：P(1)=0，其他節(jié)點標(biāo)上24步驟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)+d24]=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。步驟4：節(jié)點4剛得到P標(biāo)號。節(jié)點5、7與4相鄰，且均為T標(biāo)號，修改這兩點的T標(biāo)號：T4(5)=min[T(5)，P(4)+d45]=min[4,2+1]=3T4(7)=min[T(7)，P(4)+d47]=min[∞,2+2]=4在所有T標(biāo)號中，節(jié)點5為最小，給節(jié)點5標(biāo)上P標(biāo)號，即P(5)=T4(5)=3。步驟3：節(jié)點2剛得到P標(biāo)號。節(jié)點3、5與2相鄰25

步驟5：節(jié)點5剛得到P標(biāo)號。節(jié)點6、8與5相鄰，且均為T標(biāo)號，修改這兩點的T標(biāo)號：T5(6)=min[T(6)，P(5)+d56]=min[∞,3+1]=4T5(8)=min[T(8)，P(5)+d58]=min[∞,3+2]=5在所有T標(biāo)號中，節(jié)點3為最小，給節(jié)點3標(biāo)上P標(biāo)號，即P(3)=T3(3)=4。步驟6：節(jié)點3剛得到P標(biāo)號。節(jié)點6與3相鄰，且為T標(biāo)號，修改6的T標(biāo)號：T6(6)=min[T(6)，P(3)+d36]=min[4,4+2]=4在所有T標(biāo)號中，節(jié)點6為最小，給節(jié)點6標(biāo)上P標(biāo)號，即P(6)=T6(6)=4。步驟5：節(jié)點5剛得到P標(biāo)號。節(jié)點6、8與5相鄰，且均26步驟7：節(jié)點6剛得到P標(biāo)號。節(jié)點9與6相鄰，且為T標(biāo)號，修改9的T標(biāo)號：T7(9)=min[T(9)，P(6)+d69]=min[∞,4+2]=6在所有T標(biāo)號中，節(jié)點7為最小，給節(jié)點7標(biāo)上P標(biāo)號，即P(7)=T4(7)=4。步驟8：節(jié)點7剛得到P標(biāo)號。節(jié)點8與7相鄰，且為T標(biāo)號，修改8的T標(biāo)號：T8(8)=min[T(8)，P(7)+d78]=min[5,4+2]=5在所有T標(biāo)號中，節(jié)點8為最小，給節(jié)點8標(biāo)上P標(biāo)號，即P(8)=T8(8)=5。步驟7：節(jié)點6剛得到P標(biāo)號。節(jié)點9與6相鄰，且27步驟9節(jié)點8剛得到P標(biāo)號。節(jié)點9與8相鄰，且為T標(biāo)號，修改9的T標(biāo)號：T9(9)=min[T(9)，P(8)+d89]=min[6,5+2]=6在所有T標(biāo)號中，節(jié)點9為最小，給節(jié)點9標(biāo)上P標(biāo)號，即P(9)=T9(9)=6。節(jié)點123456789路權(quán)024234456P標(biāo)號P(1)P(2)P(3)P(4)P(5)P(6)P(7)P(8)P(9)采用逆序法尋求最小路徑，可得最短路徑為：1-4-5-6-9，總的最小路權(quán)為6。步驟9節(jié)點8剛得到P標(biāo)號。節(jié)點9與8相鄰，28交通規(guī)劃實際中，需要求出路網(wǎng)中任意兩個節(jié)點之間的最短路權(quán)矩陣（n×n階）；盡管Dijkstra算法一次能夠算出從起點到其它各節(jié)點的最短路權(quán)，但仍不能滿足要求，用此方法求最短路權(quán)矩陣，需要反復(fù)運算n次，導(dǎo)致計算效率不高，且速度較慢，所需存儲空間較多，在大規(guī)模交通規(guī)劃中應(yīng)用受到一定限制。Dijkstra算法的局限性交通規(guī)劃實際中，需要求出路網(wǎng)中任意兩個節(jié)點之間的29①借助距離（路權(quán)）矩陣的迭代運算來求解最短路權(quán)的算法。②該方法能一次獲得任意兩點之間的最短路權(quán)矩陣。（二）矩陣迭代算法

1、矩陣迭代法—算法思想①借助距離（路權(quán)）矩陣的迭代運算來求解最短302、矩陣迭代法—算法步驟①首先構(gòu)造距離矩陣（以距離為權(quán)的權(quán)矩陣）。②矩陣給出了節(jié)點間只經(jīng)過一步（一條邊）到達(dá)某一點的最短距離。③對距離矩陣進(jìn)行如下的迭代運算，便可以得到經(jīng)過兩步達(dá)到某一點的最短距離。

（k=1,2,3,…,n）式中，n——網(wǎng)絡(luò)節(jié)點數(shù)；——矩陣邏輯運算符；——距離矩陣D中的相應(yīng)元素。2、矩陣迭代法—算法步驟①首先構(gòu)造距離矩陣（以距離為權(quán)的權(quán)矩31例題8.2:

求解例題7-1網(wǎng)絡(luò)任意節(jié)點間的最短路徑?！窘狻?/p>

（1）構(gòu)造距離矩陣，如下表所示。（第1步）i/j123456789102∞2∞∞∞∞∞2202∞2∞∞∞∞3∞20∞∞2∞∞∞42∞∞01∞2∞∞5∞2∞101∞2∞6∞∞2∞10∞∞27∞∞∞2∞∞02∞8∞∞∞∞2∞2029∞∞∞∞∞2∞2022①②③112222④2⑤⑥2⑦⑧⑨22圖7-1交通網(wǎng)絡(luò)示意圖例題8.2:

求解例題7-1網(wǎng)絡(luò)任意節(jié)點間的最短32（2）進(jìn)行矩陣迭代運算（第2步）=min[0+2,2+0,∞+2,2+∞,∞+2,∞+∞,∞+∞,∞+∞,∞+∞]=2（i=1,j=2；k=1,2，…,9）計算同理，如：=min[0+∞,2+2,∞+∞,2+1,∞+0,∞+1,∞+∞,∞+2,∞+∞]=3（i=1,j=5；k=1,2，…,9）從節(jié)點1經(jīng)過兩步到達(dá)5的最短路權(quán)為3。其他元素按同樣方法計算，得到D2。（3）進(jìn)行矩陣迭代運算（第3步）經(jīng)過三步到達(dá)某一節(jié)點的最短距離為：（k=1,2,3,…,n）式中，——距離矩陣D2中的元素；

——距離矩陣D中的元素。（2）進(jìn)行矩陣迭代運算（第2步）=min[0+2,2+0,33（k=1,2,3,…,n）式中，——距離矩陣Dm-1中的元素；

——距離矩陣D中的元素。迭代不斷進(jìn)行，直到，即中每個元素等于此時的便是任意兩點之間的最短路權(quán)矩陣。中的每個元素為止，（4）進(jìn)行矩陣迭代運算（第m步）經(jīng)過m步到達(dá)某一節(jié)點的最短距離為：（k=1,2,3,…,n）式中，——距離矩陣Dm-1中的元素34本例中，，如下表所示。i/j123456789102423445622023235453420432654423401223453231013236432210432745623402485453232029654432420用矩陣迭代法求解網(wǎng)絡(luò)的最短路，能夠一次獲得n×n階的最短路權(quán)矩陣，簡便快速。軟件的開發(fā)比Dijkstra方法節(jié)省內(nèi)存，速度快。網(wǎng)絡(luò)越復(fù)雜，該方法的優(yōu)越性越明顯。

本例中，，如下表所示。i/j1234567891024234353、最短路徑辨識

得到最短路權(quán)矩陣后，還需把每一個節(jié)點對之間具體的最短路徑尋找出來，將交通流分配上去。最短路徑辯識采用追蹤法：從每條最短路徑的起點開始，根據(jù)起點到各節(jié)點的最短路權(quán)搜索最短路徑上的各個交通節(jié)點，直至路徑終點。3、最短路徑辨識得到最短路權(quán)矩陣后，還需把每一個節(jié)363.最短路徑辨識——算法思想

設(shè)某最短路徑的起點是r，終點是s。路徑辯識算法如下：（1）從起點r開始，尋找與r相鄰的節(jié)點i，滿足：

式中，——路段r到i的距離；——節(jié)點i到s的最短路權(quán)；——節(jié)點r到s的最短路權(quán)。則路段[r,i]便是從r到s最短路徑上的一段。（2）尋找與i相鄰的一點j，使其滿足：

則路段[i,j]便是從r到s最短路徑上的一段。（3）如此不斷反復(fù)，直到終點s。把節(jié)點r,i,j,…,s連接起來，便得到從r到s的最短路徑。3.最短路徑辨識——算法思想設(shè)某最短路徑的起點是r，終點是37例題7.3：

辨識出例題7-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。例題7.3：【解】從起點1開始，由于38【本章主要內(nèi)容】8.5交通分配模型中存在的問題8.2交通網(wǎng)絡(luò)平衡與非平衡分配理論8.1概述交通流分配8.3非平衡分配法8.4平衡分配法【本章主要內(nèi)容】8.5交通分配模型中存在的問題8.2交通398.2交通網(wǎng)絡(luò)平衡與非平衡分配一、概述若兩點之間有很多條道路而這兩點之間的交通量又很少的話，這些交通量顯然會沿著最短的道路行走。隨著交通量的增加，最短路徑上的交通流量也會隨之增加。增加到一定程度之后，這條最短路徑的行駛時間會因為擁擠或堵塞而變長，最短路徑發(fā)生變化，一部分道路利用者會選擇次短的道路。隨著兩點之間的交通量繼續(xù)增加，兩點之間的所有道路都有可能被利用。若所有的道路利用者都準(zhǔn)確知道各條道路所需的行駛時間，并選擇行駛時間最短的道路，最終兩點之間被利用的各條道路的行駛時間會相等。沒有被利用的道路的行駛時間更長。這種狀態(tài)被稱之為道路網(wǎng)的平衡狀態(tài)。背景8.2交通網(wǎng)絡(luò)平衡與非平衡分配一、概述背40在交通流分配中，一個實際道路網(wǎng)中一般有很多個OD對，每個OD對間都有多條路徑。且各組OD之間的路徑也互相重疊。1952年著名學(xué)者Wardrop提出了交通網(wǎng)絡(luò)平衡定義的第一原理和第二原理，奠定了交通流分配的基礎(chǔ)。在交通流分配中，一個實際道路網(wǎng)中一般有很多個OD對，每個OD41二、Wardrop平衡原理1、Wardrop第一原理——用戶最優(yōu)原理(UE)

在道路網(wǎng)的利用者都確切知道網(wǎng)絡(luò)的交通狀態(tài)并試圖選擇最短路徑時，網(wǎng)絡(luò)會達(dá)到平衡狀態(tài)。在考慮擁擠對走行時間影響的網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)達(dá)到平衡狀態(tài)時，每個OD對的各條被利用的路徑具有相等而且最小的走行時間；沒有被利用的路徑的走行時間大于或等于最小走行時間。——Wardrop平衡實際交通流分配中稱為用戶均衡（UE）或用戶最優(yōu)。網(wǎng)絡(luò)擁擠的存在是平衡形成的條件。二、Wardrop平衡原理1、Wardrop第一原理——用戶422、Wardrop第二原理——系統(tǒng)最優(yōu)原理（SO）原理：系統(tǒng)平衡條件下，擁擠的路網(wǎng)上交通流應(yīng)該按照平均或總的出行成本最小為依據(jù)來分配。第二原理是一個設(shè)計原理，是面向交通運輸規(guī)劃師和工程師的。第一原理主要是建立每個道路利用者使其自身出行成本（時間）最小化的行為模型，而第二原理則是旨在使交通流在最小出行成本方向上分配，從而達(dá)到出行成本最小的系統(tǒng)平衡。一般來說，兩個原理下的平衡結(jié)果不會是一樣的，但是在實際交通中，人們更期望交通流能夠按照Wardrop第一原理，即用戶平衡的近似解來分配。二、Wardrop平衡原理2、Wardrop第二原理——系統(tǒng)最優(yōu)原理（SO）二、War433、Wardrop平衡原理比較分析第一原理反映了道路用戶選擇路線的一種準(zhǔn)則。按照第一原理分配出來的結(jié)果應(yīng)該是路網(wǎng)上用戶實際路徑選擇的結(jié)果。第二原理則反映了一種目標(biāo)，即按照什么樣的方式分配是最好的（系統(tǒng)最優(yōu)）。在實際網(wǎng)絡(luò)中很難出現(xiàn)第二原理所描述的狀態(tài)，除非所有的駕駛員相互協(xié)作，為系統(tǒng)最優(yōu)化而努力。這在實際中是不太可能的。但第二原理為交通管理人員提供了一種決策方法。

總結(jié)3、Wardrop平衡原理比較分析第一原理反映了道路用戶選擇44

例題8.4：設(shè)OD之間交通量q=2000veh/h，有兩條路徑a與b。路徑a行駛時間短，但是通行能力小，路徑b行駛時間長，但通行能力大。假設(shè)各自的行駛時間（min）與流量的關(guān)系為：

這時需要求路徑a，b上分配的交通流量。根據(jù)Wardrop第一原理的定義，很容易建立下列的方程組：則有：

例題8.4：設(shè)OD之間交通量q=2000veh45第八講交通流分配課件46三、平衡和非平衡分配1952年Wardrop提出道路網(wǎng)平衡的概念和定義之后，如何求解Wardrop平衡成了重要的研究課題。1956年，Beckmann等提出了描述平衡交通分配的一種數(shù)學(xué)規(guī)劃模型。1975年由LeBlanc等學(xué)者將Frank—Wolfe算法用于求解Beckmann模型獲得成功，從而形成了現(xiàn)在的實用解法。Wardrop原理—Beckmann模型—LeBlanc算法這些突破是交通分配問題研究的重大進(jìn)步，也是交通分配問題的基礎(chǔ)。

三、平衡和非平衡分配1952年Wardrop提47交通流分配方法分為平衡分配和非平衡分配兩大類。對于完全滿足Wardrop原理定義的平衡狀態(tài)，則稱為平衡分配法；對于采用啟發(fā)式方法或其他近似方法的分配模型，則稱為非平衡分配方法。

交通流分配方法分為平衡分配和非平衡分配兩大類。48【本章主要內(nèi)容】8.3非平衡分配法8.5交通分配模型中存在的問題8.2交通網(wǎng)絡(luò)平衡與非平衡分配理論8.1概述8.4平衡分配法交通流分配【本章主要內(nèi)容】8.3非平衡分配法8.5交通分配模型中存49非平衡分配方法按其分配方式可分為變化路阻和固定路阻兩類；按分配形態(tài)可分為單路徑與多路徑兩類。固定路阻變化路阻單路徑全有全無方法容量限制方法多路徑靜態(tài)多路徑方法容量限制多路徑方法8.3非平衡分配方法非平衡分配方法按其分配方式可分為變化路阻和固定507.3.1全有全無分配法

（All-or-NothingAssignmentMethod）

全有全無方法（0-1分配法）不考慮路網(wǎng)的擁擠效果，取路阻為常數(shù)，即假設(shè)車輛的路段行駛速度、交叉口延誤不受路段、交叉口交通負(fù)荷的影響。每一個OD點對的OD交通量被全部分配在連接OD點對的最短路徑上，其他路徑上分配不到交通量。優(yōu)點是計算相當(dāng)簡便，分配只需一次完成；不足之處是出行量分布不均勻，出行量全部集中在最短路徑上。

8.3非平衡分配方法7.3.1全有全無分配法

（All-or-Nothing51全有全無分配法

——算法思想和計算步驟

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

Step0：初始化，使路網(wǎng)中所有路段的流量為0，并求出各路段自由流狀態(tài)時的阻抗；

Step1：計算網(wǎng)絡(luò)中每個出發(fā)地O到每個目的地D的最短路徑；

Step2：將O、D間的OD交通量全部分配到相應(yīng)的最短路徑上。8.3非平衡分配方法全有全無分配法

——算法思想和計算步驟52例題7.5:設(shè)圖7-2所示交通網(wǎng)絡(luò)的OD交通量為t=200輛，各徑路的交通費用函數(shù)分別為：試用全有全無分配法求出分配結(jié)果。

8.3非平衡分配方法例題7.5:設(shè)圖7-2所示交通網(wǎng)絡(luò)的OD交通量為t=2053【解】：

全有全無分配法

由路段費用函數(shù)可知，在路段交通量為零時，徑路1最短。根據(jù)全有全無原則，交通量全部分配到徑路1上，得到以下結(jié)果：因為，，根據(jù)Wardrop原理，網(wǎng)絡(luò)沒有達(dá)到平衡狀態(tài)，沒有得到均衡解。此時路網(wǎng)總費用為：8.3非平衡分配方法【解】：全有全無分配法因為，，根據(jù)Wardrop原理54由于0-1分配法不能反映擁擠效果，主要是用于某些非擁擠路網(wǎng)，用于沒有通行能力限制的網(wǎng)絡(luò)的情況。

建議使用范圍是：在城際之間道路通行能力不受限制的地區(qū)可以采用；一般城市道路網(wǎng)的交通量分配不宜采用該方法。在實際中由于其簡單實用的特性，一般作為其他各種分配技術(shù)的基礎(chǔ)，在增量分配法和平衡分配法等方法中反復(fù)使用。8.3非平衡分配方法由于0-1分配法不能反映擁擠效果，主要是用于某55

增量分配法（簡稱IA分配法）是一種近似的平衡分配法。在全有全無分配方法的基礎(chǔ)上，考慮了路段交通流量對阻抗的影響，進(jìn)而根據(jù)道路阻抗的變化來調(diào)整路網(wǎng)交通量的分配，是一種“變化路阻”的交通量分配方法。首先需將OD表分解成N個分表（N個分層），然后分N次使用最短分配方法，每次分配一個OD分表，并且每分配一次，路阻就根據(jù)路阻函數(shù)修正一次，直到把N個OD分表全部分配到路網(wǎng)上。8.3非平衡分配方法7.3.2增量分配法

（IncrementalAssignmentMethod）增量分配法（簡稱IA分配法）是一種近似的平衡分56增量分配法

—算法思想

將OD交通量分成若干份（等分或不等分）；循環(huán)地分配每一份的OD交通量到網(wǎng)絡(luò)中；每次循環(huán)分配一份OD交通量到相應(yīng)的最短路徑上；每次循環(huán)均計算、更新各路段的走行時間，然后按更新后的走行時間重新計算最短路徑；下一循環(huán)中按更新后的最短路徑分配下一份的OD交通量。

8.3非平衡分配方法增量分配法

—算法思想57，停止計算。當(dāng)前的路段交通流量即是最終解；

Step0：初始化。將每組OD交通量平分成N等分，即使同時，令。

。Stepl：更新，。

Step2：增量分配。按Step1計算所得，用0-1分配法將的OD交通量分配到網(wǎng)絡(luò)中去。這樣得到一組附加交通流量。

Step3：交通流量累加。即令。

step4：判定。如果，令，返回stepl。

如果8.3非平衡分配方法增量分配法

—算法步驟

，停止計算。當(dāng)前的路段交通流量即是最終解；Step0：初58例題7.6:設(shè)圖7-2所示交通網(wǎng)絡(luò)的OD交通量為t=200輛，各徑路的交通費用函數(shù)分別為：試用增量分配法求出分配結(jié)果。

8.3非平衡分配方法例題7.6:設(shè)圖7-2所示交通網(wǎng)絡(luò)的OD交通量為t=2059【解】：

增量分配法采用2等分。①第1次分配與全有全無分配法相同，徑路1最短。②第2次分配，此時最短徑路變?yōu)閺铰?這時，根據(jù)Wardrop原理，各條徑路的費用接近相等，路網(wǎng)接近平衡狀態(tài)，結(jié)果接近于平衡解。此時路網(wǎng)總費用為：8.3非平衡分配方法【解】：增量分配法②第2次分配，此時最短徑路變?yōu)閺铰?60復(fù)雜程度和解的精確性都介于0-1分配法和后述的平衡分配法之間。時便與0-1分配法的結(jié)果一致；時，其解與平衡分配法的解一致。優(yōu)點：簡單可行，精確度可以根據(jù)分割數(shù)N的大小來調(diào)整。在實際的道路網(wǎng)交通量分配中經(jīng)常被采用，而且也有比較成熟的商用軟件可供使用。缺點：仍然是一種近似方法，當(dāng)路阻函數(shù)不是很敏感時，有時會將過多的交通流量分配到某些容量很小的路段上。一般情況下，得不到平衡解。

總結(jié)8.3非平衡分配方法復(fù)雜程度和解的精確性都介于0-1分配法和后述61算法思想不斷調(diào)整已分配到各路段上的交通流量而逐漸到達(dá)或接近平衡分配。在每步循環(huán)中，根據(jù)已分配到各路段上的交通流量進(jìn)行一次0-1分配，得到一組各路段的附加交通量。然后用該循環(huán)中各路段的分配交通流量和該循環(huán)中得到的附加交通量進(jìn)行加權(quán)平均，得到下一循環(huán)中的分配交通流量。當(dāng)相鄰兩個循環(huán)中分配的交通流量十分接近時，即可停止計算。最后一次循環(huán)中得到的分配交通量即是最終的交通量。

8.3非平衡分配方法7.3.3迭代加權(quán)法

（MethodofSuccessiveAverage,MSA）算法思想8.3非平衡分配方法7.3.3迭代加權(quán)法

（Me62Step0：初始化。按照各路段的自由走行時間進(jìn)行一次0-1分配，得到各路段的分配交通流量。令Step1：令，按照當(dāng)前各路段的交通量

Step2：按照Step1計算的路段走行時間和OD交通量進(jìn)行0-1分配，得到Step3：用加權(quán)平均的方法計算各路段的當(dāng)前交通量：Step4：如果與的差值不大，則停止計算，否則返回Step1。。計算各路段的路阻。各路段的附加交通流量。即為最終分配結(jié)果。8.3非平衡分配方法算法步驟：Step0：初始化。按照各路段的自由走行時間進(jìn)行一次0-63在Step4中，判別與差值大小時可控制它們的相對誤差在百分之幾以內(nèi)。但用得更多的準(zhǔn)則是循環(huán)多少次以后令其停止。在Step3中，權(quán)重系數(shù)需由計算者自己定。既可定為常數(shù)，也可定為變數(shù)。定為常數(shù)時，最普遍的情況是令。定為變數(shù)時，最普遍的情況是令(n為循環(huán)次數(shù))。有研究表明時，會使分配盡快接近平衡解。二次加權(quán)平均法是一種簡單實用卻又最接近于平衡分配法的一種分配方法。如果每步循環(huán)中權(quán)重系數(shù)嚴(yán)格按照數(shù)學(xué)規(guī)劃模型取值時，即可得到平衡分配的解。

總結(jié)8.3非平衡分配方法7.3.3迭代加權(quán)法

（IncrementalAssignmentMethod）在Step4中，判別與差值大小時可控制它64【本章主要內(nèi)容】8.5交通分配模型中存在的問題8.2交通網(wǎng)絡(luò)平衡與非平衡分配理論8.1概述8.3非平衡分配法8.4平衡分配法交通流分配【本章主要內(nèi)容】8.5交通分配模型中存在的問題8.2交通658.4平衡分配法用戶平衡分配模型和系統(tǒng)最優(yōu)平衡分配模型一、用戶平衡分配模型及其求解算法用戶平衡分配模型（UE）1956年Beckmann等學(xué)者提出了一種滿足Wardrop準(zhǔn)則的數(shù)學(xué)規(guī)劃模型，奠定了研究交通分配問題的理論基礎(chǔ)。后來的許多分配模型，諸如彈性需求交通分配模型、分布—分配組合模型等都是在Beckmann模型的基礎(chǔ)上擴(kuò)展得到的。8.4平衡分配法用戶平衡分配模型和系統(tǒng)最優(yōu)平衡分配模型66用戶平衡分配模型

——Bechmann模型St:用戶平衡分配模型

67用戶平衡分配模型1、模型中使用的變量和參數(shù)：路段a上的交通流量；：路段a的交通阻抗，也稱為走行時間；：路段a的阻抗函數(shù)，因而；：出發(fā)地為r，目的地為s的OD間的第k條路徑上的交通流量；：出發(fā)地為r，目的地為s的OD間的第k條路徑的阻抗；：出發(fā)地為r，目的地為s的OD間的最短路徑的阻抗；：路段-路徑變量，即0-1變量，如果路段a在出發(fā)地為r目的地為s的OD間的第k條路徑上，則，否則，。用戶平衡分配模型1、模型中使用的變量和參數(shù)68

：網(wǎng)絡(luò)中節(jié)點的集合；：網(wǎng)絡(luò)中路段的集合；：網(wǎng)絡(luò)中出發(fā)地的集合；：網(wǎng)絡(luò)中目的地的集合；：r與s之間的所有路徑的集合；：r與s間的OD交通量。第八講交通流分配課件69用戶平衡分配模型用數(shù)學(xué)語言直接表達(dá)Wardrop用戶平衡準(zhǔn)則，則可以描述為：當(dāng)交通網(wǎng)絡(luò)達(dá)到平衡時，若有，必有，說明若從r到s有兩條及其以上的路徑被選中，則它們的行駛時間相等；若有，必有，說明若某條從r到s的路徑流量等于零，則該路徑的行駛時間一定超過被選中的路徑的行駛時間。

用戶平衡分配模型用數(shù)學(xué)語言直接表達(dá)War70用戶平衡分配模型2.模型的基本約束條件分析平衡分配過程中應(yīng)滿足交通流守恒的條件，即OD間各條路徑上的交通之和應(yīng)等于OD交通總量：路段交通量應(yīng)是由各個（r，s）對的途徑該路段的路徑的流量累加而成：路徑阻抗應(yīng)是該路徑途徑的各路段的阻抗的累加：

用戶平衡分配模型2.模型的基本約束條件分析713.模型的基本約束條件分析——例證用戶平衡分配模型3.模型的基本約束條件分析——例證用戶平衡分配模型72用戶平衡分配模型

——Bechmann模型Subjectto:用戶平衡分配模型

73Beckmann模型的解就是交通流分配達(dá)到平衡狀態(tài)時的解——例證兩個路段的阻抗函數(shù)分別是：

OD量為q=5，分別求該網(wǎng)絡(luò)的Beckmann模型的解和平衡狀態(tài)的解。s.t.【解】先求Beckmann模型的解。將阻抗函數(shù)帶入模型，得：x1,

x2≥0例證Beckmann模型的解就是交通流分配達(dá)到平衡74將代入目標(biāo)函數(shù)并進(jìn)行積分，轉(zhuǎn)換為無約束的極小值問題：Min:

令dZ/dx1=0，解得，。下面求平衡狀態(tài)的解。根據(jù)Wardrop用戶平衡原理，網(wǎng)絡(luò)達(dá)到平衡時應(yīng)該有：

t1=t2和聯(lián)立求解這個方程組，很容易求得，此時，t1=t2=5?？梢?，對于該路網(wǎng)，Beckmann模型的解和平衡狀態(tài)的解完全相同。將代入目標(biāo)函數(shù)并進(jìn)行積分，轉(zhuǎn)換為無約束的極小值問題：Min:75三、系統(tǒng)最優(yōu)化分配模型系統(tǒng)最優(yōu)分配模型

系統(tǒng)最優(yōu)分配（SO）：在擁擠的網(wǎng)絡(luò)中，交通量應(yīng)該按照使得網(wǎng)絡(luò)中總阻抗即總走行時間最小的原則進(jìn)行分配。第二原理反映了一種目標(biāo)，是交通系統(tǒng)管理者的主觀愿望，即按什么樣的方式分配是最好的?？梢宰鳛閷ο到y(tǒng)評價的指標(biāo)，為管理者提供一種決策方法。從此種意義上說，第二原理是道路系統(tǒng)管理者所希望的分配原則，尤其在智能交通系統(tǒng)獲得廣泛應(yīng)用之后。

三、系統(tǒng)最優(yōu)化分配模型系統(tǒng)最優(yōu)分配模型76系統(tǒng)最優(yōu)分配模型約束條件：對阻抗函數(shù)進(jìn)行不同的修改，UE模型與SO模型可以互相轉(zhuǎn)換。

系統(tǒng)最優(yōu)分配模型約束條件：對阻抗函數(shù)進(jìn)行不同77【本章主要內(nèi)容】8.5交通分配模型中存在的問題8.2交通網(wǎng)絡(luò)平衡與非平衡分配理論8.1概述8.3非平衡分配法8.4平衡分配法交通流分配【本章主要內(nèi)容】8.5交通分配模型中存在的問題8.2交通788.5交通分配模型中存在的問題一、對交通流量的近似假定只有在OD交通流量都是穩(wěn)定不變的的前提條件下，才會有道路網(wǎng)的“平衡”，前述的各種交通分配方法才成立。而實際的交通量是動態(tài)的。在實際交通量分配中，一般以一天為單位，對一天的平均交通流量進(jìn)行分配，而得到每條道路一天的平均流量。產(chǎn)生兩個問題。一是交通分配問題非線性問題，用一天的平均OD交通流量進(jìn)行分配得到的結(jié)果與用實際的動態(tài)OD交通量進(jìn)行分配得到的結(jié)果肯定會有差別。二是在實際的道路網(wǎng)規(guī)劃中，有時不只是需要一天的平均情況，而且需要知道某個特定時間段的道路交通狀況，而靜態(tài)交通量分配模型無法推定某個特定時間段的道路網(wǎng)狀況。8.5交通分配模型中存在的問題一、對交通流量的近似假定79二、利用者路徑選擇方法的假定在交通分配模型中，假定道路網(wǎng)的利用者都知道道路網(wǎng)中各條路線的擁擠狀況和所需走行時間，并且具有相同的選擇標(biāo)準(zhǔn)。路徑選擇與交通量分配的研究一直各自獨立互不相干地進(jìn)行著，沒有很好地結(jié)合在一起。二、利用者路徑選擇方法的假定在交通分配模型中，80三、交通網(wǎng)絡(luò)的局限性使用的網(wǎng)絡(luò)是經(jīng)簡化后的網(wǎng)絡(luò)。在網(wǎng)絡(luò)中簡化掉狹小道路有可能使干線道路的分配交通量大于實際交通流量。在實際道路網(wǎng)中，交通量一般是在區(qū)域內(nèi)均勻地發(fā)生和吸引。在目前的交通量分配模型中，都是將OD交通量集中在區(qū)域的某一點——中心節(jié)點上發(fā)生和吸引。造成的誤差是靠近該點的路線上將可能被分配到多于實際流量的交通流量，而離該點較遠(yuǎn)的路線上分配的交通流量則較少。路阻函數(shù)的簡化。交通量分配模型中的路阻函數(shù)一般涉及到兩個量，即路段交通量和交通容量。但實際道路中影響走行時間的遠(yuǎn)不止這兩種因素。道路的幾何形狀、坡度、信號控制狀況、禁止左右轉(zhuǎn)等都對走行時間有影響。

三、交通網(wǎng)絡(luò)的局限性使用的網(wǎng)絡(luò)是經(jīng)簡化后的網(wǎng)絡(luò)。在網(wǎng)81【課后作業(yè)】

如圖所示的交通網(wǎng)絡(luò)，從A到B有兩條路徑1、2，兩條路徑上的交通阻抗函數(shù)分別為：路徑1：t1=15+0.005x1路徑2：t2=10+0.02x2現(xiàn)從A到B有3000輛車，分別用以下方法進(jìn)行交通流分配：（1）UE分配方法（2）全有全無分配方法（3）增量分配方法（OD三等分）。【課后作業(yè)】如圖所示的交通網(wǎng)絡(luò)，從A到B有兩條路徑1、82

謝謝大家謝謝大家83第八講交通流分配課件84【本章主要內(nèi)容】8.5交通分配模型中存在的問題8.2交通網(wǎng)絡(luò)平衡與非平衡分配理論8.1概述交通流分配8.3非平衡分配法8.4平衡分配法【本章主要內(nèi)容】8.5交通分配模型中存在的問題8.2交通85重點問題：

1、Wardrop第一、第二原理

2、簡單平衡分配模型的求解

3、非平衡分配中的增量分配方法

4、簡單的隨機(jī)分配問題求解重點問題：868.1概述交通流分配是交通需求預(yù)測四階段法的第四階段，任務(wù)是將各種出行方式的OD矩陣按照一定的路徑選擇原則分配到交通網(wǎng)絡(luò)中的各條道路上，求出各路段上的流量及相關(guān)的交通指標(biāo)，從而為交通網(wǎng)絡(luò)的設(shè)計、評價等提供依據(jù)。一、交通流分配概述8.1概述交通流分配是交通需求預(yù)測四階段法的第四階段，任務(wù)878.1概述OD矩陣OD矩陣反映了各種方式的交通需求在不同時段的空間分布形態(tài)，這是需求預(yù)測前三個階段得到的結(jié)果。在進(jìn)行交通分配之前，需要將OD矩陣的單位轉(zhuǎn)換為交通量或運量的單位（如出行次數(shù)轉(zhuǎn)換為車輛數(shù)）。此外還需要進(jìn)行時段的轉(zhuǎn)換（如全日OD矩陣轉(zhuǎn)換為高峰小時OD矩陣）。8.1概述OD矩陣88交通量分配即是將已經(jīng)預(yù)測得出的OD交通量，根據(jù)已知的道路網(wǎng)描述，按照一定的規(guī)則符合實際地分配到道路網(wǎng)中的各條道路上，進(jìn)而求出路網(wǎng)中各路段的交通流量。一般的道路網(wǎng)中，O與D之間有很多條道路，如何將OD交通量正確合理地分配到O與D之間的各條道路上即是交通分配模型要解決的問題。交通量分配即是將已經(jīng)預(yù)測得出的OD交通量，根據(jù)已知的道路網(wǎng)描89交通分配涉及以下幾個方面1、將現(xiàn)狀OD交通量分配到現(xiàn)狀交通網(wǎng)絡(luò)上，以分析目前交通網(wǎng)絡(luò)的運行狀況。若有某些路段的交通量觀測值，還可以將觀測值與分配結(jié)果進(jìn)行比較，以檢驗?zāi)Ｐ途取?、將規(guī)劃年OD交通量預(yù)測值分配到現(xiàn)狀交通網(wǎng)絡(luò)上，以發(fā)現(xiàn)對規(guī)劃年的交通需求而言的現(xiàn)狀交通網(wǎng)絡(luò)的缺陷，為交通網(wǎng)絡(luò)的規(guī)劃設(shè)計提供依據(jù)。3、將規(guī)劃年OD交通量預(yù)測值分配到規(guī)劃交通網(wǎng)絡(luò)上，以評價交通網(wǎng)絡(luò)規(guī)劃方案的合理性。交通分配涉及以下幾個方面1、將現(xiàn)狀OD交通量分配到現(xiàn)狀90交通分配所需基本數(shù)據(jù)1、表示需求的OD交通量。在擁擠的城市道路交通網(wǎng)中通常采用高峰期OD交通量，在城市間公路網(wǎng)中通常采用年平均日交通量（AADT）的OD交通量。2、路網(wǎng)定義，即路段及交叉口特征和屬性數(shù)據(jù)，同時還包括其時間—流量函數(shù)。3、路徑選擇原則。運行線路固定類型、運行線路不固定類型。交通分配所需基本數(shù)據(jù)1、表示需求的OD交通量。在擁擠的91交通網(wǎng)絡(luò)8.1概述交通網(wǎng)絡(luò)是交通需求作用的載體。在交通分配前，需要將現(xiàn)狀（或規(guī)劃）的交通網(wǎng)絡(luò)抽象為數(shù)學(xué)中的有向圖模型，以表達(dá)交通網(wǎng)絡(luò)的拓?fù)潢P(guān)系和交通供給的各種特性。二、交通網(wǎng)絡(luò)概述交通網(wǎng)絡(luò)8.1概述交通網(wǎng)絡(luò)是交通需求作用的載92交通網(wǎng)絡(luò)的抽象與簡化

交通分配中所使用的網(wǎng)絡(luò)是圖論中抽象的網(wǎng)絡(luò)圖，由節(jié)點和連線組成。節(jié)點一般代表道路網(wǎng)中道路的交叉點以及交通小區(qū)的重心，連線則代表在兩點之間存在一條道路。交通網(wǎng)絡(luò)的抽象與簡化交通分配中所使用的網(wǎng)絡(luò)是圖93交通網(wǎng)絡(luò)的抽象與簡化簡化時主要考慮以下幾點：

①窄而容量小的道路可不予考慮；②小的道路交叉點不作節(jié)點考慮，而在與之相關(guān)的道路的行駛時間函數(shù)中恰當(dāng)?shù)乜紤]其影響；③可將幾條平行道路合并成一條道路，并修改其容量；④分級構(gòu)成網(wǎng)絡(luò)。交通網(wǎng)的抽象與簡化是由分析費用與分析精度的平衡決定的。

交通網(wǎng)絡(luò)的抽象與簡化簡化時主要考慮以下幾點：交通網(wǎng)的抽象94

交通阻抗（或者稱為路阻）直接影響到交通流路徑的選擇和流量的分配。道路阻抗在交通分配中可以通過路阻函數(shù)來描述。

路阻函數(shù)是指路段行駛時間與路段交通負(fù)荷、交叉口延誤與交叉口負(fù)荷之間的關(guān)系。在具體分配過程中，由路段行駛時間及交叉口延誤共同組成出行交通阻抗。三、交通阻抗交通阻抗（或者稱為路阻）直接影響到交通流路徑95交通阻抗交通網(wǎng)絡(luò)上的路阻，應(yīng)包含反映交通時間、交通安全、交通成本、舒適程度、便捷性和準(zhǔn)時性等等許多因素。交通時間常常被作為計算路阻的主要標(biāo)準(zhǔn)：

（1）理論研究和實際觀測表明，交通時間是出行者所考慮的首要因素，尤其在城市道路交通中；（2）幾乎所有的影響路阻的其它因素都與交通時間密切相關(guān)，且呈現(xiàn)出與交通時間相同的變化趨勢；（3）交通時間比其它因素更易于測量，即使有必要考慮到其它因素，也常常是將其轉(zhuǎn)換為時間來度量。

交通阻抗交通網(wǎng)絡(luò)上的路阻，應(yīng)包含反映交通時間、交96路段阻抗

對于單種交通網(wǎng)絡(luò)，出行者在進(jìn)行路徑選擇時，一般都是以時間最短為目標(biāo)。有些交通網(wǎng)絡(luò)，路段上的行駛時間與距離成正比，與路段上的流量無關(guān)，如城市軌道交通網(wǎng)絡(luò)，可選距離為阻抗。有些交通網(wǎng)絡(luò)，如公路網(wǎng)、城市道路網(wǎng)，路段上的行駛時間與距離不一定成正比，而與路段上的交通流量有關(guān)，選用時間作為阻抗，可表達(dá)為：：路段a的所需時間；

：路段a上通過的交通流量。路段阻抗對于單種交通網(wǎng)絡(luò)，出行者在進(jìn)行路徑選97路段阻抗美國道路局BPR函數(shù)：

：路段a的交通容量，即單位時間內(nèi)路段a可通過的最大車輛數(shù)；

：阻滯系數(shù)；

：零流阻抗，即路段a上為空靜狀態(tài)時車輛自由行駛所需時間。最早的BPR函數(shù)中，，，指實用交通容量；后來經(jīng)過改進(jìn)的BPR函數(shù)為，。指穩(wěn)定交通容量。路段阻抗美國道路局BPR函數(shù)：：路段a的交通容量，即單位時98路段阻抗理想的路段阻抗函數(shù)應(yīng)該具備下列的性質(zhì)：1、真實性，用它計算出來的行駛時間應(yīng)具有足夠的真實性。2、函數(shù)應(yīng)該是單調(diào)調(diào)遞增與連續(xù)可導(dǎo)的。3、函數(shù)應(yīng)該允許一定的“超載”，即當(dāng)流量等于或超過通過能力時，行駛時間不應(yīng)該為無窮大。應(yīng)該反饋一個行駛時間，否則一個無窮大的數(shù)可能會導(dǎo)致計算機(jī)死機(jī)。。4、從實際應(yīng)用的角度出發(fā)，阻抗函數(shù)應(yīng)該具有很強(qiáng)的移植性，所以采用工程參數(shù)如自由流車速、通過能力等就比使用通過標(biāo)定而得到的參數(shù)要好些。

路段阻抗理想的路段阻抗函數(shù)應(yīng)該具備下列的性質(zhì)：99節(jié)點阻抗

節(jié)點阻抗——指車輛在交通網(wǎng)絡(luò)節(jié)點處（主要指在交叉口處）的阻抗。交叉口阻抗與交叉口的形式、信號控制系統(tǒng)的配時、交叉口的通過能力等因素有關(guān)。在城市交通網(wǎng)絡(luò)的實際出行時間中，除路段行駛時間外，交叉口延誤占有很大的比重。高峰期間交叉口延誤可能會超過路段行駛時間。由于不同流向車輛在交叉口的不同延誤在最短路徑算法中的表達(dá)沒能得到很好的解決，已有的城市道路交通流分配中一直忽略節(jié)點阻抗問題。節(jié)點阻抗節(jié)點阻抗——指車輛在交通網(wǎng)絡(luò)節(jié)點處（100四、最短路徑的計算方法交通網(wǎng)絡(luò)上任意一OD點對之間，從發(fā)生點到吸引點一串連通的路段的有序排列叫做這一OD點對之間的路徑。一OD點對之間可以有多條路徑，總阻抗最小的路徑叫“最短路徑”。

最短路徑的計算是交通量分配中最基本也是最重要的計算：

任何一種交通量分配法都是建立在最短路徑的基礎(chǔ)上；幾乎所有交通量分配方法中都是以它作為一個基本子過程反復(fù)調(diào)用，最短路徑的計算占據(jù)了全部計算時間的主要部分。四、最短路徑的計算方法交通網(wǎng)絡(luò)上任意一OD點對之間，101最短路徑算法問題包含兩個子問題：1、兩點間最小阻抗的計算；2、兩點間最小阻抗路徑的辨識。前者是解決后者的前提。許多算法都是將這兩個子問題分開考慮，設(shè)計出來的算法是分別單獨求出最小阻抗和最短路徑。

交通流分配最短路徑的算法有:(1)Dijkstra法、(2)矩陣迭代法、(2)Floyd-Warshall法。最短路徑算法問題包含兩個子問題：102（一）Dijkstra法

Dijkstra法也稱標(biāo)號法。常用于計算從某一指定點（起點）到另一指定點（終點）之間的最小阻抗。Dijkstra法可以同時求出網(wǎng)絡(luò)中所有節(jié)點到某一個節(jié)點的全部最短路徑或最短路徑樹。

標(biāo)號的基本特點是：從網(wǎng)絡(luò)中的某一個目的地節(jié)點開始，同時尋找網(wǎng)絡(luò)中所有節(jié)點到該目的地節(jié)點的最短路徑樹，算法以一種循環(huán)的方式檢查網(wǎng)絡(luò)中所有的節(jié)點。在每一步循環(huán)中，總試圖找到一條從被檢查節(jié)點到目的地節(jié)點的更短路線。直到?jīng)]有更短的路線可能被發(fā)現(xiàn)為止。（一）Dijkstra法Dijkstra法也1031、Dijkstra法—算法思想

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

T標(biāo)號是臨時標(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é)束。1、Dijkstra法—算法思想①首1042、Dijkstra法—算法步驟步驟1初始化。給起點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設(shè)經(jīng)過了（K-1）步標(biāo)號，節(jié)點i是剛得到P標(biāo)號的點，則對所有沒有得到P標(biāo)號的點進(jìn)行下一步新的標(biāo)號（第K步）；考慮所有與節(jié)點i相鄰且沒有標(biāo)上P標(biāo)號的點｛j｝，修改它們的T標(biāo)號：Tk（j）=min[T（j），P（i）+dij]式中，dij——i到j(luò)的距離（路權(quán)）；

T（j）——第K步標(biāo)號前j點的T標(biāo)號。在所有的T標(biāo)號（包括沒有被修改的）中，比選出最小的T標(biāo)號Tk（j0）：

Tk（j0）=min[Tk（j），T（r）]式中，j0——最小T標(biāo)號所對應(yīng)的節(jié)點；

T（γ）——與i點不相鄰點r的T標(biāo)號。給點j0標(biāo)上P標(biāo)號：P（j0）=Tk（j0），第K步標(biāo)號結(jié)束。步驟3當(dāng)所有節(jié)點中已經(jīng)沒有T標(biāo)號，算法結(jié)束，得到從起點1到其它各點的最短路權(quán)；否則返回第二步。2、Dijkstra法—算法步驟步驟1105例題8.1

用Dijkstra法計算圖7-1所示路網(wǎng)從節(jié)點1到各節(jié)點的最短路權(quán)。22①②③112222④2⑤⑥2⑦⑧⑨22圖7-1交通網(wǎng)絡(luò)示意圖例題8.1

用Dijkstra法計算圖7-1106步驟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]=2T2(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。【解】步驟1：給定起點1的P標(biāo)號：P(1)=0，其他節(jié)點標(biāo)上107步驟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)+d24]=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。步驟4：節(jié)點4剛得到P標(biāo)號。節(jié)點5、7與4相鄰，且均為T標(biāo)號，修改這兩點的T標(biāo)號：T4(5)=min[T(5)，P(4)+d45]=min[4,2+1]=3T4(7)=min[T(7)，P(4)+d47]=min[∞,2+2]=4在所有T標(biāo)號中，節(jié)點5為最小，給節(jié)點5標(biāo)上P標(biāo)號，即P(5)=T4(5)=3。步驟3：節(jié)點2剛得到P標(biāo)號。節(jié)點3、5與2相鄰108

步驟5：節(jié)點5剛得到P標(biāo)號。節(jié)點6、8與5相鄰，且均為T標(biāo)號，修改這兩點的T標(biāo)號：T5(6)=min[T(6)，P(5)+d56]=min[∞,3+1]=4T5(8)=min[T(8)，P(5)+d58]=min[∞,3+2]=5在所有T標(biāo)號中，節(jié)點3為最小，給節(jié)點3標(biāo)上P標(biāo)號，即P(3)=T3(3)=4。步驟6：節(jié)點3剛得到P標(biāo)號。節(jié)點6與3相鄰，且為T標(biāo)號，修改6的T標(biāo)號：T6(6)=min[T(6)，P(3)+d36]=min[4,4+2]=4在所有T標(biāo)號中，節(jié)點6為最小，給節(jié)點6標(biāo)上P標(biāo)號，即P(6)=T6(6)=4。步驟5：節(jié)點5剛得到P標(biāo)號。節(jié)點6、8與5相鄰，且均109步驟7：節(jié)點6剛得到P標(biāo)號。節(jié)點9與6相鄰，且為T標(biāo)號，修改9的T標(biāo)號：T7(9)=min[T(9)，P(6)+d69]=min[∞,4+2]=6在所有T標(biāo)號中，節(jié)點7為最小，給節(jié)點7標(biāo)上P標(biāo)號，即P(7)=T4(7)=4。步驟8：節(jié)點7剛得到P標(biāo)號。節(jié)點8與7相鄰，且為T標(biāo)號，修改8的T標(biāo)號：T8(8)=min[T(8)，P(7)+d78]=min[5,4+2]=5在所有T標(biāo)號中，節(jié)點8為最小，給節(jié)點8標(biāo)上P標(biāo)號，即P(8)=T8(8)=5。步驟7：節(jié)點6剛得到P標(biāo)號。節(jié)點9與6相鄰，且110步驟9節(jié)點8剛得到P標(biāo)號。節(jié)點9與8相鄰，且為T標(biāo)號，修改9的T標(biāo)號：T9(9)=min[T(9)，P(8)+d89]=min[6,5+2]=6在所有T標(biāo)號中，節(jié)點9為最小，給節(jié)點9標(biāo)上P標(biāo)號，即P(9)=T9(9)=6。節(jié)點123456789路權(quán)024234456P標(biāo)號P(1)P(2)P(3)P(4)P(5)P(6)P(7)P(8)P(9)采用逆序法尋求最小路徑，可得最短路徑為：1-4-5-6-9，總的最小路權(quán)為6。步驟9節(jié)點8剛得到P標(biāo)號。節(jié)點9與8相鄰，111交通規(guī)劃實際中，需要求出路網(wǎng)中任意兩個節(jié)點之間的最短路權(quán)矩陣（n×n階）；盡管Dijkstra算法一次能夠算出從起點到其它各節(jié)點的最短路權(quán)，但仍不能滿足要求，用此方法求最短路權(quán)矩陣，需要反復(fù)運算n次，導(dǎo)致計算效率不高，且速度較慢，所需存儲空間較多，在大規(guī)模交通規(guī)劃中應(yīng)用受到一定限制。Dijkstra算法的局限性交通規(guī)劃實際中，需要求出路網(wǎng)中任意兩個節(jié)點之間的112①借助距離（路權(quán)）矩陣的迭代運算來求解最短路權(quán)的算法。②該方法能一次獲得任意兩點之間的最短路權(quán)矩陣。（二）矩陣迭代算法

1、矩陣迭代法—算法思想①借助距離（路權(quán)）矩陣的迭代運算來求解最短1132、矩陣迭代法—算法步驟①首先構(gòu)造距離矩陣（以距離為權(quán)的權(quán)矩陣）。②矩陣給出了節(jié)點間只經(jīng)過一步（一條邊）到達(dá)某一點的最短距離。③對距離矩陣進(jìn)行如下的迭代運算，便可以得到經(jīng)過兩步達(dá)到某一點的最短距離。

（k=1,2,3,…,n）式中，n——網(wǎng)絡(luò)節(jié)點數(shù)；——矩陣邏輯運算符；——距離矩陣D中的相應(yīng)元素。2、矩陣迭代法—算法步驟①首先構(gòu)造距離矩陣（以距離為權(quán)的權(quán)矩114例題8.2: