帶彈性需求的平衡交通分配非線性互補(bǔ)模型及算法

諶永榮

(中南民族大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)學(xué)院，武漢430074)

隨著社會的進(jìn)步和經(jīng)濟(jì)的快速發(fā)展，城市交通需求急劇增加，交通擁堵問題已成為一個世界性難題，如何合理分配有限的交通資源，提高現(xiàn)有交通網(wǎng)絡(luò)的通行能力也越來越受到重視，因而交通分配問題就成為交通問題中一個重要的組成部分.在道路交通中，交通出行的起點(diǎn)O與交通出行的終點(diǎn)D稱為一個O－D對.當(dāng)一個網(wǎng)絡(luò)中各O－D對間的交通需求給定后，確定或預(yù)測道路交通網(wǎng)上交通流的分配模式，通常稱為交通分配問題.本文主要討論了帶彈性需求的平衡交通分配問題模型及其罰方程算法，并對一個小型交通網(wǎng)絡(luò)進(jìn)行了數(shù)值實(shí)驗(yàn)，為交通分配等實(shí)際問題提供參考和借鑒.

1 問題描述

給定網(wǎng)絡(luò)G=(N，A)，N為節(jié)點(diǎn)集，A為邊集，W表示O－D對集，Rw表示O－D對w間的路徑集，設(shè)網(wǎng)絡(luò)中共有m個O－D對，各個O－D對間的路徑數(shù)分別為n1，n2，…，nm，n1+n2+…+nm=n，R為所有路徑構(gòu)成的集合，即R=∪w∈WRw.hr表示路徑r上的流量，h=(hr)∈Rn，uw為O－D對w間的最小行駛費(fèi)用，cr(h)表示路徑r上的行駛費(fèi)用，c(h)=(cr(h))∈Rn，dw(u)是O－D對w間的交通需求，d(u)=(dw(u)).

滿足Wardrop用戶平衡的交通分配問題可描述為［1，2］:

將條件(1)～(3)改寫為下列問題1.

問題1求，使得:

其中Γ=(Γrw)是路徑O－D對關(guān)聯(lián)矩陣，

問題2求，使得:

引理1若，對如果

證明若滿足(4)～(6)式的解，則它必然滿足(7)式;反之，若是(7)式的解，只需證明滿足(6)式即可.假設(shè)對某個對，有.由互補(bǔ)性條件必然有uw=0，且.由于及每個hr都是非負(fù)的，則由可得至少存在一個使得hr＞0.再由引理條件可知，產(chǎn)生矛盾.故對所有的O－D對w∈W都有

問題3求，使得對都有:

問題4求，使得:

2 收斂性分析

首先給出2個基本假設(shè):

(1)c(h)，d(u)均為連續(xù)函數(shù);

引理2設(shè)對是問題4的解，則存在與和k無關(guān)的常數(shù)M＞0，使得對?λ≥0，都有

證明對?λ≥0，設(shè)是問題4的解，將(8)式兩邊同乘以有:

由假設(shè)(2)得:

引理3設(shè)為問題4的解，則存在與和λ無關(guān)的常數(shù)c＞0，使得

證明將(8)式兩邊同乘有:

結(jié)論成立.

定理1(收斂性定理) 設(shè)和分別是問題2和問題4的解，則存在與和λ無關(guān)的常數(shù)c＞0使得

證明設(shè)c＞0為與和λ無關(guān)的常數(shù)，則:

代入問題3有:

再根據(jù)引理3即可得到定理1的結(jié)論成立.

3 數(shù)值實(shí)驗(yàn)

考慮圖1所示的道路交通網(wǎng)絡(luò).圖1所示的網(wǎng)絡(luò)中有兩個O－D對:1－4，1－5，O－D需求量都為40，網(wǎng)絡(luò)中共有7條路段，6條路徑.

圖1 道路網(wǎng)絡(luò)Fig.1 Road network

路段費(fèi)用函數(shù)t(x)=10－2Hx+b，其中:

x是路段流量構(gòu)成的向量，x=ΔTh，Δ是路徑路段關(guān)聯(lián)矩陣，c(h)=Δt(ΔTh)，需求函數(shù)dw=4e－0.01uw.采用本文的算法得到的結(jié)果如表1(k=2)所示.

表1 各O－D對之間路徑上所分配到的流量及對應(yīng)的成本(路徑行駛時間)Tab.1 Flow and travel cost distributed on every route of O － D pair

4 結(jié)語

本文討論了帶彈性需求的平衡交通分配問題的非線性互補(bǔ)模型，針對文章給出的模型，本文采用了罰方程算法［4，5］，并用一個小的網(wǎng)絡(luò)進(jìn)行了仿真計算，計算結(jié)果與Wardrop用戶平衡準(zhǔn)則相吻合，表明本文提出的算法是可行有效的.

［1］Wardrop J G.Some theoretical aspects of road traffic research［J］.Proceedings of the Institute of Civil Engineers，1952，Ⅱ:325-378.

［2］Beckmann M，McGuire C B，Winsten C B.Studies in the economics of transportation［M］.New Haven:Yale University Press，1956.

［3］Facchinei F，Pang S.Finite-dimensional variational inequalities and complementarity problems［M］.New York:Springer，2003，I:4-5.

［4］Wang S，Yang X Q.A power penalty method for linear complementarity problems［J］.Operations Research Letters，2008，36:211-214.

［5］Huang Chongchao，Wang Song.A power penalty approach to a nonlinear complementarity problem［J］.Operations Research Letters，2010，38:72-76.