交通网络稳定性的评估文档.doc

特大型城市公共交通网络的稳定性评估问题 摘 要 本文将站点间的线路选择抽象为图论最短路模型采用0-1整数规划，得到相邻站点的路径矩阵。利用复杂网络原理，引入网络的度和平均最短路径长度的概念，并定义公共交通网络的服务能力为网络的平均最短路径长度。 对于问题1，利用相邻路径矩阵，通过最短路的Flody算法，可得出网络中两个站点之间的最短距离（），网络在路线未发生中断的情况下网络的服务能力： 当相邻站点(1522,3674)断开时，相对影响系数最大，网络平均最短路径，再利用公式，求出其相对影响系数。 对于问题2，考虑地铁的影响。对矩阵进行修正，得到，其中。根据问题1的方法求得新路线未发生中断的情况下服务能力和线路发生中断时的服务能力。当相邻站点(751,3878)断开时，相对影响系数最大，此时的网络平均最短路径，相对影响系数。 对于问题3，对因下游路线中断而停止使用的线路中的相邻站点进行检索，若中断线路为相邻站点之间的唯一通路，则令，得到修正后的邻接矩阵。 解得， 。 对于问题4，乘客到达前一个站点时才能获知阻塞信息，该乘客只能以站点为起点，原目的地站点为终点，避开阻塞站点重新规划一条最短路径 ，依此对最短路径修正，计算出此时的网络平均最短路径最大为17.5632，为去掉1839站点后的平均最短路径值，其相对影响系数 。 对于问题5，假设出行前就知道中断信息的乘客与抵达拥塞站点前一站才知道中断信息的乘客人数权重比可表示为。得到第号站点中断的网络平均最短路径：解得当第584号站点中断时， ， 。 关键词： 复杂网络 平均最短路径 服务能力 Flody算法 矩阵 一、问题重述 交通拥堵是大城市的顽疾，发展城市公共交通被认为是改善大城市交通环境的有效手段之一。当越来越多的市民依赖于城市公共交通系统时，为市民提供可靠的公共交通服务至关重要。但大城市的公共交通线路往往很多，所构成的公共交通网络也比较复杂，如何评估网络的稳定性成为设计可靠的公共交通服务的第一步。 利用2007年全国大学生数学建模竞赛B题《乘公交，看奥运》提供的数据完成以下任务： 任务1、仅考虑北京市公交汽车线路构成的网络，假设某时刻有且仅有一对相邻站点间的道路因各种原因发生中断（其他站点间公交汽车都正常运行），且乘客在出行前就已经知道中断信息。请建立合理的数学模型并合理的定义公共交通网络的服务能力的概念，判断是否存在某对（或某几对）相邻站点间的道路，致使公共交通网络服务能力下降最多？若存在这样的道路，请指出并定量的描述下降的服务能力。 任务2、在任务1的基础上，如果加入考虑北京市地铁线路，但假设地铁线路总是能够正常运行，那么结果将如何？ 任务3、在任务2的基础上，如果一对相邻站点间的道路因各种原因发生中断后，经过该道路的公交汽车线路的下游线路都将停止运行（即线路的任意运行方向经过该道路以后的站点都将停止运行），那么结果又将如何？ 任务4、仅考虑北京市公交汽车线路构成的网络，假设某时刻有且仅有一个站点因各种原因发生拥塞（其他站点的公交汽车都正常运行），且乘客只有抵达拥塞站点的前一个站点时才能得知拥塞信息，并根据自己的出行需求考虑另择线路。请建立合理的数学模型，判断是否存在某个（或某几个）站点，致使公共交通网络服务能力下降最多？若存在这样的站点，请指出并定量的描述下降的服务能力。 任务5、在任务4的基础上，如果假设部分乘客在出行前就已经知道中断信息，而部分乘客只有抵达拥塞站点的前一个站点时才能得知拥塞信息，那么结果将如何？ 二、模型假设 1. 不考虑路况、气候、交通管制等外界不确定因素对交通的影响。 2. 假设相邻公汽站行驶时间是均等的。 3. 假设相邻地铁站行驶时间是均等的且与相邻公汽站行驶时间相等。 4. 不考虑乘车费用对网络服务能力的影响。 5. 假设各相邻公汽站点间距相等，行车总距离的大小可由行车所经过的站点总数衡量。 6. 以路径为评价指标，不考虑换乘和换乘时间对网络服务能力的影响，即认为为追求最短路程可无限次换乘。 三、符号说明 符号 意义说明 相邻站点的路径矩阵 两相邻站点 任意两个站点 任意两站点的之间的最短路径 各站点间的最短路程矩阵 网络的平均最短路径 网络中节点的度分布分布函数 站点发生中断时的相对影响系数 所有由到站点的公交线路集合 四、模型的建立与求解 4.1 问题1的模型建立与求解 4.1.1问题分析 根据题目中给出的公交车线路，利用复杂网络原理对问题一进行分析。引入网络的度和平均最短路径长度的概念。 1、复杂网络的度 节点的度定义为与该节点相连接的边的数目，记为。直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”。网络中节点的度分布情况可用分布函数来描述。度分布函数反映了网络系统的宏观统计特征，表示的是一个随机选定的节点度恰