基于复杂网络理论的交通网络评估

下载后可任意编辑 队伍编号 1261 选题 A 徐州工程学院 第六届数学建模校赛 队长 王双双 队员1 徐超飞 队员2 徐娟 题目 基于复杂网络理论的交通网络稳定性评估 摘 要 本文主要讨论破坏一对关键相邻站点对交通网络稳定性的影响，利用0-1整数规划， 运用复杂网络相关知识，转化为对网络抗毁性的讨论。以网络效率建立一个网络服务能力的评价模型，根据网络的度和算法相关知识进行求解。 对于问题一，本题根据所给数据用画出公交路线网络图。确定该交通网络的复杂性，基于复杂网络理论对于网络抗毁性的讨论，本题以网络效率建立了一个网络服务能力的综合评价模型： 根据图论最短路问题采纳0-1整数规划，得到各站点邻接矩阵，运用算法求解得出网络站点未中断时网络服务能力，由复杂网络中度的相关知识，求得当在一对相邻点（1522，3674）断开时，网络服务能力下降最大。根据网络服务能力下降幅度模型： ， 从而得出道路中断后服务能力下降幅度为：1.89% 对于问题二，问题的求解模型与问题一基本一致，本题可以将地铁系统看作不可中断的公交路线，采纳0-1整数规划对加入地铁后的网络站点邻接矩阵进行修改得到新的矩阵，代入问题一建立的求解模型得到当相邻点（751,3878）断开时网络服务能力下降最大为：1.51% 对于问题三，基于前两问模型的求解建立，提出乘客要到达中断站点的前一站点才能得知堵塞信息。且只能重新规划一条最短路径，因此本题只需要对最短路径矩阵进行修正。在问题二的基础上求出在断点断开后，最小网络服务效率,利用上述模型求解得网络服务能力下降幅度 对于问题四，可以看作是对以上问题的总结，将快速公交的快捷性，定义为已知量，即两点间的距离缩短。利用整数规划重新建立一个相邻站点邻接矩阵，求解出引入快速公交系统时的网络服务能力为：=0.1267,建立一个求解网络服务能力增长模型： 代入求解得到引入快速交通系统后网络服务能力定性增长了100.1%。 关键词 复杂网络 0-1整数规划 网络效率 算法 邻接矩阵 一、问题重述 1.1背景分析 交通网络是一个城市建设、进展、繁荣的关键所在，是承载了整个城市的资源流通的基础。近几年来随着城市的扩张，交通网络需要承载的运输流量也在增大，交通拥堵所带来的时间浪费、环境污染、交通安全等问题也在近几年开始制约城市的可持续进展。对于许多城市，交通拥堵已经成为城市进展的瓶颈之一。面对这些问题，需正确清楚地认识到当前城市交通的现状才能提出正确高效的解决问题的途径。分析公共交通网络路线，有利于减缓交通拥堵问题，为城市的政治经济、文化教育、科学技术等方面提供便利，更有利于城市的建设。城市交通网络正朝网络化法律规范，网络化建设和网络化运营三个层面进展。并且兼顾轨道交通网络与常规公交网络、对外交通枢纽网络和铁路网络的一体化规划进展。因此无论从基础设施，还是运营管理方面城市轨道交通总是以网络化的形式存在的。 近年来全球恐怖活动日益猖獗，而交通网络作为人流量特别密集的运输载体，具有防护措施薄弱，人流量大，等特点，所以日益成为恐怖分子以及对社会心怀不满人员的最佳施暴地点。除了人为破坏以外，网络系统本身引发的故障，导致系统稳定性下降，甚至造成重大事故也是可能的因此，针对城市交通网络抗毁性和稳定性的讨论是十分必要的。 1.2问题重述 分析公共交通网络路线，有利于减缓交通拥堵问题，为城市的政治经济、文化教育、科学技术等方面提供便利，更有利于城市的建设。城市交通网络正朝网络化法律规范，网络化建设和网络化运营三个层面进展。并且兼顾轨道交通网络与常规公交网络、对外交通枢纽网络和铁路网络的讨论。 随着社会的进展，交通堵塞变得越来越频繁，并且对城市公共交通系统造成了很大的影响。大城市的公共交通线路往往很多，所构成的公共交通网络也比较复杂，如何评估网络的稳定性成为设计可靠的公共交通服务的第一步。 大城市的公共交通线路往往很多，所构成的公共交通网络也比较复杂，如何评估网络的稳定性成为设计可靠的公共交通服务的第一步。请根据所给数据探讨一下问题： 1、画出南京公交路线的网络图。若相邻站点间的道路中断时，请分析这样的几对或一对中断对公共交通网络服务能力的影响，定量分析服务能力（中断时其他站点间公交汽车都正常运行，且乘客在出行前就已经知道中断信息）； 2、在问题一的情况下加入南京市地铁路线，将发生什么情况？并对比问题一，分析地铁对于城市交通网络的稳定性的影响； 3、画出完整的城市公共交通系统网络图（包括地铁和公交系统），并分析在相邻站点间的道路中断时，对公共交通网络服务能力的影响。若有影响，可用定量分析下降的服务能力（中断时其他站点间公交汽车都正常运行，且乘客只有抵达拥塞站点的前一个站点时才能得知拥塞信息，并根据自己的出行需求考虑另择线路）； 4、定量分析引入快速交通系统后，公共交通网络服务能力的稳定性以及服务能力是否有显著改善。 二、问题分析 2.1对于问题一的分析 本题要求几对或一对相邻站点中断时，分析某对点中断时服务能力下降最显著和定量解释下降的交通网络服务能力。针对本题，首先要建立一个交通网络服务能力的综合评价模型。交通网络的服务能力可以看作是道路的连通性和抗毁性的统一，即道路的连通性越好，网络的抗毁性越好，服务能力也就越好。城市公共交通网络是一个复杂系统，可以把该交通网络抽象为一个复杂网络，可以参考文献[1]。本题应属于讨论交通复杂网络的静态抗毁性，即讨论节点和边在失效情况下的网络结构变化。因此本题可以转化为对城市交通网络抗毁性的评估。交通网络抗毁性的测度指标有特征路径长度（即最短平均路径）和网络效率等，经过对这两个指标的简单分析评估，当选择特征路径长度作为测度指标。会出现当点或边在受到攻击可能会出现孤立的点，这些点和其他任意站点都不相连。这样该点到任意站点的最短路径都为无穷大，从而导致最终的测度指标特征路径长度也为无穷大。很明显会影响整个网络的测度评价，基于这样的特别情况，本文选择网络效率作为交通网络服务能力的测度标准。进而建立一个下降的服务能力的求解模型。只要定量的求出某对相邻点中断时的网络效率且使网络效率下降最多，最后代入建立的下降能量求解模型，就可完成对问题一的解答。而对于服务能力求解模型，本文需用到了算法求解任意两站点最短距离。所以同时要建立一个算法模型。 2.2对于问题二的分析 本题要求在问题一的基础上加入南京市地铁线路，分析地铁路对网络服务能力的影响。地铁线路总是能够正常运行的，本文可以将地铁看成一个不会中断的公交线路，每个地铁站点以及相邻地铁和对应换乘的的公交站点看成是相邻连通的路线。即把地铁对应的公交站点都看作是互相连通的站点,本文参考了文献[2]。根据问题一中求解得到的0-1邻接矩阵，根据站点之间的连通情况进行修改。本题建立的求解模型与问题一基本一致，两者本质没区别，根据前后求得的网络服务能力，就可对下降的服务能力进行综合评价。 2.3对于问题三的分析 本题与第二题类似，都要同时考虑公交和地铁系统，并对一对相