其他数模-与一等

第三届“ScienceWord杯”数学中页参赛队伍的参赛号码：（请各个参赛队提前填写好竞赛（由竞赛送至评委团前竞赛评阅（由竞赛评委团评阅前进行2010年第三ScienceWord数学中国 目：交通网络中Braess悖论的实证分析及其多主体模：Braess悖论；交通规划；非合作均衡；多主体模拟 要Braess悖论局部的改善反而可能降低交通网络的整体效率。本文构建Braess悖论，并且结合实证数据在市展览馆路处发现了Braess悖论。进一步，采用多主体建模的方法GPSGPS，否则会适得其反。另外发现GPS导航系统在提高整个系统效率的同时能够，参 （参 （ 填写BBraessparadoxdemonstratedasituationinwhichanewaddedtoimprovethetrafficcondition,resultsinaworseone.Inthispr,roposedanon-cooperativemodeltodetecttheparadox.EmpiricalinvestigationssuggestthatsuchparadoxdoeshappenaroundZhanLanGuanRoadinBeijing.Moreover,aMulti-AgentbasedmodelisbuilttoinvestigatewhetherGPScanimprovethetrafficcongestion.ThesimulationresultsindicatethatGPSwillobtainsignificantprogresswhenitsatisfiesacertainconditiondeterminedbythecurrenttrafficnetworkitself.Meanwhile,itispossibleforGPSinourmodeltofindouttheroadswidelyused.Thiscanprovidescientificsupporttothetrafficmanagement问题的重城市的机动车数目有了明显的增加，市机动车数量近400万[1]。那么如何使得城市的交通网络更加有效率呢？地理学家曾经花费了很多的笔墨区域1968年意大利数学家DietrichBraess在他的一篇中提出了在交通网络中存在悖论[4]。通常情况下，人们在直观上认为在原本拥挤的道加入一条新的道路可以使得系统的效率增加，但是Braess证明了在某些情况下，在效率。这一违背常理的现象称为Braess悖论。这法对现实产生了深远的意论的重要部分[5,6,7]。由于这一悖论的存在，也使得重新考虑是否应该在1RBraessPQPQOQRPQOPR,OQROPQRQ降了，这与的违背。1：BraessBraess悖论。路)，交通拥堵的情况是否由BraessBraess悖论引起了这一路段的交通拥堵。2，如果广泛使用能够反映当前路GPS基本假设和符号说i.假设通过道路所需时间为tijaijbijfij，其中tij为道的通行时间，aij为道的交通时间,反应了道路的长短；bij为道路

fij表示单位时间内通过道 的车流量

fk和tk分别表示经过路径k的车流量和通过路径k1T和T12问题一模型的建立与求(一)模型的建，，Braess糕。对于图1所表示的交通网络在实际中并不常见，针对这个问题考虑如市的交通网络。在这个问题中只对这样的小单元进行分析，这样的分，，析可以推广至市二环的所有道路2：实际交通系统中常见的交通网络模型图，左图表示没有加入新道路时的状态，右图表示假设有Q辆车从起点OD2中的左图，即在原始交通RQOD和OSD，经过路径OSDtOSDtORtRStSDtORaORbORt t RS SD经过路径OPD的需要的时间如下：tOPD tPQtQD，其tOPaOPbOPtPQaPQbPQ QD定义路径OSD1OPD2t1tORtRSt2tOP Qf 2RQ路(R,Q)，此时从起点O到终点D有三条路线OPQD，ORSD和ORQD。经过路径ORQD的时间如下：tORQDtORtR D，其中tORaORbORtRQaRQbRQfRQ QD12ORSDORQD2OPQD3t1tORtRSt OR t t3tOP Qff (二)模型求在求解这个问题之前，回顾的假设：都是自私的，每一个人都只考只需要求解出整个系统的用户均衡然会导致系统的不稳定从而使得新的解向均衡解靠拢。系统的均衡解是t1t2 1)的均衡：没加入新道路的情在没有加入新道路的情况下，系统在t1t2时达到均衡，即所有在对径1和路径2的选择上没有偏好。如果不满足这个条件，在所用时间较长的路径t1f1f2t f f st.

OR

RS

SDt

f

PQ

QDf,f,f 2)的均衡：加入新道路之后的情在，考虑如果加入新的道路(R,Q)之后会发生什么，图2的右图表示了上类似地，系统在t1t2t3时达到均衡，即所有在路段选择上没有偏好t1t2f1f2f3t1aORbOR(f1f2)aRSbRSf1aSDbSDst.t2aORbOR(f1f2) bRQf2aQDbQD(f2f3t f (ff PQ f,f,f 在以上的两个情况中，只考虑fk0的情况，如果出现fk0，则认为总通行时间T1f1t1f2t2；在加入新的道路(RQ之后，系统的总通行时间为T2f1t1f2t2f3t3，，

交通网络的压力，Braess悖论不存在；当T1T2时，则认为新增道路使得个交通网络更加拥堵，Braess3)实际问题的求解分析连接二环路阜成门街的局域交通网络实际交通网路如下图3，1。同上面模型，假设有Q辆车从OD31为ORSD，2为ORQD3为OPQD。长度(L)(延迟系数1.阜成门.6.7.1表1：市某区域局部交通网络路2图3：表1的数据所对应的市实际交通网络RQRQ前后整个交通网络的RQfi与总车流量Q1数据来源：等，非合作交通网络中的Braess悖论及其避免，公路交通科技，21卷第5期：92- 来源 f10.56Q20f 0.44QfRQfi与总车流量Qf10.58Qf ff 0.45Qf通过还可以求得在两种情况下系统的总通过时间之差TT1T2与总车流量Q的关系。另外，由加入道路RQ后各路线的车流量fi与总车流量Q关系，我们可知当Q149f1或者f3小于0；当Q5338f2小于0。所以在此先考虑149Q5338RQ后各路线的车流量fi随总车流量Q的变化曲线图以及新增道路前后系统的总通过时间之差T随总车流量Q的变化4所示：

（a）每条路线分布的车流量变路线1路线1车流f1路线2车流f2路线3车流量各路各路线车流量f(辆/小时0 总车流量Q（辆/小时(b)新增道路前后总时间差的变时间t时间t（秒

车流量Q（辆/小时i4：(a)f随着车流量Q的变化趋势,i2为新增路线(b)图表示新增道路前后系统总时间差T与车流量Q通过图(a)Q而减小，由此说明新增道路并没有很好的分流车辆，缓解交通。通过图(b)可以0通，反而更加拥堵，Braess当Q5338时，f2小于0 所考虑的均衡情况不存在，此时系统要达最优时f2等于0，即新增道没有车辆通行，而原有路线1，3上的车流量新增道路是浪费的，Braess悖论存在。当Q149时，由于总车流量Q太小，实际中不大可能出现这种情况，所以(三)结利用2007年10月1日上半天二环的车流量和平均速度的数据统计了二环路阜成门街的车流量3，数据描述的是，以两分钟作为间隔观察通过某一截面的车流量以及车时速。假设当车时速小于40km/h时道路处于拥堵状态，这样依据车速可以把数据分为两个时段，一个时段表示交通处于通畅状态，另一个时段表示交通处于拥堵状态。在对数据进行初步处理之后，对二环路阜成门街的通畅时和拥堵时的车流量分别求算术平均，得出在阜成门街通畅时和拥堵时每分钟通过截面的平均车辆数分别36辆和393f3与Q的关系可以估计出Q4926辆/12758辆/小时，由前面的分析结果可知，这一部分交通网络存Braess悖论。问题二模型的建立与求(一)模型的建多主体模型由于其独具的优越性，近年来受到了不同领域的学者和的模型能够考虑到之间的异质性并且方便行为与整体表现行为之间的关系。鉴于此，引入多主体建模的方法对本问题进行。考虑到的实际交通网络情况使用如图5所示的网格对的交通网络进行抽象。图中的每一个结点代表一个路口，假定从任何一个路口4条线路，如果正好处在边界则仅仅存在两条可能的高速公路。为了体现现实中各条线路之间的异质性假定在网络中存在如图5所示的两车辆在路口SSA,SB,SC,SD中的和SD之中，也就是说在每一步的选择都应该使得更加靠近终点5：为了广泛使用可以反映目前交通拥堵情况的GPS导航系统是否能够缓解交通阻塞，首先需要明确GPS导航系统能够提供怎样的导航信息。在模型中，假定使用GPS导航系统只能够提供给当前时刻当前路口和下一路口之间的车辆数。以图5为例，当前处于路口S，如果使用GPS，航将会获得SA,SB,SC,SD四条线的车辆数目。此假，GPS导航不完全符合，但是仍然具有相当的合理性。因为现实中GPS总是实时更新的所以能够对决策起到主要作用的将是在假设中给出的在的模型中，每一个车辆看成一个主体(gent)，整个网络中存11(i,j通过时间为tijaijbijfija示没有车辆阻塞的情况下通过该线路所需要的时间，b表示受阻系数fij表示通条线车流量成正比。如果S(x,y)处的车辆的目的地是T(x0,y0)，那么引GPS后的策略可以表示成为如下的模型：X

Min{tSA,tSB,tSC,tSDA,B,Ctab其中dST

xx0

yy0

ij当不存在GPS进行导航的时候，不能够估计出任意线的车辆总数，因X

A,B,Ct (二)模型的初始条件与仿5所示的两条高速环线，给定在该高速环线上aH0.5，其他线路上aL2，并且所有的线都有b0.02。初始时刻将N1辆车随机分布在网络的格点上，并且令每一车辆的终点坐标为(N0,N0)。N025N166GPS和GPSGPSGPSGPS是否有效以及在多大少，引入GPS并不能够提高整个网络的效率，甚至可能会出现一定程度上适得其反的效果。认为出现此种情况的原因可能在于GPS导航系统使得交通系统中的做出了相同的决策从而在一定的程度上了预期自我GPS导航系统，车辆也能够较快地到达终点。然而，GPS的情况相比，引GPSGPSGPS6的右面部分从另一个侧面反映了这一结GPSGPS的情况。没有GPS存在没有GPS存在 平均时间平平均时间平均速度 5001000150020002500车辆

5001000150020002500车辆图6N025，503000时，整个交通网络的运行效率变化情况。当需要改善交通状况的时候，一个自然的想法是扩建交通网络。因而GPSN12000N077左面部分仍然表示所有的车辆到达终点所需平均时间的变化情况由于在模N0的增加，所需平均时间也将不断增加。但是在此过程中仍然可以发现引入S能够改善整个网络的运行效率。图7右面部分N0的导航，在网络规模增加的最开始反而会造成更大交通阻塞，此种情况正是Braess悖论的发生所致。因为网络规模的增加，将会使得车辆到达终点的路径增加，也就是为车辆提供了更加丰富的选择，由于此时没有GPS信息的导航，作为单个车辆并不了解网络的全局信息，并且都是自私的，他们只考虑自己的加的路径充分多的时候，发生Braess悖论的可能性将会。此时，整个交通GPSBraess悖论。平均速度随着网络规模的增加出现不断上升的趋势。这一模拟结果，为提出了解决Braess悖论的两种思路：一种简单的方法是引入GPS，为提供相关的交通信息；另外一种思路是，扩建足够多的道路，从而降低Braess悖论发生的可能性。相比较而言，显然前者更经济转折没有转折没有GPS存在 平均时间平平均时间平均速度 00 0 网络规网络规图7N12000N05201时，整个交通网络运行效率变化情况。在整个交通网络的运行效率时，所有车辆的最后到达时间也是一个十谓的慢变量决定快变量的过程。具体的模拟结果如图8所示可以发现所有GPS后的GPS将会收到显著的改善效果。。没有没有GPS存在最后最后到达时间 车辆8：为了改善局部交通能力而增加投入最终却使得整体的交通状况更加这Braess悖论引起广泛关注的原因。因此，为了节约成本总是希望在承载同样的车流量条件下网络中连边的数量越少越好。既然广泛使用GPS之后能够提高整个过程的效率，那么是否在提高运输效率的同时也能够更节约成本呢？针对这一问题使用同样的模型对此行了初步地分析。考虑随着网络承载量的N1不断增们现有的交通网络否得到了充分地利用。从图9可以看出，使用GPS之后网络的公路空置率始终高于不使用GPS的情况，也就是说使用GPS能够以更小规模的网络承载相同的车流量。综合前面得出的结论可以知道，在一定量的车流量下，使用GPS将会显著提高效率和节约成本。没有GPS没有GPS存在00公路公路闲置率000 车辆图9N025N1(三)模型参数分本文仅仅选取一个有代表性的重要参数aH进行，此参数衡量了修建的高速环线上的运行速度。由于模型初始给定的一般 的相应参数为aL2因此在区间[0.5,2]上对

进行 选取网络规N12500,N025。相应的模拟结果如下图所示。当aH0.5时，等价 文中设定的模型参数，显然此条件下的模拟结果和前文中结果一致。aH不断增随着aH不断增加，整个网络的运行效率在逐渐下降；另外可以看出没有GPS和存在GPS两种情况下的效率下降速度几乎相同。换一个角度观察，发现当aH0.5GPSaL2GPSGPS

没有GPSS存在GPS平均时平均时间平均速度

10aH(四)结。通过以上的多主体模型知道如果当前的交通网络满足一定条件后广泛使用GPS导航系统确实能够显著缓解整个交通网络的拥挤程度具体到市的GPS会适得其反构建的模型的一个重要特点是能够再现。，Braess7降低整个交通网络的运行效率。因此，只要根据实际情况合理估计参数提出的多主体模型可以检验现有交通网络中的某些堵塞拥挤情况是否来源于Braess悖论。，，与此同时，当网络中的车辆总数超过测算阈值时，引入GPS能够在较大程度上缓解整个网络的交通状况。进一步还发现引入GPS在提高整个网络运行，模型总体的结论及政策建，通过以上对模型一的求解可以得出在市二环路(包括二环路)以内确实存在Braess悖论，展览馆路就是这样一个例子，这个事实提醒，在考虑优化交通网络系统时要慎重考虑道路参数对实际情况的影响。通过对模型二的求解得出合理使用GPS的确能够帮助优化当前存在的网络引导交通流将紧缺的资源重点放在高效线另外可以在模型的基础上进行扩展在有限的前提下采用何种方式对现有网络进行改建能够最大幅度地提高现有交通网络运行效率，这一扩展将具有很强的现实意义。， .cn，晚报，2009年12月15日[2]，，Braess模型与城市网络的空间复杂化探讨，地理科学，266期：659-WilsonAG,ComplexSpatialSystems:TheModelingFoundationsofUrbanandRegionalysis,Singapore:PearsonEducationAsiaP td,2000.BraessD,AParadoxonTrafficNetworks,ruhr-uni-bochum.de/,ArnottR,SmallK,TheEconomicsofTrafficCongestion,AmericanScientist,Vol.82:446-455,1994.LamWHK,EffectsofRoricingonSystemPerformance,TrafficEng.Control,Vol.29,No.12:631-635:1988.PasE,PrincipioS,Braess’paradox:SomeNewInsights,TranspnRes.-B,Vol.31,No.3:265-276,1997.，，非合作交通网络中的Braess悖论及其避免，公路交通科技5期：92-main.m文件的代fori=1:NT%%N1=50.*t0;N1=2-holdonholdoffholdonholdoff%%hold%%hold nogps.m文件的代码Function[meannogps,longesttimenogps,averagevelocitynogps,edgex,edgey]=me %numberofcarsinthetransportnetworkglobalN0globalSOURCEXglobalSOURCEYglobaldistance=zeros(1,N1);%离目标点的当前距离dis=zeros(1,N1);velocity=zeros(1,N1);thevelocityofeachagenttime=zeros(1,N1);%记录每一车辆用时globalcorrxglobalfori=1:N0forifrem(i,(N0-1)/4)==1||rem(i,N0-1)==0||rem(j,(N0-1)/4)==1||rem(j,(N0-1))==0 %没有交通阻塞时候所需要的时间横向边 %没有交通阻塞时候所需要的时间纵向边corrx(i,j)=2;corry(i,j)=2;%没有交通阻塞时候所需要的时间纵向边globalb%给定初始时刻agentforsourcex(k)=randint(1,1,[1,N0-1]);%randomchoosethesourceofagenti 下3：左4：右； T=400;%upperbondoftime %timestep,forwecouldnothavethecontinioustimefort1=0:0.02:T %timestep0.02ifNT<N1 fori=1:N1dis(i)=abs(sourcex(i)-x)+abs(sourcey(i)- %whetherthecurrentpositionofagentiisclosetothestopifso,%dicidewhichwaytochooseifabs(ceil(sourcex(i))-sourcex(i))<crit&&abs(ceil(sourcey(i))-sourcey(i))<crit ifdis(i)>0D(1)=abs(sourcex(i)-x)+abs(sourcey(i)+1-y);%往上走ifsourcey(i)+1<=N0elseD(1)=100000; D(2)=abs(sourcex(i)-x)+abs(sourcey(i)-1-y);%往下走ifsourcey(i)-1>=1elseD(3)=abs(sourcex(i)-1-x)+abs(sourcey(i)-y);%往左走ifsourcex(i)-1>=1 y);%往右走ifsourcex(i)+1<=N0 forj=1:L%GPSisnotallowedhere,sothatwhenmakedecisionswedonotknowexactlythevalueofNUMandweassuMiszero%However,whenwecaculatetherealizedrequiredtime,weshouldcount%onethingisthat,weshouldnoticethetimewhencarsarrivethenextstationswitchtempt1caseA=sourcey<=sourcey(i)+1;ifsourcey(i)==N0-1casecasecaseifsourcex(i)==N0-1

index1=find(tn-min(tn)==0);%makechoicewithoutgps %realtimerequired thesameasthecasewithgps %agenthavedifferentvelocity%updatethecurrentpositionaccordingtothechoiceswitchtemptcase1%recordwhichhighwayagentienter,andupdatethenumber%carspassedthathighedgey(sourcex(i),sourcey(i))=edgey(sourcex(i),sourcey(i))+1;caseedgey(sourcex(i),sourcey(i))=edgey(sourcex(i),sourcey(i)-1)+1;case3edgex(sourcex(i),sourcey(i))=edgex(sourcex(i)-1,sourcey(i))+1;sourcex(i)=sourcex(i)-

caseedgex(sourcex(i),sourcey(i))=edgex(sourcex(i),sourcey(i))+1;switchtempt3case1case

case3case4 %ifallthecarshavearrivedtothathenbreak.stoprunningthe withgps.m的代globalN0globalSOURCEXglobalSOURCEYedgexwithgps=zeros(N0-1,N0);%记录每一条横向边的通行状况edgeywithgps=zeros(N0,N0-1);%记录每一条纵向边的通行状况globalcorrxglobalcorryglobalbglobalDISTANCEdis=zeros(1,N1);velocity=zeros(1,N1);%thevelocityofeachtimewithgps=zeros(1,N1);%下3：左4：右； T=400;%upperbondoftime %timestep,forwecouldnothavethecontinioustimefort1=0:0.02:T %timestep0.02ifNT<N1 fori=1:N1dis(i)=abs(sourcex(i)-x)+abs(sourcey(i)- %whetherthecurrentpositionofagentiisclosetothestopifso,%dicidewhichwaytochooseifabs(ceil(sourcex(i))-sourcex(i))<crit&&abs(ceil(sourcey(i))-sourcey(i))<crit ifdis(i)>0D(1)=abs(sourcex(i)-x)+abs(sourcey(i)+1-y);%往上走ifsourcey(i)+1<=N0elseD(1)=100000; D(2)=abs(sourcex(i)-x)+abs(so