《交通网络稳定性的评估.docx》由会员分享，可在线阅读，更多相关《交通网络稳定性的评估.docx（19页珍藏版）》请在三一办公上搜索。
1、特大型城市公共交通网络的稳定性评估问题摘 要本文将站点间的线路选择抽象为图论最短路模型采用0-1整数规划，得到相邻站点的路径矩阵。利用复杂网络原理，引入网络的度和平均最短路径长度的概念，并定义公共交通网络的服务能力为网络的平均最短路径长度。对于问题1，利用相邻路径矩阵，通过最短路的Flody算法，可得出网络中两个站点之间的最短距离（），网络在路线未发生中断的情况下网络的服务能力：当相邻站点(1522,3674)断开时，相对影响系数最大，网络平均最短路径，再利用公式，求出其相对影响系数。对于问题2，考虑地铁的影响。对矩阵进行修正，得到，其中。根据问题1的方法求得新路线未发生中断的情况下服务能力和
2、线路发生中断时的服务能力。当相邻站点(751,3878)断开时，相对影响系数最大，此时的网络平均最短路径，相对影响系数。对于问题3，对因下游路线中断而停止使用的线路中的相邻站点进行检索，若中断线路为相邻站点之间的唯一通路，则令，得到修正后的邻接矩阵。解得， 。对于问题4，乘客到达前一个站点时才能获知阻塞信息，该乘客只能以站点为起点，原目的地站点为终点，避开阻塞站点重新规划一条最短路径 ，依此对最短路径修正，计算出此时的网络平均最短路径最大为17.5632，为去掉1839站点后的平均最短路径值，其相对影响系数 。对于问题5，假设出行前就知道中断信息的乘客与抵达拥塞站点前一站才知道中断信息的乘客人
3、数权重比可表示为。得到第号站点中断的网络平均最短路径：解得当第584号站点中断时， ， 。关键词： 复杂网络 平均最短路径 服务能力 Flody算法 矩阵一、问题重述交通拥堵是大城市的顽疾，发展城市公共交通被认为是改善大城市交通环境的有效手段之一。当越来越多的市民依赖于城市公共交通系统时，为市民提供可靠的公共交通服务至关重要。但大城市的公共交通线路往往很多，所构成的公共交通网络也比较复杂，如何评估网络的稳定性成为设计可靠的公共交通服务的第一步。利用2007年全国大学生数学建模竞赛B题乘公交，看奥运提供的数据完成以下任务：任务1、仅考虑北京市公交汽车线路构成的网络，假设某时刻有且仅有一对相邻站点
4、间的道路因各种原因发生中断（其他站点间公交汽车都正常运行），且乘客在出行前就已经知道中断信息。请建立合理的数学模型并合理的定义公共交通网络的服务能力的概念，判断是否存在某对（或某几对）相邻站点间的道路，致使公共交通网络服务能力下降最多？若存在这样的道路，请指出并定量的描述下降的服务能力。任务2、在任务1的基础上，如果加入考虑北京市地铁线路，但假设地铁线路总是能够正常运行，那么结果将如何？任务3、在任务2的基础上，如果一对相邻站点间的道路因各种原因发生中断后，经过该道路的公交汽车线路的下游线路都将停止运行（即线路的任意运行方向经过该道路以后的站点都将停止运行），那么结果又将如何？任务4、仅考虑北
5、京市公交汽车线路构成的网络，假设某时刻有且仅有一个站点因各种原因发生拥塞（其他站点的公交汽车都正常运行），且乘客只有抵达拥塞站点的前一个站点时才能得知拥塞信息，并根据自己的出行需求考虑另择线路。请建立合理的数学模型，判断是否存在某个（或某几个）站点，致使公共交通网络服务能力下降最多？若存在这样的站点，请指出并定量的描述下降的服务能力。任务5、在任务4的基础上，如果假设部分乘客在出行前就已经知道中断信息，而部分乘客只有抵达拥塞站点的前一个站点时才能得知拥塞信息，那么结果将如何？二、模型假设1. 不考虑路况、气候、交通管制等外界不确定因素对交通的影响。2. 假设相邻公汽站行驶时间是均等的。3. 假
6、设相邻地铁站行驶时间是均等的且与相邻公汽站行驶时间相等。4. 不考虑乘车费用对网络服务能力的影响。5. 假设各相邻公汽站点间距相等，行车总距离的大小可由行车所经过的站点总数衡量。6. 以路径为评价指标，不考虑换乘和换乘时间对网络服务能力的影响，即认为为追求最短路程可无限次换乘。三、符号说明符号意义说明相邻站点的路径矩阵两相邻站点任意两个站点任意两站点的之间的最短路径各站点间的最短路程矩阵网络的平均最短路径网络中节点的度分布分布函数站点发生中断时的相对影响系数所有由到站点的公交线路集合四、模型的建立与求解4.1 问题1的模型建立与求解4.1.1问题分析根据题目中给出的公交车线路，利用复杂网络原理
7、对问题一进行分析。引入网络的度和平均最短路径长度的概念。1、复杂网络的度节点的度定义为与该节点相连接的边的数目，记为。直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”。网络中节点的度分布情况可用分布函数来描述。度分布函数反映了网络系统的宏观统计特征，表示的是一个随机选定的节点度恰好为的概率分布。有时度分布也可以近似理解为网络中度为的节点个数占总个数的比例，即其中为网络中节点的度为k的节点数目。通过研究的分布特点，可以判断出复杂网络的特点，有利于建模。2、复杂网络的平均最短路径长度网络中两个节点之间的距离，定义为连接这两个节点的最短路径上边的数目。网络中任意两个节点之间的距离的最
8、大值称为网络的直径(diameter)。记为，即网络的平均最短路径定义为任意两个节点之间的距离的平均值，即：其中为网络节点数。4.1.2 网络的服务能力的定义定义公共交通网络的服务能力为网络的平均最短路径长度。公共交通网络的服务能力在一定情况下可以看作网络的可靠性与抗毁性的统一，平均最短路径长度是公交线路上各点稳定性在整个网络上的体现，平均最短路径长度越短，网络的稳定性越好，公交网络的抗毁性也越好。现要求一对相邻站点间的道路因各种原因发生中断致使公共交通网络服务能力下降最多，即对该网络中的某条重要路线进行选择性攻击，致使该网络的平均最短路径长度增长最大。现给出一组模拟复杂网络的平均最短路径长度
9、在选择性攻击下，随着中断的重要点数的增加平均路径的变化情况：图1 平均最短路径长度随着重要点数中断的变化规律图中，横坐标代表的是在有选择性的攻击下度大的结点去掉的数目占所有结点数的比例，单位为万分之一。由上图可以看出，度数大的结点去掉大约5.6%，后整个系统就快速崩溃。由此可知，选用网络的平均最短路径来描述该公交网络的服务能力是合理的。4.1.3 编程时所需数据矩阵的建立根据题中所给的520个车次往返方式的不同，将整个线路分成三类：表示“下行”路段是“上行”路段原路返回的车次；：表示行车路线分为“上行”与“下行”的车次；：表示环形车次；因为各车次“上行”与“下行”的情况较复杂，特作如下约定：1
10、、对类车次即“下行”路段是“上行”路段原路返回的车次，如题中的L001：S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524- S0820-S3914-S0128-S0710则将其上行路段及下行路段分作两个车次考虑，即将L001分为L001+和L001-两车次，其中L001-为L001+原路返回所经各站，如下：L001=（L001+）+（L001-）L001+：S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819- S3524- S0820-S3914
11、-S0128-S0710L001- ： S0710-S0128-S03914-S0820-S3524-S0819-S3612-S3885-S0436-S0429- S0392-S0348-S0388-S1914-S06192、对类车次即行车路线分为“上行”与“下行”的车次，如题中的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-S221
12、1- 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、对类车次即环
13、形车次，由环形车次本身特点，认为同一环形车次上的各站点之间都是可以直达的，且公交车是按顺时针和逆时针两个方向行驶的，故也做两个车次考虑。经统计，北京市公交系统公汽站点共有3957个,分别为S0001，S0002,S3957,公汽线路共有520个车次，其中类车次（即原路返回的车次）共有89个， 类车次（即来回站点有差异）共有409个，类车次（即环形车次）共有22个，为了便于列表和导出结果，不妨规定每1车次占表中1列，由约定知，类车次与类车次的每个车次均分成了2个车次（共占2列），若将类的每个车次写成上列为顺时针行驶时所经各站，下列为逆时针行驶时所经各站，则类的每个车次也占2列，这样，公汽的520
14、个车次对应于列表中的1040列，编程求解时只需求得列数，则对应的车次就很容易求得.例如求得的列数为56，则对应车次为S0028；求得的列数为57，则对应车次为S0029，即设列数为，则对应的车次为（表向下取整）.4.1.4 公交网络类型的判断利用MATLAB程序，可求出这3957个站点的度，其中站点1839的度最大，为13。求出度数为的站点的个数，如下表所示：表1 不同度数的站点个数度数（k）站点数140521797363344875260616271048459361017117123131由上表可知，度为2的站点数最多，有1797个。根据公式： （1）用不同度对应站点数除以总站点数，即可求
15、出。根据的分布，可画出其概率分布图为：图1 公交网络模型的节点度分布由图可知，该公交网络结点的度分布满足的Poisson分布，故可建立基于公交线路的最短路径网络模型。4.1.5 模型建立1.根据上述数据矩阵，计算出相邻路径矩阵由于该公交车网络有3957个站点，故相邻路径矩阵为一个的矩阵，以下是其站点连通情况的统计学图形：图3 站点连通情况的统计学图形由此统计学图形可以定性的看出，总共有11826条相邻连通路线，图上有比较明显的各点连成的曲线6条，说明有3条路线对整个网络的影响比较大。利用矩阵，通过求最短路的Flody算法，可得出网络中两个站点之间的最短距离（），其构成的矩阵代表公交网络中各个站
16、点之间的最短路程对矩阵中的所有数据求和再与进行比较，便可得到该网络在路线未发生中断的情况下的网络平均最短路径，即此时网络的服务能力 （2）2.分别讨论当原来连通的某对相邻站点发生中断时，对网路平均路径的影响，即若两相邻站点发生中断，则此时由1变为0，再利用flody算法求出此时的最短路矩阵，利用公式（2）计算出此时的网络的平均最短路径。定义相对影响系数： （3）利用（3）式可得到相对影响系数：使越大的站点中断对网络的服务能力影响越大，求出最大使最大的某对相邻站点即可。4.1.6模型求解利用MATLAB编程可求得3957个站点之间在未发生相邻站点中断的情况下的最短路径矩阵，并求出此时的网络平均最
17、短路径。再根据上述模型，解得当相邻站点(1522,3674)断开时，相对影响系数最大。求得此时的网络平均最短路径，则此时的相对影响系数。4.2 问题2的模型建立与求解4.2.1问题分析 问题2要求在问题1的基础上考虑铁路对网络的服务能力的影响，由于地铁是始终连通的，故可把地铁看成是不会中断的公交路线，把每个地铁站点以及相邻地铁站点对应的公交站点看成是相邻连通的路线，例如对于地铁T1：1、地铁站D01对应着S0567、S0042、S0025三个公交车站点，即可认为：2、地铁站D22与地铁站D23相邻，且他们分别对应着公交站点S3457、S2512，则可认为：依据以上原理，对相邻路径矩阵进行修正，
18、计算出此时的网络服务能力，再对原先的相邻站点实行逐一中断处理，得出此时对服务能力影响最大的一对相邻站点。4.2.2 模型建立由题可知，共有40个地铁站点，分别记为、。对于其中的任意站点，都有若干公交站点可以换乘，可换乘的公交站点分别记为、。对于其中的任意两个可换乘站点、，其中定义矩阵其中故修正后的相邻路径矩阵 （4）其中得到利用此矩阵，通过求最短路的Flody算法，可得出网络中两个站点之间的最短距离（），其构成的矩阵代表公交网络中各个站点之间的最短路程得到该网络在路线未发生中断的情况下网络的平均路径，即此时网络的服务能力 （5）当原来连通的某对相邻站点发生中断时，即若两相邻站点发生中断，利用F
19、lody算法求出此时的最短路矩阵，计算出此时的网络的平均路径，求得相对影响系数： （6）使越大的站点中断对网络的服务能力影响越大，求出最大使最大的某对相邻站点即可。4.2.3 模型求解首先根据地铁的连通情况及以上定义，对相邻路径矩阵进行修正，得到新的相邻路径矩阵；再利用MATLAB编程可求得3957个站点之间在未发生相邻站点中断且加入地铁线路的情况下的最短路径矩阵，并求出此时的网络的平均路径。再根据上述模型，解得当相邻站点(751,3878)断开时，相对影响系数最大。求得此时的网络平均最短路径，则此时的相对影响系数。4.3 问题3的模型建立与求解4.3.1 问题分析 问题3中由于中断公交路线的
20、下游路线也停止使用，而某些路线的下游路线中包含了从一个站点到另一个站点的唯一通路，即是说在相邻路径矩阵中，原来某些相邻的站点会因为下游路线的停止使用而单方向中断，因此，必须对中断路线的下游路线中的此类站点进行检索，同时调整相邻线路矩阵，重新计算网路的平均最短路径，分析其对网络的服务能力产生的影响。4.3.2模型建立在基于公交线路的最短路径网络模型的基础上，建立基于邻接站点的网络模型。以停靠站点为节点，建立基于邻接站点的网络模型，若2个邻接站点之间有同一次车经过，则2个站点之间连一条边。由相邻站点构造的公交邻接站点网络是个比较稀疏的网络，所构造的网络接近于自然形成的路网结构。由于两个相邻的站点会
21、被不同的车次同时停靠也可以构造该网络为复杂加权网络，边权代表两个站点之间有公共线路停靠的的次数，权值越大，说明两个站点联系越紧密，也反应了2节点间的线路在交通网络中的重要性。记，为两相邻站点, 为所有由到站点的公交线路集合。 将满足的公交线的第路定义如下：把满足所有的公交线路的集合记为：所以 （7）当时，=0，定义矩阵通过编程找出矩阵中的最大值，此时对应的站点，之间的路段，即为对交通网络影响最大的路段，即通过这两个站点之间的公交车线路数最多，即： （8）找出通过，两个站点的每条公交线路，将在相邻路径矩阵中的值调整为0，并检索每条路线的下游路线中的各相邻站点，若其中的条路线下游中的两相邻站点在矩
22、阵中的值为1，即则将在相邻路径矩阵中的值同时调整为0，得到新的相邻路径矩阵 利用计算此时的公交网络中各个站点之间的最短路程矩阵：通过计算得到、两相邻站点中断后的网络的平均路径，利用公式 定量求出的值。4.3.3 模型求解根据上述原理，利用MATLAB程序，求出相邻站点间的公交车线路数，由于数据较为庞大，故只列出对结果产生较大影响的相邻站点，如下表所示：表2 相邻站点间的公交车线路数站点、的编号双向公交车线路数(2796,2861)54(1522,3674)50(1520,2992)49(751,3878)49(3623,3761)48(2861,2903)48(2303,3917)46(211
23、3,2636)46(2952,3761)46(533,3004)44(1300,3229)44(1808,3013)42(1729,2654)41(872,3919)41(2952,3229)40(2599,3512)40(1746,3697)40(2416,3878)40对公交线路数最多的前六对站点进行进一步的分析，得到站点（2796，2861）断开后，网络的平均最短路径上升程度最大，此时，由于，则相对影响系数：。4.4 问题4的模型建立与求解4.4.1 问题分析问题4中由于乘客到达拥塞站点的前一站才知道路线阻塞，故乘客不能提前规划此站点拥塞后新的最短路线，只能到达其前一站点时，才能以这前一
24、站点为起点、原目的地为终点重新规划一条最短路线，这势必会影响整个网络的平均最短路径长度，影响其服务能力。4.4.2 模型建立在问题1的公交车网络上，假设一乘客希望从站点到站点，按照原来的规划最短路程为，路径为：。但当该乘客到达站点时，发现站点拥塞；此时，该乘客只能以站点为起点，原目的地站点为终点，避开站点重新规划一条最短路径，则此时可认为站点到站点的最短路径长度为： （9）若站点的度为，则说明该拥塞站点周围有个相邻站点，需对最短路径经过它们的各条路径按照以上原理进行修正，得到站点拥塞后新的最短路径矩阵，再利用公式（2）计算出此时的网络平均最短路径，利用公式（3）求出对应的相对影响系数。现要求使
25、服务能力下降最大的站点，即该站点的相对影响系数满足： （10）若对全部站点进行以上处理，运算量将相当大，根据以上定义，可以发现此时站点的度对的增大有较大影响，站点的度越大，的增大越多，所以，只需对度数较大的几个站点进行讨论研究，即可得到所求的站点。4.4.3 模型求解计算得出度数较大的站点及其度数如下表所示：表3 度数较大的站点及其度数站点度数1839135411258412387412301114971161811132711165311192011248211按照模型原理，对这11个站点进行讨论，分别计算出去掉它们后，整个网络的平均最短路径，如下表：表4 去掉站点编号及其对应的网络平均最短
26、路径去掉的站点网络的平均最短路径183917.563254117.430458417.4675387417.385930117.412249717.379161817.3035132717.3746165317.3379192017.3109248217.2991故其中最大为17.5632，为去掉1839站点后的平均最短路径值，此时其相对影响系数 。4.5 问题5的模型建立与求解4.5.1 问题分析 问题5是建立在问题1和问题4的基础上的，问题5中有部分乘客在出行前就知道了中断信息，可认为这部分乘客可用问题1的模型和计算方法，所不同的是站点中断所导致的公交线路的中断与中断公交站点的度有关，需在
27、问题1模型的基础上进行改进；而一部分乘客在前一站才知道中断信息，可认为这部分乘客适用问题4的模型和计算方法。因此，此问可利用问题1和问题4的结论，在根据这两部分乘客所占的比例，给它们各自的网络平均最短路径加上权重即可。4.5.2 模型建立 假设出行前就知道中断信息的乘客与抵达拥塞站点前一站才知道中断信息的乘客比例为：，把它换算成两种乘客人数的权重可表示为 （11）假设第号站点中断，该站点的度为，而与它相邻的站点分别为：。 1、对于出行前就知道中断信息的乘客，可理解为第号站点与相邻的所有站点之间的道路全部中断，即：根据以上原理对相邻站点的路径矩阵进行路径修正，在利用修正后的计算此时的网络的平均最
28、短路径。2、对于抵达拥塞站点前一站才知道中断信息的情况，利用问题4的模型及原理，可计算出第号站点中断后的网络平均最短路径。加入权重后，所得到的第号站点中断的网络平均最短路径： （12）通过比较，找出满足 （13）的站点，并利用公式： （14）求出此时的相对影响系数。4.5.3 模型求解利用MATLAB程序，计算出当第584号站点中断时，得到网络平均最短路径的最大，为17.2229，此时的为16.9783，为17.4675，利用公式（13），可求得 。五、模型评价优点：（1）模型有针对性的解决了不同乘客的不同需求，并能给出各种乘车方案的各项参数，为出行者提供确切完整的乘车信息。（2）模型由简单到
29、复杂，不断完善，是在前一模型的基础上进行改进的，这样模型简单明了。（3） 模型考虑因素全面，适用性强，易于推广。缺点：（1）不能有效地将数据进行简化，数据处理复杂，编程困难。（2）在模型的求解过程中，运算量大，易出错。六、参考文献1 赵静 但琦数学建模与数学实验（第二版）高等教育出版社2006年12月2 王沫然MATLAB与科学计算（第二版）电子工业出版社 2006年7月3 王莉 李文权公共交通系统最佳路径算法东南大学学报（自然科学版）第34卷第二期 2004年3月4 徐多勇，李志蜀，梅林，基于GSM短信息的公交查询系统的最优化转乘方案研究与设计，计算机应用， 27卷：2007年6月17附 录
30、21、 求各站点的度及度的分布% p(i,j)为原始数据矩阵b=zeros(3958,3958);for i=1:1040 for j=1:85 m=p(i,j); n=p(i,j+1); b(m,n)=1; endendb(:,3958)=0;b(3958,:)=0;c=sum(b);b;cd=zeros(1,13)for i=1:3957 m=c(1,i); d(1,m)=d(1,m)+1; if c(1,i)=13 n=i; endend2、 求各站点间的最小距离Flody算法a=zeros(3958,3958);for i=1:1040 for j=1:85 m=p(i,j); n=p
31、(i,j+1); a(m,n)=1; endenda(:,3958)=0;a(3958,:)=0;a;n=size(a,1); d=a; for i=1:n for j=1:n r(i,j)=j; end end r for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j)d(i,j) d(i,j)=d(i,k)+d(k,j); r(i,j)=r(i,k); end end end end d r3、 求各相邻站点间的公交线路数a=zeros(3958,3958);for i=1:1040 for j=1:85 m=p(i,j); n=p(i,j+1); a
32、(m,n)=a(m,n)+1; endenda(:,3958)=0;a(3958,:)=0;ab=zeros(3958,3958)for i=1:3958for j=i:3958b(i,j)=a(i,j)+a(j,i);endendc=sparse(b);c4、 统计学图形画图程序a=zeros(3958,3958);for i=1:1040 for j=1:85 m=p(i,j); n=p(i,j+1); a(m,n)=1; endenda(:,3958)=0;a(3958,:)=0;spy(a)5、 生成相邻路径01矩阵程序a=zeros(3958,3958);for i=1:1040 for j=1:85 m=p(i,j); n=p(i,j+1); a(m,n)=a(m,n)+1; endenda(:,3958)=0;a(3958,:)=0;a
