諶永榮

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

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

1 問題描述

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

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

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

問題1求，使得:

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

問題2求，使得:

引理1若，對如果

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

問題3求，使得對都有:

問題4求，使得:

2 收斂性分析

首先給出2個基本假設:

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

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

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

由假設(2)得:

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

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

結論成立.

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

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

代入問題3有:

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

3 數(shù)值實驗

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

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

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

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

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

4 結語

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

［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.