10 交通運輸規(guī)劃原理：第八章 交通分配預測(中)

1

交通運輸規(guī)劃原理

西南交通大學本科生課程

主講教師：楊達博士

開課單位：交通運輸與物流學院

第九講交通分配預測（中）第1節(jié)交通流分配理論的產(chǎn)生和發(fā)展第2節(jié)基本概念第3節(jié)非均衡分配方法第4節(jié)均衡分配方法第5節(jié)交通流分配模型中的問題

最短路徑算法

最短路徑算法是交通流分配中最基本也最重要的算法，幾乎所有交通流分配方法都是以它作為一個基本子過程反復調(diào)用。最短路徑算法的設(shè)計問題是圖論、運籌學和交通規(guī)劃領(lǐng)域的學者們廣為關(guān)注的問題，因此已經(jīng)設(shè)計出了多種方法。

最短路算法問題包含兩個子問題：兩點間最小阻抗的計算和兩點間最小阻抗路徑的辨識，前者是解決后者的前提。許多算法都是將這兩個子問題分開考慮，設(shè)計出來的算法是分別單獨求出最小阻抗和最短路徑。

在各類文獻中，有關(guān)交通流分配最短路徑的算法很多，如標號法、矩陣迭代法、Floyd-Warshall法等。

最短路徑算法-Dijkstra法

最短路徑算法-Dijkstra法

最短路徑算法-Dijkstra法

最短路徑算法-Dijkstra法

最短路徑算法-Dijkstra法

最短路徑算法-Dijkstra法

最短路徑算法-Dijkstra法

最短路徑算法-Dijkstra法

最短路徑算法-Dijkstra法

最短路徑算法-Dijkstra法v1v2v3v4v5v6v7v8v9v10v112817615129341369272149

最短路徑算法-Dijkstra法v1v2v3v4v5v6v7v8v9v10v1128176151293413692721490281∞∞∞∞∞∞∞

最短路徑算法-Dijkstra法v1v2v3v4v5v6v7v8v9v10v112817615129341369272149028∞∞10∞∞∞∞1,v1

最短路徑算法-Dijkstra法v1v2v3v4v5v6v7v8v9v10v112817615129341369272149083∞10∞∞∞∞2,v1

最短路徑算法-Dijkstra法1,v1v1v2v3v4v5v6v7v8v9v10v11281761512934136927214908610125∞∞3,v2

最短路徑算法-Dijkstra法1,v12,v1v1v2v3v4v5v6v7v8v9v10v112817615129341369272149086101214∞

最短路徑算法-Dijkstra法1,v12,v13,v25,v5v1v2v3v4v5v6v7v8v9v10v11281761512934136927214907101214∞

最短路徑算法-Dijkstra法1,v12,v13,v25,v56,v5v1v2v3v4v5v6v7v8v9v10v112817615129341369272149091214∞

最短路徑算法-Dijkstra法1,v12,v13,v25,v56,v57,v6v1v2v3v4v5v6v7v8v9v10v1128176151293413692721490121410

最短路徑算法-Dijkstra法1,v12,v13,v25,v56,v57,v69,v3v1v2v3v4v5v6v7v8v9v10v11281761512934136927214901114

最短路徑算法-Dijkstra法1,v12,v13,v25,v56,v57,v69,v310,v7v1v2v3v4v5v6v7v8v9v10v112817615129341369272149013

最短路徑算法-Dijkstra法1,v12,v13,v25,v56,v57,v69,v310,v711,v10v1v2v3v4v5v6v7v8v9v10v1128176151293413692721490

最短路徑算法-Dijkstra法1,v12,v13,v25,v56,v57,v69,v310,v711,v1013,v9最短路徑辨識

通過Dijkstra算法或矩陣迭代法得到最短路權(quán)矩陣后，還需要把每一個節(jié)點對之間具體的最短路徑尋找出來，將交通流分配上去，進而進行網(wǎng)絡的規(guī)劃。

最短路徑辨識采用追蹤法：從每條最短路徑的起點開始，根據(jù)起點到各節(jié)點的最短路權(quán)搜索最短路徑上的各個交通節(jié)點，直至路徑終點。

算法思想：第3節(jié)非均衡分配法概述：目前已提出的非均衡分配模型及其解法，其模型都不用數(shù)學表達式描述。根據(jù)分配手法可分為路段阻抗可變和阻抗不變兩大類，就路徑選擇可分為單路徑和多路徑兩類。綜合起來可以分為四類，如下表所示：分類固定路阻變化路阻單路徑最短路徑（全有全無法）分配容量限制分配多路徑靜態(tài)多路徑分配容量限制多路徑分配1、全有全無法1.1簡介（All—or—NothingAssignmentMethod，簡稱0—1分配法）是最簡單的分配方法，該方法不考慮路網(wǎng)的擁擠程度，取路阻為常數(shù)，即假設(shè)車輛的路段行駛速度、交叉口延誤不受路段、交叉口交通負荷的影響。每一個OD對的交通量全部分配到它們之間的最短路徑上，其它路徑分配不到交通量。全有全無法是最簡單、最基本的路徑選擇和分配方法，是其它分配方法的基礎(chǔ)。第3節(jié)非均衡分配法1、全有全無法1.2假設(shè)和前提假定阻抗為常數(shù)；假定路段出行時間不受流量的影響；假定出行者對交通網(wǎng)絡的結(jié)構(gòu)和各條路段的阻抗非常清楚。第3節(jié)非均衡分配法1、全有全無法1.3計算步驟（1）初始化，使路網(wǎng)中所有路段的流量為0，并求出各路段自由流狀態(tài)時的阻抗；（2）確定各OD對點之間的最短路徑；（3）將OD點之間的交通量全部分配到相應的最短路徑上。第3節(jié)非均衡分配法第3節(jié)非均衡分配法第3節(jié)非均衡分配法1、全有全無法1.4適用性討論由于全有全無法不能反映擁擠程度，主要是用于某些非擁擠道路網(wǎng)，適用于沒有通行能力限制的網(wǎng)絡。因此，其使用范圍可以是城際之間道路通行能力不受限制的地區(qū)，而一般城市道路網(wǎng)不宜采用此方法。第3節(jié)非均衡分配法2、容量限制分配方法

增量分配法（IncrementalAssignmentMethod，簡稱IA分配法）是一種近似的平衡分配方法。該方法是在全有全無分配方法的基礎(chǔ)上，考慮了路段交通流量對阻抗的影響，進而根據(jù)道路阻抗的變化來調(diào)整路網(wǎng)交通量的分配，是一種“變化路阻”的交通量分配方法。

增量分配法有容量限制—增量分配、容量限制—迭代平衡分配兩種形式。

第3節(jié)非均衡分配法2、容量限制分配方法2.1增量分配法增量分配法是一種近似的平衡分配方法，在全有全無法基礎(chǔ)上考慮了流量對阻抗的影響。

其思路是：首先將OD分布矩陣分成若干份（N份），各份比重由大到小，具體比重值可以人為任意確定；然后從大份開始，每次進行一次全有全無分配，每次分配前根據(jù)前一次的分配結(jié)果用阻抗公式更新各路段的阻抗值，直到OD交通量全部分配完。第3節(jié)非均衡分配法2、容量限制分配方法2.1增量分配法計算步驟：第3節(jié)非均衡分配法第3節(jié)非均衡分配法第3節(jié)非均衡分配法2、容量限制分配方法2.1增量分配法優(yōu)缺點：

該方法的優(yōu)點是：簡單可行，精確度可以根據(jù)分割數(shù)N的大小來調(diào)整；實踐中經(jīng)常被采用，且有比較成熟的商業(yè)軟件可供使用。缺點是：與平衡分配法相比，仍然是一種近似方法；當路阻函數(shù)不是很敏感時，會將過多的交通量分配到某些容量通行能力很小的路段上。第3節(jié)非均衡分配法2、容量限制分配方法2.2迭代平衡法該方法不需要將OD表分解，先假設(shè)路網(wǎng)中各路段上的流量為零，按零流量計算初始路阻，并分配這個OD表，然后按分配流量計算路阻，重新分配整個OD表，最后比較新分配的路段流量與原來分配的路段流量、新計算的路阻與原來計算的路阻，若分別比較接近，滿足迭代精度要求，則停止迭代，獲得最后的分配的交通量。否則，根據(jù)新計算的路權(quán)，再次分配，直到滿足精度為止。美國聯(lián)邦公路局改進了算法，設(shè)定了最大的迭代次數(shù)，平衡解取最后四次迭代的路段流量的平均值，而且當前迭代的阻抗值為前兩次阻抗值的加權(quán)值。（0.75，0.25）第3節(jié)非均衡分配法3、迭代加權(quán)法（MethodofSuccessiveAverages，MSA法）

其思路是：每次都將全部OD分布量按照全有全無法分配到路網(wǎng)上去，得到的各路段上的分配量，叫做“附加量”。這一次分配得到的附加量與原路段上的交通量的加權(quán)平均值作為新的路段交通量，再由這個量計算出各路段的阻抗值，最為下一次分配的依據(jù)。當前后兩次分配的結(jié)果近似相等時，停止迭代。由算法步驟可看出，全有全無法在迭代加權(quán)分配方法中也反復調(diào)用。第3節(jié)非均衡分配法3、迭代加權(quán)法第3節(jié)非均衡分配法3、迭代加權(quán)法第3節(jié)非均衡分配法

增量分配和迭代加權(quán)法分配形式的原理基本是相同的，分配過程中最主要的是確定路阻和計算最短路阻矩陣。理論上講，若迭代精度控制得合理，迭代加權(quán)法分配的結(jié)果優(yōu)于增量分配的結(jié)果。但迭代加權(quán)法事先無法估計迭代次數(shù)及計算工作量，對于較復雜的網(wǎng)絡，可能會因為個別路段的迭代精度無法滿足要求而使迭代進入死循環(huán)，出現(xiàn)算法不收斂的情況。

在實際使用中，停止計算的判斷即可用誤差大小，也可以用循環(huán)次數(shù)的多少來進行運算的控制；用的比較多的是循環(huán)次數(shù)?！纠?】第3節(jié)非均衡分配法設(shè)下圖所示交通網(wǎng)絡的OD交通量為t=200輛，各路徑的交通費用函數(shù)如下，試用全有全無分配法、增量分配法法求出分配結(jié)果，并進行比較。

【例3】第3節(jié)非均衡分配法1.全有全無分配法

由路段費用函數(shù)可知，在路段交通量為零時，路徑1最短。根據(jù)全有全無原則，交通量全部分配到路徑1上，得到以下結(jié)果：

因為，根據(jù)Wardrop原理，網(wǎng)絡沒有達到平衡狀態(tài)，沒有得到均衡解。

此時路網(wǎng)總費用為：

Z=200*25=5000【例3】第3節(jié)非均衡分配法2.增量分配法

采用2等分。

(1)第1次分配

與全有全無分配法相同，路徑1最短。

(2)第2次分配，此時最短路徑變?yōu)槁窂?這時，根據(jù)Wardrop原理，各條路徑的費用接近相等，路網(wǎng)接近平衡狀態(tài)，結(jié)果接近于平衡解。此時路網(wǎng)總費用為：

Z=100*15+100*12.5=27504、阻抗為常數(shù)的多路徑分配方法

概述：由于交通網(wǎng)絡的復雜性和路段交通狀況的多變性，以及各出行者主觀判斷的多樣性，某OD點對之間不同出行者所感知的“最短路徑”將是不同的、隨機的，因此不一定是同一條，從而出現(xiàn)多路徑選擇的現(xiàn)象。對于這種情況的交通分配叫做“多路徑分配”，或“隨機加載”。阻抗為常數(shù)的多路徑分配方法主要有兩個：Logit方法和Probit方法。第3節(jié)非均衡分配法4、阻抗為常數(shù)的多路徑分配方法4.1Logit方法設(shè)點對OD（r，s）之間每個出行者總是選擇他認為阻抗最小的路徑k（稱出行者主觀判斷的阻抗值為“感知阻抗”）：第3節(jié)非均衡分配法4、阻抗為常數(shù)的多路徑分配方法4.1Logit方法根據(jù)前面方式劃分介紹的“效用”的定義，可以用路徑感知阻抗的負值表示選擇的效用：——路徑k（作為選擇路徑）的效用；——路徑k的感知阻抗；——路徑k的實際阻抗；——隨機變量。

第3節(jié)非均衡分配法4、阻抗為常數(shù)的多路徑分配方法4.1Logit方法如此，這就是一個多項選擇中挑選效用最大的選擇枝的問題了。當假定?k是獨立服從相同的Gumbel分布（此時可以用一個?表示所有的?k）時，選擇概率為：式中：b——參數(shù)，與?的方差有關(guān)。第3節(jié)非均衡分配