模擬退火算法求解的道路網(wǎng)絡(luò)分配方法

許修權(quán)，廉 冠，張曼婷

（桂林電子科技大學(xué)建筑與交通工程學(xué)院，廣西 桂林 541004）

0 引言

在交通規(guī)劃四階段的交通分配階段，要對交通流量進(jìn)行分配，就要考慮到某條路徑的時間阻抗。對于路段行駛時間的修正，可以根據(jù)行駛時間和路段交通量之間的關(guān)系，即路阻函數(shù)確定。最為常見的路阻函數(shù)是美國聯(lián)邦公路局函數(shù)（BPR函數(shù)）其具體公式如下：

式中：t（q）為流量為q時路段的行程時間；t0為路段的自由行程時間；c為路段的實際通行能力；α，β為回歸系數(shù)，α建議取值=0.15，β建議取值=4。

BPR路阻函數(shù)是本文函數(shù)關(guān)系構(gòu)造的基礎(chǔ)，通過BPR函數(shù)得到每條道路行駛時間和路段交通負(fù)荷之間的函數(shù)關(guān)系。

1 系統(tǒng)平均行程時間函數(shù)的構(gòu)造

假設(shè)A和B之間有n條道路分別記作Link1、Link2、Link3…Linkn，每條道路的實際通行能力為C1、C2、C3…Cn，道路的自由通行時間為t1、t2、t3…tn，A和B之間的交通總量為C。將每條道路分配的交通量的百分比分別記作x1、x2、x3…xn-1、，則

每條道路的路阻函數(shù)為：

系統(tǒng)平均行程時間為：

通過分析得，系統(tǒng)的平均行程實際是一個n-1元的多元函數(shù)，只要求得該函數(shù)取得最小值時的自變量，就能得到道路網(wǎng)絡(luò)的最優(yōu)分配。

結(jié)合實際意義，對函數(shù)的解的可行域進(jìn)行分析：

（1）x1、x2、x3…xn-1均應(yīng)該∈[0，1]；取0時，此道路不分配任何交通量，取1時，所有交通量分配于此道路。

（3）?x1、x2、x3…xn-1的組合都應(yīng)該小于等于1（不難理解當(dāng)條件1、2均滿足時，條件3也滿足）

通過上述分析不難理解，當(dāng)n=3時，解的可行域為三角形；當(dāng)n=4時，解的可行域為三棱錐；當(dāng)n比較大時解的可行域就是更加復(fù)雜的高緯度的圖形。

下面對函數(shù)的構(gòu)造進(jìn)行舉例說明：

圖1 交通量、行程時間分配圖Fig.1 Map of traffic volume and travel time allocation

假設(shè)A和B之間有三條道路且道路網(wǎng)絡(luò)交通的分配滿足Wardrop第一原理、第二原理。Link1路段的實際通行能力為1 200，道路自由通行時間為1。Link2路段的實際通行能力為1 500，道路自由通行時間為1.2。Link3路段的實際通行能力為1 000，道路自由通行時間為1.5。

A與B之間產(chǎn)生的交通量為3 000。如果令Link1分配的交通量的百分比為自變量x，Link2分配的交通量的百分比為自變量y，顯然z分配的交通量為1－x－y；那么不難構(gòu)造出三條道路的路阻函數(shù)。

Link1的路阻函數(shù)：

Link2的路阻函數(shù)：

Link3的路阻函數(shù)：

很容易得到整個系統(tǒng)的平均行程時間為：

至此，得到整個系統(tǒng)的平均行程時間的函數(shù)表達(dá)式，做出該圖形，并求得此圖形的最小值點。

圖2 系統(tǒng)平均行程時間圖Fig.2 Map of system average travel time

由圖不難找出最小值點（圖像范圍應(yīng)該限制于x+y≤1內(nèi)的三角形）為（0.4，0.4，1.275），即Link1、Link2分配1 200的交通量，Link3分配600的交通量。此時系統(tǒng)內(nèi)平均行程時間最短為1.275。

2 系統(tǒng)平均行程時間的解法——模擬退火算法

模擬退火算法（Simulated Annealing，SA）是一種全局優(yōu)化方法，它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法，理論上算法具有概率的全局優(yōu)化性能,目前已在工程中得到了廣泛應(yīng)用。

通過道路平均行程時間函數(shù)的構(gòu)造，能夠得到道路網(wǎng)絡(luò)的最優(yōu)分配方式，但通過一般求全導(dǎo)數(shù)的方式求函數(shù)最小值是極其復(fù)雜的，特別是當(dāng)自變量較多的時候，其結(jié)果實際是多維空間的一個點，計算難度很大。通過模擬退火智能算法來求道路平均行程時間函數(shù)的最優(yōu)解。

2.1 模型構(gòu)建

對于一個目標(biāo)函數(shù)為f（x）、自變量為x的n維極小化問題，設(shè)fk，fk+1分別為目標(biāo)函數(shù)在第k次和k+1次的迭代值，即fk=f（xk），fk+1=f（xk+1）。若fk＞fk+1，則接受xk+1為當(dāng)前點，作為下一次迭代的初值繼續(xù)進(jìn)行迭代運算，直到滿足收斂結(jié)束條件；若fk≤fk+1，則xk+1可能被接受也可能被拒絕，接受的概率為Boltzmann概率p。

Boltzmmann概率p也稱為接受概率，定義為：

其中，T是控制參數(shù)，在迭代尋優(yōu)過程中，T必須緩慢減少，控制參數(shù)變化太快，會使優(yōu)化陷入局部極值點。

2.2 模型介紹

圖3 系統(tǒng)迭代優(yōu)化步驟流程框架Fig.3 System iterative optimization step process framework

模擬退火的基本思想：

（1）初始化：初始溫度T（充分大），初始解狀態(tài)S（是算法迭代的起點），每個T值的迭代次數(shù)L；

（2）對k=1，…，L做第（3）至第6步；

（3）產(chǎn)生新解S′；

（4）計算增量ΔT=C（S′）－C（S），其中C（S）為評價函數(shù)；

（5）若ΔT＜0則接受S′作為新的當(dāng)前解，否則以概率exp（-ΔT/T）接受S′作為新的當(dāng)前解；

（6）如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。

2.3 舉例分析

使用模擬退火算法求解系統(tǒng)平均行程時間函數(shù)：

圖4 求解路徑平均行程時間示例圖Fig.4 Example diagram of the average travel time of the solution path

我們舉一個簡單的例子假設(shè)A和B之間有兩條道路，且道路網(wǎng)絡(luò)交通的分配滿足Wardrop第一原理、第二原理。Link1路段的實際通行能力為1 200，道路自由通行時間為1。Link2路段的實際通行能力為1 500，道路自由通行時間為1.2。

A與B之間的出行量為2 000輛/h。令A(yù)與B之間的出行量中A承擔(dān)的百分比為自變量x，則可以構(gòu)造出Link1和Link2的BPR路阻函數(shù)。

Link1的路阻函數(shù)：

Link2的路阻函數(shù)：

得到整個系統(tǒng)的平均行程時間為：

可以通過求導(dǎo)等方法得到整個系統(tǒng)的最優(yōu)值，但是當(dāng)A與B之間有多個道路時，就需要求多元函數(shù)的最優(yōu)值。因此直接利用matlab中模擬退火算法工具箱求全局優(yōu)化方法，得到結(jié)果如圖5所示。

圖5 函數(shù)優(yōu)化結(jié)果示例圖Fig.5 Example graph of function optimization results

優(yōu)化結(jié)果顯示，取x=0.51時，系統(tǒng)的平均行程時間最少，為1.153，即Link1分配的交通量為1 020。

Link2分配的交通量為980時得到最優(yōu)的分配方式，這時系統(tǒng)的平均行程時間為1.153。

圖6 目標(biāo)函數(shù)迭代優(yōu)化圖Fig.6 Graph of objective function iterative optimization

經(jīng)過3 000次的迭代運算，在約800次的運算之后函數(shù)收斂至1.153位置。

2.4 模型的對比

至此已經(jīng)通過案例對利用BPR路阻函數(shù)求解平衡的交通分配問題有了一定認(rèn)識，與其他交通分配模型相比，此模型具有以下優(yōu)勢。

與容量限制-多路徑交通分配方法比較：

采用容量限制-多路徑交通分配方法先將交通量分配為k個分交通量，然后分k次用多路徑分配模型分配交通量。多路徑分配模型采用Logit型的路徑選擇模型進(jìn)行計算。

利用容量限制-多路徑交通分配方法對剛才的例子進(jìn)行計算（迭代次數(shù)取4次，每次交通量均為500；分配參數(shù)θ=3.00）計算結(jié)果見表1。

表1 迭代求解結(jié)果Tab.1 Iterative solution result

分配后系統(tǒng)的平均路阻為1.196 9，大于模擬退火算法求得的1.153。顯然模擬退火算法計算結(jié)果優(yōu)于容量限制-多路徑交通分配方法。

（1）與非平衡交通分配方法的對比

非平衡模型具有結(jié)構(gòu)簡單、概念明確、計算簡便等優(yōu)點，也得到了廣泛應(yīng)用，但無法取得最優(yōu)解是這類分配方法的致命缺點；而本文的方法則通過隨機(jī)類全局優(yōu)化算法求得了最優(yōu)的結(jié)果。不可否認(rèn)，非平衡模型具有一定的優(yōu)勢，比如多路徑交通分配方法一般取5次就能滿足精度要求，而本文的方法在經(jīng)過約800次迭代后才完成了計算的收斂。

（2）固定需求分配方法，彈性需求平衡分配類模型的對比

這類算法利用線性規(guī)劃的方法通過Frank-wolfe算法求得最優(yōu)解，但由于Frank-wolfe算法不能求解非線性規(guī)劃問題，非線性規(guī)劃問題并沒有一般的通用解法。所以這類算法不能給出一般解法，依然具有一定的局限性。

2.5 模型的改進(jìn)

通過與其他交通平衡方法的比較，發(fā)現(xiàn)該模型的主要缺點是迭代次數(shù)多，計算量大，為了加快計算的收斂，本文提出以下建議：

（1）適當(dāng)增加概率函數(shù)中參數(shù)T（控制參數(shù)T不能過大，否則優(yōu)化會陷入局部極值點）。

（2）初始點的確定可以通過非平衡交通分配方法確定，合理的初始點能夠有效地減少迭代次數(shù)。

系統(tǒng)平均行程時間的準(zhǔn)確性改進(jìn)：

系統(tǒng)平均行程時間實質(zhì)是由BPR路阻函數(shù)推導(dǎo)求得，本文中均采用了BPR路阻函數(shù)中的推薦值，即α=0.15，β=4。在更復(fù)雜的情況下，可以根據(jù)實際的需要修改t（q）=t0[1+α（q/c）β]中的回歸系數(shù)α，β，以獲得更加準(zhǔn)確的路阻函數(shù)和系統(tǒng)平均行程時間。

模型經(jīng)改進(jìn)后迭代情況：當(dāng)t位于0.950 0～0.996 0范圍時，路阻收斂于1.153 916 944，收斂情況較好，圖7為優(yōu)化結(jié)果。

圖7 一元函數(shù)優(yōu)化結(jié)果Fig.7 Unary function optimization results

優(yōu)化結(jié)果顯示，取x=0.51時，系統(tǒng)的平均行程時間最少，為1.153。

圖8 一元函數(shù)優(yōu)化過程Fig.8 Unary function optimization process

3 000次迭代運算后，約500次迭代后函數(shù)收斂于1.153 916 944位置。

3 結(jié)論

本文應(yīng)用模擬退火算法，通過BPR路阻函數(shù)得到道路行駛時間與交通負(fù)荷之間的關(guān)系，構(gòu)建系統(tǒng)平均行程時間函數(shù)，通過對函數(shù)帶入?yún)?shù)進(jìn)行迭代優(yōu)化得到了系統(tǒng)平均行程最短時間以及相應(yīng)的道路網(wǎng)絡(luò)交通分配，優(yōu)化結(jié)果較優(yōu)，令人滿意。