5 四步驟交通需求預測模型(4.1)交通分配ppt課件.ppt

1、交通規(guī)劃理論與方法（4） “四步驟”交通需求預測模型,西南交通大學交通運輸學院 楊 飛 （博士、講師）,交通工程本科課程,交通運輸學院,主要內(nèi)容,交通分配的基本問題描述 交通分配作用 基本概念： 路徑與最短路徑、交通阻抗、交通均衡問題、非均衡問題、交通網(wǎng)絡的數(shù)學化表示 非均衡分配方法 如全有全無分配法、單路徑分配法等 B-L均衡分配法（重點）,4 交通分配,4.1 基本問題 交通分配是指將各分區(qū)之間出行分布量分配到連接交通小區(qū)的交通網(wǎng)絡的各條邊上去的工作過程,出行者會如何選擇路徑？會考慮哪些因素？,4 交通分配,4.2 交通分配的功用 （1）檢驗四階段預測模型的精度 將現(xiàn)狀OD量在現(xiàn)狀交通網(wǎng)絡

2、上的分配，以分析目前交通網(wǎng)絡的運行狀況，如果有某些路段的交通量觀測值，還可以將這些觀測值與在相應路段的分配結(jié)果進行比較，從而進行精度校驗,4 交通分配,4.2 交通分配的功用 （2）交通網(wǎng)絡的規(guī)劃設(shè)計提供依據(jù) 規(guī)劃年OD分布預測值在現(xiàn)狀交通網(wǎng)絡上的分配，以發(fā)現(xiàn)對規(guī)劃年的交通需求來說，現(xiàn)狀交通網(wǎng)絡的缺陷，為后面交通網(wǎng)絡的規(guī)劃設(shè)計提供依據(jù) （3）評價交通網(wǎng)絡規(guī)劃方案 還可以是規(guī)劃年OD分布預測值在規(guī)劃交通網(wǎng)絡上的分配，以評價交通網(wǎng)絡規(guī)劃方案的優(yōu)劣,4 交通分配,4.3 基本概念 （1）交通分配的單位 交通分配中的出行分布量一般是指機動車，以pcu為單位 出行量的單位轉(zhuǎn)換：人（交通生成預測）-車（方

3、式劃分） （2）交通分配的對象 線路不固定的機動車輛分布量 公共汽電車是按固定路線行駛的，不能自由選擇行駛路徑，交通分配不包括這部分車輛,4 交通分配,4.3 基本概念 （3）路段、路徑與最短路徑 1）路段：交通網(wǎng)絡上相鄰兩個節(jié)點之間的交通線路稱作“路段” 2）路徑：交通網(wǎng)絡上任意一對OD點之間，從產(chǎn)生點到吸引點一串連通的路段的有序排列叫作這對OD點之間的路徑。一對OD點之間可以有多條路徑 3）最短路徑：一對OD點之間路徑中總阻抗最小的路徑叫“最短路徑”,4 交通分配,4.3 基本概念 （4）交通阻抗 交通阻抗是指交通網(wǎng)絡上路段或路徑之間的運行距離、時間、費用、舒適度，或這些因素綜合 對不同交

4、通網(wǎng)絡其含義隨關(guān)注點不同而有所偏重，或為了簡單起見可單指其中某個因素。如對城市道路網(wǎng)，一般指出行時間；公路網(wǎng)較多地指距離,4 交通分配,4.3 基本概念 （4）交通阻抗 交通阻抗有兩部分組成：路段阻抗、節(jié)點阻抗 A. 路段阻抗的函數(shù)關(guān)系確定 以出行時間為主要因素考慮路段阻抗。有些交通網(wǎng)絡，路段上的走行時間與距離成正比，與路段上的流量無關(guān)，如城市軌道交通網(wǎng)。用時間或距離作為等價阻抗 有些交通網(wǎng)絡，路段上的走行時間與距離不一定成正比，與路段上的交通流量有關(guān)，如公路網(wǎng)、城市道路網(wǎng)，僅就選用時間作為阻抗,4 交通分配,4.3 基本概念 （4）交通阻抗 A.路段阻抗的函數(shù)關(guān)系確定 車輛在公路或城市道路路

5、段上所需走行時間是隨著該路段上交通流量的增加而增加，其走行時間交通流量的關(guān)系可表達為：,4 交通分配,4.3 基本概念 （4）交通阻抗 A.路段阻抗的函數(shù)關(guān)系確定 通過實測數(shù)據(jù)進行回歸分析或者理論研究兩種方式對于公路走行時間函數(shù)研究 其中被廣泛應用的是由美國道路局（BPR Bureau of Public Road）開發(fā)的函數(shù)，被稱為BPR函數(shù),4 交通分配,4.3 基本概念 （4）交通阻抗 A.路段阻抗的函數(shù)關(guān)系確定 時間-流量函數(shù)曲線變化特征猜想,4 交通分配,4.3 基本概念 （4）交通阻抗 A.路段阻抗的函數(shù)關(guān)系確定 BPR函數(shù)形式：,4 交通分配,4.3 基本概念 （4）交通阻抗 B

6、.節(jié)點阻抗問題 車輛在節(jié)點處也是要花費時間代價的，如機動車在城市道路信號燈交叉口等待綠燈 但問題是在于目前圖論等應用數(shù)學中沒有關(guān)于節(jié)點方位和路徑走向的數(shù)學描述，因而在求最短路徑的算法中就不能一般地表達不同流向車輛在交叉口的不同延誤 這個問題多年來一直未能得到很好的解決，已有的城市道路交通分配理論一直回避節(jié)點阻抗問題,4 交通分配,4.4 非均衡分配方法 （1）全有全無分配方法 “All or Nothing”，又稱“0-1分配法”、“最短路徑分配法”,4 交通分配,4.4 非均衡分配方法 （1）全有全無分配方法 方法假設(shè)和前提： A. 假定阻抗為常數(shù) B. 假定路段出行時間不受路段上流量的影響

7、 C. 假定出行者對這個交通網(wǎng)絡的結(jié)構(gòu)和各條路段的阻抗非常清楚 這是一種最簡單的分配方法，是討論其它分配方法的基礎(chǔ),4 交通分配,4.4 非均衡分配方法 （1）全有全無分配方法,4 交通分配,4.4 非均衡分配方法 （2）阻抗可變的單路徑分配方法 考慮道路交通量變化對阻抗的影響 流量越大，阻抗也越大 城市道路網(wǎng)中，路段上容量通行能力有限，路段上行駛的車輛越多，擁擠程度加大，車輛速度降低，從而行駛時間會增加,4 交通分配,4.4 非均衡分配方法 （2）阻抗可變的單路徑分配方法 方法：增量分配法 A. 將PA分布矩陣分成若干份（N份），各份比重由大到小，具體比重值可以人為任意確定 B. 從大份開始

8、，每次取一份進行全有全無分配，每次分配前根據(jù)前一次的分配結(jié)果用走行時間公式修正各路段的阻抗值,4 交通分配,4.4 非均衡分配方法 （2）阻抗可變的單路徑分配方法 方法：增量分配法算法,4 交通分配,4.4 非均衡分配方法 （2）阻抗可變的單路徑分配方法 方法：增量分配法算法,4 交通分配,4.4 非均衡分配方法 （3）阻抗為常數(shù)的多路徑分配方法 全有全無分配法：假定出行者明確交通網(wǎng)絡的結(jié)構(gòu)和各條路段的阻抗，在假定阻抗為常數(shù)的前提下，每對PA點之間的出行者都同時選擇該點對之間的最短路徑 實際中，由于交通網(wǎng)絡的復雜性和路段上交通狀況的多變性，以及各個出行者主觀判斷的多樣性，某PA點對之間不同出行

9、者所感知的最短路徑將是不同的、隨機的，出行者所選擇的“最短路徑”不一定是同一條，從而出現(xiàn)多路徑選擇的現(xiàn)象,4 交通分配,4.4 非均衡分配方法 （3）阻抗為常數(shù)的多路徑分配方法 分配方法有兩個： Logit方法和Probit方法 Logit方法 設(shè)某PA點對(r, s)之間每個出行者總是選擇他認為阻抗最小的路徑k，稱出行者主觀判斷的阻抗值為“感知阻抗”：,4 交通分配,4.4 非均衡分配方法 （3）阻抗為常數(shù)的多路徑分配方法 根據(jù)“效用”的定義，這里用路徑的感知阻抗的負值來表示選擇的效用,4 交通分配,4.4 非均衡分配方法 （3）阻抗為常數(shù)的多路徑分配方法 問題劃歸為一個多項選擇中挑選效用最

10、大的選擇枝的問題，回想交通方式選擇模型的推導過程 假定k是獨立服從相同Gumbel分布，選擇概率：,4 交通分配,4.4 非均衡分配方法 （3）阻抗為常數(shù)的多路徑分配方法 算法求解難題 運用模型求解路徑選擇概率，需要把點對(r, s)間所有的路徑都找出來，道路網(wǎng)絡節(jié)點越多越難 例如對一個含有100個節(jié)點的交通網(wǎng)絡來說，當r與s離的較遠的時，可能存在上千條路徑，直接設(shè)計算法可實施性較差,4 交通分配,4.4 非均衡分配方法 （3）阻抗為常數(shù)的多路徑分配方法 Dail算法 1971年Dail發(fā)明了一個算法，其特點包括： A. 假定出行者不是在起點r就決定選擇哪條路徑，而是在出行過程的每個節(jié)點都做一

11、次關(guān)于下步選擇哪條路段的選擇。即真正選擇的不是路徑，而是路段 B. 出行者在一個節(jié)點處選擇路段時，并不是以該節(jié)點為起點的每條路段都是被選擇的對象，只有那些所謂的“有效路段”才可能被選擇到,4 交通分配,4.4 非均衡分配方法 （3）阻抗為常數(shù)的多路徑分配方法 Dail算法 有效路段的定義是：當路段(i, j)的上游端點i比下游端點j離起點r近，而且i比j離終點s遠，則稱該路段為有效路段。有效路段組成的路徑叫“有效路徑”,4 交通分配,4.4 非均衡分配方法 （4）阻抗可變的多路徑分配方法 阻抗不變的多路徑分配方法，假設(shè)路段實際阻抗為一個常數(shù)，沒有考慮路段阻抗與流量的關(guān)系 阻抗可變的多路徑分配方

12、法，考慮路段上的流量對路段實際阻抗存在影響的情況下的多路徑分配方法，這將會使分配結(jié)果更加接近實際情況 特點分析：非均衡分配方法的算法比較簡單，容易理解，但這些方法缺乏理論依據(jù)，并且與實際交通網(wǎng)絡的分配存在一定的差距，需要在此基礎(chǔ)上探討更為準確的均衡分配算法,4 交通分配,4.5 交通均衡基礎(chǔ)問題 OD之間的路徑選擇行為特征：流量增加與路徑選擇的關(guān)系如何？ 如果兩點之間有很多條路線可供出行者選擇，那每個出行者自然都選擇最短路徑 隨著這兩點之間交通量的增大，其最短路徑上的交通流量也會隨之增加，增加至一定程度之后，這條最短路徑的走行時間就會因為擁擠或堵塞而變長，以至長過次短路徑的走行時間，于是就有一

13、部分道路利用者會選擇次短的道路 隨著兩點之間的交通量繼續(xù)增加，兩點之間的所有道路都有可能被利用（特大城市支路的利用）,4 交通分配,4.5 交通均衡基礎(chǔ)問題 道路網(wǎng)均衡狀態(tài)特征 如果所有的道路利用者都準確知道各條道路所需的行走時間，并選擇走行時間最短的道路，最終兩點之間被利用的各條道路的走行時間會相等，沒有被選擇的道路的走行時間會更長，這種狀態(tài)被稱之為道路網(wǎng)的均衡狀態(tài) 1952年Wardrop給這種均衡狀態(tài)下了準確定義,4 交通分配,4.5 交通均衡基礎(chǔ)問題 Wardrop第一原理 在道路網(wǎng)利用者都知道網(wǎng)絡的狀態(tài)并試圖選擇最短路徑時，網(wǎng)絡會達到這樣一種均衡狀態(tài)： 每對OD點之間各條被利用的路徑

14、的走行時間都相等而且是最小的走行時間，而沒有被利用的的路徑的走行時間都大于或等于這個最小的走行時間,4 交通分配,4.5 交通均衡基礎(chǔ)問題 Wardrop均衡模型求解方法問題 實際道路網(wǎng)中一般有很多對OD點，每對OD點之間的各條路徑都是由很多獨立的路段組成，由這些獨立的路段又可以組合成許多條不同的路徑 因此實際道路網(wǎng)的每對OD點都有很多條路徑。另外，各對OD點的路徑也互相重疊。因此，實際道路網(wǎng)的均衡狀態(tài)是非常復雜的 均衡分配原理在理論上結(jié)構(gòu)嚴謹，思路明確；但其數(shù)學規(guī)劃模型維數(shù)太大，約束條件多，且為非線性規(guī)劃問題,4 交通分配,4.6 B-L均衡分配法 （1）交通均衡分配理論發(fā)展概況 1952年

15、，Wardrop提出均衡分配原理 1956年，Beckmann提出了一種關(guān)于Wardrop原理的數(shù)學優(yōu)化模型，但之后近20年無人能解此模型 1975年，LeBlanc終于用一種解非線性數(shù)學規(guī)劃的算法，F(xiàn)rankWolfe算法，對該模型成功地進行了求解，實現(xiàn)了交通分配的計算技術(shù)從非均衡問題到均衡問題的一個飛躍，開創(chuàng)了關(guān)于均衡交通分配問題算法設(shè)計的新方向,4 交通分配,4.6 B-L均衡分配法 （1）交通均衡分配理論發(fā)展概況 后來分別由Aashtiani(1981)等人和Smith(1979)、Dafermos(1982)提出了描述Wardrop均衡原理的更廣義的數(shù)學模型，非線性互余（NCNonl

16、inear Complementarity）模型，和變分不等式（VIVariational Inequality）模型，模型適用范圍更廣 非線性互余問題（NCP）、變分不等式問題（VIP），在應用數(shù)學領(lǐng)域分別對這兩種模型進行了大量的研究，提出了多種算法，研究成果豐富,4 交通分配,4.6 B-L均衡分配法 （1）交通均衡分配理論發(fā)展概況 對于Beckmann提出的模型和LeBlanc的算法及其擴展問題，為區(qū)別于后來廣義的模型，和紀念他們兩人的重要學術(shù)貢獻，命名為：BeckmannLeBlanc均衡分配方法，簡記為B-L均衡分配方法；把Beckmann的模型所描述的問題叫做“均衡優(yōu)化問題（EOP

17、Equilibrium Optimization Problem）”,4 交通分配,4.6 B-L均衡分配法 （2）Beckmann均衡分配模型 相關(guān)模型參數(shù)和變量釋義：,4 交通分配,4.6 B-L均衡分配法 （2）Beckmann均衡分配模型 相關(guān)模型參數(shù)和變量釋義：,4 交通分配,4.6 B-L均衡分配法 （2）Beckmann均衡分配模型 相關(guān)模型參數(shù)和變量釋義： 路段流量與路徑流量的關(guān)系 路段阻抗與路徑阻抗的關(guān)系,4 交通分配,4.6 B-L均衡分配法 （2）Beckmann均衡分配模型 例題：如圖，網(wǎng)絡包含2個OD對，1-4和2-4，節(jié)點3是中間點；包含4個路段。假設(shè)OD對1-4中

18、，路徑1=Link1，Link3，路徑2=Link1，Link4；OD對2-4中，路徑1=Link2，Link3，路徑2=Link2，Link4。求 和 的表達式。,4 交通分配,4.6 B-L均衡分配法 （2）Beckmann均衡分配模型 Wardrop均衡原理的數(shù)學語言表達：,4 交通分配,4.6 B-L均衡分配法 （2）Beckmann均衡分配模型 Beckmann數(shù)學規(guī)劃模型,出行量守恒條件,流量非負條件,目標函數(shù)物理意義？,Beckmann模型等價于Wardrop均衡原理！,4 交通分配,4.6 B-L均衡分配法 （2）Beckmann均衡分配模型 Beckmann數(shù)學規(guī)劃模型 通過

19、簡單實例說明其模型的解，確實就是交通分配達到均衡狀態(tài)時的解，然后再從數(shù)學上證明該模型的解滿足Wardrop均衡原理,4 交通分配,4.6 B-L均衡分配法 （2）Beckmann均衡分配模型 Beckmann數(shù)學規(guī)劃模型 例題：如圖所示的一個只有兩條路徑（同時也是路段）連接一個產(chǎn)生點和一個吸引點的交通網(wǎng)絡，兩路段的阻抗函數(shù)分別是： PA量為q=5，兩條道路都會使用。分別求該網(wǎng)絡的Beckmann模型解和均衡狀態(tài)解，并進行對比。,4 交通分配,4.6 B-L均衡分配法 （2）Beckmann均衡分配模型 Beckmann數(shù)學規(guī)劃模型 例題：Beckmann模型求解，阻抗函數(shù)帶入模型,4 交通分配

20、,4.6 B-L均衡分配法 （2）Beckmann均衡分配模型 Beckmann數(shù)學規(guī)劃模型 例題：Beckmann模型求解，阻抗函數(shù)帶入模型,4 交通分配,4.6 B-L均衡分配法 （2）Beckmann均衡分配模型 Beckmann數(shù)學規(guī)劃模型 例題：均衡狀態(tài)求解。根據(jù)Wardrop均衡原理的定義，應該有： 綜上可見，對于該網(wǎng)絡， Beckmann數(shù)學模型解與均衡狀態(tài)解完全相同,4 交通分配,4.6 B-L均衡分配法 （3）Wordrop原理與Beckmann模型的等價性證明 運用路段流量和路徑流量的關(guān)系，將Beckmann模型的目標函數(shù)變換為f為自變量的函數(shù)ZX(f),4 交通分配,4.

21、6 B-L均衡分配法 （3）Wordrop原理與Beckmann模型的等價性證明 根據(jù)非線性規(guī)劃理論，由Beckmann模型約束條件構(gòu)造Lagrange函數(shù),4 交通分配,4.6 B-L均衡分配法 （3）Wordrop原理與Beckmann模型的等價性證明,4 交通分配,4.6 B-L均衡分配法 （3）Wordrop原理與Beckmann模型的等價性證明,4 交通分配,4.6 B-L均衡分配法 （3）Wordrop原理與Beckmann模型的等價性證明,4 交通分配,4.6 B-L均衡分配法 （3）Wordrop原理與Beckmann模型的等價性證明,4 交通分配,4.6 B-L均衡分配法 （

22、3）Wordrop原理與Beckmann模型的等價性證明,4 交通分配,4.6 B-L均衡分配法 （4）Beckmann模型解的唯一性 必要性： 在研究了Beckmann數(shù)學規(guī)劃模型的求解方法之前，有必要討論解的唯一性問題。如果解不是唯一的，則對同樣的已知條件，不同的算法可能得出不同的解，研究算法就沒有意義,4 交通分配,4.6 B-L均衡分配法 （4）Beckmann模型解的唯一性 由非線性規(guī)劃理論 1）對于規(guī)劃問題： 如果目標函數(shù)f(X)是凸函數(shù)，各個約束函數(shù)gj(X)都是凹函數(shù)，則該規(guī)劃為凸規(guī)劃 2）對于凸規(guī)劃，有以下結(jié)論：若目標函數(shù)f(X)是嚴格凸的，則其最優(yōu)解x*只有一個,4 交通分

23、配,4.6 B-L均衡分配法 （4）Beckmann模型解的唯一性 就 Beckmann模型的非線性規(guī)劃而言，約束條件都是線性的； 線性函數(shù)既是凸的，又是凹的，符合“各約束函數(shù)都是凹函數(shù)”的條件 剩下的問題就是考察其目標函數(shù)是否為凸，即考察 的Hessian矩陣的正定性,4 交通分配,4.6 B-L均衡分配法 （4）Beckmann模型解的唯一性 因為路段的阻抗只與自身的流量有關(guān)，與別的路段流量無關(guān)，則,4 交通分配,4.6 B-L均衡分配法 （4）Beckmann模型解的唯一性 目標函數(shù)Z(X)的Hessian矩陣為,4 交通分配,4.6 B-L均衡分配法 （4）Beckmann模型解的唯一

24、性 通過以上證明分析可以看出，當達到均衡狀態(tài)時，分配到各路段上的流量是唯一的。這就意味著當交通分配達到均衡狀態(tài)時，各個路段上的流量是被唯一確定的,4 交通分配,4.6 B-L均衡分配法 （4）Beckmann模型求解算法 1975年由Leblanc等學者將Frank-Wolfe 算法用于求解Bechmann模型，形成了目前廣泛使用的既嚴格又實用的F-W算法 Bechmann模型是一個非線性數(shù)學規(guī)劃模型，而對非線性數(shù)學規(guī)劃模型即使是現(xiàn)在仍沒有普遍通用的解法，但是Frank-Wolfe算法可以求解其中一類特殊的模型，而Bechmann模型正是這一類特殊的模型,4 交通分配,4.6 B-L均衡分配法

25、 （4）Beckmann模型求解算法 Frank-Wolfe算法思路 F-W法要求模型的約束條件必須都是線性的 該法是用線性規(guī)劃逐步迭代逼近非線性規(guī)劃的方法，在每步迭代中，先找到一個目標函數(shù)的最速下降方向，然后再找到一個最優(yōu)步長，在最速方向上截取最優(yōu)步長得到下一步迭代的起點，重復迭代直到找到最優(yōu)解,4 交通分配,4.6 B-L均衡分配法 （4）Beckmann模型求解算法 Frank-Wolfe算法思路 設(shè)非線性規(guī)劃模型： f(X)在X0處的一階泰勒展開，f(X)近似地表達成線性函數(shù)，近似化為線性規(guī)劃模型求解,4 交通分配,4.6 B-L均衡分配法 （4）Beckmann模型求解算法 Fran

26、k-Wolfe算法思路 解該線性規(guī)劃問題，得最優(yōu)解Y，F(xiàn)-W方法認為X0與Y的連線為最速下降方向，然后根據(jù)下列一維極值問題 求得的最優(yōu)解作為最佳步長，循環(huán)迭代,4 交通分配,4.6 B-L均衡分配法 （5）系統(tǒng)最優(yōu)的交通分配 Wardrop第一原理：均衡狀態(tài)為“用戶均衡狀態(tài)（User Equilibrium，UE）”，又稱“用戶最優(yōu)原理” Wardrop第二原理：系統(tǒng)最優(yōu)原理“（System Optimization，SO）”，即在交通網(wǎng)絡中的交通量應該按某種方式分配，以使網(wǎng)絡中所有交通的總阻抗最小,4 交通分配,4.6 B-L均衡分配法 （5）系統(tǒng)最優(yōu)的交通分配 第一原理反映了用戶對路徑的選擇的行為準則，任何系統(tǒng)中的有行為選擇能力的個體總是以自己利益最大化來決定自己的行為，該原理其實正是反映了交通網(wǎng)絡中的用戶的實際選擇出行路徑的情