交通網(wǎng)絡(luò)平衡配流模型算法研究★

楊 海 飛

(河海大學(xué)土木與交通學(xué)院，江蘇 南京 210098)

1 交通配流基本原理與常用模型

1.1 交通配流問題的基本原理

交通網(wǎng)絡(luò)分配問題是將實測或預(yù)測的交通分布量按照特定的出行規(guī)則分配加載至具體的道路網(wǎng)中，并根據(jù)相應(yīng)算法求解得到各道路路段與交叉口節(jié)點的交通流量。交通分布量，即OD交通量，是出行起訖點小區(qū)重心之間的交通量，即從出發(fā)起點至出發(fā)目的地之間的交通流量。通常情況下，對于特定城市或區(qū)域，任意出行端點之間具有多條出行路徑，因而，通過科學(xué)的原則和高效的算法將OD交通量合理的分配在出行起訖點之間的各條路徑上(包括路段與節(jié)點)是交通配流需要解決的核心問題。

1952年，Wardrop首次提出了道路網(wǎng)平衡的概念和定義[1]，即Wardrop第一原理和Wardrop第二原理。

Wardrop第一原理亦稱為用戶平衡原理(簡稱UE)，其定義是指：在道路網(wǎng)上行駛的車輛駕駛員都明確清楚當前道路網(wǎng)絡(luò)的交通運行狀態(tài)，并在選擇最短出行路徑過程中使得道路網(wǎng)絡(luò)達到平衡狀態(tài)。所謂平衡狀態(tài)是指路網(wǎng)中每個OD對之間所有被使用的通行路徑具有最短的出行時間或最小的出行阻抗，而沒有被使用的路徑通行時間一定不小于被使用路徑的最小出行時間。滿足以上原理的交通配流模型即稱為用戶平衡模型(UE模型)。

Wardrop第二原理亦稱為系統(tǒng)最優(yōu)原理(簡稱SO)，其定義是指：考慮交通擁堵水平對出行阻抗的影響，道路網(wǎng)絡(luò)中的交通流量應(yīng)當以特定規(guī)律加載分配，從而使得網(wǎng)絡(luò)整體的總出行時間達到最小。系統(tǒng)最優(yōu)化模型為交通規(guī)劃管理人員提供了一種決策方法。

進行交通配流的前提條件是已知OD交通量、網(wǎng)絡(luò)圖和網(wǎng)絡(luò)中各路段的走行時間函數(shù)。而走行時間—交通流量函數(shù)可表達為：

ta=f(qa)

(1)

其中，ta為路段a的走行時間;qa為路段a的交通流量。被廣泛應(yīng)用的走行時間函數(shù)的是由美國公路局開發(fā)的BPR函數(shù)，其形式為：

(2)

1.2 交通網(wǎng)絡(luò)配流模型

1.2.1非平衡配流模型

非平衡配流模型結(jié)構(gòu)形式簡單、參數(shù)標定明確、求解算法快速，在滿足精度要求的情況下，是交通規(guī)劃與交通管理等工程實踐的重要配流方法。

1)“全有全無”配流法?！叭腥珶o”法[2]是最簡單最基本的配流方法。該方法具有以下兩個特點：首先在配流過程中不考慮交通擁堵情況對道路出行阻抗的影響，即認為路網(wǎng)范圍內(nèi)所有路段的出行阻抗為常數(shù)，不會隨著道路交通量的變化而變化；其次是認為駕駛員對道路路徑的選擇具有同質(zhì)性，即同一OD對之間所有駕駛員都將選擇相同的路徑行駛。該配流模型的求解過程相當簡便快速，計算效率高，然而所面臨的主要問題是交通量在路網(wǎng)上的分配極度不均，全部集中在初始最短路，造成不同路段間的交通量差異懸殊，與實際的道路交通狀況顯著不符。通常城市交通網(wǎng)絡(luò)的配流問題不宜直接采用“全有全無”法，但該方法可作為多種復(fù)雜配流模型的基礎(chǔ)算法。

2)增量配流法。增量配流法[3]是一種模擬平衡的配流方法。該方法的基本思想是將OD交通量按照特定的比例循環(huán)分批加載至路網(wǎng)當中(加載運用“全有全無”算法)，并且每次加載循環(huán)結(jié)束后，根據(jù)當前各路段的交通量情況重新計算路網(wǎng)的出行阻抗或出行時間，在接下來的循環(huán)中將下一批交通量加載至當前最短路徑上。增量配流算法的計算過程簡單，計算精度可根據(jù)OD量的加載循環(huán)數(shù)進行控制，因此在工程實踐中得以廣泛應(yīng)用。該方法仍然是一種近似方法，一般情況下，得不到平衡解。

3)連續(xù)平均法。連續(xù)平均法[4]是在增量配流法基礎(chǔ)上對平衡配流原理的進一步模擬，其基本思路是反復(fù)優(yōu)化已加載至路網(wǎng)上的交通量，使之在迭代過程中逐漸接近或達到平衡交通量。在每一階段的循環(huán)過程中，根據(jù)增量分配法已加載的各路段交通流量，應(yīng)用“全有全無”算法額外進行一次配流得到附加交通量，隨后將上次循環(huán)得到的配流交通量與附加交通量進行加權(quán)平均處理，從而得到本次循環(huán)的加載交通量。算法結(jié)束的依據(jù)是相鄰循環(huán)的分配結(jié)果誤差應(yīng)小于一定閾值。連續(xù)平均法是簡單實用卻又最接近于平衡配流法的配流方法。

1.2.2交通網(wǎng)絡(luò)平衡分析模型

平衡配流模型通常被分為用戶平衡模型(UE)，隨機用戶平衡模型(SEU)以及動態(tài)用戶平衡模型(DUE)三類。本文重點研究用戶平衡模型(UE)。

用戶平衡模型(UE)中，OD矩陣在整個交通量加載過程下保持恒定。通常情況下，UE問題的求解需要抽象出一個高維凸優(yōu)化模型，可運用遺傳算法等現(xiàn)代化智能化算法求解。Bechman提出了經(jīng)典的固定需求式用戶平衡模型，其數(shù)學(xué)表達式如下：

(3)

平衡交通流配流模型具有明確的理論意義，模型結(jié)構(gòu)嚴謹，參數(shù)含義明確，比較適用于理論和宏觀層面的研究。然而，這類模型通常具有較多的優(yōu)化變量，導(dǎo)致數(shù)學(xué)模型維數(shù)高，約束條件苛刻，求解算法十分復(fù)雜，運算效率較低，盡管當前學(xué)者提出了一系列智能算法，但計算理念和過程較為復(fù)雜，在工程實踐應(yīng)用中具有一定難度。

2 改進的平衡配流算法

Beckman提出了關(guān)于交通配流的數(shù)學(xué)規(guī)劃模型，但在整整20年后LeBlanc 等學(xué)者才開始用Frank-Wolfe算法求解Beckman模型，形成了目前廣泛應(yīng)用的F-W法。F-W法是用線性規(guī)劃逐步逼近非線性規(guī)劃的方法來求解平衡模型的。其主要算法步驟如下所示：

Step3：計算迭代步長，按照下式求參數(shù)αn。

(4)

從上面的算法步驟可以看出，F(xiàn)-W法是一種迭代算法。影響迭代算法的解最后能否收斂到平衡解的因素很多，其中，初始解的選取很大程度上決定了F-W算法最后能否收斂到平衡解以及收斂速度的快慢，初始解越接近平衡解計算就越容易收斂，迭代步驟也就越少。本文就從計算初始解的方法上來改進平衡配流算法。

由以上步驟，傳統(tǒng)的F-W算法是通過應(yīng)用“全有全無”配流的方法來獲得初始各路段的交通量的，然后進行迭代計算?！叭腥珶o”配流法是一種十分粗糙的算法，最后配流的交通量與實際的路網(wǎng)交通流狀態(tài)相差甚遠，自然用這種方法求得的初始解與平衡解也就相差很多。

本文研究提出的改進平衡配流法中的初始解擬采用連續(xù)平均法來代替“全有全無”最短路配流。

連續(xù)平均法是非平衡算法中最接近于平衡算法的一種方法，可以很快的接近平衡解，所以可以用來代替“全有全無”配流法來求解平衡解的初始解。連續(xù)平均算法的計算步驟如下：

Step2：按照上一步Step1計算的各路段出行阻抗和OD量，并進行一次“全有全無”分配，得到各路段的附加交通量Fa。

(5)

連續(xù)平均法和F-W法相比，核心區(qū)別在于如何確定移動步長αn/φ(相關(guān)平衡分配模型是以嚴謹?shù)臄?shù)學(xué)原理為基礎(chǔ)的，因此可以求出平衡解；而連續(xù)平均法是由計算者自己定，可以取常數(shù)，也可以定為變數(shù)。定為常數(shù)時，一般取0.5，定為變數(shù)時一般取1/n(n為循環(huán)次數(shù))。由于連續(xù)平均法只是用來求初始解，為了減少計算時間，故可以將其收斂準則適當放寬，通過預(yù)先規(guī)定迭代循環(huán)次數(shù)的方法來命令求解過程停止。

改進的平衡配流算法計算步驟：

Step3：計算迭代步長，按照下式求參數(shù)αn。

3 實例計算與結(jié)論

根據(jù)張家港市交通規(guī)劃資料，應(yīng)用改進平衡配流算法對早高峰交通量進行分配。結(jié)果分析：經(jīng)過計算，應(yīng)用改進平衡配流算法對路網(wǎng)進行配流所需時間為傳統(tǒng)方向搜索算法的(即F-W算法)60%左右，迭代次數(shù)是7次，而改進平衡配流算法的配流結(jié)果與傳統(tǒng)算法的配流結(jié)果相差無幾，交通量相差在5%以內(nèi)的路段占到路段總數(shù)比例的91.5%，超過10%的僅占1.9%。經(jīng)過上述的評測分析，本文把交通非平衡配流方法運用到交通平衡配流中的改進平衡配流法，迭代次數(shù)減少，在一定程度上減少了運算時間，提高了計算精度，進一步優(yōu)化了求解平衡配流問題的傳統(tǒng)算法。

本文在總結(jié)傳統(tǒng)平衡與非平衡分配算法原理的基礎(chǔ)上，提出將非平衡算法與平衡算法進行結(jié)合，以提高算法的運行效率。結(jié)合實例發(fā)現(xiàn)，本文提出的改進平衡分配算法能夠顯著提升交通分配計算速度，為相關(guān)交通規(guī)劃的實踐應(yīng)用提供了一種高效的交通需求預(yù)測方法。