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

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

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

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

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

6、本概念基本概念（4）交通阻抗B.節點阻抗問題車輛在節點處也是要花費時間代價的，如機動車在城市道路信號燈交叉口等待綠燈但問題是在于目前圖論等應用數學中沒有關于節點方位和路徑走向的數學描述，因而在求最短路徑的算法中就不能一般地表達不同流向車輛在交叉口的不同延誤這個問題多年來一直未能得到很好的解決，已有的城市道路交通分配理論一直回避節點阻抗問題4 交通分配4.4 非均衡分配方法非均衡分配方法（1）全有全無分配方法“All or Nothing”，又稱“0-1分配法”、“最短路徑分配法”小區1小區2路徑1：5min路徑2：10min4 交通分配4.4 非均衡分配方法非均衡分配方法（1）全有全無分配方法

7、方法假設和前提：方法假設和前提：A. 假定阻抗為常數B. 假定路段出行時間不受路段上流量的影響C. 假定出行者對這個交通網絡的結構和各條路段的阻抗非常清楚這是一種最簡單的分配方法，是討論其它分配方法的基礎4 交通分配4.4 非均衡分配方法非均衡分配方法（1）全有全無分配方法951234567834586471035274 交通分配4.4 非均衡分配方法非均衡分配方法（2）阻抗可變的單路徑分配方法考慮道路交通量變化對阻抗的影響流量越大，阻抗也越大城市道路網中，路段上容量通行能力有限，路段上行駛的車輛越多，擁擠程度加大，車輛速度降低，從而行駛時間會增加4 交通分配4.4 非均衡分配方法非均衡分配方

8、法（2）阻抗可變的單路徑分配方法方法：增量分配法方法：增量分配法A. 將PA分布矩陣分成若干份（N份），各份比重由大到小，具體比重值可以人為任意確定B. 從大份開始，每次取一份進行全有全無分配，每次分配前根據前一次的分配結果用走行時間公式修正各路段的阻抗值4 交通分配4.4 非均衡分配方法非均衡分配方法（2）阻抗可變的單路徑分配方法方法：增量分配法方法：增量分配法算法算法4 交通分配4.4 非均衡分配方法非均衡分配方法（2）阻抗可變的單路徑分配方法方法：增量分配法方法：增量分配法算法算法4 交通分配4.4 非均衡分配方法非均衡分配方法（3）阻抗為常數的多路徑分配方法全有全無分配法：假定出行者明

9、確交通網絡的結構和各條路段的阻抗，在假定阻抗為常數的前提下，每對PA點之間的出行者都同時選擇該點對之間的最短路徑實際中，由于交通網絡的復雜性和路段上交通狀況的多變性，以及各個出行者主觀判斷主觀判斷的多樣性，某PA點對之間不同出行者所感知的最短路徑感知的最短路徑將是不同的、隨機的，出行者所選擇的“最短路徑”不一定是同一條，從而出現多路徑選擇的現象4 交通分配4.4 非均衡分配方法非均衡分配方法（3）阻抗為常數的多路徑分配方法分配方法有兩個： Logit方法和Probit方法Logit方法方法設某PA點對(r, s)之間每個出行者總是選擇他認為阻抗最小的路徑k，稱出行者主觀判斷的阻抗值為“感知阻抗

10、”：4 交通分配4.4 非均衡分配方法非均衡分配方法（3）阻抗為常數的多路徑分配方法根據“效用”的定義，這里用路徑的感知阻抗的負值來表示選擇的效用4 交通分配4.4 非均衡分配方法非均衡分配方法（3）阻抗為常數的多路徑分配方法問題劃歸為一個多項選擇中挑選效用最大效用最大的選擇枝的問題，回想交通方式選擇模型的推導過程假定k是獨立服從相同Gumbel分布，選擇概率：4 交通分配4.4 非均衡分配方法非均衡分配方法（3）阻抗為常數的多路徑分配方法算法求解難題算法求解難題運用模型求解路徑選擇概率，需要把點對(r, s)間所有的路徑都找出來，道路網絡節點越多越難例如對一個含有100個節點的交通網絡來說，

11、當r與s離的較遠的時，可能存在上千條路徑，直接設計算法可實施性較差4 交通分配4.4 非均衡分配方法非均衡分配方法（3）阻抗為常數的多路徑分配方法Dail算法算法1971年Dail發明了一個算法，其特點包括：A. 假定出行者不是在起點r就決定選擇哪條路徑，而是在出行過程的每個節點都做一次關于下步選擇哪條路段的選擇。即真正選擇的不是路徑，而是路段路段B. 出行者在一個節點處選擇路段時，并不是以該節點為起點的每條路段都是被選擇的對象，只有那些所謂的“有效路段有效路段”才可能被選擇到4 交通分配4.4 非均衡分配方法非均衡分配方法（3）阻抗為常數的多路徑分配方法Dail算法算法有效路段的定義是：當路

12、段(i, j)的上游端點i比下游端點j離起點r近，而且i比j離終點s遠，則稱該路段為有效路段。有效路段組成的路徑叫“有效路徑”4 交通分配4.4 非均衡分配方法非均衡分配方法（4）阻抗可變的多路徑分配方法阻抗不變的多路徑分配方法，假設路段實際阻抗為一個常數，沒有考慮路段阻抗與流量的關系阻抗可變的多路徑分配方法，考慮路段上的流量對路段實際阻抗存在影響的情況下的多路徑分配方法，這將會使分配結果更加接近實際情況特點分析特點分析：非均衡分配方法的算法比較簡單，容易理解，但這些方法缺乏理論依據，并且與實際交通網絡的分配存在一定的差距，需要在此基礎上探討更為準確的均衡分配算法4 交通分配4.5 交通均衡基

13、礎問題交通均衡基礎問題OD之間的路徑選擇行為特征：流量增加與路徑選之間的路徑選擇行為特征：流量增加與路徑選擇的關系如何？擇的關系如何？如果兩點之間有很多條路線可供出行者選擇，那每個出行者自然都選擇最短路徑隨著這兩點之間交通量的增大，其最短路徑上的交通流量也會隨之增加，增加至一定程度之后，這條最短路徑的走行時間就會因為擁擠或堵塞而變長，以至長過次短路徑的走行時間，于是就有一部分道路利用者會選擇次短的道路隨著兩點之間的交通量繼續增加，兩點之間的所有道路都有可能被利用（特大城市支路的利用）4 交通分配4.5 交通均衡基礎問題交通均衡基礎問題道路網均衡狀態特征道路網均衡狀態特征如果所有的道路利用者都準

14、確知道各條道路所需的行走時間，并選擇走行時間最短的道路，最終兩點之間被利用的各條道路的走行時間會相等，兩點之間被利用的各條道路的走行時間會相等，沒有被選擇的道路的走行時間會更長沒有被選擇的道路的走行時間會更長，這種狀態被稱之為道路網的均衡狀態1952年Wardrop給這種均衡狀態下了準確定義4 交通分配4.5 交通均衡基礎問題交通均衡基礎問題Wardrop第一原理第一原理在道路網利用者都知道網絡的狀態并試圖選擇最短路徑時，網絡會達到這樣一種均衡狀態：每對OD點之間各條被利用的路徑的走行時間都相等而且是最小的走行時間，而沒有被利用的的路徑的走行時間都大于或等于這個最小的走行時間4 交通分配4.5

15、 交通均衡基礎問題交通均衡基礎問題Wardrop均衡模型求解方法問題均衡模型求解方法問題實際道路網中一般有很多對OD點，每對OD點之間的各條路徑都是由很多獨立的路段組成，由這些獨立的路段又可以組合成許多條不同的路徑因此實際道路網的每對OD點都有很多條路徑。另外，各對OD點的路徑也互相重疊。因此，實際道路網的均衡狀態是非常復雜的均衡分配原理在理論上結構嚴謹，思路明確；但其數學規劃模型維數太大，約束條件多，且為非線性規劃問題4 交通分配4.6 B-L均衡分配法均衡分配法（1）交通均衡分配理論發展概況1952年，Wardrop提出均衡分配原理原理1956年，Beckmann提出了一種關于Wardro

16、p原理的數學優化模型模型，但之后近20年無人能解此模型1975年，LeBlanc終于用一種解非線性數學規劃的算法，FrankWolfe算法算法，對該模型成功地進行了求解，實現了交通分配的計算技術從非均衡問題到均衡問題的一個飛躍，開創了關于均衡交通分配問題算法設計的新方向4 交通分配4.6 B-L均衡分配法均衡分配法（1）交通均衡分配理論發展概況后來分別由Aashtiani(1981)等人和Smith(1979)、Dafermos(1982)提出了描述Wardrop均衡原理的更廣義的數學模型，非線性互余（NCNonlinear Complementarity）模型，和變分不等式（VIVariat

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

18、4.6 B-L均衡分配法均衡分配法（2）Beckmann均衡分配模型相關模型參數和變量釋義：4 交通分配4.6 B-L均衡分配法均衡分配法（2）Beckmann均衡分配模型相關模型參數和變量釋義：4 交通分配4.6 B-L均衡分配法均衡分配法（2）Beckmann均衡分配模型相關模型參數和變量釋義：路段流量與路徑流量的關系路段阻抗與路徑阻抗的關系4 交通分配4.6 B-L均衡分配法均衡分配法（2）Beckmann均衡分配模型例題例題：如圖，網絡包含2個OD對，1-4和2-4，節點3是中間點；包含4個路段。假設OD對1-4中，路徑1=Link1，Link3，路徑2=Link1，Link4；OD對

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

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

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

22、(f)4 交通分配4.6 B-L均衡分配法均衡分配法（3）Wordrop原理與Beckmann模型的等價性證明根據非線性規劃理論，由Beckmann模型約束條件構造Lagrange函數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模型的等價性證明

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

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

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

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

27、為線性規劃模型求解4 交通分配4.6 B-L均衡分配法均衡分配法（4）Beckmann模型求解算法 Frank-Wolfe算法思路算法思路解該線性規劃問題，得最優解Y，F-W方法認為X0 0與Y的連線為最速下降方向，然后根據下列一維極值問題求得的最優解作為最佳步長，循環迭代4 交通分配4.6 B-L均衡分配法均衡分配法（5）系統最優的交通分配Wardrop第一原理：均衡狀態為“用戶均衡狀態（User Equilibrium，UE）”，又稱“用戶最優原理”Wardrop第二原理：系統最優原理“（System Optimization，SO）”，即在交通網絡中的交通量應該按某種方式分配，以使網絡中所有交通的總阻抗最小4 交通分配4.6 B-L均衡分配法均衡分配法（5）系統最優的交通分配第一原理第一原理反映了用戶對路徑的選擇的行為準則，任何系統中的有行為選擇能力的個體總是以自己利益最大化利益最大化來決定自己的行為，該原理其實正是反映了交通網絡中的用戶的實際選擇實際選擇出行路徑的情形，按Beckmann模型和上述F-W算法計算出來的結果