第三届数学建模论文Braess悖论

1、第三届“ScienceWord杯”数学中国数学建模网络挑战赛承 诺 书我们仔细阅读了第三届“ScienceWord杯”数学中国数学建模网络挑战赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们允许数学中国网站()公布论文，

2、以供网友之间学习交流，数学中国网站以非商业目的的论文交流不需要提前取得我们的同意。我们的参赛报名号为：参赛队员 (签名) ：队员1： 队员2：队员3： 参赛队教练员 (签名)： 参赛队伍组别：2010年第三届“ScienceWord杯”数学中国数学建模网络挑战赛交通网络中的Braess悖论及其博弈论分析摘要随着经济的发展和汽车保有量的增加，各大中城市交通拥堵日趋严重，而在平衡交通网络中扩建道路，有时候却出现了Braess悖论现象，即在交通网络中增加一条通路反而会降低网络性能。本文在分析悖论产生机理的基础上，指出Braess悖论的出现是由于非合作网络中Nash平衡点不在Pareto边界上。以北京

3、市二环路以内的路网中（包括二环路）出现的交通拥堵为例判断是否为Braess悖论现象，通过建立通行时间与车流量的关系，并以北京道路中最常见的“日“字型道路作为切入点，来求解是否存在Breass悖论现象。我们选取了北京二环以内路网中很典型的“日”字结构，通过谷歌地图显示的路况估算出每条路流量和自由通行时间，得到了延迟参数，并根据延迟参数间的关系判断出了是否存在Breass悖论。另一方面从每个出行者出发，建立动态博弈模型，说明广泛使用GPS对于缓解交通压力的意义。关键词 Braess悖论 Pareto最优 博弈论 交通分配With the development of economy and inc

4、reasing number of cars retained, traffic in large cities become worse and worse. However, sometimes extending roads to traffic network induces the phenomenon of Braess's Paradox in which adding a new link to traffic network results in increased equilibrium travel cost for all travelers. On the b

5、asis of analyzing cause of Braess's Paradox, we state that it occurs when the Nash equilibrium is not Pareto optimal. And we take the Second Ring Road in Beijng for example to determine whether the traffic jams in it was caused by Braess's Paradox. We prove whether Braess's Paradox exist

6、s by establishing the relationship between passing time and traffic flow. We get the traffic flow and free passing time of every road by Google Map, thus obtaining the delay parameter. Then determine whether Braess's Paradox exists by the relationship of different delay parameters. On the other

7、hand, we take everyone into consideration to state the significance to relieve traffic jams of using the GPS guided system. Key Words: Braess's Paradox; Pareto optimal; Game theory; Traffic assignment一、问题重述1背景：近年来，日益严重的堵车问题已成了北京交通的难题。造成交通拥堵的直观原因是城市道路建设速度赶不上机动车增长的速度。如果车量不变，单靠扩充交通网络中道路的通行能力，却不一定能缓

8、解交通的拥挤堵塞。1968 年Dietrich Braess 在他的一篇论文中提出在平衡交通流网络中存在一种看似矛盾的Braess 悖论现象。它的含义是：有时在一个交通网络上增加一条路段，或者提高某个路段的局部通行能力，反而使所有出行者的出行时间都增加了，这种为了改善通行能力的投入不但没有减少交通延误，反而降低了整个交通网络的服务水平。人们对这个问题做过许多研究，在城市建设当中也尽量避免这种现象的发生。但在复杂的城市道路当中，Braess 悖论仍然不时出现，造成实际交通效率的显著下降。本文分析了悖论产生的机理,指出Braess 悖论的出现本质上是由于非合作网络中的Nash平衡点不在Pareto

9、边界上,这种情况下,存在一种非平衡的流量分布使网络相对平衡流量分布时，某些用户的出行时间缩短, 同时其他用户的出行时间也不会增加。我们通过实例分析说明交通规划时应该尽量避免设计出可能导致Braess悖论发生的路网结构,而对于现有交通网络中存在的Braess悖论现象,可以通过控制和诱导等策略使交通流的分配达到Pareto 最优,从而避免悖论发生。2问题：(1)通过分析实际城市的道路交通情况（自行查询的数据需给出引用来源），建立合理的模型，判断在北京市二环路以内的路网中（包括二环路）出现的交通拥堵，是否来源于Braess 悖论所描述的情况。(2)建立模型以分析：如果司机广泛使用可以反映当前交通拥堵

10、情况的GPS 导航系统，是否会缓解交通堵塞，并估计其效果。（1）一 问题假设1、假设在后面所分成的两组司机中他们只选择时间最短的方针。并且两组是同时进行的；2、再行对应的路上，在说明时满足用户均衡原则，相对于流量等因素。以及满足一定的对称性。3、在一定的时间内整个路网和局部道路网络内车流量不发生显著变化，即可认为不发生改变。4、天气道路质量、拥挤程度和综合路阻等这些可测因素都在后面的延时参数中体现。不再考虑这样的问题；5、司机对道路是熟悉的，不存在迷路绕远问题，并且能自行选择最短路径。6、谷歌地图中的路况四种颜色反应为道路上的车距，并认为车距平均分布，不考虑道路的车道数量。车长假设为5米，不考

11、虑公交车与小轿车的不同，认为所有车都是5米。7、道路的自由通行时间认为汽车达到法律规定的本路段最大限速值。二、模型分析与建立交通网络中各路段的容量直接影响到交通流在网络上的分布格局。而Braess 悖论是由于司机从个人利益出发,选择出行成本最小的路径,致使系统达到均衡状态时的总出行成本增加。1952 年Wardrop 通过对交通现象的分析提出了关于交通网络流量分布的用户均衡原理5：在所有实际使用的路径上,出行成本相等,且小于任何未使用路径上的出行成本。所有合作博弈的解都具有这样的性质:在均衡点处，任何用户收益的增加都必将导致其他用户收益的降低,网络所能调整的全部合作对策解的集合构成了Paret

12、o边界。从博弈论角度来看,Braess悖论实质上是非合作网络中Nash平衡点不满足Pareto最优性时出现的诡异现象。如图1 所示的路网, 路段出行时间（a）4个路段组成的路网（b）5个路段组成的路网图1路网结构图其中，为用户在路段上的出行时间；为自由流情况下，路段上的出行时间；为路段的延迟参数，即路段上，每增加单位流量时，所增加的出行时间；为路段上的车流量。假设该问题满足对称条件进一步假定路网中的瓶颈路段和很短，因此自由流情况下的出行时间近似为，即假定新增路段的延迟参数与路段和相等，即设，则各路段出行时间可表示成，。路网（）由4个路段构成，从至有两条路线：路线1（），路线2（），其出行时间为

13、令，并取，则，。做出和的函数曲线分别如图2路网（）中实线和星号线所示。图中两条线的交点为用户均衡解，偏离这一平衡必然导致一个目标数值减小时另一个目标函数值增加。此时用户均衡解在Pareto边界上，因此，尽管用户之间是非合作关系，其结果任满足Pareto最优性，不存在可以同时提高双方性能的解。路网（）中除了线路1、2以外，增加了路线3（）。设为分配道路线1上交通流，根据路网对称性，分配到路线2上的交通就也是，因此，分配到路线3上的交通流为。取与路网（）相同的参数并另，做出和的函数曲线如图2路网（）所示。出行时间，min用户均衡解路线3路线1、2Pareto 最优解流量路网（b）流量路网（a）出行

14、时间，min用户均衡解路线1路线2此时只有一个Pareto最优解，路线3上没有车流；而用户均衡解为，。显然用户均衡解不在Pateto边界上，此时出现Braess悖论：在路网（）中增加一条通路反而增加了所有用户的出行时间。实际路网中图1所示的结构并不常见，北京路网中经常见到的结构如图3所示。图3 路网结构及路段出行时间描述从到有3条路线，。设交通需求为，分配到3条路线上的交通流分别为、和。当时，则该问题存在Pareto最优解，并且与用户均衡解不一致，发生Braess悖论。二、模型求解分析北京市二环路以内的某区域路网。首先，根据路段上一个月的车速()和流量（）数据以及路段长度()，估计路段的自由流

15、出行时间和延迟参数。路段出行时间，因此根据车速和流量的数据，可以拟合出关系曲线，从而估计和的值。而对于某一路段的车流量的获取，我们根据该路段的堵塞程度的情况，由图中各种颜色的比例求得其总流量。假设:车长 ：车距 ：路长车流量表示：车速假设，车距根据4种堵塞程度来确定。方法如下：从左到右车距依次为：、选取5段路网分析计算得由关系曲线估计出和的值如表14（备注：路段编号和图3模型中一样按顺时针编排）图4 鼓楼桥路段编号流量flow（辆）路长L (m)自由出行时间(s)延迟参数1199153068.920.019823262500112.610.0198310070031.530.043742501

16、80081.080.0185514070031.530.012963542400108.110.03367260180081.080.0178此路网验证存在悖论。图5 西便门桥路段编号流量flow（辆）路长L (m)自由出行时间(s)延迟参数1179120054.050.0173212990040.540.0180313390040.540.03354183120054.050.0169514394042.340.0169614283037.390.01507171110049.550.0166此路网验证不存在悖论。图6 东直门北桥路段编号流量flow（辆）路长L (m)自由出行时间(s)延迟

17、参数118890040.540.0123210077034.680.01983195150067.570.0381413590040.540.01725377150067.570.0102618870031.530.0232712895042.790.0198此路网验证存在悖论。图7 广渠门桥 路段编号流量flow（辆）路长L (m)自由出行时间(s)延迟参数1211120054.050.0147213790040.540.0169312580036.040.03174163110049.550.0174510960027.030.01426202120054.050.015371861300

18、58.560.0180此路网不存在悖论。图8 建国门桥路段编号流量flow（辆）路长L (m)自由出行时间(s)延迟参数110080036.040.0206210376034.230.0190310378035.140.0375413080036.040.0158512778035.140.0158610070031.530.0180711480036.040.0180此路网不存在悖论。根据对以上路网的分析可知，在北京市二环路以内，某些路网中（包括二环路）存在Braess悖论。三、模型评价1.论文中关于出行时间 的假设是比较合理的，出行时间包括自由出行时间和延迟时间。2.针对北京市二环路以内的

19、路网中（包括二环路），本论文没有对其中的每个路网做计算，而是抽取了其中5个比较典型的“日”字形网络进行分析。数据估算难免存在误差，有些路段上的堵塞情况没有考虑到，这是本论文的缺陷之处，但我们的结果也基本解决了题目中的要求。3.对于某一路段车流量的估算，本论文采取的是flow=L/(s1+s2)的方法。道路越堵塞，则车流密度越大，车距越短；道路越串通，则车流密度越小，车距越长。这种假设大致符合实际情况。4.通过对悖论的验证，知道要使城市道路网络变成一个高效的城市交通网络，就必须根据整个城市的交通量及其出行分布来合理划分车道。当要在城市道路网络中添加一条道路，需要通合理设计路网结构和确定路段参数，

20、尽量避免Braess悖论出现。（2）一 问题假设1、假设GPS导航系统只对拥堵情况做出判断提供给用户，没有其他方面的提供，比如天气，路况等。也就是司机只通过拥堵状况选择路径。2、GPS导航系统对道路一定未来时间有预测能力。3、司机没有个人爱好选择，只是根据导航系统所提供的所花时间最短的道路来行使。4、同上题一样，所有司机，无论是否用导航系统，司机都对道路非常熟悉，并且所假设的司机如果没有导航系统都会选择距离最短那条路。5实际情况中部分车辆，如公交车不根据GPS路况改变路线，在此假设不存在这种情况。二、模型分析与建立第二问是能否缓解减缓交通堵塞，若能缩短一部分出行者出行时间，同时也不会增加其他出行者的出行时间，系统的总体性能会有所提高就可以缓解该状况。出行者之间不了解其他出行者所能选择的道路策略，但知道其他出行者做出选择后的道路状况，并且出行者选择路径是从个人角度出发，使得自己出行时间最短做出的选择，每个出行者选择路径不是同时进行，所以出行者之间为动态博弈关系，并且信息不完全，为不完全信息动态博弈。在实际情况中，因为出行者很多，策略空间也很大，博弈分为很多周期，并且即使每个出行者都其他出行者每个周期结束时的行动，由于难以确定对方所属类型，我们不能检验后续策略是否为Nash均衡。局中人属于何种类型被假设为由“自然”赋予的概率而