基于終點(diǎn)的用戶均衡交通分配模型求解算法

摘 要：用戶均衡分配模型是更接近實(shí)際交通狀態(tài)的分配模型，它是建立在出行者總選擇起迄點(diǎn)間交通時間最短的路徑作為出行路線的行為假設(shè)基礎(chǔ)上的。分析基于終點(diǎn)的用戶均衡交通分配模型，指出該模型與基于路徑均衡配流模型是等價的，在選擇美國BPR路阻函數(shù)后，模型可以轉(zhuǎn)化為帶線性約束的非線性規(guī)劃問題，并給出模型的矩陣表示。對這類問題，采用簡便實(shí)用的仿射尺度算法求解，給出算法的基本思想及詳細(xì)的實(shí)現(xiàn)過程。仿真結(jié)果顯示，所得最優(yōu)解滿足Wardrop第一準(zhǔn)則，表明該算法是有效的，可用于大型路網(wǎng)的配流計(jì)算。

關(guān)鍵詞：交通分配;Wardrop準(zhǔn)則;基于終點(diǎn)模型;仿射尺度算法

中圖分類號：U491;TP274文獻(xiàn)標(biāo)識碼：B

文章編號：1004-373X(2008)22-145-03

Algorithm for User Equilibrium Traffic Assignment Model Based on Destination

LIU Bingquan，WANG Mingjun

(Weinan Teachers University，Weinan，714000，China)

Abstract：User equilibrium assignment model is the one that is closer to actual traffic situation.It is established on the fact that the travellers are apt to choose the shortest paths as travel routes between OD(origin destination).The paper analyzes user equilibrium traffic assignment model based on destination，and points out that the model and traffic assignment model based on path are equivalent.By using BPR link travel time function，the model can be translated into nonlinear programming problem with linear constraints and represented in matrix form.To solve the problem，affine scaling algorithm is adopted and the general idea and detailed implementation process of the algorithm are given.Simulation demonstrates that the optimal solution observes Wardrop first principle and the method is effective，so it is suitable to solve the traffic assignment problem in large scale road network.

Keywords：traffic assignment;Wardrop principle;destination-based model;affine scaling algorithm

交通分配就是把各種出行方式的空間OD量分配到具體的交通路網(wǎng)上，它是城市交通規(guī)劃的一個重要環(huán)節(jié)。依據(jù)Wardrop第一、第二準(zhǔn)則，通常把交通分配劃分為均衡分配與非均衡分配。Beckman最早提出了滿足Wardrop第一準(zhǔn)則的用戶均衡交通分配模型，常采用Frank-wolfe算法進(jìn)行求解^［1-3］。由于該模型以各OD對之間的路徑流量為變量，需要枚舉OD對間的所有路徑，因此對大型路網(wǎng)，模型求解相對比較困難。

近年來，許多學(xué)者對這類問題進(jìn)行了多方面研究^［4-6］，提出許多新的模型與算法，如基于路段模型與算法^［7］，基于起點(diǎn)和終點(diǎn)的模型與算法^［8，9］等。這些模型與算法都是以路段流量為變量，并發(fā)現(xiàn)基于路段的交通分配模型同樣滿足Wardrop第一準(zhǔn)則。選擇路段流量為變量，避免路徑枚舉，減少計(jì)算的復(fù)雜程度。

基于終點(diǎn)的用戶均衡交通分配模型可以歸結(jié)為一個具有線性約束的非線性規(guī)劃問題，本文采用簡單實(shí)用的仿射尺度算法^［10］求解這類問題。首先給出基于終點(diǎn)的用戶均衡交通分配模型，指出該模型與基于路徑均衡配流模型是等價的，當(dāng)選擇適當(dāng)路阻函數(shù)后，模型可以歸結(jié)為帶線性約束的非線性規(guī)劃問題，并轉(zhuǎn)化為仿射尺度算法的處理形式;最后采用該算法求解一個小型路網(wǎng)的交通配流問題，仿真結(jié)果顯示，該算法是有效的，可用于大型路網(wǎng)的配流計(jì)算.

1 交通分配模型

1.1 用戶均衡交通分配模型

用戶均衡分配模型是更接近實(shí)際交通狀態(tài)的分配模型。在均衡狀態(tài)時，在同一OD對間所有被使用的路徑上，其路徑行駛時間相等且該行駛時間小于或等于未被使用路徑上的行駛時間，此時網(wǎng)絡(luò)處于平衡狀態(tài)，任何出行者均無法通過變更選擇路徑達(dá)到減少出行時間的目的。對于一個給定交通網(wǎng)絡(luò)G＝（N，A），N為節(jié)點(diǎn)集，A為邊集，R為起點(diǎn)集，S為終點(diǎn)集，R與S可以有公共元素；A(i)為以i為起點(diǎn)的有向路段集合;B(i)為以i為終點(diǎn)的有向路段集合;(r，s)為以r為起點(diǎn)，s為終點(diǎn)的OD對；xsa表示路段a上到終點(diǎn)s，(s∈S)的流量;Prs為OD對(r，s)間所有路徑集合。對應(yīng)于Wardrop第一準(zhǔn)則的用戶均衡交通分配模型（1）:

min z(x)=∑a∈A∫xa0ta(ω)dω(1)

s.t.∑p∈Prsfrsp=qrs，r，s(2)

frsp≥0，p，r，s(3)

xa=∑r∈R∑s∈S∑p∈Prsδrsap·frsp，a(4)

式中：frsp是O-D對（r，s）間路徑p上的交通量；qrs是OD對(r，s)間的交通需求量；

δrsap=1，OD對(r，s)間路徑p經(jīng)過路段a

0，否則

上面模型是基于路徑用戶均衡交通分配模型，求解該模型需要枚舉OD對間的所有路徑，因此在大型路網(wǎng)上應(yīng)用比較困難。下面給出的基于終點(diǎn)的用戶均衡交通分配模型(2):

min z(x)=∑a∈A∫xa0ta(ω)dω（5）

s.t. ∑a∈A(i)xsa－∑b∈B(i)xsb=qis，i∈R，s∈S，i≠s（6）

∑a∈A(i)xsa－∑b∈B(i)xsb=0，iR，s∈S，i≠s（7）

xsa≥0（8）

xa=∑s∈Sxsa（9）

該優(yōu)化模型以路段到終點(diǎn)的流量xsa為變量，避免了路徑枚舉，從而適用于大型路網(wǎng)的配流計(jì)算。

1.2 模型分析

模型(1) 中目標(biāo)函數(shù)是路段行駛時間函數(shù)積分之和，該目標(biāo)函數(shù)在交通上的含義并不直觀，但它的K-K-T條件卻正好與Wardrop第一準(zhǔn)則一致。并且可以證明，模型(2)與模型(1)是等價的。事實(shí)上，令xrsa為路段a從起點(diǎn)r到終點(diǎn)s的流量，則有xrsa=∑p∈Prsfrsp·δrspa，對i≠r，i≠s，有∑a∈A(i)∑p∈Prsfrsp·δrsap－∑b∈B(i)∑p∈Prsfrsp·δrsbp=0，即OD對(r，s)中，當(dāng)節(jié)點(diǎn)i為中間點(diǎn)時進(jìn)入i的流量等于流出流量。從而有：

∑a∈A(i)xsa－∑b∈B(i)xsb=∑a∈A(i)∑r∈Rxrsa－∑b∈B(i)∑r∈Rxrsb

=∑a∈A(i)∑r∈R∑p∈Prsfrsp·δrsap－∑b∈B(i)∑r∈R∑p∈Prsfrsp·δrsbp

=∑r∈R(∑a∈A(i)∑p∈Prsfrsp·δrsap－∑b∈B(i)∑p∈Prsfrsp·δrsbp)=0

即為式(7)。同樣對i∈R，i≠s時有:

∑a∈A(i)xsa－∑b∈B(i)xsb

=∑a∈A(i)∑r∈R∑p∈Posfrsp·δrsap－∑b∈B(i)∑r∈R∑p∈Prsfrsp·δrsbp

=∑a∈A(i)∑p∈Pisfisp·δisap+∑a∈A(e)∑r∈R{i}∑p∈Prsfrsp·δrsap－

∑b∈B(i)∑p∈Pisfisp·δisbp－∑b∈B(i)∑r∈R{i}∑p∈Prsfrsp·δrsbp

=∑a∈A(i)∑p∈Pisfisp·δisap+∑r∈R{i}(∑a∈A(i)∑p∈Prsfrsp·δrsap－

∑b∈B(i)∑p∈Pisfisp·δisbp)

=∑a∈A(i)∑p∈Pisfisp·δisap=∑p∈Pisfisp=qis

與式(2)一致，所以模型(1)與(2)是等價的。

1.3 模型的矩陣表示

令x=(…，x1a…x|S|a，…)T(|A|×|S|)×1表示路網(wǎng)中各路段基于終點(diǎn)的流量向量;ei(s)=(…，eia(s)，…)1×|A|表示s為OD對終點(diǎn)時節(jié)點(diǎn)i的點(diǎn)弧關(guān)聯(lián)向量;其中:

eia(s)=1，s為OD終點(diǎn)時，i為a的起點(diǎn)

－1，s為OD終點(diǎn)時，i為a的終點(diǎn)

0，否則

設(shè)：

E(s)=e1(s)e2(s) …e|N|(s)〗|N|×|A|

E=E(1)0…0

0E(2)…0

… … … …

00…E(|S|)〗(|N|×|S|)×(|A|×|S|)

b=(…，bsi，…)T(|N|×|S|)×1，

bsi=qis，i∈R，s∈S且i≠s

0，否則

采用矩陣表示模型(2)轉(zhuǎn)化為式(10):

min z(x)=∑a∈A∫xa0ta(ω)dω

s.t.Ex=b

x≥0（10）

2 仿射尺度算法

2.1 算法的基本思想

設(shè)模型（3）的內(nèi)可行域Q+={x|Ex=b，x>0}，當(dāng)前迭代點(diǎn)為xk=(xk1，…，xk|A|×|S|)T，xk∈Q+，構(gòu)造對角陣Dk=diag(xk1，xk2，…，xk|A|×|S|)，做仿射尺度變換Tk：g=D－1kx，在此變換下，式(10)變?yōu)椋?/p>

min Gk(g)

s.tEkg=b，g≥0（11）

其中，Ek=EDk，并且xk被變換到式(11)約束區(qū)域的中心e=(1，1，…，1)T(|A|×|S|)×1。從e出發(fā)沿式(11)的目標(biāo)函數(shù)在gk＝e處的負(fù)梯度在矩陣Ek的核空間的投影方向：qk=－(Gk(e)－Ek′(EkEk′)－1EkGk(e))做一維搜索，這里Gk(e)=Dkz(xk)。若qk＝0，則可證xk是式(11)一個K-T點(diǎn)；若qk≠0，則記pk=qk‖qk‖，做一維搜索min0≤λ≤θ F(xk+λDkpk)，（0<θ<1）。

2.2 算法的迭代步驟

Step 1: 給定初始點(diǎn)x0∈Q+，x0＝(x01，x02，…，x0|A|×|S|)T，允許誤差ε，σ>0，置k =1；

Step 2: 令Dk=diag(xk1，xk2，…，xk|A|×|S|)，計(jì)算qk=－(Gk(e)－Ek′(EkEk′)－1EkGk(e))，其中Gk(e)=Dkz(xk)，Ak=ADk；

Step 3: 若‖qk‖<ε，則令xmin=xk，停止；否則，轉(zhuǎn)Step 4；

Step 4: 計(jì)算pk=qk‖qk‖，進(jìn)行一維搜索min0≤λ≤θ z(xk+λDkpk)，θ∈（0，1）；

Step 5: 設(shè)λk是Step4中最優(yōu)解，若‖λkDkpk‖<σ，則令xmin=xk，停止；否則，轉(zhuǎn)Step 6；

Step 6: 令xk+1=xk+λkDkpk，置k=k+1，轉(zhuǎn)Step2；

3 仿真實(shí)驗(yàn)

考慮如圖1所示的交通路網(wǎng)，有14條路段，變量xsa有28個;有2個OD對1-9和3-7，OD需求量分別為q1，9=q3，7=55;路阻函數(shù)采用美國公路局1964年提出的BPR函數(shù)，具體可取ta(xa)=ta(0)(1+0.15xaca4)，ta(0)為路段自由流行駛時間，設(shè)每條路段飽和容量為40;路段自由流行駛時間見表1。

圖1 交通路網(wǎng)圖

采用仿射尺度算法，使用Matlab軟件編程對這個實(shí)例進(jìn)行求解。求解中所取允許誤為ε=0.01，σ=0.1時，各路段分配流量見表2。表3給出分配流量路徑的行駛時間，可以看到，同一OD對路徑行駛時間基本相同，從而滿足Wardrop 第一準(zhǔn)則。圖2給出了仿射尺度算法的收斂曲線圖，可以發(fā)現(xiàn)，本算法收斂速度快，算法迭代528步后誤差降為0.01。

表1 路段自由流行駛時間

路段1234567891011121314

ta(0)54.54544.54.56654.54.555

表2 各路段分配流量

路段1234567

xa9.6628.4545.3438.1026.5545.3437.83

路段891011121314

xa26.5526.7237.8345.4426.7217.1728.28

表3 各OD對路徑行駛時間

OD對路徑(按節(jié)點(diǎn))行駛時間

(1，9)

1-4-5-8-921.4181

1-2-5-6-921.4336

1-4-5-6-921.4191

1-2-5-8-921.4326

(3，7)

3-2-5-4-720.9307

3-6-5-8-720.9417

3-6-5-4-720.9317

3-2-5-8-720.9407

圖2 算法的收斂曲線

4 結(jié) 語

本文給出了基于終點(diǎn)的用戶平衡交通分配模型的仿射尺度算法，模型以基于OD對終點(diǎn)的路段流量作為變量，避免了路徑枚舉，減少計(jì)算量。仿真計(jì)算結(jié)果顯示，本文采用的仿射尺度算法是有效的，分配到各路段的流量滿足Wardrop 第一準(zhǔn)則。

參考文獻(xiàn)

［1］Lee Der-Horng，Nie Yu.Accelerating Strategies and Computational Studies of the Frank-Wolfe Algorithm for the Traffic Assignment Problem［J］.Trans.Research Record，2001，1 771:97-105.

［2］Gao Ziyou，Lam W H K，Wong S C.The Convergence of Equilibrium Algorithms with Non-monotone Line Search Technique［J］.Applied Mathematic and Computation，2004，148:1-13.

［3］Michael Patriksson.Algorithm for Comuting Traffic Equilibria［J］.Network and Spatial Economics，2004，4:242-250.

［4］Yu Nie，Zhang H M.Models and Algorithms for the Traffic Assignment Problem with Link Capacity Constraints［J］.Transportation Research Part B，2004，38:285-312.

［5］Lee Der-Horng，Nie Yu，Chen Anthony.A Conjugate Gradient Projection Algorithm for Traffic Assignment Problem［J］.Mathematical and Computer Modeling，2003，37:863-878.

［6］蘆群，劉燦齊.城市公共交通網(wǎng)絡(luò)均衡分配模型與算法［J］.交通與計(jì)算機(jī)，2004，22(4):3-6.

［7］肖海燕.基于路段流量的交通分配模型的算法［J］.武漢科技大學(xué)學(xué)報(bào):自然科學(xué)版，2007，30(3):274-277.

［8］Bar-Gera H.Origin-based Algorithm for the TrafficAssignemnt Problem［J］.Trans.Science，2002，36:398-417.

［9］李峰，王書寧.基于終點(diǎn)的路徑交通量求解算法［J］.清華大學(xué)學(xué)報(bào):自然科學(xué)版，2006，46(1):149-152.

［10］Huang Chong-Chao.Gradient Projection Method with Affine Scaling for Nonlinear Programming［J］.Advances in Modelling and Analysis(A)，AM SE Press，1994，22:43-48.

作者簡介 劉炳全 男，渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)系，講師。主要研究方向?yàn)橄到y(tǒng)優(yōu)化建模與算法。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文