交通运输网络的数学模型

交通运输网络的数学模型

关键词：交通运输，用户优化，系统优化，网络均衡，交通分配，变分不等式，复杂网络，集中决策论对比分散决策论，Braess悖论，网络动力学，因特网，供应链，发电和配电网络，金融网络，网络评估模型与重要性识别，运输网络的易破坏性 目录： 1.简介

2.决策论基本概念和模型 2.1 用户优化对比系统优化 2.1.1 用户优化问题 2.1.2 系统优化问题 2.1.3 Braess悖论 3.非对称链路的费用模型 3.1固定需求问题的变分不等式 3.2弹性需求问题的变分不等式 3.3其他的网络均衡问题和交通运输 4.动力学

5.一种运输网络效率度量法和网络元素的重要性 6.总结

摘要： 在这篇文章里，我们提供了运输网络问题的严格求解，分析和解决方案的基础理论。我们讨论了相当于分

散决策论的用户优化和相当于集中决策论的系统优化，根据集中决策论中央处理器可以以优化方案规划交通线路。我们描述了一系列越发精密的模型，并且把运输网络和其他以流量为关键因素的网络应用领域联系起来，例如因特网，供应链，发电配电网还有金融网络。最后，我们论证了运输网络元素的重要性，即节点和线路可以通过一种最新提出的运输网络有效性评估方法和元素重要性定义来识别（分等级）。文章中有例子来说明这一点。 1.简介

运输网络是一个复杂，大规模的系统，它以不同的方式存在，如公路，轨道，航空和水路。运输网络通过人，物和服务的流动为经济和社会的运行提供基础。从经济学角度讲，这种网络系统的供应以基础网络拓扑和费用规格参数来代表，但是需求以运输系统的用户来代表。当一个O/D间的出行数量等于以市场价格给出的出行需求时就会呈现均衡态势，典型代表是出行时间。

运输网络的学习和它们的有效管理源于古代。据说，罗马为了处理交通拥堵，在不同时间段对战车进行交通管理。从经济学角度讲，对这一学科最早的贡献可以追溯到K和P，他们考虑两个节点和两条线路的运输网络，把交通拥堵作为一个问题，并且认识到关于道路选择，不同的行为观念起主要作用。

正式的运输网络研究因不同原因挑战了一批运输科学家，经济学家，运筹家，工程师和物理学家，这些原因有：系统的规模和范围，网络用户的行为可能根据应用程序设置不同而改变，导致不同的优化/均衡概念；不同层次的用户可能以个人习惯来看待网络使用的费用，令外，拥堵成为运输网络中越来越重要的难题。

例如，为了定位现代运输网络的大小和范围，我们指出芝加哥区域运输网络包括12982个节点，39018个线路和2297945个出行者选择路线的O/D对，然而在南加利福尼亚州国会的模型中有25428个节点，99240个线路和6种不同阶层用户。

据估计，道路拥挤造成仅美国自身损失将近1000亿生产总值，截止2010年欧洲的汽车数有望增加50%，到2030年有望加倍，因道路拥挤造成的生产总值将减少1500亿。特别的，在发展中国家如中国和印度，机动车尤其是小汽车的使用正在变革。并且，在当今许多的运输网络中，用户的不配合行为加重了拥堵问题。例如，城市运输网络中，出行者选择自己的出行路线使他们的出行费用或是出行时间最少，这从用户的角度来说最优，而对社会却未必最优，决策者或是中央处理器控制整个网络流并试图分配流量使得网络的总代价最小。与交通堵塞并行的是污染问题，它作为另一个负面的外在因素对我们生存的社会将产生深远影响。

著名的Braess悖论的例子，以生动明确的方式对比了不配合行为和系统优化行为。那个例子假设潜在的行为准

则是用户优化，出行者选择自己的路线。在Braess网络中，在所有出行者出行需求不改变的情况下增加一条新的道路会引起所有用户产生更高的出行费用。因此，增加新的道路后情况会变得更糟！事实上，这一现象已经在纽约和斯图加特发生。1990年，纽约的42街在地球日禁止通行，这一区域的交通流得到了改善。相反，在斯图加特，商业区增加了一条新道，交通流变得很糟，紧接着是抱怨，而后这条新道瘫痪。同样的经历也发生在了韩国首尔。有趣的是，这一现象与电信网也有关。这种现象不会发生在系统优化网络中，如果添加一条道路将会降低总费用。堵塞代价是当今研究的活跃话题，在世界的不同城市中通行费已经通过改变人们的行为成功地改善了交通，包括开放的伦敦，英国。

在这篇文章中，我们回顾了运输网络严谨研究的基础理论，我们追溯了他们的模型架构的发展历程。这些讲解对从业者和学生都是易懂的，包括研究者，政策制定者和对相关网络话题感兴趣的人们。技术发展和深层次的支撑文献在引文中指出。关于这一论题，深层次有用的资料和按时间顺序排的增补文献在一些评论文章中可以找到。 这篇文章，详细地概览了一些方法，这些方法是在规划，分析和解决运输网络问题时被激发形成的。它也将运输模型和先进算法的贡献和其他网络应用领域结合起来。最后，考虑到运输网络的重要性和与电信，电力网络，供应链和金融网的密切联系，我们完整的讨论了一个网络有效评估方法，它将识别关键节点和线路。这个方法是由N和Q提出的，它可以帮助政策制定者，策划者，工程师和网络策划者识别网络中哪些元素需要被保护。因为它们如果遭到自然灾害，结构瘫痪和恐怖袭击的破坏，对整个网络将会产生巨大影响。因此，一旦移除这些节点线路，运输网络会变得易受损。 2．决策论的基本概念和模型

半个世纪以前，Ω明确的思考了运输网络用户的其他可能行为，这里显然是指城市运输网络，提出了两个以z自己名字命名的原理：

原理一：实际所使用的所有道路的出行时间是相等的，少于那些只被单量机动车经过的道路的出行时间。 原理二：平均的出行时间最少。

第一条准则相当于用户寻求自己最少费用的行为准则，而第二条准则相当于网络总费用最小的行为准则。 B，M和Ω是最早严谨地用数学方法公式化这些条件的。特别的，他们在运输网络均衡间建立了平等，指出所有使用过的连接O/D对的路线会有相等且最小的行程时间（或是费用），KUHN-TUCKER在隐函数对称假设下，考虑

合理性建立了优化问题。因此，在这种情况下，数学规划问题的解决使得平衡的链路和路径流量可以求得。他们的方法使得以实际为依据的运输网络问题的公式化，分析以及随后的计算变得可靠。

D和S在两种完全不同的情况下区分运输网络的用户优化和系统优化，用户分别以两种方式决定出行路线：以自己的利益单方面做决定和以社会角度使得网络总费用最低来做决定。在后一问题中，边际费用而不是平均费用会平衡。前一问题与Ω的准则一一致，后一问题与准则二一致。表一说明了隐含在运输网络中的两个截然不同的行为准则。

表1：运输网络的不同行为

系统优化概念也和其他一些类型的路线模型相关联，如通信，包括那些货运和电脑信息的传输。D和S还提供了详细的计算过程，这个算式计算了在一个特定路线上当流量是增函数（为了处理堵塞）时用户的出行费用。现今，在网络中包括因特网用户优化和系统优化占领了集中决策和分散决策的地位。 2.1用户优化和系统优化

这一部分，在两种不同的假设，即网络运作和用户的潜在行为下的运输网络模型已经最早回顾了。基于Beckmann, McGuire, and Winsten (1956) and Dafermos and Sparrow (1969)，模型很经典。在接下来的部分，我们介绍一些广泛的模型，用户的出行费用方程不再是可分离的，而是不对称的。针对这些模型我们也提供了控制均衡条件的变分不等式，因此，在这种情况下，在KUHN-TUCKER考虑凸优化问题时控制均衡条件不再能用公式化表示。

为了精确和简单的查阅，我们在2.1.1节介绍了用户优化网络模型，在2.1.2节介绍了系统优化网络模型。然后，

每个O/D对使用路径的用户出行费用相等且达到最小。 每个OD对间使用路径的边际总出行费用相等且达到最用户均衡原则 系统最优原则 用户最优 系统最优 我们在2.1.3节回顾了Braess悖论来进行证明。 2.1.1 用户优化问题

用户优化网络问题经常作为交通分配问题或是交通网络平衡问题在运输文化中被提到。回顾一下Ω准则一之后的用户优化。

考虑一个普通的网络G = [N,L]，N代表节点，L代表连线。连线连接网络中的节点，用a,b代表。令p代表连接O/D的有序路径。路径被假设为非循环，以p,q等来表示。在运输网络中，节点连接O/D，同交叉口一样。另一方面，在城市运输网络中连线相当于道路|街道，在轨道交通中相当于轨道路段。在最基本的环境中的一条线路是指一系列有先后次序的道路，这些道路包含O/D。然而，在电信环境下，节点相当于交换机或是电脑，连线相当于是电话线，电缆，微波链等。这里我们考虑路线而不是路径，因为前者包含后者。这里介绍的网络概念足够抽象，不仅指运输决策制定，还包括整体的方位运输决策制定。另外,在超网中，路径不必局限于路径类型的决策，而应该看的宽泛一点，事实上，不光相当于运输决策制定，也可以是电信决策的制定，或是两者结合如电话购物或是远程办公。 用dω代表连接O/D节点Ω的路线，P代表网络中的所有路径，并且假设在模型Ω中有J个O/D对。令xp代表路径p的非负流量，fa代表连线a的流量。网络中的路径流量集中于列向量x∈R+，这里np代表网络中的路径数。

nL

相应的，路线流量集中于列向量f ∈R+，这里nL代表网络中的路线。

我们假设需求与O/D对Ω相关联，表示为dω，ω dω这里，xp≥

np

∈Ω。在网络中，流量方程必须满足：

= p∈Pωxp , ?ω∈Ω, （1）

0,?p∈P；即所有O/D对Ω间路径的流量总和必须等于所给的需求dω。

另外，下面守恒的流量方程还必须满足： fa

= p∈Pxp δap,?a∈L, （2）

这里δap =1，如果路线a包含于路径p，否则等于0.表达式2说明a的流量等于路径p中包含路线a的所有流量总和。

特别的，方程1和2保证网络中的流量（出行者，电子信息等）是守恒的，即它们会从出发点到达设定的目的，而不会在网络中消失。

令Ca代表与横贯路线相关联的用户，Cp代表和路径p有关的用户费用。假设用户路线费用函数由一个路线费用仅依据此路线流量的分离函数规定，即：

ca

=ca fa , ?a∈L, (3)

为了塑造流量对费用的影响，特别是在拥堵的状况，我们假设Ca是连续的以fa为自变量的增函数。 这里费用被诠释为一个普通的含义。从一个交通运输设计师的角度考虑，一条线路上的费用尤其与出行时间相关联。另外，也可以建立普通意义上的线路费用函数，可以以金钱和出行时间权衡，也包括其他的尺度，包括环境因素。

一条路径上的费用等于这条路径上所有线路的费用总和，即 Cp

运输网络均衡条件

在用户优化问题中，人们试图确定一个线路流量类型x，它满足守恒的流量方程1和2，也满足线路流量的非负假设，且满足接下来规定的运输网络平衡条件。对于每一个O\\D对ω

= a∈Lca fa δap, ?p∈P. (4)

∈Ω和每条线路p∈Pω:

?

= λω,xp>0 Cp= (5) ?

=λω,xp=0

因此，在用户优化问题中，没有明确的优化化概念，因为运输网络系统中的用户以不合作的方式独立行动，直到

他们不能单方面改善自己的状况为止，此时，受上述均衡条件控制的均衡状况就会出现。事实上，条件5是Ω准则一的简单数学重述，它的意义是仅仅那些被使用的连接O|D对的线路会有相等和最低的用户费用。在5中，以λω代表O/D对Ω的最低费用，一旦均衡流量模型出现它的值就会达到。否则，用户可以通过转换的费用低的线路来改善自己的状况。用户优化代表离散决策，而系统优化代表集中决策。见表一。

为了得到解决上述问题的方法，B，M和Ω在用户费用函数是形式3的条件下建立了解决网络均衡问题的方法。式3中线路的费用仅依据线路流量来决定，并且假设为是连续的以流量为自变量的增函数，解决上述问题可以通过解决一下优化化问题：

a

Min a∈L c(y)dy (6) 0a

f

满足：

p∈Pωxp=dω, ?ω∈Ω, (7) fa= p∈Pxpδap, ?a∈L, (8) xp≥0, ?p∈P. (9)

6给出的目标函数是用普通目标凸优化设计算法来得到解决方案所建立的一个简单策略。它不包含下面介绍的经济学意义上系统优化问题中遇到的目标函数。注意，在分离和不分离但是对称的情况下，用户线路费用函数中λω

相当于与O/D对Ω限制条件7关联的啦格朗日乘数。但是，在不分离对称函数中没有运输网络均衡条件在形成的条件下，λω只简单的反映在均衡条件下与O/D对相关联的最小用户费用。和D与S同样早闻名，上述网络均衡条件也相当于纳什均衡。这个联系在计算机科学上获得广泛兴趣。如果目标函数严格凸优化，均衡线路流量模型受7-9限制对于问题6来说是独特的。 2.１.2系统优化问题

现在我们来描述和讨论系统优化问题。和用户优化问题类似，在网络G=[N,L]中，和O/D对相关联的需求和假设的用户线路费用函数已经给出。在系统优化问题中，由一个交通中心控制者来决定交通线路来使网络中的总费用最低。

线路ａ的总费用，用c a(fa)来表示，表达式为：

c a(fa)=ca(fa)×fa, ?a∈L, (10)

即一条线路的总代价等于用户费用乘以这条线路的流量。正如先前提到的，在系统优化问题中，在网络系统中存在一个中央控制者来寻求最小总费用，总费用表达式为：

a∈Lc a fa , (11)

其中一条线路的总费用为表达式10 系统优化问题即：

Min a∈Lc a(fa) (12)

满足用户优化问题中的流量方程，以及线路流量的非负假设；即限制条件7，8，在系统优化问题中同样要满足条件9.

路线的总费用用Cp表示，是路线的用户费用乘以流量，即：

Cp=Cpxp, ?p∈P, (13)

这里用户费用CP以组成此线路的所有连接线上用户费用总和来表示，即

Cp= a∈Lca(fa)δap, ?a∈L. (14)

鉴于2，3和4，人们可能把路线P的费用表示为以流量为变量的方程，因此，上述系统优化问题的目标函数用

另一个视角可以表达为仅以线路流量为变量的形式，即为如下问题：

Min p∈PCp(x)xp (15)

满足限制条件7和9. 系统优化条件

在假设用户线路费用方程为增函数的条件下，在S—O问题中目标函数12为凸优化函数，包含线性限制条件7—9的合理的设也是凸优化性的。因此，在优化条件下，即K—T条件：对每一个O|D对ωp∈Pω，流量形式x（相当于线路流量形式f）满足7—9并且要满足：

,=μω, xp>0, (16) Cp

≥μω, xp=0,

∈Ω，对每一条线路

这里Cp代表线路p的边界总费用，有一下式子给出：

,?c a(fa) C=δap, (17) pa∈L

?fa

在解决方案中以式子16来评估，μω是该O|D对Ω中与限制条件相关联的啦格朗日常数。

观察到条件16可能被改变，使得每一对O|D存在有先后顺序的线路，凭借这个所有使用的线路（正流量）有相等且最小的边界总费用，没有使用的线路（零流量）有较高的边际总费用。因此，在S—O问题中，表一所示，根据优化条件16，每一条连接O|D对的使用路线的边际总费用相等且最低。 2.1.3 Braess悖论

为了在一个明确的例子中说明用户优化和系统优化，且增强上述概念，我们回顾了众所周知的Braess悖论。像在运输网络中一样这个矛盾同样与电信网络相关联，特别是，因特网，因为这种网络符合交通控制的离散控制。 ·

c

2 3 2 311 a b a b d c d 4 4 图一：Braess网络实例

假设一个网络像图表一所示有四个节点：1，2，3，4；四条连线：a，b，c，d;和一个O/D对Ω1＝（１，4）．因此，在O/D间有两条路径可供选择：p1＝（ａ，C）和p2＝（B，D）。

用户线路流量方程为：

ca fa =10fa,cb fb =fb+50, cc fc =fc+50, cd fd =10fd.

假设一个固定的出行需求dω1=6. 很简单就可以证明均衡的路径流量为：xp1

?

????

=3，xp=3,均衡的线路流量为：f=3,f=3,f=3,acb2

?

fd=3，与之相关联的均衡路径出行费用为：Cp1=ca+cc=83,Cp2=cb+cd=83.

现在假设，如图一描述，一条新的线路＂ｅ＂，在原始网络中加入节点2和3，以及用户线路费用函数

ce fe =fe+10.。这条线路的增加创造了新的路径p3=(a,e,d)可供出行者选择。假设出行需求dΩ1遗留六个

单位的流量。注意到原始的流量分配类型xp1=3和xp2=3不再是均衡模型，因为在这一水平的流量路线p3的用户费用为Cp3=ca+cb+cc=70。因此，路径p1和p2的用户将会转换到p3.

?

新网络中的均衡流量模型为：xp1

????

=2,xp2=2,xp3=2,相应的均衡线段流量为：fa=4,fb=2,

??

fc?=2,fe=2,fd=4，相应的均衡用户路径出行费用为：Cp1=92,Cp2=92。事实上，我们可以证明任

何重新分配的路径流量将会带来更高的出行费用。

注意到网络中每一个用户的出行费用从83增加到92对出行需求不产生任何改变！

路径出行费用的增加部分原因是在这个网络中两条路段被不同的路径享有，这些路段在流量和费用上产生增量。因此，Braess悖论和网络的基础拓扑学有关，当然，和用户行为也有关联，此时是用户优化。但是我们可以说明，在一个O|D段增加一条不分享原始路径上路段的路径不会引发Braess悖论。

回顾和Ω准则二相当的系统优化解决方案，可以最小化网络总费用，所有连接每个O/D对的利用的路径将会有相等的最低出行总费用。

图一中第一个网络的系统优化解决方案为：xp1=xp2=3，相应的边际总费用为：Cp1

,, =Cp2=116。加入线段

ｅ这个依然是最有化方案，因为路径p3的边际费用在可行模型中等于１30.

一条新的线段的加入不会增加网络总费用，但是会增加用户的费用，因为出行者独立决定自己的行为。 3.非对称线段费用的模型

在建模和使更普遍的运输网络均衡模型公式化和计算成为可能的方法学的发展方面，前几十年已经有很多研究

活动。普通模型的例子包括那些允许运输模式多样化或是用户阶层多样化（如计算机信息），这些类型的路段费用仅依靠自身的流量。在这部分，我们考虑用户费用不仅仅依靠路段流量的网络模型。在3.１，我们介绍一个有固定需求的运输网络均衡模型，在3.2介绍一个有弹力需求的模型。在3.１.3部分，我们进一步详尽说明运输网络均衡概念和它的公式化，以及强调几种新的应用。

假设用户路段费用方程是一个普通形式，即，路段费用不仅仅视此路段的流量而定，还跟网络流量有关，即：

ca=ca(f), ?a∈L. (18)

在均衡假设

?ca(f)?fb

=

?cb(f)?fa

存在的情况下，对于所有的路段a,b∈L，我们依然可以把满足均衡条件的网络均

衡问题的解决方案以优化化问题的解决方案来表示出来，尽管，目标函数是人为的一个简单的数学手段。但是，当均衡假设不再满足时，这样的优化形式不再存在，我们必须求助于变分不等式原理。非对称费用方程的运输网络模型很重要，因为他们允许公式化表述，定性分析，最终，一条线路费用的解决方法可能以一种不同的方式依据另一条线路的流量而定，而不是依据自身线路流量而定。这样一个概论适用于交叉口，双向路段和多种运输模式包括网络有不同阶层用户的实际处理。

在这种运输网络均衡问题的领域里固定维数变分不等式原理意识到自身最初的成就，它们以S和D的贡献开始。N的书中又对这门学科的简介，包括运输网络和财政中的立体均衡问题的应用。以下我们展示了运输网络均衡问题中固定需求和弹性需求的变分不等式化表述。

相应地，系统优化问题中，不分离的用户路段费用函数变为：

Min a∈Lc a f , (19)

满足7—9·这里c a f =ca f ×fa,?a

∈L.

系统优化条件仍为式16，但是现在的边界总费用以一种更为普遍的形式表示为：

?c ,b(f) C=δap, ?p∈P. (20) a,b∈Lp

?fa

3.1固定需求问题的变分不等式

如先前所提，在用户路段费用方程不对称的情况下，我们不能计算出U-O解决方案，即对于网络均衡问题使用标准

的优化化算法。我们再次强调，从应用角度老说这种基本费用方程很重要，因为它们允许网络中的非对称作用。例如，非对称费用方程允许人们处理一条特定路段的流量以一种不同的方式影响另条路段的费用而不是这条特定路段的费用受别条路段流量影响的情况。

首先，回顾变分不等式问题的定义。查看N和D的书和其他文献可以获知深层的背景，理论公式，起源和结果的证明。我们提供路径流量和路段流量中网络均衡条件的变分不等式形式。

特别地，变分不等式问题的定义如下： 定义一：变分不等式问题

固定维数的变分不等式问题，VI(F,K)是来确定一个向量X*∈

K,如

≥0, ?X∈K, (21)

Normal Cone

X X-X* X* -F(X*)

F(X) Feasible Set K 图2：VI(F,K)的图形解释

*

这里F是一个给定的从K到R*连续函数，K是一个给定的闭向量，<.,.>代表R*的内部结果。

变分不等式在标准形式里被提到。因此，对于一个给定的问题，特别是一个均衡问题，我们必须决定进入变分不等式问题中的函数F，变化向量X，和可行区间K。

特殊情况下，变分不等式问题包括总所周知的方程组问题，优化化问题和补足问题，因此，它是解决均衡分析和计算的很强的方法学。

变分不等式问题的图形解释在图2给出。特别地，在点X* F(X*)与可行域K是直交的。 原理一：网络的变分不等式 固定需求的均衡—线路流量描述

一个向量x

*

∈K1是一个网络均衡线路流量类型，即，它满足均衡条件5仅当它满足以下变分不等式问题：

ω∈Ω p∈PωCp x? × x?x? ≥0, ?x∈K1, (22)

或者，以向量形式表示为：

≥0, ?x∈K1, (23)

这里C是路径用户费用的nP维列向量，K的定义为K≡ x≥0,满足（7）

定理2：网络的变分不等式 固定需求的均衡—路段流量描述 一个向量f?

1

1

∈K2是一个网络均衡路段流量类型仅当它满足一下变分不等式问题：

? a∈Lca f? × fa?fa≥0, ?f∈K2, (24)

或以向量形式表示：

≥0, ???∈K2, (25)

这里c是路段用户费用的nL维列向量，K的定义为：K≡ f/这里存在一个x≥0满足 7 和（8）

注意到我们可以通过让F

2

2

≡C,X≡x,K≡K1把变分不等式23化为标准形式21.同样，当F≡c,X≡f,K≡

K2时我们也可以把变分不等式式25化为标准形式。因此，在不对称的用户路段费用函数的情况下固定需求的运输

网络均衡问题可以以变分不等式问题来解决，想上面所给出的一样。

在设计其他模型中一个问题的其他变分不等式和有用，包括动力形式，用不同算法来达到计算目的。在第4节，

我们描述了变分不等式和规划的动力学系统，在这里面后者提供了在平衡动力学之前有成就的不平衡动力学，因为前者通过后者形成。

变分不等式理论允许我们在存在性，独特性和解决方案的敏感度和可靠性方面定量分析，以及应用严谨的算法来对均衡模型进行数字计算。变分不等式算法经常把变分不等式问题分解为一系列简单的独立问题，相应地为可以用不同算法有效解决的优化化问题，这些算法有D和S的平衡算法，它们运用在时间算法中的时候也开发新的网络结构，还有BG的基本算法，似乎很适合大规模的网络模型。特别地，和松弛方法一样的设计方法已经被成功运用到运输网络均衡问题的变分不等式的计算机解决方案中。

我们强调上述网络均衡框架足够基础，可以在一个合理构建的网络或是超网中进行路径选择时使整个运输计划过程（包含起点选择，目的选择，或共同选择，加上路径选择，以一种优化方式）书面化。这点在1976年（在分离的路径费用函数的背景下）被D验证，她发展了整合的运输网络均衡模型，在模型里运输路线选择和住所选择同时进行。在参考书目和N的书中会有深层讨论，他们发展了更一般的模型，在这些模型中，费用不必是分离或是非对称的。

有一点值得注意，固定需求模型的变分不等式的介绍是在单模型运输网络的背景中给出的。但是，考虑到函数的普遍性，上面描述的模型框架适用于多种模型/多层次用户的问题，在这些问题中，有多种运输模式和以各自习惯看待网络线路费用的不同用户。D正式展示了一个多层次用户的交通网络可以通过建立一个包含原始网络中多层用户的扩展网络来映射为单一用户网络。这一转换的应用和电信网络也有关联。

同样的，我们注意到，这里的重点是确定性网络均衡问题。在S中可以找到一些基本的随机运输网络均衡模型。显然，D发展了最早的随机路径选择模型。相应的，D和S确切的阐述了一个随机路径选择的用户优化交通网络模型，在模型中，均衡原则可以简单地声明为没有用户可以通过改变各自路径来改善他的出行时间。 3.2弹性需求问题的变分不等式

我们现在描述一个来自D的有弹性需求的普通网络均衡模型，但是我们以简单的单模型角度来介绍他。假设我们引入一个和网路中每个O\\D对Ω关联的出行负效用方程λω，这里通常情况下，负效用被考虑为视整个需求向量而定，现在需求向量是一个不确定的变量，即

λΩ=λΩ d , ?ω∈Ω (26)

这里，D是Ｊ维需求向量。

标记与早先描述的一样，不过在这里我们也考虑普通的用户路段费用函数，即式子(18)所示。相应的流量方程依下列形式给出：

fa= p∈Pxpδap, ?a∈L, (27)

dω

= p∈Pωxp, ?ω∈Ω, (28)

xp≥0, ?p∈P. (29)

在弹性需求的情况下，表达式28的需求是变量不再是给定的，与表达式１给出的固定需求相反。

弹性需求情况下网络均衡条件

在弹性需求下呈现的网络均衡条件为以下形式。对于每一个O/D对Ω∈Ω，每一条路径p∈求的向量满足28和29（通过27引发一个路径流量类型）是一个网络均衡类型如果它满足：

ω? =λd, x>0ωp? Cp(x) (30) ?

≥λω dω , xp=0

Pω，路径流量和需

均衡条件声明每一条O/D对间使用的路径的费用相等且最小，等于O/D间的负效用。没有使用路径的费用可以

超过负效用。我们观察到在弹性需求模型中，如果O/D间的用户路径费用超过出行负效用，网络中的用户可以同时提前出行。因此，这个模型允许我们依据不同O/D间最终的平衡需求来确定他们的吸引力。另外，这个模型可以处理如下情况：上班族工作地点和路径选择的均衡决定，住所和路径选择，或者通过加入节点和线段的这种合理的转换来表示住所，工作地和路径选择，而且给出各自的函数。

注意到，虽然弹性需求运输网络模型的介绍是在单一运输模式和用户的情况下，我们可以简单介绍和上面模型

不同的模式。我们只需要介绍代表模式/类型的下标，有依据地重新定义上述向量，流量方程，最后声明式30必须满足每一个模式/类型。换句话说，在均衡中，一个给定模式的使用路径和O/D对必须有最小和相等的使用路径费用，相应地，必须等于此模式和均衡需求O/D对的出行负效用。当然，像在固定需求中所描述的，我们也可以在网络中建立许多模式，在这种情况下，除了扩展弹性需求模型以外的单一模型网络应该与一个多模型网络相当。 在接下来的两个命题中，网络均衡条件的变分不等式（30）以路径流量形式和路段流量形式呈现出来。依D来说，他们各自存在和固定需求模型相似的公式22，23，24，25.

命题3：网络变分不等式 弹性需求均衡—路径流量形式 一个向量(x题：

3 ω∈Ω p∈PωCp x? × x?x? ? ω∈Ωλω d? × dω?d?ω ≥0, ? x,d ∈K, (31)

?

,d?)∈K3是一个网络均衡路径流量类型，即它满足均衡条件（30）仅当它满足满足变分不等式问

或者，以向量形式表示为：

C x? ,x?x?>?≥0, ? x,d ∈K3, (32)

这里, λ是J维负效用向量，K3的定义为：K3≡ x≥0,满足（28） 命题4：网络变分不等式 弹性需求的均衡—路径流量形式

向量(f?,d?)∈K4是一个网络均衡路段流量类型仅当它满足变分不等式问题：

? 4

a∈Lca f? × fa?fa? ω∈Ωλω d? × dω?d?ω ≥0, ?(f,d)∈K, (33)

或者，以向量形式：

?≥0, ? f,d ∈K4, (34)

这里??4≡ ??,?? ,存在??≥0满足 27 ，（28） 。

a b

3 图3：一个弹性需求例子 在负效用方程的对称假设条件下，即，如果

?λω?dω

1 2 =

?λω?dω,

，对于ω,Ω，加上用户路段费用方程的这一条假设，我

们可以得到（参考B，M和Ω）一个网络均衡条件的优化化公式，这个公式是在分离的用户路径费用函数和负效用方程的条件下给出的：

aω

Min a∈L cydy?λω(z)dz (35) aω∈Ω00

fd

满足：27—29

我们现在介绍一个有弹性需求的运输网络均衡问题，且是对称的用户路径费用方程。

一个有弹性需求的运输网络均衡例子

考虑图3描述的网络，有三个节点：1，2，3;三条线段：a,b,c;一个简单的O/D对ω1=(1,3)。令路径p1=(a,c),令路径p2=(b,c).

假设用户路段费用函数为：

ca(f)=4fa+fb+10, cb(f)=3fb+2fa+20, cc(f)=2fc+fb+fa+5,

负效用函数为：

λω1 dω1 =?dω1+120.

观察到在这个例子中，用户路段费用函数方程是不分离和对称的，因此，均衡条件不能作为解决优化化问题的方案公式化给出，但是可以作为解决变分不等式问题的方案。但是，假定在这个简单的例子中，网络和费用结构很简单，我们可以直接解决均衡条件。

?

此U—O流量和需求模型满足均衡条件（30）：xp1

?

=10,xp2=5,d?和相关联的路段流量形式：ω1=15，

??

fa=10,fb=5,fc?=15。所产生的用户路径费用为：Cp1=Cp2=105，即负效用的值λω1。因此，这个流量

和需求模型满足均衡条件（30）。事实上，p1和p2是使用路径，它们的用户路径费相等。另外，他们的费用等于与这两条路径相联系的O/D对的负效用。

值得一提的是税收的形式的政策，例如，可以应用它来保证出行者在税收的制约下能以系统优化的角度来决定自己的行为。可以看D，N，L，H，和S的书或其他文献获得一些背景资料。 3.3其他的网络均衡问题和交通运输

注意到上述弹性需求模型与S，T和J的著名的空间价格均衡模型紧密关联。事实上，像D和N在单商品和随后的

多商品背景下所展示的，空间价格均衡问题和合理建立的网络均衡问题是一致的。因此，运输网络中发展的理论可以转移到在空间价格均衡的情况下的商品流量的学习，在这里，均衡生产，假设和商品贸易流量以满足均衡条件来决定。如果供应市场的价格加上运输的单位费用等于需求市场的价格，在供求市场间会存在一个商品的正流量。 很多这种模型和关联的文献可以在N和Z的书中找到。

虽然，此篇的重点是一个主要焦点为市区的运输网络均衡模型，但是，货物网络模型和上述模型有紧密联系。显然，在这个背景下，我们必须区别此种类型网络操控者的行为，适当的建立竞争模型。像B，M和N，B，M所强调的，Ω明确的把网络的概述作为一个公司决策制定的概念，路径与生产过程关联，物质在O/D间的转移与路段关联。从决策中提取的路径和生产可能性对一个公司来说是可行的。例如，B，M和Ω提出了一个与公司理论类似的运输网络，如下面描述：“考虑一个在不同阶段都可用或是修改的化学和冶金材料，一个承担将它从一个阶段转移到另一个阶段的公司，这里阶段包括材料的位移，与道路相当的转移，材料的一系列转移过程，即生产过程—与路径关联。”这个描述很符合另一个关联的应用，在此，网络均衡的概念引起了兴趣，即供应链网络。供应链网络的学习是跨学科的，因为此种网络包含生产，销售，运输，经济和运筹学以及管理科学。

N，D和Z是最早在供应链的背景中运用网络均衡概念的。在他们的模型中，在网络节点的决策者有各自的包含利益最大化的决策函数，他们不仅试图决定节点间的优化/均衡流量，而且决定不同层次节点间产品的价格。随后，这个模型即被N，L，D和Z普遍地包含了电子商务。N证明供应链网络均衡问题可以转化并以运输网络均衡问题来解决。潜在的均衡条件的详尽解释以路段和路径流的形式给出。最近，由B，M，和Ω假象，N和L与Ω，L和S证明，电力的产生和分配网络也可以转换为运输网络均衡问题，有此分解了一个对外界开放了50年的假想。最终，L和N证实了调节财政网络也可以在合理建立抽象网络或是巨网的前提下转化为运输网络。相应地，Z，D和N把Ω理论普遍化，考虑到网络中的路径和环都可以被认定为“成功的”供应链。在这个背景下，路径相当于生产过程，连线可以是操作或是接口连线。它们的框架结构适用于供应链的竞争模型，对一些公司都可用（生产，运输，销售）。 因此，用于发展运输网络均衡问题的工具，如上简述可以转用到应用领域，如电力网络，财政网络加上供应链网络。这些网络，加上运输和通信网络，形成我们所谓的“关键基础设施”，因为它们在当今社会和经济中发挥重要的作用。一系列相关问题的深入讨论，多个决策者的复杂网络问题，和运输网路均衡问题直接关联的不同的应用可以在N的书中找到。 4.动力学

在一部分，我们简单总结一下设计的动力系统原理运用到在地3部分介绍的弹性需求运输网路均衡问题中，以此来介绍不平衡动力学。这里介绍的相当于N中所展示的。D和N证明，给定一个变分不等式问题，存在一个自然关联的动力系统，这个系统静止点的域准确的和变分不等式问题的解决域一致。这个被Z和N称为预期动力系统的系统是非经典的，也是不连续的。但是，它可以定量分析，而且可以通过D和N所描述的离散时间算法来估计。重点是，预期动力系统理论提供了出行者制定他们旅程决定和调整他们路径决策的动力行为。再者，它提供了稳定性分析的有利依据。动力运输网络问题的其他方法可以在R和B，M的书中找到。这里我们特别强调不平衡动力学和均衡达到以前我们可以每天观测的调整结果。

因为网络中的用户选择可以达到他们目的地的路径，对于动力系统均衡我们考虑把变分不等式作为基础。我们特别注意到，考虑限制条件（28），我们可以定义 λ x ≡λ d ,，在这种情况下，我们可以以单一流量变量x重新定义变

P分不等式式子，即我们试图决定x?∈Rn+,如

P ≥0, ???∈Rn+, (36)

这里 λ(x)是nPω1,×nPω2×…nPωJ-维列向量，元素有：

( λω1 x ,…, λω1 x ,…, λωJ x ,…, λωJ(x)),

P

如果现在我们令X≡x以及F X ≡C x ? λ(x)及K≡{x/x∈Rn+}，然后(36)可以（23）这种标准形式给出。动力系统最早被D和N提出，他们的

静态点相当于（36）的解决，以下列形式给出：

x= K x, λ x ?C x , x 0 =x0∈K, (37) 这里投影算子 K(x,v)被定义为：

K x,v =limσ→0和

(PK x+δv ?x)

δ

, (38)

PK=argminz∈K z?k . (39)

（37）所描述的动力学如下所示：O\\D路径的流量变化率等于出行负效用和例子中的路径费用的不同。如果路径费用超过出行负效用，路径上的流量就会减少；如果少于负效用，路径流量就会增加。投影算子保证路径上的流量不会是负值，因为这样容易产生矛盾。因此，从原始路径流量类型演化来的路径流量在时间零表示为x(0)直到一个静态点达到，即x=0；在这一点我们得到特殊的点x*：

x=0= K x?, λ x? ?C x? , (40) 这个x*也解决变分不等式式子（36），因此，一个运输网络均衡满足弹性需求均衡条件（30）。

动力轨迹的质量属性，解决方案稳固性条件，离散时间算法都可以在Z和N以及其他文献中找到。我们特别注意到离散时间算法提供了连续时间轨迹的时间离散化，或者解释为离散时间评估过程。

另外，除了运输网络模型的动力学引起了广泛关注，参考R和B以及其他文献。

为了讨论包括电力网络在内的动力供应链网络和以上的扩展网络，得出了发展的变分不等方程理论和双层动力学，参考N和其他文献。

5.运输网络有效性测量和网络元素的重要性

在这一篇文章中，我们关注运输的数学经济模型和这个模型和其他网络领域的关系。现在我们进一步把运输网络和一些复杂网络学科联系，这些年这一课题已经成为紧张研究活动的科目，但是这个以图论为基础的课题如我们上面所提到的已经有百年历史。事实上，网络学科它的广泛应用已经被经济学家，应用数学家，物理学家，工程师，生物学家和社会学家所解决。三种类型的网络，它们的研究最近已经发展起来，没有与流量产生很多相互作用，尤其是为了网路方法的发展收到热烈关注的行为运输模型是随机模型，以Ｅ看来是小世界模型。

学习和鉴定网络易损元素的重要性已经联系到事件如9/11，以及2003年8月14号发生在南美的大停电。为了

避免恐怖袭击和自然灾害，很多相关的复杂网络（有时指网络科学）研究关注有关应用的图的特性，有此来估计网络可靠性和易攻击性，例如参考C和P和H。

如N 和Q中所闻名的，为了能够评价一个网络的易损性和可靠性，一个可以计量得到网络有效性的方法要发展起来。例如，从2001年开始的一系列文献中，L和M通过在一个 有利的网络中衡量“全球有效性”与简单的非有利小世界网络比较来讨论网络行为议题。在一个有利网络中，网络不光以连接节点的边也以不同边的权重来表示其特点，以此来展示不同节点的联系。一个网络G的有效性E在L和M的著作中被定义为E=

1n(n?1)

i≠j∈G

1dij

，

这里n是网络G中的节点数，dij是节点i和j的最短路径长度。这一方法已经被上述作者运用到不同网络中，包括波斯顿地铁网络和因特网。

虽然一个网络的拓扑结构对网络性能和网络易损性产生重要影响，显然，上述讨论主张网络流量是一个重要的指示，如感应费用和网络用户的行为。事实上，流量代表一个网络的使用，哪些路径和线路有正流量，这些流量的重要性与网络分裂的情况相联系。有趣的是，虽然最近出现在复杂网络研究中的一些著作强调运输网络的流量。在上述著作中航空网络的焦点仅仅考虑了节点的重要性，忽略了路段和用户行为的重要性。一个网络有效性测量包括流量，出行费用，用户行为和网络拓扑，在像评估运输网络这样的网络中很合适，他们是经典的关键性基础设施。事实上，在分裂影响节点，或是路径，或两者的情况下，我们期待出行者可以看情况重新调整他们的行为和网络的使用。进一步，像J，P和N所提到的，一个网络元素包括节点，路段和两者的结合的重要性与网络系统的易损性相关，元素越是重要，网络系统除去它以后的破坏性就越大，它通过自然灾害，恐怖袭击，结构倒闭来作用。 我们现在描述一个新的运输网络性能测量方法，它不仅可以运用运输网络有效性测量，也可以测量网络元素的重要性。它包含用在“复杂”网络研究中的L和M的方法。因为N和Q的贡献，这个方法有附加重要的特性可以应用，它伴随着网络元素的重要性定义，甚至成为不连通网络（元素被移除以后）。

定义2：一个运输网络有效性测量

给定一个网络拓扑G和O/D需求向量，运输有效性测量，ε（G,d），定义如下：

ε=ε G，d =这里λ

ω?Ω

J

dω

λ

ω (41)

ω

代表连接O/D对Ω的使用路径的最小费用，即为正流量。J是网络中的O/D对的数量。

如N和Q所强调的，（41）给出的运输网络有效性测量有一个有意义的经济学解释，运输网络有效性等于以O\\D对形式给出的平均出行价格率dω，O/D间的出行均衡价格由λ在一个给定价格的可行性越高，运输网络的有效性或是性能就越高。

有趣的是，接下来的理论表明，在合理的假设下，N和Q的方法包括，L和M的网络有效性测量这一特殊情况，但是，它没有考虑流量或是需求而且不包含任何潜在用户行为。

命题5：

如果每一对节点的需求等于１，dij等于λω，这里ω= i,j .那么提出的网络有效性测量方法与L和M的方法相同。

证明：让N代表网络G中的总结点数。因此，原则上，总的O\\D对数可以假设等于n（n-1）。通过进一步假设，我们得到dω=1,?ω∈Ω，这里ω是Ｇ中O\\D对的集合。ω= i,j 以及dij=λω。这里i≠j,?i,j∈G。那么式子（41）中的方法即为：

ε G,d =

ω∈Ω

J

dω

ωω

表示。出行可以被控制

λ

=

i≠j∈G

J

1dij

=n(n?1) i≠j∈Gd (42)

ij

11

从定义中观察到，λω是O\\D对间使用路径的最小费用值，dij是i和j的最短路径长度（测距）。因此，λω等于dij并不是不合理的。但是N和Q的方法比较普遍，依据定义2，它包含了网络流量和行为。

通过最新的运输网络有效性方法，我们可以通过学习移除网络元素对运输网络的影响来观察他们的重要性。节点和边的重要性定义如下：

定义3：网络元素的重要性

I(g)是一个网络元素g∈G的重要性，它通过从网络中移除ｇ来测量： I g =

?εε

=

ε G,d ?ε(G?g,d)

ε(G,g)

, (43)

这里G-g是移除g以后的网络G。 网络元素重要性较高的范围是1．

在N-Q方法中移除路段的方式为直接移除，然而移除节点需要同时移除与节点相连接的线段。在移除结果造成O/D对间没有路径的情况下，我们简单地分配有无限费用的抽象路径。这个方法在非联通网络中明确定义。显然，L和M也提到这一重要特点使得这一方法有超过小世界网络模型的吸引力。 一个例子

考虑图4的网络，这里存在两个给定需求ω1=(1,2)和ω2=(1,3)的O\\D对，dω1=100和dω2=20。我们得到路径p1=a和p2=b．假设路径费用方程给定：ca(fa)=.01fa+19和cb(fb)=.05fb+19。显然，我们得到

??xp=100和xp=20。λ12

ω1

=λ

ω2

=20。网络有效性为ε=3然而L—M的方法得到E=.0167.

1 a b

2 3 图4：例子

使用重要性测量方法，例子中节点和线段的重要性等级分别在表2和3中列出。

N和Q的方法包含了流量信息，更加普遍，合理以及精确。路段a的流量是路段b的5倍，在分裂的情况下，a的破坏将会造成有效性很大的损失！相同的定量分析符合节点2和3.更多的例子可以在N和Q的书中找到。

表2：例子中路段的重要性及等级 线路 a b 重要度 N-Q方法 0.83 0.17 重要等级 N-Q方法 1 2 重要度 L-M方法 0.5 0.5 重要等级 L-M方法 1 1 表3：例子中节点的重要性及等级 线路 1 2 3 重要度 N-Q方法 1.00 0.83 0.17 重要等级 N-Q方法 1 2 3 重要度 L-M方法 1.00 0.50 0.50 重要等级 L-M方法 1 2 2

这个网络有效性测量可以应用到其他运输网络中，包括像因特网和电力网，供应链以及财政网这些基础设施网络中。事实上，它不仅仅可以鉴定给定网络的关键元素，也可以帮助决策者判断哪些网络元素要更好的保护。 6.总结

这篇文章概述了运输在数学经济模型中的重大发展，也识别了运输网络和其他一些网络应用的一些显著联系。用户优化对比系统优化的关联行为准则通过BRAESS悖论进行了讨论。从具有分离用户路段费用函数的固定需求的运输网络模型（用户优化和系统优化角度）开始，接着是有非对称用户路段费用的弹性需求运输网络均衡模型，最后为出行负效用函数，逐步深入的复杂普遍运输网络模型被一一介绍。因为与运输网络问题关联，优化化理论，变分不等式理论，投影动态系统理论的讨论也有介绍。另外，运输网络有效性测量与网络元素即节点和线段的重要性鉴定一同进行了重新讨论。通过这篇文章中的例子，我们起到了说明解释的作用。最后，因特网，供应链，电力网和财政网的相关应用也被注意到。这篇文章生动地展示了运输网络的重要性和它在理论和实践方面的严谨研究。

本文来源：https://www.bwwdw.com/article/5ldp.html