第09章 基本交通分配模型

1、長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院第九章基本交通分配模型長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.1 交通分配與平衡交通分配與平衡 v 由于連接由于連接OD對間的道路有很多條，如何將對間的道路有很多條，如何將OD交通量正確合理地分交通量正確合理地分配配O與與D之間的各條路線上，是交通分配模型要解決的首要問題。之間的各條路線上，是交通分配模型要解決的首要問題。 v 如果兩點之間有很多條路線，而這兩點之間的交通量又很少的話，如果兩點之間有很多條路線，而這兩點之間的交通量又很少的話，這些交通量顯然會選擇最短的路行走。隨著兩點間交通量的增加，這些交通量顯然會選擇

2、最短的路行走。隨著兩點間交通量的增加，選次短路，選次短路，最后兩點間的所有路線都有可能被利用。，最后兩點間的所有路線都有可能被利用。 v 如果道路用戶都能準確知道各路線的行駛時間，并選擇時間最短的如果道路用戶都能準確知道各路線的行駛時間，并選擇時間最短的路線，最終兩點間被使用的各條道路的行駛時間會相等；而沒有被路線，最終兩點間被使用的各條道路的行駛時間會相等；而沒有被利用的路線的行駛時間更長。這種狀態(tài)稱為：道路網(wǎng)的均衡狀態(tài)。利用的路線的行駛時間更長。這種狀態(tài)稱為：道路網(wǎng)的均衡狀態(tài)。 v 由于在實際的交通分配過程中，有很多對由于在實際的交通分配過程中，有很多對OD，每一，每一OD對間又有很對間又

3、有很多條路線，且路線間有許多路段相互交織。由于這種復雜性，多條路線，且路線間有許多路段相互交織。由于這種復雜性，1952年年Wardrop提出了網(wǎng)絡均衡的概念和定義后，如何求解均衡交通分提出了網(wǎng)絡均衡的概念和定義后，如何求解均衡交通分配成了運輸研究者的重要課題。配成了運輸研究者的重要課題。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院v 1956年，年，Backmann提出了均衡交通分配的數(shù)學規(guī)劃模型。提出了均衡交通分配的數(shù)學規(guī)劃模型。20年后年后即即1975年才由年才由LeBlance等人將等人將Frank-Wolfe算法用于求解算法用于求解Backmann模型獲得成功，從而形成

4、了現(xiàn)在的實用解法。模型獲得成功，從而形成了現(xiàn)在的實用解法。 v Wardrop對交通網(wǎng)絡均衡的定義為：在考慮擁擠對走行時間影響的對交通網(wǎng)絡均衡的定義為：在考慮擁擠對走行時間影響的網(wǎng)絡中，當網(wǎng)絡達到均衡狀態(tài)時，每對網(wǎng)絡中，當網(wǎng)絡達到均衡狀態(tài)時，每對OD間各條被使用的路線具有間各條被使用的路線具有相等而且最小的走行時間，其它任何未被使用的路線其走行時間大相等而且最小的走行時間，其它任何未被使用的路線其走行時間大于或等于最小走行時間。通常稱為于或等于最小走行時間。通常稱為Wardrop第一原理或用戶優(yōu)化均第一原理或用戶優(yōu)化均衡原理。衡原理。 v 實例實例100.02aatx150.005bbtx長沙

5、理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.2 交通分配模型的分類交通分配模型的分類 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院舉例說明非均衡交通分配、均衡交通分配與隨機交通分配。舉例說明非均衡交通分配、均衡交通分配與隨機交通分配。 12000q 120t 215t 12000q 11200.005tx22150.01tx長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院v 均衡模型一般都可以歸結為一個維數(shù)很大的凸規(guī)劃問題或非線性均衡模型一般都可以歸結為一個維數(shù)很大的凸規(guī)劃問題或非線性規(guī)劃問題。理論上說，這類模型結構嚴謹，思路明確，比較適合規(guī)劃問題。理論上說，這

6、類模型結構嚴謹，思路明確，比較適合于宏觀研究。但是，由于維數(shù)太大、約束條件太多，這類模型的于宏觀研究。但是，由于維數(shù)太大、約束條件太多，這類模型的求解比較困難，盡管人們提出了一些近似方法，但計算仍很復雜，求解比較困難，盡管人們提出了一些近似方法，但計算仍很復雜，實際工程中很難應用。實際工程中很難應用。v 相比之下，非均衡模型具有結構簡單、概念明確、計算簡便等優(yōu)相比之下，非均衡模型具有結構簡單、概念明確、計算簡便等優(yōu)點，因此在實際工程中得到了廣泛的應用。非均衡模型根據(jù)其分點，因此在實際工程中得到了廣泛的應用。非均衡模型根據(jù)其分配手段可分為無迭代和有迭代配手段可分為無迭代和有迭代2類，就其分配形態(tài)

7、可分為單路徑類，就其分配形態(tài)可分為單路徑與多路徑與多路徑2類。因此，非均衡模型可分為如下表所示的分類體系。類。因此，非均衡模型可分為如下表所示的分類體系。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院非均衡模型的分類體系非均衡模型的分類體系長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.3 非均衡交通分配模型非均衡交通分配模型 9.3.1 最短路交通分配法（最短路交通分配法（all or nothing traffic assignment model） v 分配原理：每一分配原理：每一OD對對應的對對應的OD量全部分配在連接該量全部分配在連接該OD對的最對的最短路線上

8、，其它道路上分配不到交通量。短路線上，其它道路上分配不到交通量。v 分配步驟分配步驟n 計算網(wǎng)絡中每個出發(fā)地計算網(wǎng)絡中每個出發(fā)地O到目的地到目的地D的最短路線；的最短路線；n 將該將該OD交通量全部分配最短路線上；交通量全部分配最短路線上；n 每分配完一對每分配完一對OD后進行流量迭加，直到最后一對后進行流量迭加，直到最后一對OD分配分配完畢。完畢。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院v 0-1分配法的特點分配法的特點n 計算簡單；計算簡單；n 是其它交通分配的基礎；是其它交通分配的基礎；n 出行量分布不均勻，全部集中在最短路上；出行量分布不均勻，全部集中在最短路上；n

9、未考慮路段上的容量限制，有時分配到的路段交通量大于道未考慮路段上的容量限制，有時分配到的路段交通量大于道路的通行能力；路的通行能力；n 有時某些路段上分配到的交通量為有時某些路段上分配到的交通量為0，與實際情況不符；，與實際情況不符；n 隨著交通量的增加，未考慮到行程時間的改變。隨著交通量的增加，未考慮到行程時間的改變。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院0-1分配算例：分配算例：長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.3.2 容量限制最短路交通分配法容量限制最短路交通分配法 v 為克服最短路交通

10、分配方法的缺陷，可采用容量限制最短路交通分為克服最短路交通分配方法的缺陷，可采用容量限制最短路交通分配方法，這種方法既考慮了路權與交通負荷之間的關系（即隨著道配方法，這種方法既考慮了路權與交通負荷之間的關系（即隨著道路上交通量的增大，行程時間也發(fā)生變化，即增大），同時也考慮路上交通量的增大，行程時間也發(fā)生變化，即增大），同時也考慮到了交叉口、路段的通行能力限制。到了交叉口、路段的通行能力限制。v 容量限制最短路交通分配法的原理如下：將原始的容量限制最短路交通分配法的原理如下：將原始的OD矩陣（矩陣（nn） 階分成階分成 k 個同階的小個同階的小OD矩陣，然后分矩陣，然后分 k 次用最短路分配模

11、型分配次用最短路分配模型分配OD量，每次分配一個小量，每次分配一個小OD矩陣，每分配完一個小矩陣，每分配完一個小OD矩陣，修正路矩陣，修正路權一次（采用路段阻抗函數(shù)模型），再分配下一個小權一次（采用路段阻抗函數(shù)模型），再分配下一個小OD矩陣，直到矩陣，直到所有的小所有的小OD矩陣都分配完為止。矩陣都分配完為止。v 在具體應用時，視路網(wǎng)的大小選取分配次數(shù)在具體應用時，視路網(wǎng)的大小選取分配次數(shù)k及每次分配的及每次分配的OD量比量比例。實際常使用五級分配制，第一次分配例。實際常使用五級分配制，第一次分配OD總量的總量的30%，第二次，第二次25%，第三次的，第三次的20%，第四次，第四次15%，第五

12、次，第五次10%。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.3.3 增量分配法（增量分配法（incremental traffic assignment model） v 增量分配法是容量限制最短路交通分配法的進一步推廣，又增量分配法是容量限制最短路交通分配法的進一步推廣，又稱為比例配流方法。稱為比例配流方法。 v 分配原則分配原則n 將原將原OD矩陣分成矩陣分成 N 等份，對每一個小矩陣用最短路分配等份，對每一個小矩陣用最短路分配方法分配，完成以后，根據(jù)阻抗函數(shù)

13、重新計算各條邊的阻方法分配，完成以后，根據(jù)阻抗函數(shù)重新計算各條邊的阻抗（時間），然后再對下一個小矩陣進行分配，直到抗（時間），然后再對下一個小矩陣進行分配，直到 N 個個矩陣分配完畢。矩陣分配完畢。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院v 算法描述算法描述長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院v 增量分配法的特點增量分配法的特點n 當當 N = 1 時為時為01分配；當分配；當 N 時，趨向均衡分配。時，趨向均衡分配。n 該方法簡單，精度可以根據(jù)該方法簡單，精度可以根據(jù) N 的大小來調節(jié)，因而在實際中的大小來調節(jié)，因而在實際中常被采用。常被采用。n 該方法

14、仍然是近似算法，有時會將過多的流量分配到容量小該方法仍然是近似算法，有時會將過多的流量分配到容量小的路段。的路段。n N 越大，配流結果越接近均衡解，但計算工作量相應增加。越大，配流結果越接近均衡解，但計算工作量相應增加。另外，非常大的另外，非常大的 N 值也不能完全保證配流結果一定滿足用戶值也不能完全保證配流結果一定滿足用戶均衡條件。均衡條件。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院算例：算例：長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.3.4 二次加權平均分配法二次加權平均分配法 (method of successive averages) v 分配思路

15、：該方法是一種介于增量分配法和均衡分配法之間的一分配思路：該方法是一種介于增量分配法和均衡分配法之間的一種循環(huán)分配方法?；舅悸肥遣粩嗾{整已分配到各路段上的交通種循環(huán)分配方法?；舅悸肥遣粩嗾{整已分配到各路段上的交通流量而逐漸達到或接近均衡分配。在每步循環(huán)中，根據(jù)已分配到流量而逐漸達到或接近均衡分配。在每步循環(huán)中，根據(jù)已分配到各路段上的交通量進行一次各路段上的交通量進行一次01分配，得到一組各路段的附加流分配，得到一組各路段的附加流量，然后用該循環(huán)中各路段的分配交通量和附加交通量進行加權量，然后用該循環(huán)中各路段的分配交通量和附加交通量進行加權平均，得到下一循環(huán)中的分配交通量。當連續(xù)兩個循環(huán)中的

16、分配平均，得到下一循環(huán)中的分配交通量。當連續(xù)兩個循環(huán)中的分配交通量十分接近時，即可停止計算。最后一個循環(huán)中得到的分配交通量十分接近時，即可停止計算。最后一個循環(huán)中得到的分配交通量即是最終結果。交通量即是最終結果。 v 分配步驟分配步驟長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院分配算例：分配算例： 試用二次加權平均分配法（試用二次加權平均分配法（MSA方法）求解下面的固定需求交通方法）求解下面的固定需求交通分配問題（迭代分配問題（迭代2次）。次）。 12t1t211200.01tx22160.1tx12100q長沙理工大學交通

17、運輸工程學院長沙理工大學交通運輸工程學院9.4 用戶優(yōu)化均衡交通分配模型（用戶優(yōu)化均衡交通分配模型（User Equilibrium Model） UE（用戶均衡）的概念最早由（用戶均衡）的概念最早由Wardrop于于1952年提出。年提出。User Equilibrium的基本假設有：的基本假設有：v 假設出行者都力圖選擇阻抗最小的路徑；假設出行者都力圖選擇阻抗最小的路徑；v 假設出行者能隨時掌握整個網(wǎng)絡的狀態(tài)，即能精確計算每條假設出行者能隨時掌握整個網(wǎng)絡的狀態(tài)，即能精確計算每條路徑的阻抗從而做出完全正確的路徑選擇決策；路徑的阻抗從而做出完全正確的路徑選擇決策；v 假設出行者的計算能力和計算

18、水平是相同的。假設出行者的計算能力和計算水平是相同的。v User Equilibrium的定義：當不存在出行者能單方面改變其出的定義：當不存在出行者能單方面改變其出行路徑并能降低其阻抗時，達到了行路徑并能降低其阻抗時，達到了UE狀態(tài)。狀態(tài)。長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.4.1 均衡分配模型的建立均衡分配模型的建立 Wardrop第一原理的數(shù)學描述第一原理的數(shù)學描述 v 變量說明：變量說明：v 變量關系變量關系 ：()( )( )rsrsrsaaakkakrsrsrsxttfCRR rqA aNW： ：(0/1)：S(s)： ：)(aaaxtt arsrsakaa

19、rskWsrRkxtC),()(， rskrsakrskaAafx，WsrfqrsRkrskrs),(，長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院v Wardrop第一原理的數(shù)學描述第一原理的數(shù)學描述()0rsrskkrsfC0rsrskC0rskf0rsrsRkrskrsfq1長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院 等價最優(yōu)性條件（等價最優(yōu)性條件（Backmann模型）模型） 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院算例：算例：長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院 對對Beckmann模型的進一步說明模型的進一步說明 長沙理

20、工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.4.2 模型解的等價性和唯一性證明模型解的等價性和唯一性證明 v 模型解的等價性證明就是證明模型解的等價性證明就是證明UE模型與模型與Wardrop第一原理等價，第一原理等價，模型解的唯一性證明就是證明模型解的唯一性證明就是證明UE模型具有唯一的路段流量解。模型具有唯一的路段流量解。 模型解的等價性證明模型解的等價性證明 v 對于任何一個非線性規(guī)劃問題，其駐點（最優(yōu)解）均滿足一階必對于任何一個非線性規(guī)劃問題，其駐點（最優(yōu)解）均滿足一階必要條件。如果要條件。如果UE模型的一階必要條件等價于模型的一階必要條件等價于Wardrop均衡，則說均衡，

21、則說明明UE模型的解服從模型的解服從Wardrop均衡。均衡。 v 由于由于UE模型的一階最優(yōu)性條件與模型的一階最優(yōu)性條件與Wardrop第一原理的數(shù)學描述相第一原理的數(shù)學描述相同，因此，模型的解為均衡網(wǎng)絡流。同，因此，模型的解為均衡網(wǎng)絡流。 v 具體有兩種證明方法（拉格朗日函數(shù)法）。具體有兩種證明方法（拉格朗日函數(shù)法）。長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院 模型解的唯一性證明模型解的唯一性證明 v 凸規(guī)劃：約束集是凸集（函數(shù)為凹函數(shù)）、目標函數(shù)是凸函數(shù)。凸規(guī)劃：約束集是凸集（函數(shù)為凹函數(shù)）、目標函數(shù)是凸函數(shù)。v 對于凸規(guī)劃，任何局部最優(yōu)解必是全局最優(yōu)解，即目標函數(shù)的最對于

22、凸規(guī)劃，任何局部最優(yōu)解必是全局最優(yōu)解，即目標函數(shù)的最優(yōu)值是唯一的。優(yōu)值是唯一的。v 嚴格凸規(guī)劃：約束集是凸集、目標函數(shù)是嚴格凸函數(shù)。嚴格凸規(guī)劃：約束集是凸集、目標函數(shù)是嚴格凸函數(shù)。v 對于嚴格凸規(guī)劃問題，其最優(yōu)點唯一。對于嚴格凸規(guī)劃問題，其最優(yōu)點唯一。v 多元函數(shù)的梯度多元函數(shù)的梯度v 向量對向量的導數(shù)向量對向量的導數(shù)v 多元函數(shù)的多元函數(shù)的Hesse矩陣矩陣長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院v 考察考察UE模型的目標函數(shù)是否為嚴格凸函數(shù)模型的目標函數(shù)是否為嚴格凸函數(shù))()()()()()(111AAAxtxtxxzxxzdxxdzxz111111111212222222

23、212212()()()()00()()()()00()()()()00AAAAAAAAAAAAt xt xt xdt xxxxdxtxtxtxdtxxxxdxHtxtxtxdtxxxxdx0長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院v 考察考察UE模型的約束集是否為凸集模型的約束集是否為凸集n 分析分析UE模型，可見模型，可見UE模型的約束均為等式約束和不等式（非模型的約束均為等式約束和不等式（非負）約束，且約束條件均是線性約束。根據(jù)線性函數(shù)既是凸負）約束，且約束條件均是線性約束。根據(jù)線性函數(shù)既是凸的又是凹的這一性質，所以的又是凹的這一性質，所以UE模型符合模型符合“各約束函數(shù)

24、都是凹各約束函數(shù)都是凹函數(shù)函數(shù)”的條件，即約束集合是凸集。的條件，即約束集合是凸集。 v UE模型的唯一性結論模型的唯一性結論n UE模型的約束集是凸集，目標函數(shù)是嚴格凸函數(shù)，故模型的約束集是凸集，目標函數(shù)是嚴格凸函數(shù)，故UE模型模型是嚴格凸規(guī)劃，模型有唯一最優(yōu)解。是嚴格凸規(guī)劃，模型有唯一最優(yōu)解。n 這就是說，當達到均衡狀態(tài)時，分配到各路段上的流量是唯這就是說，當達到均衡狀態(tài)時，分配到各路段上的流量是唯一的。一的。 v 需注意的問題需注意的問題n UE分配對于路段流是嚴格凸的、對于路徑流則不一定是嚴格分配對于路段流是嚴格凸的、對于路徑流則不一定是嚴格凸的。即模型有唯一的路段流量解而沒有唯一的路

25、徑流量解。凸的。即模型有唯一的路段流量解而沒有唯一的路徑流量解。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院UE模型路徑流不唯一的反例模型路徑流不唯一的反例 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.4.3 UE模型的求解模型的求解 v Backmann提出的上述交通分配數(shù)學規(guī)劃模型沉睡提出的上述交通分配數(shù)學規(guī)劃模型沉睡20年后，年后，1975年年LeBlance等學者成功地將等學者成功地將Frank-Wolfe算法用于模型的求解。最終形算法用于模型的求解。最終形成了目前廣泛應用的一種既嚴格又實用的解法（成了目前廣泛應用的一種既嚴格又實用的解法（F-W算法）。算

26、法）。v UE模型是一組非線性規(guī)劃模型。對于非線性規(guī)劃模型既使現(xiàn)在也沒模型是一組非線性規(guī)劃模型。對于非線性規(guī)劃模型既使現(xiàn)在也沒有普遍通用的解法。只是對于某些特殊的非線性規(guī)劃模型才有可靠有普遍通用的解法。只是對于某些特殊的非線性規(guī)劃模型才有可靠的解法，而的解法，而UE模型正是一種特殊的非線性規(guī)劃模型。模型正是一種特殊的非線性規(guī)劃模型。v Frank-Wolfe算法是用線性規(guī)劃逐步逼近非線性規(guī)劃的方法來求解算法是用線性規(guī)劃逐步逼近非線性規(guī)劃的方法來求解UE模型的。該方法是一種迭代算法。思路如下：模型的。該方法是一種迭代算法。思路如下：從某一初始點出發(fā)，從某一初始點出發(fā)，進行迭代，每步迭代中，先找到

27、一個最速下降的方向，然后再找到進行迭代，每步迭代中，先找到一個最速下降的方向，然后再找到一個最優(yōu)步長，在最速下降方向上截取最優(yōu)步長得到下一步迭代的一個最優(yōu)步長，在最速下降方向上截取最優(yōu)步長得到下一步迭代的起點。重復此過程，直到找到最優(yōu)解。此法的前提條件是模型的約起點。重復此過程，直到找到最優(yōu)解。此法的前提條件是模型的約束條件必須都是線性的。束條件必須都是線性的。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院Frank-Wolfe算法簡介算法簡介長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院UE模型的搜索方向問題模型的

28、搜索方向問題 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院最優(yōu)步長的確定問題最優(yōu)步長的確定問題 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院用戶均衡交通分配模型的求解步驟用戶均衡交通分配模型的求解步驟 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院F-W算法的缺陷算法的缺陷 v F-W算法在迭代后期階段收斂很慢，原因是當趨近于最優(yōu)解時，算法在迭代后期階段收斂很慢，原因是當趨近于最優(yōu)解時，搜索方向將垂直于目標函數(shù)在點搜索方向將垂直于目標函數(shù)在點 的梯度。的梯度。v 影響影響F-W算法收斂速度的因素還有：初始解、網(wǎng)絡結構和擁擠程算法收斂速度的因素還有：初始解、網(wǎng)絡

29、結構和擁擠程度。初始解離平衡點越近，則需要的迭代次數(shù)就越少；網(wǎng)絡結構度。初始解離平衡點越近，則需要的迭代次數(shù)就越少；網(wǎng)絡結構越復雜，或者說從起點到終點的可行路徑數(shù)越多，則需要的迭代越復雜，或者說從起點到終點的可行路徑數(shù)越多，則需要的迭代次數(shù)就越多；擁擠程度越大的網(wǎng)絡，需要更多的迭代次數(shù)來達到次數(shù)就越多；擁擠程度越大的網(wǎng)絡，需要更多的迭代次數(shù)來達到平衡點。平衡點。v 在實際應用中，對于大規(guī)模網(wǎng)絡，通常在實際應用中，對于大規(guī)模網(wǎng)絡，通常4至至6次迭代就夠了。確定次迭代就夠了。確定迭代次數(shù)時，要綜合考慮原始數(shù)據(jù)的準確性、財力約束和具體的迭代次數(shù)時，要綜合考慮原始數(shù)據(jù)的準確性、財力約束和具體的網(wǎng)絡結構

30、。網(wǎng)絡結構。 ()nax長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院UE分配算例：分配算例：網(wǎng)絡模型如下，試用網(wǎng)絡模型如下，試用F-W算法求兩邊的交通量。算法求兩邊的交通量。 11150.01tx22200.005tx2000q 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.5 系統(tǒng)優(yōu)化均衡交通分配模型（系統(tǒng)優(yōu)化均衡交通分配模型（SO Model） 9.5.1 SO模型的基本思想模型的基本思想 v Wardrop第一原理有時也稱為用戶均衡（第一原理有時也稱為用戶均衡（UE）原理、或用戶最優(yōu)原理。）原理、或用戶最優(yōu)原理。UE模型就是建立在模型就是建立在UE原理上的數(shù)學模

31、型。原理上的數(shù)學模型。v Wardrop第二原理第二原理 系統(tǒng)最優(yōu)原理系統(tǒng)最優(yōu)原理n Wardrop還提出了另一原理，即系統(tǒng)最優(yōu)原理，也稱第二原理。還提出了另一原理，即系統(tǒng)最優(yōu)原理，也稱第二原理。n Wardrop第二原理：在考慮擁擠對走行時間影響的網(wǎng)絡中，網(wǎng)絡中第二原理：在考慮擁擠對走行時間影響的網(wǎng)絡中，網(wǎng)絡中的交通量應該按某種方式分配以使網(wǎng)絡中交通量的總行駛時間最小。的交通量應該按某種方式分配以使網(wǎng)絡中交通量的總行駛時間最小。v 第一原理與第二原理的比較第一原理與第二原理的比較n Wardrop第一原理反映了用戶選擇路線的一種準則，分配出來的流第一原理反映了用戶選擇路線的一種準則，分配出來

32、的流量結果是道路網(wǎng)上交通利用者實際路徑選擇的結果；量結果是道路網(wǎng)上交通利用者實際路徑選擇的結果；n Wardrop第二原理反映的是一種系統(tǒng)目標，即按什么樣的分配是最第二原理反映的是一種系統(tǒng)目標，即按什么樣的分配是最好的，為規(guī)劃管理人員提供了一種決策方法，在實際中難以實現(xiàn)，好的，為規(guī)劃管理人員提供了一種決策方法，在實際中難以實現(xiàn)，除非所有的道路使用者都相互協(xié)作為系統(tǒng)最優(yōu)而努力。除非所有的道路使用者都相互協(xié)作為系統(tǒng)最優(yōu)而努力。長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.5.2 數(shù)學模型數(shù)學模型 UE/SO模型目標函數(shù)的含義模型目標函數(shù)的含義 v UE模型僅僅是一個能有效產生模型僅僅

33、是一個能有效產生UE條件的數(shù)學結構，缺乏直觀的條件的數(shù)學結構，缺乏直觀的物理或經(jīng)濟含義。物理或經(jīng)濟含義。Beckmann變魔術產生的。變魔術產生的。 v SO模型是可以直觀理解的，其目標是令系統(tǒng)的總交通時間最小。模型是可以直觀理解的，其目標是令系統(tǒng)的總交通時間最小。 數(shù)學模型數(shù)學模型 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院 UE模型與模型與SO模型解的比較模型解的比較 v 除非是特殊情況（如所有路段的時間是固定的常數(shù)），否則一般除非是特殊情況（如所有路段的時間是固定的常數(shù)），否則一般情況下情況下SO解和解和UE解是不會相同的。解是不會相同的。v 在在SO狀態(tài)，所有的出行者都能

34、夠在統(tǒng)一指揮下做出協(xié)調路徑選擇，狀態(tài)，所有的出行者都能夠在統(tǒng)一指揮下做出協(xié)調路徑選擇，以確保系統(tǒng)的總時間最小，而以確保系統(tǒng)的總時間最小，而UE狀態(tài)下的出行者只考慮個體的出狀態(tài)下的出行者只考慮個體的出行時間最小。行時間最小。 SO問題的一階最優(yōu)性條件問題的一階最優(yōu)性條件 ()0, ,0, , ,0, ,rsrskkrsrskrsrsrskkrskfCr s kCr s kqfr sfr s k,()()()()aaaaaaaarsrskaaa kadtxtxtxxdxCtx類似于類似于UE模型的一階最優(yōu)性條件模型的一階最優(yōu)性條件長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院 SO問題解

35、的唯一性證明問題解的唯一性證明 v SO問題的約束條件是線性等式約束和非負約束，因此其可行域是凸集。問題的約束條件是線性等式約束和非負約束，因此其可行域是凸集。 v 考察考察SO模型的目標函數(shù)是否是嚴格凸函數(shù)。模型的目標函數(shù)是否是嚴格凸函數(shù)。 ( )()aaaaZ xtxx12( )( )( )( )( )( ),TaAdZ xZ xZ xZ xZ xZ xdxxxxx21111121122222222222222()()2()()2()()2()()2000000( )0000000aaaaaaaAAAAAAAdtxd txxdxdxdtxd txxdxdxdtxd txxdxdxdtxd

36、txxdxdxz x長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院v SO模型的模型的Hessian矩陣是一個對角矩陣，由于路段走行時間函數(shù)矩陣是一個對角矩陣，由于路段走行時間函數(shù)是一個典型的凸的升函數(shù)，因此是一個典型的凸的升函數(shù)，因此Hessian矩陣為正定矩陣。即矩陣為正定矩陣。即SO模型的目標函數(shù)是一個嚴格凸函數(shù)。模型的目標函數(shù)是一個嚴格凸函數(shù)。v 約束集是凸集，目標函數(shù)是嚴格凸函數(shù)，故約束集是凸集，目標函數(shù)是嚴格凸函數(shù)，故SO模型是一個嚴格凸模型是一個嚴格凸規(guī)劃，有唯一的路段流量解。規(guī)劃，有唯一的路段流量解。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.5.3

37、 SO模型和模型和UE模型之間的關系模型之間的關系 v 很顯然，二者只有目標函數(shù)不同，約束條件完全一致，故二者之很顯然，二者只有目標函數(shù)不同，約束條件完全一致，故二者之間可以進行轉化。間可以進行轉化。 SO模型轉化成模型轉化成UE模型來求解模型來求解 v 通過對走行時間函數(shù)的修正，可以利用通過對走行時間函數(shù)的修正，可以利用UE模型來求解模型來求解SO模型。模型。 v 只有當交通量較小時，道路上不存在擁擠時，系統(tǒng)最優(yōu)和用戶均只有當交通量較小時，道路上不存在擁擠時，系統(tǒng)最優(yōu)和用戶均衡才有可能相等；若道路上的交通量大時，二者不可能相等。衡才有可能相等；若道路上的交通量大時，二者不可能相等。 UE模型

38、轉化為模型轉化為SO模型模型 v 顯然，通過對走行時間函數(shù)進行不同的修改可使顯然，通過對走行時間函數(shù)進行不同的修改可使UE模型和模型和SO模模型進行相互轉換。型進行相互轉換。 UE模型與模型與SO模型之間的差別舉例模型之間的差別舉例 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.5.4 SO模型求解算例模型求解算例 v 網(wǎng)絡如下，試求系統(tǒng)最優(yōu)均衡解。網(wǎng)絡如下，試求系統(tǒng)最優(yōu)均衡解。 11150.01tx22200.005tx2000q 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.5.5 能力詭異現(xiàn)象能力詭異現(xiàn)象 v 城市交通網(wǎng)絡中，經(jīng)常會遇到一種奇怪的反常現(xiàn)象。即在

39、擁擠的城市交通網(wǎng)絡中，經(jīng)常會遇到一種奇怪的反?，F(xiàn)象。即在擁擠的道路網(wǎng)絡中增加一條新的路段或對某些路段進行投資改造，增加道路網(wǎng)絡中增加一條新的路段或對某些路段進行投資改造，增加其能力后不但不能達到改善交通狀況的本意，反而會導致整個交其能力后不但不能達到改善交通狀況的本意，反而會導致整個交通網(wǎng)絡中擁擠程度的加劇，或使每個出行者的出行阻抗增加。這通網(wǎng)絡中擁擠程度的加劇，或使每個出行者的出行阻抗增加。這稱之為稱之為Braess詭異現(xiàn)象。詭異現(xiàn)象。 v Braess詭異現(xiàn)象指出：增加網(wǎng)絡中路段的數(shù)量反而使網(wǎng)絡的總阻詭異現(xiàn)象指出：增加網(wǎng)絡中路段的數(shù)量反而使網(wǎng)絡的總阻抗增加，而不是預料中的減少?？乖黾樱?/p>

40、是預料中的減少。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院Braess詭異現(xiàn)象的算例：詭異現(xiàn)象的算例：已知已知qOD=6，各路段的走行時間函數(shù)為，各路段的走行時間函數(shù)為t1(x1)=50+x1、t2(x2)=50+x2、t3(x3)=10 x3、t4(x4)=10 x4，試用，試用Wardrop第一原理和第二原理直接第一原理和第二原理直接求解網(wǎng)絡求解網(wǎng)絡并計算系統(tǒng)的總走行時間。為緩解交通擁擠，在節(jié)點并計算系統(tǒng)的總走行時間。為緩解交通擁擠，在節(jié)點A和節(jié)點和節(jié)點B之間再建一條道路，假設這條道路的走行時間函數(shù)為之間再建一條道路，假設這條道路的走行時間函數(shù)為t5(x5)=10+x5，試

41、用，試用Wardrop第一原理求解網(wǎng)絡第一原理求解網(wǎng)絡并計算系統(tǒng)的總并計算系統(tǒng)的總走行時間。比較新建道路后，系統(tǒng)總走行時間的變化并簡要分析走行時間。比較新建道路后，系統(tǒng)總走行時間的變化并簡要分析其原因。（網(wǎng)絡圖中路段數(shù)字為路段的編號）其原因。（網(wǎng)絡圖中路段數(shù)字為路段的編號） 網(wǎng)絡網(wǎng)絡 網(wǎng)絡網(wǎng)絡 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院v 增加一條道路后系統(tǒng)的總走行時間反而增加了，這就是著名的增加一條道路后系統(tǒng)的總走行時間反而增加了，這就是著名的Braess悖論。產生這種現(xiàn)象的根源在于悖論。產生這種現(xiàn)象的根源在于UE原則下的交通分配每個原則下的交通分配每個人都極小化個人的出行時間

42、，而不考慮對別人的影響，這樣下來，人都極小化個人的出行時間，而不考慮對別人的影響，這樣下來，盡管系統(tǒng)新增了道路但沒有效果、甚至比以前更差。進一步分析盡管系統(tǒng)新增了道路但沒有效果、甚至比以前更差。進一步分析還可以說明所謂的還可以說明所謂的Braess悖論只可能發(fā)生在按照悖論只可能發(fā)生在按照UE原則進行的交原則進行的交通分配上。通分配上。v 就本例而言，產生能力詭異現(xiàn)象的根本原因在于：新增路段就本例而言，產生能力詭異現(xiàn)象的根本原因在于：新增路段AB后，后，出行者新增了可選路徑的機會（即路徑出行者新增了可選路徑的機會（即路徑OABD），但構成），但構成這條路徑的路段這條路徑的路段3和路段和路段4是網(wǎng)

43、絡的瓶頸路段，從而導致在一定的是網(wǎng)絡的瓶頸路段，從而導致在一定的OD需求下網(wǎng)絡的總出行時間增加。需求下網(wǎng)絡的總出行時間增加。 v 因此，投資當局在決定增擴線路時，一定要謹慎，并非增加或擴因此，投資當局在決定增擴線路時，一定要謹慎，并非增加或擴建了線路就一定能改善交通狀態(tài)。相反，有的約束交通規(guī)則，如建了線路就一定能改善交通狀態(tài)。相反，有的約束交通規(guī)則，如限制車輛在某限制車輛在某時間段（如高峰期）進入主干道，或有意讓司機時間段（如高峰期）進入主干道，或有意讓司機們走一些表面上不經(jīng)濟的路線，能使整個網(wǎng)絡的交通擁擠程度減們走一些表面上不經(jīng)濟的路線，能使整個網(wǎng)絡的交通擁擠程度減小，這就是考慮了系統(tǒng)最優(yōu)原

44、則。小，這就是考慮了系統(tǒng)最優(yōu)原則。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.6 隨機交通分配模型（隨機交通分配模型（Logit型型/Probit型）型） v 0-1分配法假定出行者對交通網(wǎng)絡的結構和各條路段的阻抗分配法假定出行者對交通網(wǎng)絡的結構和各條路段的阻抗非常清楚，因此在假定阻抗為常數(shù)的前提下，每對非常清楚，因此在假定阻抗為常數(shù)的前提下，每對OD點之點之間的出行者都同時選擇該點對之間的最短路徑。間的出行者都同時選擇該點對之間的最短路徑。v 但實際上，由于交通網(wǎng)絡的復雜性和路段上交通狀況的多但實際上，由于交通網(wǎng)絡的復雜性和路段上交通狀況的多變性，以及各個出行者主觀判斷的多

45、樣性，某變性，以及各個出行者主觀判斷的多樣性，某OD點對之間點對之間不同出行者所感知的最短路徑將是不同的、隨機的，因此不同出行者所感知的最短路徑將是不同的、隨機的，因此這些出行者所選擇的這些出行者所選擇的“最短路徑最短路徑”不一定是同一條，從而不一定是同一條，從而出現(xiàn)多路徑選擇的現(xiàn)象。這種交通分配叫做出現(xiàn)多路徑選擇的現(xiàn)象。這種交通分配叫做“多路徑分多路徑分配配”，或，或“隨機加載隨機加載”。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.6.1 Logit型隨機配流的基本理論型隨機配流的基本理論 v 假定用戶對當前路網(wǎng)信息的掌握不完全；同時出行者對阻抗的估假定用戶對當前路網(wǎng)信息的

46、掌握不完全；同時出行者對阻抗的估計視為隨機變量。計視為隨機變量。v 仍然用仍然用Wardrop第一原理選擇路徑，但這里的路徑為估計最短路第一原理選擇路徑，但這里的路徑為估計最短路徑，即徑，即OD對間存有多條路線，同一出行者對不同的路徑存在著對間存有多條路線，同一出行者對不同的路徑存在著不同的估計，不同的出行者對同一路徑也存在著不同的估計。對不同的估計，不同的出行者對同一路徑也存在著不同的估計。對某一特定的出行者來說，他總是選擇估計阻抗最小的路徑。某一特定的出行者來說，他總是選擇估計阻抗最小的路徑。v 隨機分配模型就是在研究路徑估計阻抗分布函數(shù)的基礎上，計算隨機分配模型就是在研究路徑估計阻抗分布

47、函數(shù)的基礎上，計算有多少出行者選擇每一條路徑。有多少出行者選擇每一條路徑。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.6.2 Dial算法算法 v Dial算法（算法（1971年由年由Dial提出）是有效體現(xiàn)提出）是有效體現(xiàn)Logit型隨機分配思想的方法。型隨機分配思想的方法。 v Dial算法的基本原理：算法的基本原理：n 每一每一OD對對應的對對應的OD量只能在連接該量只能在連接該OD對的有效路徑上進行分配，對的有效路徑上進行分配，流量分配的分離公式為流量分配的

48、分離公式為Logit模型。模型。 n 有效路徑：全部由有效路段組成的路徑。有效路段是指令出行者離有效路徑：全部由有效路段組成的路徑。有效路段是指令出行者離其起點越來越遠、離其終點越來越近的路段，即沿著該路段前進能其起點越來越遠、離其終點越來越近的路段，即沿著該路段前進能更靠近出行的終點。更靠近出行的終點。 n 路段似然值為：路段似然值為： n 如果僅考慮有效路徑，則如果僅考慮有效路徑，則Dial算法產生的流量與在每一起終點間使用算法產生的流量與在每一起終點間使用Logit路徑分配模型的結果一致，即路徑分配模型的結果一致，即Dial算法產生的流量與算法產生的流量與Logit模型模型配流的結果等價

49、。配流的結果等價。 otherwisejsisjririftirjrjiLij 0)()(&)()( )()(exp),(長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院Dial分配例題：分配例題： v q19=1000， =1.0，按，按Dial算法進行分配。算法進行分配。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.7 隨機多路徑交通分配模型隨機多路徑交通分配模型 9.7.1 多路徑交通分配模

50、型的改進多路徑交通分配模型的改進v 由出行者的路徑選擇特性可知，出行者總是希望選擇最合適的路線由出行者的路徑選擇特性可知，出行者總是希望選擇最合適的路線出行，如最短的、最快的、最方便的、最舒適的路線等，通常稱之出行，如最短的、最快的、最方便的、最舒適的路線等，通常稱之為最短路因素。但是由于交通網(wǎng)絡的復雜性和交通狀況的隨機性，為最短路因素。但是由于交通網(wǎng)絡的復雜性和交通狀況的隨機性，出行者在選擇路線時往往帶有不確定性，通常稱之為隨機因素。出行者在選擇路線時往往帶有不確定性，通常稱之為隨機因素。v 對于隨機因素可理解如下，由于用戶對當前路網(wǎng)信息的不完全掌握，對于隨機因素可理解如下，由于用戶對當前路

51、網(wǎng)信息的不完全掌握，出行時選擇他認為是最短的路徑，但這條路徑實際上并不一定是最出行時選擇他認為是最短的路徑，但這條路徑實際上并不一定是最短的。并且不但同一出行者對不同的路徑存在著不同的估計，而且短的。并且不但同一出行者對不同的路徑存在著不同的估計，而且不同的出行者對同一路徑也存在著不同的估計。對某一特定的出行不同的出行者對同一路徑也存在著不同的估計。對某一特定的出行者而言，他總是選擇他估計阻抗最小的路徑出行。者而言，他總是選擇他估計阻抗最小的路徑出行。v 通常，最短路因素和隨機因素存在于出行者的整個出行過程中，兩通常，最短路因素和隨機因素存在于出行者的整個出行過程中，兩因素所處的主次地位取決于

52、可供選擇的出行路線的路權差（時間、因素所處的主次地位取決于可供選擇的出行路線的路權差（時間、距離或費用差）。因此，各出行路徑被選用的概率不同，其概率可距離或費用差）。因此，各出行路徑被選用的概率不同，其概率可采用采用Logit型的路徑選擇概率來進行計算。型的路徑選擇概率來進行計算。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.7.2 有效路段與有效出行路線有效路段與有效出行路線 （1）路段與路線）路段與路線 v 路線是指出行者從路線是指出行者從OD對的起點到對的起點到OD對的訖點行走的線路；而路對的訖點行走的線路；而路段則

53、是指這一條線路上的某一段。段則是指這一條線路上的某一段。（2）有效路段）有效路段 v 有效路段有效路段 i , j 定義為路段的終點定義為路段的終點 j 比路段的起點比路段的起點 i 更靠近出行更靠近出行終點終點 s 的路段。即沿著此路段前進能更接近（或至少不遠離）出的路段。即沿著此路段前進能更接近（或至少不遠離）出行終點行終點 s 。 （3）有效出行路線）有效出行路線v 有效出行路線定義為由有效路段組成的出行路線。每一有效出行路線定義為由有效路段組成的出行路線。每一OD點對點對對應的對應的OD量只能在其相應的有效出行路線上進行分配。量只能在其相應的有效出行路線上進行分配。 長沙理工大學交通運

54、輸工程學院長沙理工大學交通運輸工程學院（4）有效出行路線的長度）有效出行路線的長度 v 有效出行路線有效出行路線 L( i j , s ) 的長度定義為有效路段的長度定義為有效路段 i , j 的路權的路權 d ( i , j ) 加上有效路段的終點加上有效路段的終點 j 至出行終點至出行終點 s 的最短路權的最短路權 Lmin ( j , s )。 v 當有效出行路線長度確定后，便可計算出各有效出行路線的分配率當有效出行路線長度確定后，便可計算出各有效出行路線的分配率及有效路段的分配交通量。及有效路段的分配交通量。 （5）有效路段與有效出行路線的數(shù)量問題）有效路段與有效出行路線的數(shù)量問題v

55、對于城市交通網(wǎng)絡，交叉口多為對于城市交通網(wǎng)絡，交叉口多為4路交叉，各節(jié)點的有效路段及有效路交叉，各節(jié)點的有效路段及有效出行路線一般為出行路線一般為2條，少數(shù)情況為條，少數(shù)情況為1條或條或3條。條。v 對于區(qū)域公路網(wǎng)，一般交通節(jié)點與城市交通節(jié)點相同，有效路段與對于區(qū)域公路網(wǎng)，一般交通節(jié)點與城市交通節(jié)點相同，有效路段與有效出行路線的數(shù)量類似。有效出行路線的數(shù)量類似。v 對于交通樞紐，連接道路可多達對于交通樞紐，連接道路可多達810條，有效路段可達條，有效路段可達5條左右。條左右。v 可以證明，對于一個網(wǎng)絡中的任一節(jié)點，至少存在一條有效路段及可以證明，對于一個網(wǎng)絡中的任一節(jié)點，至少存在一條有效路段及

56、一條有效出行路線。一條有效出行路線。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.7.3 分配模型中參數(shù)分配模型中參數(shù) 的含義的含義 v 分配模型中，分配模型中， 為配流的參數(shù)，是一個無量綱的常數(shù)。為配流的參數(shù)，是一個無量綱的常數(shù)。 的取值的取值與路權無關，僅與可供選擇的有效出行路線條數(shù)相關。若為兩路與路權無關，僅與可供選擇的有效出行路線條數(shù)相關。若為兩路選擇時，選擇時， = 33.5 ；若為三路選擇時，；若為三路選擇時， =33.75。 的取值通常的取值通常比較穩(wěn)定，在比較穩(wěn)定，在3.004.00之間。之間。v 在在Dial模型中，模型中， 為帶量綱的參數(shù)，與路權的量綱及大小相關。為帶量綱的參數(shù)，與路權的量綱及大小相關。參數(shù)的確定比較復雜，一般應用現(xiàn)狀參數(shù)的確定比較復雜，一般應用現(xiàn)狀OD量及路段交通量實測數(shù)量及路段交通量實測數(shù)據(jù)用極大似然法進行標定估計。據(jù)用極大似然法進行標定估計。 長沙理工大學交通運輸工程學院長沙理工大學交通運輸工程學院9.7.4 多路徑交通分配流程多路徑