《最优奥运公交线路的选择》由会员分享，可在线阅读，更多相关《最优奥运公交线路的选择（16页珍藏版）》请在金锄头文库上搜索。
1、最优奥运公交线路的选择摘要：对于问题一中所要求解的两个站点之间的最优路径，我们首先把它简单看成最短路径问题，使用Floyd算法得出任意两点之间的最短路径，将每条最短路径所包含的站点序列作为乘车路线，计算出在换乘次数最少情况下的最优换乘方式。但按照该模型所求得的解并不符合人们乘坐公交车出行的实际情况（例如一问第6组的始发点和终点间最短路径仅有11个公交站点，而沿该最短路径乘坐公交车出行至少须要作7次换乘），仅可以作为私家车出行的参考模型。于是从实际情况出发对模型进行进一步的改进和优化，使用基于广度优先的公交换乘算法得出，在优先考虑换乘最小并同时考虑路径、时间、费用等综合因素影响情况下，进行0次、
2、1次、2次换乘的最优换乘方案，在文章中通过图表的方式把结果表示出来。在第二问中考虑了加入地铁站及地铁线路之后的公交出行方式的影响，给出了地铁直达、公交线经过地铁站换乘、公交线与地铁线换乘等不同的换乘方案，并对题中给定的六组站点进行了计算机实验，得到了每组站点之间的最佳换乘方法。第三问中，加入了步行的过程，使得模型更加贴近实际情况，得出了在换乘公交和地铁之前可以先不信一段不太长的距离，让后找到更适合的乘车方案，并对“步行-公交-公交”的出行方式进行了实验，得出了具体的换乘方式。关键字：最小换乘、最短路径、广度优先算法一、问题背景与分析08年北京奥运会即将召开，作为世界性的盛会，奥运会吸引着世界各
3、地的观众和游客。北京的城市交通网络本来就存在着很多的问题，举办奥运会带来的巨量出行无疑会给北京城市的交通网络带来巨大的冲击。如何保证运动员、观众、游客快速准确的到达奥运场馆、奥运村、各旅游景点成为一个迫切需要解决的问题。在现实生活中人们出行时，对距离时间、费用、距离、转乘次数等的要求时不一样的。人们会根据自身的情况的需要来选择乘车的方式。比如对上班族，或要处理突发事件的人群来说就要优先考虑时间因素。对于时间较多而经济不太充裕的人群来说就要优先考虑费用因素，比如学生、下岗待业人群。如果仅考虑距离因素，会使得换乘次数较多不符合公交出行的实际情况，这种方案适合私家车出行的人群，因为私家车出行优先考虑
4、的是路径最短耗油最少这与公交出行考虑的因素是不同的。在奥运会期间应最大可能的限制私家车出行，因为这样会给本来已经不堪重负的城市交通网络带来更大的冲击。题目中所要求的最佳路线我们认为应该从公交网络的现实情况来考虑最短路径的意义公交乘客出行时更多考虑的是出门的方便性和舒适性，不会因为要求路径最短而频繁的换车因为从一条线路换到另一条线路既费时又费力，所以公交网络中的最短路径和图论中的最短路径的意义是不同的。乘客会在基于换乘次数最少的基础上，考虑路程是否最短。二、符号说明：1. A：为一组站点的起点，2. B：为一组站点的终点 3. X(i)：为穿过站点A的线路集合4. Y(j)：为穿过站点B的线路集
5、合.5. k：步行时间上界，假设为步行一站的时间6. T(xy)：x到y的时间7. LA：经过A的一条公交线路8. LB：经过B的一条公交线路三、 模型假设1. 假设公交和地铁在运行途中，经过每个站点时都必须停靠；2. 根据实际情况，假设环形线路也分上行和下行，上行和下行的站点顺序正好相反；3. 假设任意两相邻站点之间的距离是相等的；、四、模型的建立与求解1、对数据的处理为了在搜索路线时不仅能知道途经了哪条线路，而且能够清楚的知道是线路的上行还是下行，因此，我们把每条公交线路的上行和下行线路看成两条不同的线路进行处理。如果线路的上下行站点完全相同，则同样也把上行和下行线路看成两条不同的线路进行
6、处理。对环形线路，为了能够使得在环形中的任意两个站都能够通过环形中的小半园到达，我们将环形线路中的站点重复一次接在原环形线路的后面，并把环形线路也考虑成上下行两条线路。如：原环形线路是1-2-3-4-5-1，则变为上行：1-2-3-4-5-1-2-3-4-5 ；下行：5-4-3-2-1-5-4-3-2-1。对地铁T1线，把它分解成上下行两条线路，而对于T2线也像公交的环形线一样，先进行站点的扩展，然后再分解成上下行连条线路。2、对问题一的解答要求任意两点之间最佳路线作为乘客有两种情况1如果时间（如比赛即将开始）比较紧张需要在最短的时间内到达2如果时间比较充裕则对乘车的舒适度要求较高即要求换乘次
7、数最少我们可以对两种情况先分别进行处理1、先讨论第一种情况，如果要求在最短时间内到达我们近似的认为AB两站点之间站点最少则路径最短忽略每站之间路程的不同，通过FLOYD算法求出两点之间的最短路2、再讨论第二种情况，从我们的日常生活逻辑来讲出行总是会选择换乘次数最少的出行方式。对于换乘次数我们分为三种情况来分析：不换乘、换乘次数1和换乘次数为2。假设换乘上限为2（因为在现实生活中如果要换三次或三次以上的车一般会采取其他的出行方式）（1）模型一：最短路径模型把公交网络看成一个图，我们可以用图论的方法来解决公交换乘的问题。通过FLOYD算法来求最短路径，由于题目没有给出站点之间的距离，我们假设每个站
8、点之间的距离相等，即用两个站点之间的顶点数来表示两站点之间的距离，设两个连通的顶点之间的权值为1不连通权值为0通过计算得出优先考虑最短路径的结果，其中每两对站点之间通过的最少站点，经过的站点如表1所示。在优先考虑最短路径的情况下来考虑换乘方案，并要求使得换乘次数最少。经过编程计算，得出在已知的最短路径中通过每两个相邻站点之间的所有公交线路，在要求总的换乘次数最少的原则下，我们给出了相应的换乘方案，用图形表示如下，由于文章篇幅限制，现只给出了第一组和第六组的换乘方案示意图（如图1、图2），其他线路的乘车方案见附录。表1：每两对站点之间通过的最少站点经过的站点站数换乘次数费用(元)时间（分）第一组
9、S3359-S1828S3359-S2023-S2027-S1327-S1842-S609-S0483-S0604-S0525-S3162-S0073-S2703-S1784-S1828146772第二组S1557-S0481S1557-S3158-S2628-S3408-S1985-S2563-S2682-S0028-S0055-S0051-S1919-S2840-S1402-S3186-S3544-S1788-S1787-S1783-S1784-S2703-S0480-S0955-S1768-S0903-S2101-S048126910123第三组S0971-S0485S0971-S334
10、1-S2237-S3565-S3333-S1180-S3493-S1523-S1520-S2992-S0903-S1768-S0955-S0480-S2703-S1784-S1783-S1787-S1961-S0427-S0584-S3409-S3241-S2480-S1404-S1495-S0771-S0485281112139第四组S0008-S0073S0008-S3412-S2744-S1839-S3685-S1008-S0940-S2085-S0609-S0483-S0604-S0525-S3162-S0073145667第五组S0148-S0485S0148-S0462-S0361
11、-S1797-S2221-S0302-S0710-S0128-S2268-S1308-S1391-S2272-S2270-S1842-S0087-S0630-S3874-S2534-S0239-S0497-S1921-S2480-S1404-S1495-S0771-S0485261213138第六组S0087-S3676SS087-S0630-S3874-S0167-S0059-S2336-S0242-S2402-S1103-S0082-S3676117868图1：第一对站点S3359-S1828的乘车方案图2：第六对站点S0087-S3676的乘车方案注：图中的圆圈表示站点，圆圈里的数据表示
12、相应的站点，连接线表示两站点之间可以直达，连接线上的数据表示可以乘坐的车次如201表示L201路公交，324（a）中的（a）表示还有其他线路可以乘坐因篇幅有限不便全部表示出来。从图中提供的乘车方案可以看出优先考虑最短路径会造成换乘的次数很多，不符合实际的情况。因为换乘不仅需要等待而且费事。完全套用最短路径问题来解决，存在如下的问题：由表中的数据得知如果仅考虑最短路径会使得换乘的次数很多。仅把边的权值看成两点之间的距离，在公交换乘这样的实际问题中不太实际，通常情况下，行人除了考虑距离以外，还会考虑换乘的次数，即是直达还是，还是换乘一次或两次或更多次。同时也会考虑时间的因素，其中包含很多的不确定的
13、因素我们主要考虑公汽的行驶时间和换乘的等待时间其他因素忽略不计。（1）模型二：基于广度优先的公交换乘搜索算法根据人们的出行习惯，在选择从A站到B站的行车路线时，首先会先看经过A站的车是否有直接去B站的，如果有，马上会选择直达车，如果存在不止一条的直达线，再考虑距离、时间、费用等综合因素的乘车方案；如果没有直达车，就会考虑一次换乘的乘车方案：经过A站的车与经过B站的车有公共站点C吗？如果有，则可以在公共站点C处转车：如果没有则可以考虑二次乘车方案，即乘坐经过A点的车到某一处C点乘车，经过C站的车与 经过B站的车有没有公共站点D,如果有就在转到D转车，两次转车可以到达B；如果没有，则需要考虑三次换
14、乘的情况或三次以上才能到达目的地。在上述的情况中如果存在不止一种的乘车方案，则需要考虑以上诸多的因素综合考虑最高的作为最优方案。l 基于广度优先的公交换乘搜索算法步骤1、输入起始站点A和目的地站点B步骤2、搜索公交数据库，经过起始点A的公交线路存为，经过目的站点B的公交线路存为步骤3、判断是否有,将满足条件的存入Z步骤4、搜索公交数据，将公交线路所包含的公交站点存为公交换乘矩阵公交线路所包含的站点存为公交换乘矩阵步骤5、判断是否有将满足条件的存入w，若，则站点即从站点A到站点B的一次换乘点，公交线路X(i),Y(j)为换乘一次的最优线路，输出结果并结束运算。步骤6、搜索公交数据库，将经过站点的
15、公交线路存为公交线路R（k）所包含的站点)扩充到公交换乘矩阵中。步骤7、判断是否有，将满足条件的存入W, 若则站点即为从站点A到站点B的二次换乘点，公交线路为换乘二次的最佳路线，输出结果并结束运算。步骤8、设定换乘次数的上界Z,然后在不大于Z次循环的某次循环中找到可行路径，若可行路径有多条，考虑综合因素为最优的路径并输出以上步骤如果没有找到合适的公交路线则输出“没有找到换乘次数超过Z次的最优方案”，结束运算。从我们的日常生活逻辑来讲出行总是会选择换乘次数最少的出行方式。对于换乘次数我们分为三种情况来分析：换乘次数为0、换乘次数为1、换乘次数为2。假设换乘上限Z为2（因为在现实生活中如果要换三次或三次以上的车一般会采取其他的出行方式）通过MATLAB编程，实现基于广度优先的公交算法。a) 0次换乘首先计算0次换乘的情况，根据基于广度优先的公交算法在题目中六对站点之间都没有直达的公交线路。b) 1次换乘再考虑1次换乘的情况，根据基于广度优先的公交算法题目中所要求的1、3、4、6条线路可以通过一次换乘到达。换乘一次的情况下优先考虑站数，其次考虑费用，再其次考虑时间可以得出，题中各对站点
