基于复杂网络理论的交通网络评估.doc
《基于复杂网络理论的交通网络评估.doc》由会员分享,可在线阅读,更多相关《基于复杂网络理论的交通网络评估.doc(19页珍藏版)》请在咨信网上搜索。
1、 队伍编号 1261 选题 A 徐州工程学院第六届数学建模校赛队长 王双双 队员1 徐超飞 队员2 徐娟 题目 基于复杂网络理论的交通网络稳定性评估 摘 要本文主要研究破坏一对关键相邻站点对交通网络稳定性的影响,利用0-1整数规划,运用复杂网络相关知识,转化为对网络抗毁性的研究。以网络效率建立一个网络服务能力的评价模型,根据网络的度和算法相关知识进行求解。对于问题一,本题根据所给数据用画出公交路线网络图。确定该交通网络的复杂性,基于复杂网络理论对于网络抗毁性的研究,本题以网络效率建立了一个网络服务能力的综合评价模型:根据图论最短路问题采用0-1整数规划,得到各站点邻接矩阵,运用算法求解得出网络
2、站点未中断时网络服务能力,由复杂网络中度的相关知识,求得当在一对相邻点(1522,3674)断开时,网络服务能力下降最大。根据网络服务能力下降幅度模型:,从而得出道路中断后服务能力下降幅度为:1.89%对于问题二,问题的求解模型与问题一基本一致,本题可以将地铁系统看作不可中断的公交路线,采用0-1整数规划对加入地铁后的网络站点邻接矩阵进行修改得到新的矩阵,代入问题一建立的求解模型得到当相邻点(751,3878)断开时网络服务能力下降最大为:1.51%对于问题三,基于前两问模型的求解建立,提出乘客要到达中断站点的前一站点才能得知堵塞信息。且只能重新规划一条最短路径,因此本题只需要对最短路径矩阵进
3、行修正。在问题二的基础上求出在断点断开后,最小网络服务效率,利用上述模型求解得网络服务能力下降幅度 对于问题四,可以看作是对以上问题的总结,将快速公交的快捷性,定义为已知量,即两点间的距离缩短。利用整数规划重新建立一个相邻站点邻接矩阵,求解出引入快速公交系统时的网络服务能力为:=0.1267,建立一个求解网络服务能力增长模型:代入求解得到引入快速交通系统后网络服务能力定性增长了100.1%。关键词 复杂网络 0-1整数规划 网络效率 算法 邻接矩阵一、问题重述1.1背景分析交通网络是一个城市建设、发展、繁荣的关键所在,是承载了整个城市的资源流通的基础。近几年来随着城市的扩张,交通网络需要承载的
4、运输流量也在增大,交通拥堵所带来的时间浪费、环境污染、交通安全等问题也在近几年开始制约城市的可持续发展。对于许多城市,交通拥堵已经成为城市发展的瓶颈之一。面对这些问题,需正确清晰地认识到当前城市交通的现状才能提出正确高效的解决问题的途径。分析公共交通网络路线,有利于减缓交通拥堵问题,为城市的政治经济、文化教育、科学技术等方面提供便利,更有利于城市的建设。城市交通网络正朝网络化规范,网络化建设和网络化运营三个层面发展。并且兼顾轨道交通网络与常规公交网络、对外交通枢纽网络和铁路网络的一体化规划发展。因此无论从基础设施,还是运营管理方面城市轨道交通总是以网络化的形式存在的。 近年来全球恐怖活动日益猖
5、獗,而交通网络作为人流量特别密集的运输载体,具有防护措施薄弱,人流量大,等特点,所以日益成为恐怖分子以及对社会心怀不满人员的最佳施暴地点。除了人为破坏以外,网络系统本身引发的故障,导致系统稳定性下降,甚至造成重大事故也是可能的因此,针对城市交通网络抗毁性和稳定性的研究是十分必要的。1.2问题重述分析公共交通网络路线,有利于减缓交通拥堵问题,为城市的政治经济、文化教育、科学技术等方面提供便利,更有利于城市的建设。城市交通网络正朝网络化规范,网络化建设和网络化运营三个层面发展。并且兼顾轨道交通网络与常规公交网络、对外交通枢纽网络和铁路网络的研究。随着社会的发展,交通堵塞变得越来越频繁,并且对城市公
6、共交通系统造成了很大的影响。大城市的公共交通线路往往很多,所构成的公共交通网络也比较复杂,如何评估网络的稳定性成为设计可靠的公共交通服务的第一步。大城市的公共交通线路往往很多,所构成的公共交通网络也比较复杂,如何评估网络的稳定性成为设计可靠的公共交通服务的第一步。请根据所给数据探讨一下问题:1、画出南京公交路线的网络图。若相邻站点间的道路中断时,请分析这样的几对或一对中断对公共交通网络服务能力的影响,定量分析服务能力(中断时其他站点间公交汽车都正常运行,且乘客在出行前就已经知道中断信息);2、在问题一的情况下加入南京市地铁路线,将发生什么情况?并对比问题一,分析地铁对于城市交通网络的稳定性的影
7、响;3、画出完整的城市公共交通系统网络图(包括地铁和公交系统),并分析在相邻站点间的道路中断时,对公共交通网络服务能力的影响。若有影响,可用定量分析下降的服务能力(中断时其他站点间公交汽车都正常运行,且乘客只有抵达拥塞站点的前一个站点时才能得知拥塞信息,并根据自己的出行需求考虑另择线路);4、定量分析引入快速交通系统后,公共交通网络服务能力的稳定性以及服务能力是否有显著改善。二、问题分析2.1对于问题一的分析本题要求几对或一对相邻站点中断时,分析某对点中断时服务能力下降最显著和定量解释下降的交通网络服务能力。针对本题,首先要建立一个交通网络服务能力的综合评价模型。交通网络的服务能力可以看作是道
8、路的连通性和抗毁性的统一,即道路的连通性越好,网络的抗毁性越好,服务能力也就越好。城市公共交通网络是一个复杂系统,可以把该交通网络抽象为一个复杂网络,可以参考文献1。本题应属于研究交通复杂网络的静态抗毁性,即研究节点和边在失效情况下的网络结构变化。因此本题可以转化为对城市交通网络抗毁性的评估。交通网络抗毁性的测度指标有特征路径长度(即最短平均路径)和网络效率等,经过对这两个指标的简单分析评估,当选择特征路径长度作为测度指标。会出现当点或边在受到攻击可能会出现孤立的点,这些点和其他任意站点都不相连。这样该点到任意站点的最短路径都为无穷大,从而导致最终的测度指标特征路径长度也为无穷大。很明显会影响
9、整个网络的测度评价,基于这样的特殊情况,本文选择网络效率作为交通网络服务能力的测度标准。进而建立一个下降的服务能力的求解模型。只要定量的求出某对相邻点中断时的网络效率且使网络效率下降最多,最后代入建立的下降能量求解模型,就可完成对问题一的解答。而对于服务能力求解模型,本文需用到了算法求解任意两站点最短距离。所以同时要建立一个算法模型。2.2对于问题二的分析本题要求在问题一的基础上加入南京市地铁线路,分析地铁路对网络服务能力的影响。地铁线路总是能够正常运行的,本文可以将地铁看成一个不会中断的公交线路,每个地铁站点以及相邻地铁和对应换乘的的公交站点看成是相邻连通的路线。即把地铁对应的公交站点都看作
10、是互相连通的站点,本文参考了文献2。根据问题一中求解得到的0-1邻接矩阵,根据站点之间的连通情况进行修改。本题建立的求解模型与问题一基本一致,两者本质没区别,根据前后求得的网络服务能力,就可对下降的服务能力进行综合评价。2.3对于问题三的分析本题与第二题类似,都要同时考虑公交和地铁系统,并对一对相邻站点的中断作综合分析。但是针对本题,乘客要到达拥塞站点的前一站才能得知该路线堵塞,所以乘客不能提前计划好最短到达目的地路线。乘客只能到达拥塞的前一站点,然后再以改点为起点,原目的地为终点重新选择一条最短路线,本文参考文献5。如果这样,该网络中任意两站点的最短距离之和会变大。即问题二求得的任意两个站点
11、间的最短路径不在适用于本题,本题需要根据要求重新建立最短路径矩阵。根据得到的最短路径矩阵求出相邻站点发生中断时的服务能力,最后根据前文建立的网络能力下降幅度评价模型来对本题进行定量分析。本题需要用到第二问求得的使网络服务能力下降最大的相邻断点,由于本题条件与第二题基本相似,只是对于乘客是否预先得知站点拥塞发生改变。本题只需要将断点断开后的任意两点最短距离矩阵做出修改,在第二题的基础上来求出网络服务能力的下降幅度。2.4对于问题四的分析题目要求研究快速交通系统对公共交通网络服务能力的稳定性以及服务能力的影响,快速交通系统是一种介于快速轨道交通和常规公交之间的新型大运量公共客运体系。本题与上述题目
12、相似,仍是分析公共交通网络服务能力,只是本题加入了快速交通系统。而快速交通系统的优点是速度快,容量大,可靠性强,行驶速度可以达到常规公交的2倍。可以在前面题目的基础上建立模型把重要的公交路段换为快速交通系统,相邻站点之间减少的时间可以按比例看作相邻站点间距离的减少。从而修改相邻站点间的邻接矩阵。求出网络效率和对效率影响最大两相邻断点,与前面几题对比找出网络稳定性和服务能力的变化程度。三、模型假设结合本题的实际,为了确保模型求解的准确性和合理性,我们排除了一些未知因素的干扰,提出以下几点假设:1、假设只以路径为评价标准,不考虑换乘和换乘时间对该网络服务能力的影响;2、假设从地铁站点到换乘的公交站
13、点所需时间忽略;3、假设各站点之间的间距相等,行车距离大小由经过站点数来衡量;4、假设不考虑天气状况等不确定因素对交通的影响。四、符号说明为了便于问题的求解,我们给出以下符号说明: 总的站点数 度分布概率 网络节点的度 邻接0-1矩阵任意两点之间最短距离交通网络服务能力下降幅度 任意两站点最短距离矩阵 交通网络服务能力(网络效率)五、模型的建立与求解经过以上的分析和准备,我们将逐步建立以下数学模型,进一步阐述模型的实际建立过程。5.1问题一模型的建立与求解5.1.1问题一模型的建立根据给出的南京市交通网络路线,运用画出南京市部分公交网络图如下:(具体绘图代码见附录)图1 南京市部分公交路线网络
14、图由图像可知该交通网络错综复杂,属于一个复杂系统。即本题需要应用到复杂网络知识,要求根据已有的公交线路站点数据,定量分析交通网络服务能力。本题首先引入了几个复杂网络中的概念。对于复杂网络,钱学森先生给出了以下严格定义:具有自组织,自相似,吸引子,小世界,无标度中部分或全部性质的网络称为复杂网络。对于两个交通网络抗毁性的测度指标定义,1、复杂网络的特征路径长度(平均最短路径长度)特征路径长度被定义为待研究网络中任意点最短路径之和的平均值,它反映了网内部两节点彼此连通的能力。任意两个节点之间的最短距离的最大值称为该网络的直径。特征路径长度定义公式如下:2、网络效率 网络效率可以用来衡量网络中点与点
15、之间的信息沟通程度,网络效率在一定程度上被认为和特征路径长度成反比。假设两个节点离得越近,信息在这两点之间就越容易传播,因此两个节点之间的效率可以定义为这两点之间距离的倒数:与平均路径长度相比,即使两个节点之间没有通路相连,仍旧可以定义这两点之间的效率.在非联通的网络中,但是这两点的路径长度则为无穷大。以下给出了网络效率的定义式:前文针对问题一的分析已经说明了这两个指标测度的优缺点。因此本题选择网络效率作为交通网络稳定性的评价指标。针对本题对于交通网络的服务能力,我们给出定义:公共交通网络的服务能力可以抽象为该网络的稳定性和抗毁性的统一,网络效率是衡量该网络正常运行的重要指标。网络效率可以看作
16、是公交线路稳定性在整个网络上的具体表现。网络效率越大,说明网络稳定性越好,交通网络的抗毁性也越强。因此针对本题,把交通网络的服务能力定义为网络效率。从而对问题进行定量分析。要想求出交通网络的服务能力就要对本题已给数据(南京市公交路线)处理,由所给数据可知,整个线路分为3类,经过统计可得该公交系统一共有站点3957个,车次520个,520个车次一共可以分成1040个来回路线。其中有路线最多经过86个站点。因此对于原始数据,可以建立一个1040*86的矩阵,行数代表路线车次,列代表经过的站点。求解时只需求解得到行数,则对应的车次很容易求得。将其导入,以方便问题的编程求解。根据上述已经导入的数据矩阵
17、,建立一个0-1整数规划模型来求解相邻路径矩阵,以两个公交站点之间是否有通路为突破口建立一个0-1相邻路径矩阵: 该0-1邻接路径矩阵为一个3957的0-1站点邻接矩阵(0-1邻接矩阵建立代码见附录),用画出各站点网络连接情况的统计学图形如下(具体绘图代码见附录):图2 南京市交通网络的统计学图形由该图可以定量的看出,该交通网络一共有11842条相邻联通的路线,图中有比较明显的各点连成的曲线由6条,说明有6个路线车次对整个网络的影响比较大。求解任意两点之间最短距离用到经典的模型算法。该算法核心思想是通过一个图的权值邻接矩阵求出它的两点之间的最短路径矩阵。该算法的数学模型如下,即状态方程为:其中
18、表示到的距离。即若最短路径经过点,则,若最短路径不经过点,则值不变,以此递推就可以得到任意两点之间的最短距离。首先由所给数据建立一个邻接矩阵,若两点之间无直接路线,则用无穷大表示即,利用矩阵,运用编写算法,就可以求得任意两个站点之间的最短距离,从而求得该公交网络中各站点的最短路径矩阵(算法求最短路径代码见附录 ):根据以上得到数据,我们建立一个网络服务能力的综合评价模型如下:本题要求定量分析几对或一对站点中断时,下降的交通网络服务能力。根据站点间未发生中断和发生中断时的网络服务能力 ,建立如下的交通网络服务能力下降幅度评价模型如下:对于相邻断点的求解,其中当两个相邻站点发生中断时,此时,再利用
19、算法求出此时的任意两站点之间最短距离。在这里要求的点太多,很难将如此巨大的数据求解出来,所以本文选用其他标准来对关键相邻点进行确定。本文引入了复杂网络中度的概念,一个节点的度定义为该节点与其他节点连线的数量,度可以看作是描述网络局部特征的统计量,一般来说,度反映的是该节点的重要程度,即度越大,节点也就越重要,反之亦然。因此我们可以根据各点度的大小,筛选出几个相邻点,分别求出他们断开时,网络效率的大小。选取一个让此时网络效率最小的相邻点。(各节点度的大小求解代码见附录)代入网络服务能力评价模型,求得此时的网络效率。再代入求解下降幅度的模型,就可对问题进行解答。5.1.2问题一模型的求解运用求出3
20、957个站点之间在未发生相邻站点中断的情况下的最短路径矩阵,并带入上述模型公式求得在未发生站点中断情况下的网络服务能力为:=0.0633根据上述建立的模型可知,当两个相邻站点发生中断时,此时,用求出此时的网络服务能力。根据将得到的度筛选出几对相邻点,求出对应的网络服务能力进行比较,筛选得到当一对相邻站点(1522,3674)中断时网络服务能力最小,为=0.0621,最后将得到的数据代入服务能力下降幅度评价模型得下降的服务能力为:1.89%5.2问题二模型的建立与求解5.2.1问题二模型的建立 本题建立在问题一的基础上,问题的求解方法基本一致。地铁线的引入只是增加了0-1路径邻接矩阵的建立。本题
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 复杂 网络 理论 交通 评估
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。