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