最优奥运公交线路的选择

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（因为在现实生活中如果要换三次

16、或三次以上的车一般会采取其他的出行方式）通过MATLAB编程，实现基于广度优先的公交算法。a) 0次换乘首先计算0次换乘的情况，根据基于广度优先的公交算法在题目中六对站点之间都没有直达的公交线路。b) 1次换乘再考虑1次换乘的情况，根据基于广度优先的公交算法题目中所要求的1、3、4、6条线路可以通过一次换乘到达。换乘一次的情况下优先考虑站数，其次考虑费用，再其次考虑时间可以得出，题中各对站点之间的最优路径。从结果中我们可以看出在优先考虑站点最少的情况下，费用和时间都是最少的。而第二组S1557-0481和第五组S0148-S0485无法通过一次换乘到达必须考虑两次，或两次以上的换乘的情况。c)

17、 2次换乘考虑两次换乘的情况首先通过程序计算出二次换乘时六对线路所有可能的乘车方案再通过评价函数优先考虑站点数即路径其次考虑费用和时间得出最优解，由于得出的结论大多篇幅有限无法将所有的结果都用表格在文中表示出来，从每组最优解中选出其中三种最优的方案如表3所示，从表3中我们看到，不仅得到了第二对站S1557-S0481和第五对站的换乘方案。而且可以看到第一对站S3359-S1828第三对站S0971-S0485第四对站S0008-S0073在换乘两次时经过的站点和所用时间比一次换乘时经过的站点和所用的时间要少，而且可选的线路也非常多。表2：一次换乘公交的最优乘车方案始发线路中转车站转乘线路站数费

18、用(元)时间（分）第一组S3359-S1828L436（下行31站）S1784L214（下行1站）323101L436（下行31站）S1784L167（下行1站）323101第三组S0971-S0485L13(下行)20S2184L417（下行）21413128第四组S0008-S0073L463（下行14站）S2083L58（上行12站）26283L159（下行10站）S0400L475（上行16站）26283L159（下行11站）S2633L475（上行15站）26283L159（下行12站）S3053L475（上行14站）26283L159（下行17站）S2683L58（下行9站）262

19、83L159（下行18站）S0291L58（下行8站）26283L159（下行19站）S3614L58（下行7站）26283L159（下行20站）S0491L58（下行6站）26283L355（下行7站）S2263L246（上行19站）26283L355（下行8站）S3917L246（上行18站）26283L355（下行9站）S2303L246（上行17站）26283第六组S0087-S3636L455（上行11站）S3496L209（下行9站）20265表3：二次换乘公交的部分最优方案组数LACLDDLBA-CC-DD-B总站数费用(元)时间(分)方案数第一组S3359-S1828L123(

20、上行)S2903L485(下行)S1784L217(下行)116118364112L324(下行)S2027L485(下行)S1784L217(下行)215118364L484(下行)S2027L485(下行)S1784L217(下行)215118364第二组S1557-S0481L363(下行)S1919L189(下行)S3186L460(下行)123173231062L084(下行)S1919L189(下行)S3186L460(下行)12317323106L363(下行)S1919L417(上行)S2424L254(上行)12175343112第三组S0971-S0485L013(下行)S

21、2517L290(下行)S2159L469(上行)161323131031L263(下行)S1609L140(下行)S2654L469(上行)21911323106L024(下行)S1609L140(下行)S2654L469(上行)21911323106第四组S0008-S0073L198(上行)S1383L290(下行)S2184L345(上行)11531936725L463(下行)S1383L290(下行)S2184L345(上行)115319367L043(下行)S1383L290(下行)S2184L345(上行)115319367第五组S0148-S0485L308(上行)S0036L

22、156(上行)S2210L417(下行)141533231063L307(上行)S0036L156(上行)S3332L417(下行307(上行)S0036L156(上行)S3351L417(下行六组S0087-S3676SL022(下行)S0088L231(上行)S0427L462(下行)11011234648L205(上行)S0088L231(上行)S0427L462(下行)110112346L455(下行)S0088L231(上行)S0427L462(下行)110112346其中：LA表示起点所乘线路, C表示第一次转乘站, LD表示第一

23、次转乘线路, D表示第二次转乘站, LB表示第二次转乘线路，方案数表示最优方案的总个数。d) 对第一问的总结从以上的计算可以看出，如果不考虑地铁的因素，而优先考虑费用最省或时间最少，则优先考虑的因素不同得出的结果是不一样的。不同的乘客会根据自身情况，选择符合自身的乘车方案。（1）当乘客优先考虑换乘次数时，综合上面换乘次数一次和两次的计算结果，得到六组站点间换乘次数最少的换乘方案如表4。表4：问题一考虑换乘次数最少的最佳线路乘车方案换乘次数总站数费用(元)时间(分)第一组S3359-S1828乘L463(下行)到S1784转乘L214(下行)1323101第二组S1557-S0481乘L363(

24、下行)到S1919转乘L189(下行)到S3186转乘L460(下行)2323106第三组S0971-S0485乘L13(下行)到S2184转乘L417(下行)1413128第四组S0008-S0073乘L463(下行)到S2083转乘L58(上行)126283第五组S0148-S0485乘L308(上行)到S0036转乘L156(上行)到S2210转乘L417(下行)2323106第六组S0087-S3676S乘L455(上行)到S3496转乘L209(下行)120265（2）当乘客优先考虑时间和费用时，从实际情况出发一般考虑换乘次数不超过两次，综合上面换乘次数一次和两次的计算结果，得到六组

25、站点间总站数最少的换乘方案如表5所示，由于限定了换乘次数总站数最少时，所用的时间和费用都是同组站点间的其他换乘方式中最少的。表5：问题一考虑时间和费用最少的最佳线路乘车方案换乘次数总站数费用(元)时间(分)第一组S3359-S1828乘L123(上行) 到S2903转乘L485(下行) 到S1784转乘L217(下行)218364第二组S1557-S0481乘L363(下行)到S1919转乘L189(下行)到S3186转乘L460(下行)2323106第三组S0971-S0485乘L013(下行)到S2517转乘L290(下行)到S2159转乘L469(上行)2113103第四组S0008-S

26、0073乘L198(上行)到S1383转乘L290(下行)到S2184转乘L345(上行)219367第五组S0148-S0485乘L308(上行)到S0036转乘L156(上行)到S2210转乘L417(下行)2323106第六组S0087-S3676S乘L021(下行)到S0088乘L231(上行)到S0427乘L462(下行)212346 2、对第二问的解答地铁站对原模型的影响是：由于可由地铁站转到另一个公交站进行换乘，这样地铁站就把原来不能直接换乘的公交站联系起来了，并且把通过这两个站点的公交线路连接起来了。所以我们在具体处理时，可以把一个地铁站附近的所有能够通过地铁站转公交站的公交站

27、，看成是同一个公交站，相当于让所有经过这些公交线路都经过同一个公交站，即这些公交线之间都可以换乘。这样就可以把换乘时不坐地铁，但是从地铁站转公交站乘坐公交的问题转化为第一问中在公交站转乘的问题。地铁线路对原模型的影响，同时考虑公汽与地铁时由于地铁方便快捷的特点。在换乘、路径、时间、费用等综合因素中，优先考虑地铁出行和换乘次数不超过两次来确定最优乘车方案。(1)、首先考虑能否直达a)先考虑地铁能否直达通过公交站点搜索得知第六组站点是可以通过站点直接到达的。S0087可换D27，S3676可换D37。地铁T2线是环形线路，乘坐上下行线都可以到达，具体乘坐方案如表6所示。表6：第六组站点乘地铁直达的

28、方案方案乘坐的线路途经的站点总站数站数换乘次数时间(分)费用(元)1T1(上行)D28-D29-D30-D31-D32-D33-D34-D359802032T2（下行）D28-D27-D12-D26-D25-D24-D39-D38-D37-D36-D3511100253b)再考虑公汽能否直达。在第一问的解答中我们已经得出，仅考虑公汽线路题中所要求的六对站点之间是无法直达的。(2)、考虑一次换乘如果无法直达就考虑一次换乘，在一次换乘中有以下四种情况：1)地地换乘，即不出地铁站在地铁的换乘点换乘2)地公换乘，即由地铁站到公交站换乘公交3)公地换乘，即由公交站到地铁站换乘地铁4)公公换乘，仅考虑公汽

29、线路的换乘题中所求的六对站点，除了第六对站点的起点和终点在地铁站附近可以乘地铁外，其他五对站点的起点和终点都不可以直接转地铁所以前三种情况不能到达目的地。对于情况四由于增加了地铁站，在公交换乘时可以从地铁站转乘地铁站邻近的公交站，增加的地铁站具有一定的交通中转站的作用，在增加的换乘方案中可能会找到比一问中更优的解。通过计算机编程计算得出只有第四组站点可以通过在同一地铁站附近的公交站进行转乘，下表7给出了六种转乘情况，其他还有12种转乘方案由于行驶时间过长不予考虑。表7：第四组站点过地铁站转乘公交部分方案起点所乘线路下车站地铁站上车站转乘线路A-CC-B总站数费用(元)时间(分)L159（下行）

30、S0400D13S2633L474(上行)101525280L159（下行）S0291D39S0291L058（下行）18826283L159（下行）S0400D13S0400L474(上行)101626283L159（下行）S0854D28S0856L474(上行)91726283L159（下行）S2633D13S2633L474(上行)111526283L159（下行）S2633D13S0400L474(上行)111627286注：表中AC表示起点到中转站的站数，C-D表示中转站到终点的站数。两次换乘的情况会很多，我们先来考虑两大类简单的情况：(3)、第一大类情况是不乘坐地铁“公公换乘”方

31、式即仅通过公交站和地铁站来换乘公交其中又分为四种情况。情况1中途经过两个公交站转车，这种情况下的结果同问题一中转乘两次的结果。情况2第一次换乘时由公交站到地铁站再到公交站换车，第二次换乘直接在公交站车。情况3第一次换乘直接在公交站，第二次换乘时由公交站到地铁站再到公交站换车。情况4两次换乘时都通过地铁站中转换车。对情况2-4我们根据题目中给的关于地铁线换乘公汽信息数据信息，将所有在同一个地铁站附近的公交站点假设成一个新的站点，并用其替换原有的相邻站点，这样将该问题转化为问题一中直接通过公交车站二次换乘的情况。将公交线路数据修改后，直接代入问题一中二次换乘的程序，计算出可经过地铁站进行二次换乘的

32、乘车方案，但其计算结果与直接在公交车站进行转乘的换乘方式向一致，说明在经过地铁站进行转乘对于本题目所给出的6对站点来说，不能进一步优化。但理论上它能够增加公交换乘的可能性，必然能够得到更优化的结果。(4)、第二大类情况是乘坐地铁a) 只乘坐地铁时的两次换乘 不出地铁站地铁与地铁之间实现换乘。地铁单行线路T1和地铁环形线路T2有且仅有两个共同经过的两个站点D12和D18，D12和D18为地铁一号线和地铁二号线的中转站，如果要在地铁站内部实现换乘必须换乘两次。第一问中的第六对站点就有了第三种乘车方案，即在D12和D18换乘。综合考虑一问中第六对站点的乘车方案得出下表8表8：第六组站点经过地铁转乘的

33、乘车方案方案乘坐的线路途经的站点总站数站数换乘次数时间（分）费用（元）1T1T2换乘D27-D12(换T1)-D13-D14-D15-D16-D17-D18(换T2)-D33-D34-D3511102293但是从表中可以看出从距离、换乘次数、时间、和费用等因素来看直接乘坐地铁T2线直达是最优的。b) 乘坐地铁又乘坐公交时的两次换乘，由于题中除第六组站点之外其余五组站点的起点和终点均无法直接乘坐地铁，所以我们仅考虑中途换乘地铁的情况，即乘公交到公交站，由公交站到地铁站乘坐地铁，再由地铁站到公交站乘坐公交到达目的地。根据以上转乘方案得出从第一组到第五组的最有换乘方案，由于文章篇幅有限仅给出部分数据

34、如下表9所示。表9：一到五组站点乘坐地铁两次换乘时的最优方案组数起点所乘公交线下车站上地铁站下地铁站上车站转乘公交线公交站数公交时间地铁站数地铁运行时间总时间(分)总费用(元)1L015(上行)S3068D8D38S3262L041(上行)1545926.584.551L015(上行)S0616D8D38S3262L041(上行)1648926.587.552L084(下行)S0978D32D24S0537L516(上行)2781922.5116.552L084(下行)S1919D20D24S0537L516(上行)2575102911753L094(上行)S0567D1D21S0464L46

35、9(下行)113320509653L094(上行)S0567D1D21S0466L051(上行)113320509654L200(上行)S2534D15D25S0525L103(上行)824516.553.554L150(下行)S3874D30D25S0525L103(上行)9276155555L024(下行)S1487D2D21S0464L469(下行)9271947.587.555L024(下行)S1487D2D21S0466L051(上行)9271947.587.553、对第三问的解答如果考虑可以步行一段路程，根据实际情况，我们约定在到达公交车站或到达目的地时最多可以步行一站路，则我们提出了“步行公交步行”模型，即AB之间没有直达公交或地铁，但通过步行仅需坐一次公交车即可到达的线路情况进行讨论。具体实现算法如下：i. 搜索出所有经过A点的线路存为X(i)，所有经过 B点的线路存为Y(j)ii. 搜索X(i)包含的所有公交站点存为公交换乘矩阵O(i,u)，同理得Y(j)的换乘矩阵P(j,v)iii. 在 O(i,u)中找出与A点仅有一站距离的乘车点集合存为pA(m)，按相同条件搜索得pB(n)iv. 搜索线路站点对应矩阵D_Path，找出所有同时包含pA(m)与pB(n)的线路（即以pA(m)为起点pB(n)为终点的所有公交线路