谌永荣

(中南民族大学数学与统计学学院，武汉430074)

随着社会的进步和经济的快速发展，城市交通需求急剧增加，交通拥堵问题已成为一个世界性难题，如何合理分配有限的交通资源，提高现有交通网络的通行能力也越来越受到重视，因而交通分配问题就成为交通问题中一个重要的组成部分.在道路交通中，交通出行的起点O与交通出行的终点D称为一个O－D对.当一个网络中各O－D对间的交通需求给定后，确定或预测道路交通网上交通流的分配模式，通常称为交通分配问题.本文主要讨论了带弹性需求的平衡交通分配问题模型及其罚方程算法，并对一个小型交通网络进行了数值实验，为交通分配等实际问题提供参考和借鉴.

1 问题描述

给定网络G=(N，A)，N为节点集，A为边集，W表示O－D对集，Rw表示O－D对w间的路径集，设网络中共有m个O－D对，各个O－D对间的路径数分别为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对关联矩阵，

问题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)均为连续函数;

引理2设对是问题4的解，则存在与和k无关的常数M＞0，使得对∀λ≥0，都有

证明对∀λ≥0，设是问题4的解，将(8)式两边同乘以有:

由假设(2)得:

引理3设为问题4的解，则存在与和λ无关的常数c＞0，使得

证明将(8)式两边同乘有:

结论成立.

定理1(收敛性定理) 设和分别是问题2和问题4的解，则存在与和λ无关的常数c＞0使得

证明设c＞0为与和λ无关的常数，则:

代入问题3有:

再根据引理3即可得到定理1的结论成立.

3 数值实验

考虑图1所示的道路交通网络.图1所示的网络中有两个O－D对:1－4，1－5，O－D需求量都为40，网络中共有7条路段，6条路径.

图1 道路网络Fig.1 Road network

路段费用函数t(x)=10－2Hx+b，其中:

x是路段流量构成的向量，x=ΔTh，Δ是路径路段关联矩阵，c(h)=Δt(ΔTh)，需求函数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］，并用一个小的网络进行了仿真计算，计算结果与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.