交通网络稳定性的评估

1特大型城市公共交通网络的稳定性评估问题摘要本文将站点间的线路选择抽象为图论最短路模型采用0-1整数规划，得到相邻站点的路径矩阵A。利用复杂网络原理，引入网络的度k和平均最短路径长度L的概念，并定义公共交通网络的服务能力为网络的平均最短路径长度。对于问题1，利用相邻路径01矩阵A，通过最短路的Flody算法，可得出网络中两个站点,ijss之间的最短距离ijd（,1,2,,3957ij……），网络在路线未发生中断的情况下网络的服务能力：011(1)2ijijLdNN当相邻站点(1522,3674)断开时，相对影响系数最大，网络平均最短路径16.7523L，再利用公式0(1)100%LL，求出其相对影响系数2.46%。对于问题2，考虑地铁的影响。对矩阵A进行修正，得到'AAB，其中'ijijijaab。根据问题1的方法求得新路线未发生中断的情况下服务能力'0L和线路发生中断时的服务能力'L。当相邻站点(751,3878)断开时，相对影响系数最大，此时的网络平均最短路径'15.1761L，相对影响系数2.01%。对于问题3，对因下游路线中断而停止使用的线路中的相邻站点进行检索，若中断线路为相邻站点之间的唯一通路，则令''0ija，得到修正后的邻接矩阵''A。解得''15.8325L，''6.02%。对于问题4，乘客到达前一个站点m时才能获知阻塞信息，该乘客只能以m站点为起点，原目的地j站点为终点，避开阻塞站点n重新规划一条最短路径'mjd，依此对最短路径修正，计算出此时的网络平均最短路径'nL最大为17.5632，为去掉1839站点后的平均最短路径值，其相对影响系数'6.96%n。对于问题5，假设出行前就知道中断信息的乘客与抵达拥塞站点前一站才知道中断信息的乘客人数权重比可表示为12:0.5:0.5。得到第n号站点中断的网络平均最短路径：1212''''''nnnLLL解得当第584号站点中断时，''max17.2229nL，''5.12%n。关键词：复杂网络平均最短路径服务能力Flody算法01矩阵2一、问题重述交通拥堵是大城市的顽疾，发展城市公共交通被认为是改善大城市交通环境的有效手段之一。当越来越多的市民依赖于城市公共交通系统时，为市民提供可靠的公共交通服务至关重要。但大城市的公共交通线路往往很多，所构成的公共交通网络也比较复杂，如何评估网络的稳定性成为设计可靠的公共交通服务的第一步。利用2007年全国大学生数学建模竞赛B题《乘公交，看奥运》提供的数据完成以下任务：任务1、仅考虑北京市公交汽车线路构成的网络，假设某时刻有且仅有一对相邻站点间的道路因各种原因发生中断（其他站点间公交汽车都正常运行），且乘客在出行前就已经知道中断信息。请建立合理的数学模型并合理的定义公共交通网络的服务能力的概念，判断是否存在某对（或某几对）相邻站点间的道路，致使公共交通网络服务能力下降最多？若存在这样的道路，请指出并定量的描述下降的服务能力。任务2、在任务1的基础上，如果加入考虑北京市地铁线路，但假设地铁线路总是能够正常运行，那么结果将如何？任务3、在任务2的基础上，如果一对相邻站点间的道路因各种原因发生中断后，经过该道路的公交汽车线路的下游线路都将停止运行（即线路的任意运行方向经过该道路以后的站点都将停止运行），那么结果又将如何？任务4、仅考虑北京市公交汽车线路构成的网络，假设某时刻有且仅有一个站点因各种原因发生拥塞（其他站点的公交汽车都正常运行），且乘客只有抵达拥塞站点的前一个站点时才能得知拥塞信息，并根据自己的出行需求考虑另择线路。请建立合理的数学模型，判断是否存在某个（或某几个）站点，致使公共交通网络服务能力下降最多？若存在这样的站点，请指出并定量的描述下降的服务能力。任务5、在任务4的基础上，如果假设部分乘客在出行前就已经知道中断信息，而部分乘客只有抵达拥塞站点的前一个站点时才能得知拥塞信息，那么结果将如何？3二、模型假设1.不考虑路况、气候、交通管制等外界不确定因素对交通的影响。2.假设相邻公汽站行驶时间是均等的。3.假设相邻地铁站行驶时间是均等的且与相邻公汽站行驶时间相等。4.不考虑乘车费用对网络服务能力的影响。5.假设各相邻公汽站点间距相等，行车总距离的大小可由行车所经过的站点总数衡量。6.以路径为评价指标，不考虑换乘和换乘时间对网络服务能力的影响，即认为为追求最短路程可无限次换乘。三、符号说明符号意义说明A相邻站点的路径01矩阵,mnss两相邻站点,ijss任意两个站点ijd任意两站点的之间的最短路径D各站点间的最短路程矩阵L网络的平均最短路径()Pk网络中节点的度分布分布函数站点发生中断时的相对影响系数I所有由mS到nS站点的公交线路集合4四、模型的建立与求解4.1问题1的模型建立与求解4.1.1问题分析根据题目中给出的公交车线路，利用复杂网络原理对问题一进行分析。引入网络的度和平均最短路径长度的概念。1、复杂网络的度节点is的度定义为与该节点相连接的边的数目，记为k。直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”。网络中节点的度分布情况可用分布函数()Pk来描述。度分布函数反映了网络系统的宏观统计特征，()Pk表示的是一个随机选定的节点度恰好为k的概率分布。有时度分布也可以近似理解为网络中度为k的节点个数占总个数N的比例，即()()/PkfrequencykN其中()frequencyk为网络中节点的度为k的节点数目。通过研究()Pk的分布特点，可以判断出复杂网络的特点，有利于建模。2、复杂网络的平均最短路径长度网络中两个节点,ij之间的距离ijd，定义为连接这两个节点的最短路径上边的数目。网络中任意两个节点之间的距离的最大值称为网络的直径(diameter)。记为D，即,maxijijDd网络的平均最短路径定义为任意两个节点之间的距离的平均值，即：11(1)2ijijLdNN其中N为网络节点数。4.1.2网络的服务能力的定义定义公共交通网络的服务能力为网络的平均最短路径长度。公共交通网络的服务能力在一定情况下可以看作网络的可靠性与抗毁性的统一，平均最短路径长度是公交线路上各点稳定性在整个网络上的体现，平均最短路径长度越短，网络的稳定性越好，公交网络的抗毁性也越好。现要求一对相邻站点间的道路因各种原因发生中断致使公共交通网络服务能力下降最多，即对该网络中的某条重要路线进行选择性攻击，致使该网络的平均最短路径长度增长最大。现给出一组模拟5复杂网络的平均最短路径长度在选择性攻击下，随着中断的重要点数的增加平均路径的变化情况：图1平均最短路径长度随着重要点数中断的变化规律图中，横坐标代表的是在有选择性的攻击下度大的结点去掉的数目占所有结点数的比例，单位为万分之一。由上图可以看出，度数大的结点去掉大约5.6%，后整个系统就快速崩溃。由此可知，选用网络的平均最短路径来描述该公交网络的服务能力是合理的。4.1.3编程时所需数据矩阵的建立根据题中所给的520个车次往返方式的不同，将整个线路分成三类：a：表示“下行”路段是“上行”路段原路返回的车次；b：表示行车路线分为“上行”与“下行”的车次；c：表示环形车次；因为各车次“上行”与“下行”的情况较复杂，特作如下约定：1、对a类车次即“下行”路段是“上行”路段原路返回的车次，如题中的L001：S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710则将其上行路段及下行路段分作两个车次考虑，即将L001分为L001+和L001-两车次，其中L001-为L001+原路返回所经各站，如下：6L001=（L001+）+（L001-）L001+：S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710L001-：S0710-S0128-S03914-S0820-S3524-S0819-S3612-S3885-S0436-S0429-S0392-S0348-S0388-S1914-S06192、对b类车次即行车路线分为“上行”与“下行”的车次，如题中的L009：上行：S3739-S0359-S1477-S2159-S2377-S2211-S2482-S2480-S3439-S1920-S1921-S0180-S2020-S3027-S2981下行：S2981-S3027-S2020-S0180-S1921-S1920-S3439-S3440-S2482-S2211-S2377-S2159-S1478-S0359-S3739则将其上行路段及下行路段分作两个车次考虑，即将L009分为L009+和L009-两车次，如下：L009=（L009+）+（L009-）L009+：S3739-S0359-S1477-S2159-S2377-S2211-S2482-S2480-S3439-S1920-S1921-S0180-S2020-S3027-S2981L009-：S2981-S3027-S2020-S0180-S1921-S1920-S3439-S3440-S2482-S2211-S2377-S2159-S1478-S0359-S37393、对c类车次即环形车次，由环形车次本身特点，认为同一环形车次上的各站点之间都是可以直达的，且公交车是按顺时针和逆时针两个方向行驶的，故也做两个车次考虑。经统计，北京市公交系统公汽站点共有3957个,分别为S0001，S0002,,S3957,公汽线路共有520个车次，其中a类车次（即原路返回的车次）共有89个，b类车次（即来回站点有差异）共有409个，c类车次（即环形车次）共有22个，为了便于列表和导出结果，不妨规定每1车次占表中1列，由约定知，a类车次与b类车次的每个车次均分成了2个车次（共占2列），若将c类的每个车次写成上列为顺时针行驶时所经各站，下列为逆时针行驶时所经各站，则c类的每个车次也占2列，这样，公汽的520个车次对应于列表中的1040列，编程求解时只需求得列数，则对应的车次就很容易求得.例如求得的列数为56，则对应车次为S0028；求得的列数为57，则对应车次为S0029，即设列数为g，则对应的车次为12g（表向下取整）.4.1.4公交网络类型的判断利用MATLAB程序，可求出这3957个站点的度，其中站点1839的度最大，为13。求出度数为k的站点的个数，如下表所示：7表1不同度数的站点个数度数（k）站点数140521797363344875260616271048459361017117123131由上表可知，度为2的站点数最多，有1797个。根据公式：()()/PkfrequencykN（1）用不同度对应站点数除以总站点数N，即可求出()Pk。根据()Pk的分布，可画出其概率分布图为：图1公交网络模型的节点度分布8由图可知，该公交网络结点的度分布满足1的Poisson分布，故可建立基于公交线路的最短路径网络模型。4.1.5模型建立1.根据上述数据矩阵，计算出相邻路径矩阵1,11,,1,(,1,2,,3957)jiijaaAijaa,1,0,ijijaij两站点相邻两站点不相邻由于该公交车网络有3957个站点，故相邻路径矩阵A为一个39573957的01矩阵，以下是其站点连通情况的统计学图形：图3站点连通情况的统计学图形由此统计学图形可以定性的看出，总共有11826条相邻连通路线，图上有比较明显的各点连成的曲线6条，说明有3条路线对整个网络的影响比较大。利用A矩阵，通过求最短路的Flody算法，可得出网络中两个站点,ijss之间的最短距离ijd（,1,2,,3957ij……），其构成的矩阵D代表公交网络中各个站点9之间的最短路程11