1、交通流分配（Traffic Assignment）,交通流分配是本課程的重點和難點之一。最優(yōu)化理論、圖論、計算機技術(shù)的發(fā)展，為交通流分配模型和算法的研究及開發(fā)提供了堅實的基礎(chǔ)，通過幾十年的發(fā)展，交通流分配是交通規(guī)劃諸問題中被國內(nèi)外學者研究得最深入、取得研究成果最多的部分。,本章主要講述交通流分配的基本概念、基本原理和基本方法，交通流分配的非平衡分配、平衡分配的模型和算法等內(nèi)容。,概 述,兩種機制相互作用直至平衡： 一種機制是：各種車輛試圖通過在網(wǎng)絡(luò)上選擇最佳行駛路線來達到自身出行費用最小的目標； 另一種機制是：道路上的車流量越大，用戶遇到的阻力即對應的行駛阻抗越高。 用一定的模型來描述這兩種機

2、制及其相互作用，并求解網(wǎng)絡(luò)上交通流量在平衡狀態(tài)下的合理分布，即交通流分配。,就是將預測得出的OD交通量，根據(jù)已知的道路網(wǎng)描述，按照一定的規(guī)則符合實際地分配到路網(wǎng)中的各條道路上去，進而求出路網(wǎng)中各路段的交通流量、所產(chǎn)生的OD費用矩陣，并籍此對城市交通網(wǎng)絡(luò)的使用狀況做出分析和評價。,交通配流,路徑n,路徑1,路徑2,O,D,O,D,最初的交通流分配研究，多采用全有全無方法。 該方法處理的是非常理想化的城市交通網(wǎng)絡(luò)，即假設(shè)網(wǎng)絡(luò)上沒有交通擁擠，路阻是固定不變的，一個OD對間的流量都分配在“一條徑路”，即最短徑路上。 但對于既有的城市內(nèi)部擁擠的交通網(wǎng)絡(luò)，該方法的結(jié)果與網(wǎng)絡(luò)實際情況出入甚大。,交通配流的發(fā)

3、展階段,在1952年，著名交通問題專家Wardrop提出了網(wǎng)絡(luò)平衡分配的第一、第二定理，人們開始采用系統(tǒng)分析方法和平衡分析方法來研究交通擁擠時的交通流分配。 確定性的平衡配流：其前提是假設(shè)出行者能夠精確計算出每條徑路的阻抗，從而能作出完全正確的選擇決定，且每個出行者的計算能力和水平是相同的。 現(xiàn)實中出行者對路段阻抗的掌握只能是估計而得。對同一路段，不同出行者的估計值不會完全相同，因為出行者的計算能力和水平是各異的。,交通配流的發(fā)展階段,在1977年，對交通流分配理論研究最積極、活躍的美國加州大學伯克利分校的Daganzo教授及麻省理工學院的Sheffi教授提出了隨機性分配的理論。 隨機性分配的

4、前提是認為出行者對路段阻抗的估計值與實際值之間的差別是一個隨機變量，出行者會在“多條路徑”中選擇，同一起迄點的流量會通過不同的徑路到達目的地。 隨機性分配理論和方法的提出，在擬合、反映現(xiàn)實交通網(wǎng)絡(luò)實際的進程中又推進了一大步。,交通配流的發(fā)展階段,路網(wǎng)上的擁擠性、路徑選擇的隨機性、交通需求的動態(tài)性是同時存在并交互作用的，其機理是紛繁復雜的。 真正地符合路網(wǎng)實際情況，還有更重要更基本的交通需求的時變性（即動態(tài)性）需要反映出來。 需要一種交通流分配方法能夠?qū)⒙肪W(wǎng)上交通流的擁擠性、路徑選擇的隨機性、交通需求的時變性綜合集成地刻畫反映出來，這是研究交通問題的學者一直積極探索的問題。,交通配流的發(fā)展階段,

5、基 本 概 念,(1)將現(xiàn)狀OD交通量分配到現(xiàn)狀交通網(wǎng)絡(luò)上，以分析目前交通網(wǎng)絡(luò)的運行狀況，如果有某些路段的交通量觀測值，還可以將這些觀測值與在相應路段的分配結(jié)果進行比較，以檢驗模型的精度。 (2)將規(guī)劃年OD交通量預測值分配到現(xiàn)狀交通網(wǎng)絡(luò)上，以發(fā)現(xiàn)對規(guī)劃年的交通需求來說，現(xiàn)狀交通網(wǎng)絡(luò)的缺陷，為交通網(wǎng)絡(luò)的規(guī)劃設(shè)計提供依據(jù)。 (3)將規(guī)劃年OD交通量預測值分配到規(guī)劃交通網(wǎng)絡(luò)上，以評價交通網(wǎng)絡(luò)規(guī)劃方案的合理性。,交通流分配的幾種模式,（1）表示需求的OD交通量。在擁擠的城市道路網(wǎng)中通常采用高峰期OD交通量，在城市間公路網(wǎng)中通常采用年平均日交通量（AADT）的OD交通量； （2） 路網(wǎng)定義，即路段及交

6、叉口特征和屬性數(shù)據(jù)，同時還包括其時間流量函數(shù)； （3）路段阻抗函數(shù)。,交通流分配的基本數(shù)據(jù),從交通流分配的特點來說，可以分為兩類: 交通工具的運行線路固定類型和運行線路不固定類型。 線路固定類型有公共交通網(wǎng)和軌道交通網(wǎng)，這些是集體旅客運輸； 線路不固定類型有城市道路網(wǎng)、公路網(wǎng)，這一般是指個體旅客運輸或貨物運輸，這類網(wǎng)絡(luò)中，車輛是自由選擇運行徑路的。,交通阻抗（交通費用）,交通阻抗或者稱為路阻是交通流分配中經(jīng)常提到的概念，也是一項重要指標，它直接影響到交通流路徑的選擇和流量的分配。 道路阻抗在交通流分配中可以通過路阻函數(shù)來描述。 所謂路阻函數(shù)是指路段行駛時間與路段交通負荷，交叉口延誤與交叉口負荷

7、之間的關(guān)系。,交通網(wǎng)絡(luò)上的路阻（費用），應包含反映出行時間、出行費用、安全、舒適程度、便捷性和準時性等等許多因素。 經(jīng)過大量的理論分析和工程實踐，人們得出影響路阻的主要因素是時間，因此出行時間常常被作為計量路阻的主要標準。 交通阻抗有兩部分組成：路段上的阻抗、節(jié)點處的阻抗。,出行時間與流量的關(guān)系比較復雜，可以廣義地表達為： 即路段a上的費用 不僅僅是路段本身流量的函數(shù)，而且是整個路網(wǎng)上流量V的函數(shù)。,對于公路網(wǎng)而言，由于路段比較長，大部分出行時間是在路段上而不是在交叉口上，費用和流量的關(guān)系可以簡化為： 即路段的費用只與該路段的流量及其特性相關(guān)。,路段阻抗,美國道路局(BPRBureau of

8、public road)開發(fā)的函數(shù)，被稱為BPR函數(shù):,：路段 上的阻抗； ：零流阻抗，即路段 上為空靜狀態(tài)時車輛自由行駛所需 要的時間； ：路段 上的交通量； ：路段 的實際通過能力，即單位時間內(nèi)路段實際可通過 的車輛數(shù)； ：在美國公路局交通流分配程序中，這兩個參數(shù)的取值分別為 0.15、4。也可由實際數(shù)據(jù)用回歸分析求得。,車輛在交通網(wǎng)絡(luò)節(jié)點處主要指在交叉口處的阻抗。 交叉口阻抗與交叉口的型式，信號控制系統(tǒng)的配時，交叉口的通過能力等因素有關(guān)。 在城市交通網(wǎng)絡(luò)的實際出行時間中，除路段行駛時間外，交叉口延誤占有較大的比重，特別是在交通高峰期間，交叉口擁擠阻塞比較嚴重時，交叉口延誤將超過路段行駛時

9、間。,節(jié)點阻抗,1958年英國TRRL研究所的F.V. Webster 等人根據(jù)排隊論理論，提出了一個計算交叉口延誤的模型。該模型中主要包括兩部分： 一部分是車輛到達率為固定均值時產(chǎn)生的正常相位延誤即均勻延誤； 另一部分是車輛到達率隨機波動時所產(chǎn)生的附加延誤。,T：信號周期長度； ：進口道有效綠燈時間與信號周期長度之比，即綠信比； Q：進口道的交通流量； X：飽和度，X=Q/S ，S為進口道通過能力。,交通平衡問題,Wardrop提出的第一原理定義： 在道路的利用者都確切知道網(wǎng)絡(luò)的交通狀態(tài)并選擇最短徑路時，網(wǎng)絡(luò)將會達到平衡狀態(tài)。在考慮擁擠對行駛時間影響的網(wǎng)絡(luò)中，當網(wǎng)絡(luò)達到平衡狀態(tài)時，每個OD對

10、的各條被使用的徑路具有相等而且最小的行駛時間；沒有被使用的徑路的行駛時間大于或等于最小行駛時間。 這條定義通常簡稱為Wardrop平衡，在實際交通流分配中也稱為用戶均衡(UE, User Equilibrium)或用戶最優(yōu)。,Wardrop提出的第二原理： 在系統(tǒng)平衡條件下，擁擠的路網(wǎng)上交通流應該按照平均或總的出行成本最小為依據(jù)來分配。 Wardrop第二原理，在實際交通流分配中也稱為系統(tǒng)最優(yōu)原理（SO，System Optimization）。,第一原理主要是建立每個道路利用者使其自身出行成本（時間）最小化的行為模型，而第二原理則是旨在使交通流在最小出行成本方向上分配，從而達到出行成本最小的

11、系統(tǒng)平衡。 第二個原理作為一個設(shè)計原理，是面向交通管理工程師的。 在實際交通中，人們更期望交通流能夠按照Wardrop第一原理，即用戶平衡的近似解來分配。,例子： 設(shè)OD之間交通量為q=2000輛，有兩條路徑a與b。路徑a行駛時間短，但是通行能力小，路徑b行駛時間長，但通行能力大。假設(shè)各自的行駛時間（分鐘）與流量的關(guān)系是：,根據(jù) Wardrop平衡第一原理的定義，很容易建立下列的方程組： 則有：,顯然 只有在非負解時才有意義，即 也就是說，當OD交通量小于250時， ，則 即所有OD 都沿著路徑a走行。 當OD交通量大于250時，兩條徑路上都有一定數(shù)量的車輛行駛。當 時，平衡流量為： 即平衡時

12、兩條徑路的行駛時間均為22分鐘。,從1952年Wardrop提出道路網(wǎng)平衡的概念和定義之后，如何求解Wardrop平衡成了研究者的重要課題。 1956年，Beckmann等提出了描述平衡交通流分配的一個數(shù)學規(guī)劃模型。 經(jīng)過20年之后，即到1975年才由LeBlanc等學者設(shè)計出了求解Beckmann模型的算法（將Frank-Wolfe算法用于求解該模型），從而形成了現(xiàn)在的實用解法。 Wardrop原理Beckmann模型LeBlanc算法這些突破是交通流分配問題研究的重大進步，也是現(xiàn)在交通流分配問題的基礎(chǔ)。,對于完全滿足Wardrop原理定義的平衡狀態(tài)，則稱為平衡分配方法。 對于采用啟發(fā)式方法

13、或其它近似方法的分配模型，則稱為非平衡分配方法。,非平衡分配方法,非平衡分配方法按其分配方式可分為變化路阻和固定路阻兩類，按分配形態(tài)可分為單路徑與多路徑兩類。,全有全無分配方法（all-or-nothing）,將OD交通量T加載到路網(wǎng)的最短徑路樹上，從而得到路網(wǎng)中各路段流量的過程。 第1步：初始化，使路網(wǎng)中所有路段的流量為0，并求出各路段自由流狀態(tài)時的阻抗； 第2步：計算路網(wǎng)中每個出發(fā)地O到每個目的地D的最短路徑； 第3步：將O、D間的OD交通量全部分配到相應的最短徑路上。,該方法是在全有全無分配方法的基礎(chǔ)上，考慮了路段交通流量對阻抗的影響，進而根據(jù)道路阻抗的變化來調(diào)整路網(wǎng)交通量的分配，是一種

14、“變化路阻”的交通量分配方法。 增量分配法有容量限制-增量加載分配、容量限制-迭代平衡分配兩種形式。,增量分配法（incremental assignment method）,容量限制-增量加載分配方法,將OD交通量分成若干份（等分或不等分）； 循環(huán)地分配每一份的OD交通量到網(wǎng)絡(luò)中； 每次循環(huán)分配一份OD交通量到相應的最短路徑;每次循環(huán)均計算、更新各路段的行駛時間，然后按更新后的行駛行駛時間重新計算最短徑路； 下一循環(huán)中按更新后的最短徑路分配下一份OD交通量。,第1步：初始化。分割OD交通量： 令n=1 。 第2步：計算、更新路段費用： 第3步：用全有全無分配法將第n個分割OD交通量 分配到最

15、短經(jīng)路上。得到每條路段上的流量 。 第4步：計算 。 第5步：如果n=N，則結(jié)束計算。反之，令n=n+1返回第2步。,=,當分割數(shù)N=1時便是全有全無分配方法，當N趨向于無窮大時，該方法趨向于平衡分配法的結(jié)果。 優(yōu)點： 簡單可行，精確度可以根據(jù)分割數(shù)N的大小來調(diào)整；實踐中經(jīng)常被采用，且有比較成熟的商業(yè)軟件可供使用。 缺點： 與平衡分配法相比，仍然是一種近似方法；當路阻函數(shù)不是很敏感時，會將過多的交通量分配到某些通行能力很小的路段上。,增量加載和迭代平衡分配形式的原理基本是相同的。但增量加載方法事先無法估計迭代次數(shù)及計算工作量，對于較復雜的網(wǎng)絡(luò)，可能會因為個別路段的迭代精度無法滿足要求而使迭代進

16、入死循環(huán)，出現(xiàn)算法不收斂的情況。 美國聯(lián)邦公路局對這一算法進行了改進： 事先設(shè)定一個最大迭代次數(shù)N（N4） 當前迭代的阻抗值為前兩次阻抗值的加權(quán)值 平衡流解即取最后四次迭代的路段流量的平均值。,容量限制-迭代平衡分配,第1步：初始化。令 ，用全有全無方法將OD矩陣加載到交通網(wǎng)絡(luò)上，得到路段流量 ，設(shè)置迭代次數(shù)n=1。 第2步：計算 。 第3步：加權(quán)平滑。計算 ， 其中權(quán)值0.75和0.25是由經(jīng)驗得到的。 第4步：網(wǎng)絡(luò)加載。根據(jù)路段的阻抗值 ，用全有全無方法將OD矩陣加載到交通網(wǎng)絡(luò)上，得到路段流量 。 第5步：如果n=N，則結(jié)束計算。反之，令n=n+1返回第2步。,迭代平均法（MSA算法）,不

17、斷調(diào)整各路段分配的流量而逐漸接近平衡分配結(jié)果。每步循環(huán)中，根據(jù)各路段分配到的流量進行一次全有全無分配，得到一組各路段的附加流量； 然后用該循環(huán)中各路段已分配的交通量和該循環(huán)中得到的附加交通量進行加權(quán)平均，得到下一循環(huán)中的分配交通量； 當相鄰兩次循環(huán)中分配的交通量十分接近時，即停止運算，最后一次循環(huán)中得到的交通量即為最終結(jié)果。,第1步：初始化。令 。根據(jù)各路段自由行駛時間進行全有全無分配，得到初始解 。令迭代次數(shù)n=1。 第2步：更新路段的阻抗，按照當前各路段的交通量計算各路段的路阻 。 第3步：按照路段行駛阻抗 將OD交通量進行全有全無分配。得到各路段的附加交通量 。 第4步：更新路段流量。計

18、算 第5步：如果連續(xù)兩次迭代的結(jié)果相差不大，則停止計算。即為最終分配結(jié)果。否則令n=n+1，返回第2步。,連續(xù)平均法是介于增量分配法和平衡分配法之間的一種循環(huán)分配方法。 MSA方法是既簡單適用，又最接近于平衡分配法的一種分配方法；如果每步循環(huán)中1/n的嚴格按照數(shù)學規(guī)劃模型取值時，即可得到平衡分配的解。,例題 設(shè)圖示交通網(wǎng)絡(luò)的OD交通量為 輛，各路徑上的交通費用函數(shù)分別為： 試用全有全無分配法、增量分配法法求出分配結(jié)果，并進行比較。,i,j,1,2,3,全有全無分配法 由路段費用函數(shù)可知，在路段交通量為零時，路徑1最短。根據(jù)全有全無原則，交通量全部分配到路徑1上，得到以下結(jié)果： 很明顯，根據(jù)Wa

19、rdrop原理，網(wǎng)絡(luò)沒有達到平衡狀態(tài)。 此時路網(wǎng)總費用為5000。,增量分配法(假定N=2) 第1次分配：與全有全無分配法相同，路徑1最短。得到下面結(jié)果： 第2次分配：此時最短路徑變?yōu)槁窂?，得到下面結(jié)果： 此時路網(wǎng)總費用為2750。,平衡配流模型及算法,Wardrop平衡分配原理的數(shù)學模型 平衡分配模型的求解算法 用戶平衡分配模型 系統(tǒng)最優(yōu)平衡分配模型,模型中所用變量和參數(shù),：路段a上的交通流量； ：路段a的交通阻抗，也稱為行駛時間； ：路段a的阻抗函數(shù)，也稱為行駛時間函數(shù)； ：出發(fā)地為r，目的地為s的OD間的第k條徑路上的流量； ：出發(fā)地為r，目的地為s的OD間的第k條徑路的阻抗； ：出發(fā)

20、地為r，目的地為s的OD間的最短徑路的阻抗；,：路段-路徑相關(guān)變量，即0-1變量。如果路段a屬于從出發(fā)地為r目的地為s的OD間的第k條路徑，則為1，否則為0。 R：網(wǎng)絡(luò)中出發(fā)地的集合； S：網(wǎng)絡(luò)中目的地的集合； ：出發(fā)地r和目的地s之間的所有徑路的集合； ：出發(fā)地r和目的地s之間的OD交通量。,Wardrop用戶平衡準則,當交通網(wǎng)絡(luò)達到平衡時，若有 0，必有 說明如果從r到s有兩條及其以上的路徑被選中，那么它們的行駛時間最小且相等； 若有 =0，必有 說明如果某條從r到s的路徑流量等于零，那么該路徑的行駛時間一定不小于被選中的路徑的行駛時間。,基本守恒條件,（1）OD間各條路徑上的交通量之和應

21、等于OD交通總量,（2）路段上的流量等于使用該路段的各條路徑的流量之和,（3）路徑的阻抗等于組成該路徑的各個路段的阻抗之和 （4）路徑流量滿足非負約束,用戶平衡配流模型（Beckmann模型 ）,用戶均衡的概念,如圖所示，一個有兩條路徑（同時也是路段）、連接一個出發(fā)地和一個目的地的簡單交通網(wǎng)絡(luò)，兩個路段的阻抗函數(shù)分別是：,t1=2+x1，t2=1+2x2,OD量為q=5，分別求該網(wǎng)絡(luò)的Beckmann平衡模型的解和平衡狀態(tài)的解。,R,S,1,2,例題,將阻抗函數(shù)帶入模型，得：,x1,x20,s.t. x1+x2=5,將x1=5-x2帶入目標函數(shù)并進行積分，得到下面極小值問題： min:Z(X)

22、=1.5x12-9x1+30 令dZ/dx1=0 解得x1*=3，x2*=2。,求平衡狀態(tài)的解 根據(jù)Wardrop用戶平衡原理： t1=t2 x1+x2=5。 求解這個方程組，很容易求得x1=3，x2=2。 此時，t1=t2=5。 可見，Beckmann模型的解和平衡狀態(tài)的解完全相同。,等價性證明,根據(jù)非線性規(guī)劃理論，對模型構(gòu)造拉格朗日（Lagrange）函數(shù)：,其中， 是拉格朗日乘子，也是rs之間的最小阻抗。,根據(jù)非線性規(guī)劃理論中的庫恩塔克（Kuhn-Tucher）條件，拉格朗日函數(shù)在極值點必須滿足下列條件：,庫恩塔克條件可以簡化表示為：,對于某個特定的連接r和s的路徑，某路徑k的流量 有兩

23、種可能：,如果 ，得 ； 如果 ，得 。,求解方法,步驟1：初始化：按照 ，進行0-1交通流分配，得到各路段的流量 ；令n=1；,步驟2：更新各路段的阻抗 ：,步驟3：尋找下一步迭代方向：按照更新后的 ，再進行一次0-1交通流分配，得到一組附加流量 ；,步驟4：確定迭代步長：用二分法求滿足下式的,步驟5：確定新的迭代起點 ；,步驟6：收斂性檢驗。如果滿足： 其中是預先給定的誤差限值，則 就是要求的平衡解，計算結(jié)束；否則，令n=n+1，返回步驟2。,系統(tǒng)最優(yōu)模型,該模型稱為系統(tǒng)最優(yōu)模型SO(System Optimization)。 Beckmann模型稱為用戶平衡模型UE(User Equil

24、ibrium)。,系統(tǒng)最優(yōu)分配與用戶最優(yōu)分配的關(guān)系： 對阻抗函數(shù)進行變換，令：,如果用 作為阻抗函數(shù)，則此時用戶最優(yōu)分配模型完全可以轉(zhuǎn)換為系統(tǒng)最優(yōu)分配模型，所以進行該阻抗函數(shù)下的用戶最優(yōu)分配，得到的解就是系統(tǒng)最優(yōu)分配的解。,1,3,1,1,1,3,1,3,1,最短路徑算法,好的交通量分配法必須有一種好的最短路徑計算方法 尋找O-D對之間的最小費用路徑，簡稱最短路徑，是求解交通網(wǎng)絡(luò)平衡配流問題的核心。 任何一種交通量分配法都是建立在最短路徑的基礎(chǔ)上； 任何一個分配法中，最短路徑的計算占據(jù)了全部計算時間的主要部分。至少有90%的計算時間花在最短路徑的尋找上。,求解最短路徑算法 迪杰斯特拉(Dijk

25、stra)算法，即標點法（Label-correcting method） 矩陣迭代法,基本思想： 反復掃描網(wǎng)絡(luò)的節(jié)點，在每次掃描中，該方法試圖發(fā)現(xiàn)從根節(jié)點到正在掃描的節(jié)點之間的、比現(xiàn)有路徑更好的路徑，當從根節(jié)點到所有其它節(jié)點之間沒有更好的路徑時，算法就停止搜索。,標點法,在此算法中，為每一個節(jié)點設(shè)置兩個記錄：,（1） 標號 ，表示沿著最短路徑從根節(jié)點到節(jié)點 的最小費用；,（2）緊前節(jié)點 ，表示沿著最短路徑到達節(jié)點 且最靠近 的節(jié)點。,在每次掃描中，將緊前節(jié)點都記錄下來，形成緊前節(jié)點序列，這是為了停止掃描時，能反饋地找出最短路徑的軌跡。,檢查列中包含正在和需要進一步檢查的節(jié)點，掌握節(jié)點被檢查的

26、動態(tài)； 標號列中記載各節(jié)點的標號； 緊前節(jié)點列中記載各節(jié)點的緊前節(jié)點，根據(jù)緊前節(jié)點列可以找到節(jié)點之間的最短路徑； 每進行一步新的掃描，標號列、緊前節(jié)點列和檢查列就要更新一次，當檢查列中不再有節(jié)點時，算法停止。,算法步驟：,第一步：初始化，置所有標號為無窮大（或一個很大的正數(shù)），置所有的緊前節(jié)點為零，將根節(jié)點 放入檢查列中，并令 ；,第二步：從檢查列中任選一個節(jié)點，例如節(jié)點 ，掃描所有從 節(jié)點出發(fā)只經(jīng)過一條弧便可到達的節(jié)點，例如 節(jié)點，如果： 則更新節(jié)點 上的標號，令 ， 是從節(jié)點 到節(jié)點 的弧上的阻抗值。 如果上面式子不成立，則節(jié)點 的標號不變。,第三步：在改變節(jié)點 的標號的同時，修改 ，且將

27、 加入到檢查列中（因為從節(jié)點 出發(fā)還可能到達其它節(jié)點）。當從 出發(fā)只經(jīng)過一條弧便可到達的所有節(jié)點都被檢查過時，就從檢查列中刪除 節(jié)點。,第四步：當檢查列中不再有節(jié)點時，算法停止。從根節(jié)點到其它任意節(jié)點的最短路徑可通過反向搜索最后的緊前節(jié)點序列識別出來。,例：包含4條弧的簡單網(wǎng)絡(luò)，其中根節(jié)點為1，弧上的數(shù)字表示弧的阻抗。,第一步：所有節(jié)點的標號都置為 ，其緊前節(jié)點都置為零。然后，節(jié)點1的標號變?yōu)?，且把它放到檢查列中。,第二步：從節(jié)點1出發(fā)可以到達節(jié)點2和4，先考慮節(jié)點4，因為 ，則節(jié)點4的標號變?yōu)?，且被放入到檢查列中。,標號列,緊前節(jié)點列,基本思想： （1）是借助距離（路權(quán)）矩陣的迭代運算來

28、求解最短路權(quán)的算法。 （2）該方法能一次獲得任意兩點之間的最短路權(quán)矩陣。,矩陣迭代法,算法步驟：,（1）首先構(gòu)造距離矩陣（以距離為權(quán)的權(quán)矩陣） （2）矩陣給出了節(jié)點間只經(jīng)過一步（一條邊）到達某一點的最短距離 （3）對距離矩陣進行如下的迭代運算，便可以得到經(jīng)過兩步達到某一點的最短距離：,k=1,2,3,n,n：網(wǎng)絡(luò)節(jié)點數(shù)；,*：矩陣邏輯運算符； dik，dkj ：距離矩陣D中的相應元素。,例題：用矩陣迭代法計算下圖所示路網(wǎng)任意節(jié)點之間的最短阻抗值。,（1）距離矩陣如下：,（2）進行矩陣迭代運算（第2步）,d212=mind11+d12,d12+d22,d13+d32,d14+d42,d15+d5

29、2,d16+d62, d17 +d72,d18+d82,d19+d92 =min0+2,2+0,+2,2+,+2,+,+, +, +=2 (i=1,j=2;k=1,29),其它元素按同樣方法計算，得到D2,（3）進行矩陣迭代運算，經(jīng)過三步到達某一節(jié)點的最短距離為：,D3= D2 *D=d3ij d3ij =mind2ik+dkj k=1,2,3,n,d2ik :距離矩陣D2中的元素； dkj:距離矩陣D中的元素。,迭代不斷進行，直到： Dm= Dm-1。即：Dm中的每個元素等于Dm-1 中的每個元素為止，此時的Dm便是任意兩點之間的最短路權(quán)矩陣。,隨機分配方法,隨機用戶平衡的問題 任何一個道路

30、利用者均不可能通過單方面改變其徑路來降低其所估計的行駛時間時，達到了平衡狀態(tài)，這就是所說的“隨機用戶平衡（stochastic user equilibrium）”即SUE問題。,非平衡隨機分配方法 模擬隨機分配法（simulation-based）：應用Monte-Carlo等隨機模擬方法產(chǎn)生路段阻抗的估計值，然后進行全有全無分配； 概率隨機分配法（proportion-based）：利用Logit等模型計算不同徑路上承擔的出行量比例，并由此進行分配。,3、Dial算法以及其缺陷,Dial算法定義有效路徑為：O-D對rs之間的路徑是有效的，是指它所包含的所有路段都令出行者離起始點越來越遠，離

31、終結(jié)點越來越近。 只有當O-D對rs之間的路徑上任意路段（i,j）滿足以下條件時，該路徑才算是有效路徑。,且,（1）,Dial算法,3、Dial算法以及其缺陷,第一步：對于每一節(jié)點，采用最短路算法計算 和 ， ；,第二步：對于路段（i,j），計算路段似然值：,第三步：向前計算路段權(quán)重。從起點開始，按照 的上升順序?qū)γ恳粋€節(jié)點，計算離開它的所有路段的權(quán)重值。,當達到終節(jié)點時停止計算。,3、Dial算法以及其缺陷,第四步：向后計算路段流量。從終點開始，按照 的上升順序依次考慮節(jié)點，對于每一個節(jié)點，計算進入它的所有路段上的流量。,3、Dial算法以及其缺陷,Dial算法對有效路徑的定義過于嚴格，將導

32、致分配結(jié)果中阻抗較低的路徑不被使用，而阻抗較高的路徑反被使用的現(xiàn)象。 根據(jù)Dial算法的初始化階段，計算結(jié)果如表所示：,根據(jù)Dial算法，路段（2,3）不屬于有效路徑的路段，這樣，路徑1-2-3-5就被排除在有效路徑之外，但這條路徑的阻抗均為4.5，而被認為是有效路徑1-4-5的阻抗值為5，顯然，這是不合理的。如果按照“一步走過”算法，則所有連通路徑都會被看作為有效路徑，而此時路徑1-2-3-4-5的阻抗為6，為最小阻抗的1.5倍，顯然，這在現(xiàn)實中也是不合理的。,3、Dial算法以及其缺陷,Dial算法假定路徑的選擇概率與該路徑所包含的所有路段似然值的乘積成正比例關(guān)系，即,這種假定條件說明，路徑所包含的路段數(shù)量越多，那么該路徑被出行者選擇的概率就越小。但是在實際的道路交通網(wǎng)絡(luò)中，可能會出現(xiàn)這樣的情況，在某個O-D間的某條路徑上，雖然此路徑所包含的路段數(shù)量較多，但這些路段的費用