特大型城市公共交通网络的稳定性评估问题

特大型城市公共交通网络的稳定性评估问题摘要公共交通网络的服务能力，即在某一地理区域内（如北京市），乘坐公共交通工具能从任一站点到达另一站点的能力，即道路通行能力。通行能力越好，单位时间通过某段线路的车辆越多，通过某相邻两站点间的公交车次数也就越多，公交网络的服务能力越强。据此，我们可建立模型求得通过公交车次数最多的相邻站点路线，以求得使定义公共交通网络的服务能力下降最多的相邻站点间的道路。本文采用了效率高效的广度优先算法，其基本思路是每次搜索指定点，并将其所有未访问过的近邻点加入搜索队列，循环搜索过程直到队列为空。对于任务一，仅考虑公汽线路构成的网络，用MATLAB编程读取公汽线路信息数据可得到通过任意两个公交站点之间的线路，存入3957×3957的矩阵A中，得到任意两个公交站点之间能直接通行到达的线路矩阵。根据矩阵A可以求得两个公交站点之间能直接通行到达的线路条数，我们可得到通行线路数量最多的几对相邻站点，即为所求站点。继而，我们根据道路中断造成的线路瘫痪情况求得公交网络服务能力的下降幅度。对于任务二，加入考虑北京市地铁线路，且地铁线路总是能够正常运行。我们可以将地铁线路视为正常运营的公交线路，本质上没有什么区别。地铁站可等效为公交站，地铁和公交的转乘站即可作为两者的交汇点。因此，该模型与模型一中基本相同。任务三中，如果一对相邻站点发生中断，那么所有经过这对站点的下游路线就会全部瘫痪。由于地铁的运载及服务能力有限，它也不可能到达所有下游站点，所以，即使加入考虑北京市地铁线路，且地铁线路总是能够正常运行，此时的公交网络服务能力也会大大降低。对于任务四，仅考虑公汽线路构成的网络，用MATLAB编程读取公汽线路信息数据可得到通过任意公交站点线路，存入集合{a}中，得到通过任意公交站点的线路集合。根据集合{a}可以求得通过任意站点的线路条数，我们可得到通行线路数量最多的站点，即为所求站点。继而，我们根据道路中断造成的线路瘫痪情况求得公交网络服务能力的下降幅度。该模型与模型一类似。任务五是在任务四的基础上，假设部分乘客在出行前就已经知道中断信息，而部分乘客只有抵达拥塞站点的前一个站点时才能得知拥塞信息。这样，那些只有抵达拥塞站点的前一个站点时才能得知拥塞信息的乘客就只能临时进行调整，此时可依照以上建立的模型进行解答。而那些在出行前就已经知道中断信息的乘客就可以提早做打算，进行换乘或更改路线。这就缓解了由于站点发生拥塞带来的不便。关键词公交网络稳定性服务能力广度优先算法相邻站点一、问题重述1.1问题背景随着经济的快速发展以及城市的不断扩大，交通线路和交通工具越来越多，由此导致的交通拥挤现象越发严重，这种现象在大城市中体现得尤为明显。发展城市公共交通已逐步被认为是改善大城市交通环境的有效手段之一。城市公共交通是指城市中供公众乘用的经济方便的各种交通方式的总称，是由公共汽车、电车、轨道交通、出租汽车、轮渡等交通方式组成的公共客运交通系统。它通过各种交通工具之间相互配合，为乘客提供交通运输服务，维系着城市功能的正常运转，是城市社会和经济赖以生存、发展的基础，在国民经济发展中占有重要地位。交通拥堵是大城市的顽疾，发展城市公共交通被认为是改善大城市交通环境的有效手段之一。当越来越多的市民依赖于城市公共交通系统时，为市民提供可靠的公共交通服务至关重要。但大城市的公共交通线路往往很多，所构成的公共交通网络也比较复杂，如何评估网络的稳定性成为设计可靠的公共交通服务的第一步。1.2目标任务2007年全国大学生数学建模竞赛B题是《乘公交，看奥运》。该题提供了截至2007年北京市所有公共交通线路的线路、站点、票价和运行时间等的信息。任务1：仅考虑北京市公交汽车线路构成的网络，假设某时刻有且仅有一对相邻站点间的道路因各种原因发生中断（其他站点间公交汽车都正常运行），且乘客在出行前就已经知道中断信息。请建立合理的数学模型并合理的定义公共交通网络的服务能力的概念，判断是否存在某对（或某几对）相邻站点间的道路，致使公共交通网络服务能力下降最多？若存在这样的道路，请指出并定量的描述下降的服务能力。任务2：在任务1的基础上，如果加入考虑北京市地铁线路，但假设地铁线路总是能够正常运行，那么结果将如何？任务3：在任务2的基础上，如果一对相邻站点间的道路因各种原因发生中断后，经过该道路的公交汽车线路的下游线路都将停止运行（即线路的任意运行方向经过该道路以后的站点都将停止运行），那么结果又将如何？任务4：仅考虑北京市公交汽车线路构成的网络，假设某时刻有且仅有一个站点因各种原因发生拥塞（其他站点的公交汽车都正常运行），且乘客只有抵达拥塞站点的前一个站点时才能得知拥塞信息，并根据自己的出行需求考虑另择线路。请建立合理的数学模型，判断是否存在某个（或某几个）站点，致使公共交通网络服务能力下降最多？若存在这样的站点，请指出并定量的描述下降的服务能力。任务5：在任务4的基础上，如果假设部分乘客在出行前就已经知道中断信息，而部分乘客只有抵达拥塞站点的前一个站点时才能得知拥塞信息，那么结果将如何？二、模型的假设3.1基本假设1）相邻公汽站平均行驶时间(包括停站时间)：3分钟；2）相邻地铁站平均行驶时间(包括停站时间)：2.5分钟；3）公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)；4）地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)；5）地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)；6）公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)；7）公汽票价：分为单一票价与分段计价两种。单一票价：1元分段计价：0～20站：1元21～40站：2元40站以上：3元8）地铁票价：3元（无论地铁线路间是否换乘）；9）同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁费。3.2其它假设10）乘客转乘公交的次数不超过两次；11）所有环行公交线路都是双向的；12）地铁线T2也是双向环行的；13）各公交车都运行正常，不会发生堵车现象；14）公交、列车均到站停车；15）不同地区公交车站的间隔大概一致。三、符号说明,pqK：通过两个相邻站点之间的线路条数，p代表两相邻站点的上一站点，q为下一站点；,pqX：通过两个相邻站点,pq之间的线路条数，无方向性，即,,,pqpqqpXKK；cx：通过某一站点的线路条数，包括上行和下行路线，无方向性；iL：第i条公汽线路标号,i=1,2…1040。当i520时,iL表示上行公汽路线,当i520时,iL表示与上行路线i520L相对应的下行公汽路线；i,jS：经过第i条公汽路线的第j个公汽站点标号；gT：第g条地铁路线标号,g=1,2；g,hD：经过第g条地铁线路的第h个地铁站点标号。四、模型的分析所谓公共交通网络的服务能力，我们将其定义为：在某一地理区域内（如北京市），乘坐公共交通工具能从任一站点到达另一站点的能力，即道路通行能力。通行能力越好，单位时间通过某段线路的车辆越多，通过某相邻两站点间的公交车次数也就越多，公交网络的服务能力越强。据此，我们可建立模型求得通过公交车次数最多的相邻站点路线，以求得使定义公共交通网络的服务能力下降最多的相邻站点间的道路。经分析，本问题的解决归结为一个求通过公交车车次最多的相邻站点的问题，但是传统的Dijkstra算法并不适用于本问题，因为Dijkstra算法采用的存储结构和计算方法难以应付公交线路网络拓扑的复杂性,而且由于执行效率的问题，其很难满足实时系统对时间的严格要求。为此我们在实际求解的过程中，采用了效率高效的广度优先算法，其基本思路是每次搜索指定点，并将其所有未访问过的近邻点加入搜索队列，循环搜索过程直到队列为空。此方法在后文中有详细说明。五、建模前的准备为了后面建模与程序设计的方便，在建立模型前，我们有必要做一些准备工作。5．1数据的存储由于所给的数据格式不是很规范，我们需要将其处理成我们需要的数据存储格式。从所给文件中读出线路上的站点信息，存入txt文档中，其存储格式为：两行数据，第一行表示上行线上的站点信息，第二行表示下行线的站点信息，其中下行路线标号需要在原标号的基础上加上520，用以区分上行线和下行线。如果上行线与下行线的站点名不完全相同，那么存储的两行数据相应的不完全相同，以公交线L009为例：L009:373903591477215923772211248224803439192019210180202030272981L529:298130272020018019211920343934402482221123772159147803593739L529为L009所对应的下行线路。如果下行线是上行线原路返回，那么存储的两行数据中的站点信息刚好顺序颠倒，以公交线路L001为例：L001:061919140388034803920429043638853612081935240820391401280710L521:071001283914082035240819361238850436042903920348038819140619如果是环线的情况（如图5.1所示），则可以等效为两条线路:顺时针方向：S1→S2→S3→S4→S1→S2→S3→S4；逆时针方向：S1→S4→S3→S2→S1→S4→S3→S2。经过分析，此两条“单行路线”线路的作用等同于原环形路线图5.1环行线路示意图以环形公交线L158为例，此环形路线存储数据如下：L153:534649235512128121711708112600172158581426435131215121725126042606534649235512128121711708112600172158581426435131215121725126042606L673:534260626042511217121535132648141585172260081117017181212122355649534260626042511217121535132648141585172260081117017181212122355649在这里，L153被看作成上行路线，L673被当成下行路线。这样对于每条公交线路都可以得到两行线路存储信息。5．2搜寻经过每个站点的公交路线处理5.1所得信息，找出通过每个站点的所有公交路线，并将它们存入数据文件中。例如，通过搜寻得出经过站点S0001的线路和经过站点S0002的线路如下：经过S0001的线路有：L421经过S0002的线路有：L027L152L365L395L4855．3统计线路及站点个数经统计，所给出的北京市公汽线路信息中，共有3957个公交站点、1040条公汽线路（其中上行线和下行线完全重合的算为上下两条，环形线路顺时针行走和逆时针行走算为两条）；对所有线路，每条线路最多要经过86个站点。六、模型建立与求解6．1任务一的解答针对任务一，仅考虑公汽线路，先对经过每相邻两站点的线路进行统计，然后找出经过的线路数量最多的几对相邻站点，求得最终结果。6．1．1公汽路线的数学表示任意两个站点间的路线有多种情况，如果最多允许换乘两次，则换乘路线分别对应图6.1的四种情况。该图中的A、B为出发站和终点站，C、D、E、F为转乘站点。图6.1公汽路线图对于任意两个公汽站点i,jS与ij,S，经过i,jS的公汽线路表示为iL，有i,jiSL；经过ij,S的公汽线路表示为iL，有iji,SL；1）直达的路线0LS（如图6.1（a）所示）表示为：0i1i,ji1iji1,LSLSL,SL2）转乘一次的路线1LS（如图6.1（b）所示）表示为：,;1i1i2i,ji1i10i1i2iji2i2,LS(L,L)SLSLL,LLS;SCL,SCL其中：SC为i1L，i2L的一个交点；3）转乘两次的路线2LS（如图6.1（c）所示）表示为：11,,(LSS2i1i2i3i,ji1i1i3i3i2i1i2iji2,LS(L,L,L)SLSLL,L)