《第08章 交通分配基礎(chǔ)》由會(huì)員分享，可在線閱讀，更多相關(guān)《第08章 交通分配基礎(chǔ)（36頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院第八章交通分配基礎(chǔ)長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.1 交通分配的概念交通分配的概念 v 交通分配是交通分配是“四階段四階段”交通需求預(yù)測(cè)法的最后一個(gè)環(huán)節(jié)，所謂交交通需求預(yù)測(cè)法的最后一個(gè)環(huán)節(jié)，所謂交通分配就是將各種出行方式的空間通分配就是將各種出行方式的空間OD量分配到具體的交通網(wǎng)絡(luò)量分配到具體的交通網(wǎng)絡(luò)上，通過交通分配所得到的路段、交叉口交通量資料是檢驗(yàn)道路上，通過交通分配所得到的路段、交叉口交通量資料是檢驗(yàn)道路規(guī)劃網(wǎng)絡(luò)是否合理的主要依據(jù)之一。規(guī)劃網(wǎng)絡(luò)是否合理的主要依據(jù)之一。v 進(jìn)行交通分配的前提條件是進(jìn)行交通
2、分配的前提條件是已知已知OD交通量、網(wǎng)絡(luò)圖和網(wǎng)絡(luò)中各交通量、網(wǎng)絡(luò)圖和網(wǎng)絡(luò)中各路段的走行時(shí)間（或走行時(shí)間函數(shù)）路段的走行時(shí)間（或走行時(shí)間函數(shù)）。v 對(duì)于各種出行方式的對(duì)于各種出行方式的OD量的獲取已在量的獲取已在“Chap04Chap07章章”中中獲得了很好的解決，本章主要討論交通網(wǎng)絡(luò)的計(jì)算機(jī)表示方法、獲得了很好的解決，本章主要討論交通網(wǎng)絡(luò)的計(jì)算機(jī)表示方法、交通阻抗分析和路網(wǎng)最短路算法道路等交通分配的基礎(chǔ)問題。下交通阻抗分析和路網(wǎng)最短路算法道路等交通分配的基礎(chǔ)問題。下章再討論交通分配的模型和算法。章再討論交通分配的模型和算法。 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.2 交通
3、網(wǎng)絡(luò)的計(jì)算機(jī)表示交通網(wǎng)絡(luò)的計(jì)算機(jī)表示 v 交通網(wǎng)絡(luò)的抽象即是把交通網(wǎng)絡(luò)抽象為點(diǎn)（交叉口）與邊（路段）交通網(wǎng)絡(luò)的抽象即是把交通網(wǎng)絡(luò)抽象為點(diǎn)（交叉口）與邊（路段）的集合，節(jié)點(diǎn)一般代表道路網(wǎng)絡(luò)中道路的交叉點(diǎn)以及交通小區(qū)的的集合，節(jié)點(diǎn)一般代表道路網(wǎng)絡(luò)中道路的交叉點(diǎn)以及交通小區(qū)的形心，邊則代表在兩點(diǎn)之間存在一條道路。形心，邊則代表在兩點(diǎn)之間存在一條道路。v 對(duì)交通網(wǎng)絡(luò)進(jìn)行計(jì)算機(jī)處理，常用的方法有：對(duì)交通網(wǎng)絡(luò)進(jìn)行計(jì)算機(jī)處理，常用的方法有：關(guān)聯(lián)矩陣法、鄰接關(guān)聯(lián)矩陣法、鄰接矩陣法、權(quán)矩陣法、邊編目錄法和鄰接目錄表法矩陣法、權(quán)矩陣法、邊編目錄法和鄰接目錄表法5種種。 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通
4、運(yùn)輸工程學(xué)院8.2.1 關(guān)聯(lián)矩陣法關(guān)聯(lián)矩陣法 v 關(guān)聯(lián)矩陣表示的是節(jié)點(diǎn)和邊之間的關(guān)聯(lián)情況。關(guān)聯(lián)矩陣表示的是節(jié)點(diǎn)和邊之間的關(guān)聯(lián)情況。v 關(guān)聯(lián)矩陣的每一列僅有兩個(gè)元素為關(guān)聯(lián)矩陣的每一列僅有兩個(gè)元素為1，其余元素全部為，其余元素全部為0。因此，利。因此，利用此種方法來存儲(chǔ)網(wǎng)絡(luò)信息，效率不高，浪費(fèi)的計(jì)算機(jī)內(nèi)存空間大。用此種方法來存儲(chǔ)網(wǎng)絡(luò)信息，效率不高，浪費(fèi)的計(jì)算機(jī)內(nèi)存空間大。其它是相關(guān)聯(lián)的和邊如果節(jié)點(diǎn)01jiijg64111000010110001101100011G長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.2.2 鄰接矩陣法鄰接矩陣法 v 鄰接矩陣是一個(gè)方陣，其元素表示的是網(wǎng)絡(luò)中節(jié)
5、點(diǎn)與節(jié)點(diǎn)之間的鄰接矩陣是一個(gè)方陣，其元素表示的是網(wǎng)絡(luò)中節(jié)點(diǎn)與節(jié)點(diǎn)之間的一般鄰接關(guān)系。一般鄰接關(guān)系。v 有效元素（非零元素）的比例在提高，但矩陣中絕大部分的元素有效元素（非零元素）的比例在提高，但矩陣中絕大部分的元素仍為仍為0，是個(gè)稀疏矩陣，存儲(chǔ)時(shí)要浪費(fèi)大量的計(jì)算機(jī)內(nèi)存空間。，是個(gè)稀疏矩陣，存儲(chǔ)時(shí)要浪費(fèi)大量的計(jì)算機(jī)內(nèi)存空間。 之間有邊連接與節(jié)點(diǎn)節(jié)點(diǎn)之間無邊連接或與節(jié)點(diǎn)節(jié)點(diǎn)jijijiijl10440111101111011110L長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.2.3 權(quán)矩陣法權(quán)矩陣法 間有邊直接相連與節(jié)點(diǎn)節(jié)點(diǎn)給定權(quán)間無邊直接連接與節(jié)點(diǎn)節(jié)點(diǎn)jijiijwji 0770
6、232081038061106041402312061360D長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.2.4 邊編目錄法邊編目錄法 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.2.5 鄰接目錄表法鄰接目錄表法 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.3 道路交通阻抗分析道路交通阻抗分析 v 交通阻抗是指交通網(wǎng)絡(luò)上路段或路徑之間的運(yùn)行距離、時(shí)間、費(fèi)交通阻抗是指交通網(wǎng)絡(luò)上路段或路徑之間的運(yùn)行距離、時(shí)間、費(fèi)用或這些因素的綜合。用或這些因素的綜合。v 交通阻抗通常由兩部分組成：路段上的阻抗、節(jié)點(diǎn)處的阻抗。交通阻抗通常由兩部分組成：路段上的阻抗、節(jié)
7、點(diǎn)處的阻抗。v 在諸多交通阻抗因素中，時(shí)間因素是最主要的。在諸多交通阻抗因素中，時(shí)間因素是最主要的。v 有些交通網(wǎng)絡(luò)，路段上的走行時(shí)間與距離成正比，與路段上的流有些交通網(wǎng)絡(luò)，路段上的走行時(shí)間與距離成正比，與路段上的流量無關(guān)，如城市軌道交通網(wǎng)；有些交通網(wǎng)絡(luò)，路段上的走行時(shí)間量無關(guān)，如城市軌道交通網(wǎng)；有些交通網(wǎng)絡(luò)，路段上的走行時(shí)間與距離不一定成正比，與路段上的交通流量有關(guān)，此時(shí)應(yīng)選用時(shí)與距離不一定成正比，與路段上的交通流量有關(guān)，此時(shí)應(yīng)選用時(shí)間作為阻抗。間作為阻抗。v 道路交通阻抗分析就是確定路段走行時(shí)間（交叉口延誤）與路段道路交通阻抗分析就是確定路段走行時(shí)間（交叉口延誤）與路段（交叉口）交通負(fù)荷之
8、間的函數(shù)關(guān)系。（交叉口）交通負(fù)荷之間的函數(shù)關(guān)系。 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.3.1 常用的路段特性函數(shù)常用的路段特性函數(shù) 路段特性函數(shù)的一般形式路段特性函數(shù)的一般形式v 當(dāng)流量充分小時(shí)，行程時(shí)間接近于平均當(dāng)流量充分小時(shí)，行程時(shí)間接近于平均“零流量零流量”行程時(shí)間。行程時(shí)間。v 在流量遠(yuǎn)小于道路的通行能力時(shí)，流量的緩慢變化導(dǎo)致行程時(shí)間在流量遠(yuǎn)小于道路的通行能力時(shí)，流量的緩慢變化導(dǎo)致行程時(shí)間的緩慢變化。的緩慢變化。v 在在“穩(wěn)態(tài)穩(wěn)態(tài)”系統(tǒng)狀態(tài)下，曲線變成飽和流量縱坐標(biāo)的漸近線。系統(tǒng)狀態(tài)下，曲線變成飽和流量縱坐標(biāo)的漸近線。v 另外，在函數(shù)的構(gòu)造上，還要求其滿足單調(diào)遞
9、增、連續(xù)可微性，另外，在函數(shù)的構(gòu)造上，還要求其滿足單調(diào)遞增、連續(xù)可微性，同時(shí)對(duì)模型參數(shù)也要求易于標(biāo)定。同時(shí)對(duì)模型參數(shù)也要求易于標(biāo)定。()aatf q長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院 常用的路段特性函數(shù)模型常用的路段特性函數(shù)模型 v 模型模型1（BPR模型）模型）0()1() aaaaaqtqtC1212012121()() aaaaaaqqttCC12012121()()aaaaaaqqttCC長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院v 模型模型2（Davidson模型）模型）v 模型模型3（TRRL模型）模型）0(1)aaaaaqttjCq 1638/
10、49.90.163 (430) ()aaaaaaaaLLtVkm hVqWR 3256/67.60.123 (1000) ()aaaaaaaaLLtVkm hVqWR長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院v 模型模型4（中國(guó)交通部模型）（中國(guó)交通部模型）v 模型模型5v 模型模型6aaVqaaaaaLLtqVaaaaaLLtVq)1 (fjVVKKmfqqVV112136001112aafaamaLtVqq長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.3.2 常用的交叉口延誤模型常用的交叉口延誤模型 信號(hào)交叉口延誤計(jì)算模型信號(hào)交叉口延誤計(jì)算模型 v 模型模型1
11、21ddd)1 ()1 (38. 021xTd )(16) 1() 1(173222TxxxxdTgCqx 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院v 模型模型2v 模型模型3v 模型模型4)1 (2)1 (2xTd)1 (23600)1 (2)1 (22xqxxTd)1 (23600)1 (2)1 ()1 (2)1 (222xqxxTxTd長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院v 模型模型5（Webster延誤）延誤）v 模型模型6)52(31222)(65. 0)1 (2)1 (2)1 (xqTxqxxTdqxQxTd02)1 (2)1 (0000 0 1
12、)(5 . 1xxxxxxxQ60067. 00Sgx長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院 其它類型交叉口延誤計(jì)算方法其它類型交叉口延誤計(jì)算方法 )(1)(信號(hào)無控ijijdkd)(2)(信號(hào)環(huán)交ijijdkd)(3)(信號(hào)立交ijijdkd長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.3.3 路權(quán)的計(jì)算路權(quán)的計(jì)算 v 交通分配中的路權(quán)等于路段行駛時(shí)間與交叉口延誤之和。交通分配中的路權(quán)等于路段行駛時(shí)間與交叉口延誤之和。8.3.4 節(jié)點(diǎn)帶權(quán)路網(wǎng)的描述節(jié)點(diǎn)帶權(quán)路網(wǎng)的描述 v 當(dāng)存在交叉口轉(zhuǎn)向延誤或交叉口轉(zhuǎn)向限制時(shí)，對(duì)于路網(wǎng)的連通性當(dāng)存在交叉口轉(zhuǎn)向延誤或交叉口轉(zhuǎn)向限
13、制時(shí)，對(duì)于路網(wǎng)的連通性要重新進(jìn)行描述，常用的方法有增設(shè)虛擬邊法和對(duì)偶圖法。要重新進(jìn)行描述，常用的方法有增設(shè)虛擬邊法和對(duì)偶圖法。ijijijTtd長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院 增設(shè)虛擬邊法增設(shè)虛擬邊法 v 基本思想是將每個(gè)交叉口擴(kuò)展為一個(gè)子網(wǎng)絡(luò)，即增加虛擬節(jié)點(diǎn)和基本思想是將每個(gè)交叉口擴(kuò)展為一個(gè)子網(wǎng)絡(luò)，即增加虛擬節(jié)點(diǎn)和虛擬邊。一個(gè)虛擬節(jié)點(diǎn)對(duì)應(yīng)到交叉口的一個(gè)進(jìn)口或出口方向，連虛擬邊。一個(gè)虛擬節(jié)點(diǎn)對(duì)應(yīng)到交叉口的一個(gè)進(jìn)口或出口方向，連接虛擬節(jié)點(diǎn)的一條虛擬邊對(duì)應(yīng)到交叉口的一個(gè)可能轉(zhuǎn)向，其邊權(quán)接虛擬節(jié)點(diǎn)的一條虛擬邊對(duì)應(yīng)到交叉口的一個(gè)可能轉(zhuǎn)向，其邊權(quán)則對(duì)應(yīng)到相應(yīng)的轉(zhuǎn)向延誤。則對(duì)應(yīng)到
14、相應(yīng)的轉(zhuǎn)向延誤。v 優(yōu)點(diǎn)：能解決轉(zhuǎn)向延誤和轉(zhuǎn)向限制問題，可以利用現(xiàn)有的最短路優(yōu)點(diǎn)：能解決轉(zhuǎn)向延誤和轉(zhuǎn)向限制問題，可以利用現(xiàn)有的最短路算法。算法。v 缺點(diǎn)：要增加大量的虛擬節(jié)點(diǎn)和虛擬邊，而大量虛擬節(jié)點(diǎn)和虛擬缺點(diǎn)：要增加大量的虛擬節(jié)點(diǎn)和虛擬邊，而大量虛擬節(jié)點(diǎn)和虛擬邊的增加又導(dǎo)致問題規(guī)模的劇增，對(duì)于大型網(wǎng)絡(luò)這種存儲(chǔ)空間和邊的增加又導(dǎo)致問題規(guī)模的劇增，對(duì)于大型網(wǎng)絡(luò)這種存儲(chǔ)空間和運(yùn)行時(shí)間上的額外開銷是無法承受的。運(yùn)行時(shí)間上的額外開銷是無法承受的。長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院 對(duì)偶圖法對(duì)偶圖法 v 對(duì)偶圖法的實(shí)質(zhì)是進(jìn)行節(jié)點(diǎn)
15、和邊的相互轉(zhuǎn)化來表達(dá)網(wǎng)絡(luò)的連通性。對(duì)偶圖法的實(shí)質(zhì)是進(jìn)行節(jié)點(diǎn)和邊的相互轉(zhuǎn)化來表達(dá)網(wǎng)絡(luò)的連通性。在進(jìn)行邊轉(zhuǎn)化為節(jié)點(diǎn)時(shí)，原圖中的一條邊就轉(zhuǎn)化為對(duì)偶圖中的一在進(jìn)行邊轉(zhuǎn)化為節(jié)點(diǎn)時(shí)，原圖中的一條邊就轉(zhuǎn)化為對(duì)偶圖中的一個(gè)節(jié)點(diǎn)；而在節(jié)點(diǎn)轉(zhuǎn)化為邊時(shí)，則需要根據(jù)網(wǎng)絡(luò)的連通性而定。個(gè)節(jié)點(diǎn)；而在節(jié)點(diǎn)轉(zhuǎn)化為邊時(shí)，則需要根據(jù)網(wǎng)絡(luò)的連通性而定。v 通過轉(zhuǎn)化得到的對(duì)偶圖有通過轉(zhuǎn)化得到的對(duì)偶圖有2個(gè)主要特性。個(gè)主要特性。n 對(duì)偶圖中的對(duì)偶節(jié)點(diǎn)代表了原圖中的邊，并保持了原圖中邊對(duì)偶圖中的對(duì)偶節(jié)點(diǎn)代表了原圖中的邊，并保持了原圖中邊的所有特性。如對(duì)偶節(jié)點(diǎn)包含了原圖中邊的起點(diǎn)、末點(diǎn)號(hào)信的所有特性。如對(duì)偶節(jié)點(diǎn)包含了原圖中邊的起點(diǎn)、末點(diǎn)號(hào)
16、信息；對(duì)偶節(jié)點(diǎn)的權(quán)重對(duì)應(yīng)原圖中邊的權(quán)重。息；對(duì)偶節(jié)點(diǎn)的權(quán)重對(duì)應(yīng)原圖中邊的權(quán)重。n 對(duì)偶圖中的對(duì)偶邊代表了原圖中鄰接邊之間的轉(zhuǎn)向以及轉(zhuǎn)向?qū)ε紙D中的對(duì)偶邊代表了原圖中鄰接邊之間的轉(zhuǎn)向以及轉(zhuǎn)向的附屬特征，如對(duì)偶邊的權(quán)重對(duì)應(yīng)到原轉(zhuǎn)向的延誤值等。的附屬特征，如對(duì)偶邊的權(quán)重對(duì)應(yīng)到原轉(zhuǎn)向的延誤值等。長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.4 路網(wǎng)最短路算法路網(wǎng)最短路算法 v 最短路算法是交通分配的最基本算法。絕大部分的交通分配模型都以最短路最短路算法是交通分配的最基本算法。絕大
17、部分的交通分配模型都以最短路交通分配為基礎(chǔ)，并將其作為一個(gè)基本子過程反復(fù)調(diào)用。交通分配為基礎(chǔ)，并將其作為一個(gè)基本子過程反復(fù)調(diào)用。v 最短路算法的設(shè)計(jì)合理與否，將直接影響到整個(gè)交通分配的運(yùn)算效率。最短路算法的設(shè)計(jì)合理與否，將直接影響到整個(gè)交通分配的運(yùn)算效率。v 最短路問題包含著兩個(gè)子問題：一是網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的最短路權(quán)計(jì)最短路問題包含著兩個(gè)子問題：一是網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的最短路權(quán)計(jì)算，另一是網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的最短路徑的辨識(shí)。算，另一是網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的最短路徑的辨識(shí)。長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.4.1 Dijkstra算法（標(biāo)號(hào)法）算法（標(biāo)號(hào)
18、法） 適用條件適用條件 v 1959年提出，路權(quán)都必須為正，不允許出現(xiàn)負(fù)權(quán)。年提出，路權(quán)都必須為正，不允許出現(xiàn)負(fù)權(quán)。v 對(duì)無向網(wǎng)絡(luò)，也可以按照此算法來執(zhí)行，只不過認(rèn)為各邊都是可對(duì)無向網(wǎng)絡(luò)，也可以按照此算法來執(zhí)行，只不過認(rèn)為各邊都是可以雙向行駛的路段。以雙向行駛的路段。v 假定假定 P 是從是從 Vs 到到 Vt 的最短路，的最短路，Vi 是路線上的某一個(gè)節(jié)點(diǎn)，那么是路線上的某一個(gè)節(jié)點(diǎn)，那么從從 Vs 沿沿 P 到到 Vi 的路線就是從的路線就是從 Vs 到到 Vi 的最短路線。的最短路線。v 主要獲得起點(diǎn)到終點(diǎn)之間的最短路，同時(shí)可以獲得網(wǎng)絡(luò)中其它某主要獲得起點(diǎn)到終點(diǎn)之間的最短路，同時(shí)可以獲得網(wǎng)
19、絡(luò)中其它某些節(jié)點(diǎn)與起點(diǎn)之間的最短路，但具體是哪些節(jié)點(diǎn)，事先并不知道。些節(jié)點(diǎn)與起點(diǎn)之間的最短路，但具體是哪些節(jié)點(diǎn)，事先并不知道。 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院 算法簡(jiǎn)介算法簡(jiǎn)介 v 計(jì)算從某一指定節(jié)點(diǎn)到另一指定節(jié)點(diǎn)之間的最短路計(jì)算從某一指定節(jié)點(diǎn)到另一指定節(jié)點(diǎn)之間的最短路n 算法首先從源點(diǎn)開始，給每一個(gè)節(jié)點(diǎn)記一標(biāo)號(hào)，標(biāo)號(hào)分為算法首先從源點(diǎn)開始，給每一個(gè)節(jié)點(diǎn)記一標(biāo)號(hào)，標(biāo)號(hào)分為 P 標(biāo)號(hào)和標(biāo)號(hào)和 T 標(biāo)號(hào)兩種，標(biāo)號(hào)兩種，T 標(biāo)號(hào)表示從源點(diǎn)到該點(diǎn)的最短路權(quán)的標(biāo)號(hào)表示從源點(diǎn)到該點(diǎn)的最短路權(quán)的上界（臨時(shí)標(biāo)號(hào)）；上界（臨時(shí)標(biāo)號(hào)）； P 標(biāo)號(hào)表示從源點(diǎn)到該點(diǎn)的最短路權(quán)，標(biāo)號(hào)表示從源點(diǎn)
20、到該點(diǎn)的最短路權(quán)，又稱固定標(biāo)號(hào)。在標(biāo)號(hào)過程中，又稱固定標(biāo)號(hào)。在標(biāo)號(hào)過程中，T 標(biāo)號(hào)一直在改變，已得到標(biāo)號(hào)一直在改變，已得到 P 標(biāo)號(hào)的節(jié)點(diǎn)其標(biāo)號(hào)不再改變，凡是沒有標(biāo)上標(biāo)號(hào)的節(jié)點(diǎn)其標(biāo)號(hào)不再改變，凡是沒有標(biāo)上 P 標(biāo)號(hào)的節(jié)點(diǎn)，標(biāo)號(hào)的節(jié)點(diǎn)，都標(biāo)上都標(biāo)上 T 標(biāo)號(hào)。算法每執(zhí)行一步，將把某一節(jié)點(diǎn)的標(biāo)號(hào)。算法每執(zhí)行一步，將把某一節(jié)點(diǎn)的 T 標(biāo)號(hào)改標(biāo)號(hào)改變?yōu)樽優(yōu)?P 標(biāo)號(hào)，當(dāng)終點(diǎn)獲得標(biāo)號(hào)，當(dāng)終點(diǎn)獲得 P 標(biāo)號(hào)時(shí)，標(biāo)號(hào)過程結(jié)束。標(biāo)號(hào)時(shí)，標(biāo)號(hào)過程結(jié)束。 v 計(jì)算從某一指定節(jié)點(diǎn)到網(wǎng)絡(luò)中其它所有節(jié)點(diǎn)之間的最短路計(jì)算從某一指定節(jié)點(diǎn)到網(wǎng)絡(luò)中其它所有節(jié)點(diǎn)之間的最短路 n 前面的過程相同。經(jīng)過有限步運(yùn)算之后，當(dāng)把所有的前面
21、的過程相同。經(jīng)過有限步運(yùn)算之后，當(dāng)把所有的 T 標(biāo)號(hào)標(biāo)號(hào)都改變成都改變成 P 標(biāo)號(hào)，即獲得了從源點(diǎn)到網(wǎng)絡(luò)中任一節(jié)點(diǎn)的最短標(biāo)號(hào)，即獲得了從源點(diǎn)到網(wǎng)絡(luò)中任一節(jié)點(diǎn)的最短路，標(biāo)號(hào)過程結(jié)束。路，標(biāo)號(hào)過程結(jié)束。 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院 算法描述算法描述 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院 算例算例 求求V1V6的最短路。的最短路。求求V1V7的最短路。的最短路。長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.4.2 矩陣迭代算法矩陣迭代算法 v 矩陣迭代法是一種借助于權(quán)矩陣迭代運(yùn)算來
22、求解最短路權(quán)和最短矩陣迭代法是一種借助于權(quán)矩陣迭代運(yùn)算來求解最短路權(quán)和最短路徑的算法，利用該算法可以很簡(jiǎn)單地獲得交通網(wǎng)絡(luò)中任意路徑的算法，利用該算法可以很簡(jiǎn)單地獲得交通網(wǎng)絡(luò)中任意2個(gè)個(gè)節(jié)點(diǎn)之間的最短路權(quán)（徑）。節(jié)點(diǎn)之間的最短路權(quán)（徑）。v 該算法的基本思想是，記初始的權(quán)矩陣為該算法的基本思想是，記初始的權(quán)矩陣為 D，該矩陣經(jīng)過若干次，該矩陣經(jīng)過若干次迭代運(yùn)算后滿足終止條件，那么迭代運(yùn)算后滿足終止條件，那么 D*中的每個(gè)元素中的每個(gè)元素 dij 則表示從節(jié)則表示從節(jié)點(diǎn)點(diǎn) i 到節(jié)點(diǎn)到節(jié)點(diǎn) j 的最短路權(quán)，基于矩陣的最短路權(quán)，基于矩陣 D*通過前向（后向）搜索可通過前向（后向）搜索可獲得最短路徑。
23、獲得最短路徑。 v 基本思想：不是直接考慮從節(jié)點(diǎn)基本思想：不是直接考慮從節(jié)點(diǎn) i 到節(jié)點(diǎn)到節(jié)點(diǎn) j 的最短路，而是考慮的最短路，而是考慮經(jīng)過中間某個(gè)節(jié)點(diǎn)經(jīng)過中間某個(gè)節(jié)點(diǎn) k 后，距離是否有所減少。后，距離是否有所減少。 nkmkjdmikdmijd 321) 1() 1(min)(，( )(1)stopmmDD！長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院算法特點(diǎn)算法特點(diǎn) v 當(dāng)網(wǎng)絡(luò)中存在負(fù)權(quán)時(shí)，可以用該算法來計(jì)算。當(dāng)網(wǎng)絡(luò)中存在負(fù)權(quán)時(shí)，可以用該算法來計(jì)算。v 采用矩陣迭代法來計(jì)算最短路權(quán)，可一次性地獲得階最短路權(quán)矩采用矩陣迭代法來計(jì)算最短路權(quán)，可一次性地獲得階最短路權(quán)矩陣，并且同陣
24、，并且同Dijkstra算法相比更節(jié)省內(nèi)存，計(jì)算速度更快。算法相比更節(jié)省內(nèi)存，計(jì)算速度更快。v 對(duì)于復(fù)雜網(wǎng)絡(luò)迭代次數(shù)比簡(jiǎn)單網(wǎng)絡(luò)多；對(duì)于無向網(wǎng)絡(luò)迭代次數(shù)比對(duì)于復(fù)雜網(wǎng)絡(luò)迭代次數(shù)比簡(jiǎn)單網(wǎng)絡(luò)多；對(duì)于無向網(wǎng)絡(luò)迭代次數(shù)比有向網(wǎng)絡(luò)多。有向網(wǎng)絡(luò)多。v 矩陣迭代法易獲得最短路權(quán)，但不易獲得最短路徑。矩陣迭代法易獲得最短路權(quán)，但不易獲得最短路徑。 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院算例：用距離矩陣迭代算法求各節(jié)點(diǎn)之間的最短路權(quán)。算例：用距離矩陣迭代算法求各節(jié)點(diǎn)之間的最短路權(quán)。 0327041050D長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院最短路徑的搜索最短路徑的搜索 v 使用
25、矩陣迭代法運(yùn)算時(shí)，不僅可以獲得最短路權(quán)矩陣，同時(shí)還可使用矩陣迭代法運(yùn)算時(shí)，不僅可以獲得最短路權(quán)矩陣，同時(shí)還可以獲得網(wǎng)絡(luò)中任意以獲得網(wǎng)絡(luò)中任意2個(gè)節(jié)點(diǎn)之間的最短路徑。個(gè)節(jié)點(diǎn)之間的最短路徑。v 最短路徑的獲得采用搜索法，即從每條最短路線的起點(diǎn)開始，根最短路徑的獲得采用搜索法，即從每條最短路線的起點(diǎn)開始，根據(jù)起點(diǎn)至各節(jié)點(diǎn)的最短路權(quán)搜索最短路徑上的各交通節(jié)點(diǎn)，直至據(jù)起點(diǎn)至各節(jié)點(diǎn)的最短路權(quán)搜索最短路徑上的各交通節(jié)點(diǎn)，直至路徑終點(diǎn)。路徑終點(diǎn)。v 也可以采用反向搜索法，即從終點(diǎn)搜索到起點(diǎn)以獲得最短路徑。也可以采用反向搜索法，即從終點(diǎn)搜索到起點(diǎn)以獲得最短路徑。 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸
26、工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院算例：算例：0310213204140610160310023207 756 11 956643866963511 6 8594 69D求求V1V7的最短路？的最短路？長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院8.5 路段和交叉口的通行能力路段和交叉口的通行能力 v 道路路段的通行能力分析計(jì)算包括道路路段的通行能力分析計(jì)算包括n 城市道路路段通行能力分析計(jì)算；城市道路路段通行能力分析計(jì)算；n 高速公路基本路段通行能力分析計(jì)算；高速公路基本路段通行能力分析計(jì)算；n 高速公路交織區(qū)通行能力分析計(jì)算；高速公路交織區(qū)通行能力分析計(jì)算；n 高速公路匝道與主線連接點(diǎn)通行能力分析計(jì)算；高速公路匝道與主線連接點(diǎn)通行能力分析計(jì)算；n 雙車道公路路段通行能力分析計(jì)算等。雙車道公路路段通行能力分析計(jì)算等。v 交叉口的通行能力分析計(jì)算包括交叉口的通行能力分析計(jì)算包括n 信號(hào)控制交叉口的通行能力分析；信號(hào)控制交叉口的通行能力分析；n 無控交叉口的通行能力分析；無控交叉口的通行能力分析；n 環(huán)形交叉口的通行能力分析；環(huán)形交叉口的通行能力分析；n 立體交叉口的通行能力分析等。立體交叉口的通行能力分析等。
第08章 交通分配基礎(chǔ)
