P(j,v)(v?1,2,?,h,)
步骤5、判断是否有O(u,i)?P(j,v)将满足条件的存入w，若W?1，则站点O(u,i)即P(j,v)从站点A到站点B的一次换乘点，公交线路X(i),Y(j)为换乘一次的最优线路，输出结果并结束运算。
步骤6、搜索公交数据库，将经过站点O(i,u)的公交线路存为R(k)(k?1,2,?,p,)公交线路R
（k）所包含的站点G(k,t)(t?1,2,?,g,))扩充到公交换乘矩阵O(u,i)中。
步骤7、判断是否有G?k,t??P(j,v)，将满足条件的存入W, 若W?1则站点G(k,t)即P(j,v)为从站点A到站点B的二次换乘点，公交线路X(i),R(k),Y(j)为换乘二次的最佳路线，输出结果并结束运算。
步骤8、设定换乘次数的上界Z,然后在不大于Z次循环的某次循环中找到可行路径，若可行路
径有多条，考虑综合因素为最优的路径并输出
以上步骤如果没有找到合适的公交路线则输出“没有找到换乘次数超过Z次的最优方案”，结束运算。
从我们的日常生活逻辑来讲出行总是会选择换乘次数最少的出行方式。对于换乘次数我们分为三种情况来分析：换乘次数为0、换乘次数为1、换乘次数为2。假设换乘上限Z为2（因为在现实生活中如果要换三次或三次以上的车一般会采取其他的出行方式）
通过MATLAB编程，实现基于广度优先的公交算法。
a) 0次换乘
首先计算0次换乘的情况，根据基于广度优先的公交算法在题目中六对站点之间都没有直达的公交线路。
b) 1次换乘
再考虑1次换乘的情况，根据基于广度优先的公交算法题目中所要求的1、3、4、6条线路可以通过一次换乘到达。换乘一次的情况下优先考虑站数，其次考虑费用，再其次考虑时间可以得出，题中各对站点之间的最优路径。从结果中我们可以看出在优先考虑站点最少的情况下，费用和时间都是最少的。
而第二组S1557-0481和第五组S0148-S0485无法通过一次换乘到达必须考虑两次，或两次以上的换乘的情况。
c) 2次换乘
考虑两次换乘的情况
首先通过程序计算出二次换乘时六对线路所有可能的乘车方案再通过评价函数优先考虑站点数即路径其次考虑费用和时间得出最优解，由于得出的结论大多篇幅有限无法将所有的结果都用表格在文中表示出来，从每组最优解中选出其中三种最优的方案如表3所示，
从表3中我们看到，不仅得到了第二对站S1557-S0481和第五对站的换乘方案。而且可以看到第一对站S3359-S1828第三对站S0971-S0485第四对站S0008-S0073在换乘两次时经过的站点和所用时间比一次换乘时经过的站点和所用的时间要少，而且可选的
6
线路也非常多。
表2：一次换乘公交的最优乘车方案 始发线路 中转 车站 S1784 转乘线路 站数 费用(元) 3 时间（分） 101 L436（下行31站） 第一组 S3359-S1828 L436（下行31站） L214（下行1站） 32 S1784 L167（下行1站） 32 3 101 第三组 S0971-S0485 L13(下行)20 S2184 L417（下行）21 41 3 128 L463（下行14站） L159（下行10站） L159（下行11站） L159（下行12站） L159（下行17站） 第四组 S0008-S0073 L159（下行18站） L159（下行19站） L159（下行20站） L355（下行7站） L355（下行8站） L355（下行9站） 第六组 S0087-S3636 S2083 S0400 S2633 S3053 S2683 S0291 S3614 S0491 S2263 S3917 S2303 L58（上行12站） L475（上行16站） L475（上行15站） L475（上行14站） L58（下行9站） L58（下行8站） L58（下行7站） L58（下行6站） L246（上行19站） L246（上行18站） L246（上行17站） 26 26 26 26 26 26 26 26 26 26 26 2 2 2 2 2 2 2 2 2 2 2 83 83 83 83 83 83 83 83 83 83 83 L455（上行11站） S3496 L209（下行9站） 20 2 65
表3：二次换乘公交的部分最优方案
7
组数 LA C LD D LB A-C 1 2 2 12 12 12 16 2 2 1 1 1 14 14 14 1 1 1 C-D 16 15 15 3 3 17 13 19 19 15 15 15 15 16 17 10 10 10 D-B 1 1 1 17 17 5 2 11 11 3 3 3 3 2 1 1 1 1 总站数 18 18 18 32 32 34 31 32 32 19 19 19 32 32 32 12 12 12 费用(元) 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 时间(分) 64 64 64 106 106 112 103 106 106 67 67 67 106 106 106 46 46 46 方案数 L123(上行) S2903 L485(下行) S1784 L217(下行) 第一组 S3359-S1828 L324(下行) S2027 L485(下行) S1784 L217(下行) L484(下行) S2027 L485(下行) S1784 L217(下行) L363(下行) S1919 L189(下行) S3186 L460(下行) 112 第二组 S1557-S0481 L084(下行) S1919 L189(下行) S3186 L460(下行) L363(下行) S1919 L417(上行) S2424 L254(上行) L013(下行) S2517 L290(下行) S2159 L469(上行) 2 第三组 S0971-S0485 L263(下行) S1609 L140(下行) S2654 L469(上行) L024(下行) S1609 L140(下行) S2654 L469(上行) L198(上行) S1383 L290(下行) S2184 L345(上行) 1 第四组 S0008-S0073 L463(下行) S1383 L290(下行) S2184 L345(上行) L043(下行) S1383 L290(下行) S2184 L345(上行) L308(上行) S0036 L156(上行) S2210 L417(下行) 25 第五组 S0148-S0485 L307(上行) S0036 L156(上行) S3332 L417(下行) L307(上行) S0036 L156(上行) S3351 L417(下行) L022(下行) S0088 L231(上行) S0427 L462(下行) 3 第六组 L205(上行) S0088 L231(上行) S0427 L462(下行) S0087-S3676S L455(下行) S0088 L231(上行) S0427 L462(下行) 48 其中：LA表示起点所乘线路, C表示第一次转乘站, LD表示第一次转乘线路, D表示第二次转乘站, LB表示第二次转乘线路，方案数表示最优方案的总个数。
d) 对第一问的总结
从以上的计算可以看出，如果不考虑地铁的因素，而优先考虑费用最省或时间最少，则优先考虑的因素不同得出的结果是不一样的。不同的乘客会根据自身情况，选择符合自身的乘车方案。
（1）当乘客优先考虑换乘次数时，综合上面换乘次数一次和两次的计算结果，得到六组站点间换乘次数最少的换乘方案如表4。
8
表4：问题一考虑换乘次数最少的最佳线路 第一组 S3359-S1828 第二组 S1557-S0481 第三组 S0971-S0485 第四组 S0008-S0073 第五组 S0148-S0485 第六组 S0087-S3676S 乘车方案 乘L463(下行)到S1784转乘L214(下行) 乘L363(下行)到S1919转乘L189(下行)到S3186转乘L460(下行) 乘L13(下行)到S2184转乘L417(下行) 乘L463(下行)到S2083转乘L58(上行) 乘L308(上行)到S0036转乘L156(上行)到S2210转乘L417(下行) 乘L455(上行)到S3496转乘L209(下行) 换乘 次数 1 2 1 1 2 1 总站数 32 32 41 26 32 20 费用(元) 时间(分) 3 3 3 2 3 2 101 106 128 83 106 65 （2）当乘客优先考虑时间和费用时，从实际情况出发一般考虑换乘次数不超过两次，综合上面换乘次数一次和两次的计算结果，得到六组站点间总站数最少的换乘方案如表5所示，由于限定了换乘次数总站数最少时，所用的时间和费用都是同组站点间的其他换乘方式中最少的。
表5：问题一考虑时间和费用最少的最佳线路 第一组 S3359-S1828 第二组 S1557-S0481 第三组 S0971-S0485 第四组 S0008-S0073 第五组 S0148-S0485 第六组 S0087-S3676S
乘车方案 乘L123(上行) 到S2903转乘L485(下行) 到S1784 转乘L217(下行) 乘L363(下行)到S1919转乘L189(下行)到S3186转乘L460(下行) 乘L013(下行)到S2517转乘 L290(下行)到S2159转乘L469(上行) 乘L198(上行)到S1383转乘L290(下行)到S2184转乘L345(上行) 乘L308(上行)到S0036转乘L156(上行)到S2210转乘L417(下行) 乘L021(下行)到S0088乘L231(上行)到S0427乘L462(下行) 换乘 次数 2 2 2 2 2 2 总站数 18 32 11 19 32 12 费用(元) 时间(分) 3 3 3 3 3 3 64 106 103 67 106 46 2、对第二问的解答
地铁站对原模型的影响是：由于可由地铁站转到另一个公交站进行换乘，这样地铁站就把原来不能直接换乘的公交站联系起来了，并且把通过这两个站点的公交线路连接起来了。所以我们在具体处理时，可以把一个地铁站附近的所有能够通过地铁站转公交站的公交站，看成是同一个公交站，相当于让所有经过这些公交线路都经过同一个公交站，即这些公交线之间都可以换乘。这样就可以把换乘时不坐地铁，但是从地铁站转公
9
交站乘坐公交的问题转化为第一问中在公交站转乘的问题。
地铁线路对原模型的影响，同时考虑公汽与地铁时由于地铁方便快捷的特点。在换乘、路径、时间、费用等综合因素中，优先考虑地铁出行和换乘次数不超过两次来确定最优乘车方案。
(1)、首先考虑能否直达 a)先考虑地铁能否直达
通过公交站点搜索得知第六组站点是可以通过站点直接到达的。S0087可换D27，S3676可换D37。地铁T2线是环形线路，乘坐上下行线都可以到达，具体乘坐方案如表6所示。
表6：第六组站点乘地铁直达的方案
方案 乘坐的线路 途经的站点 D28-D29-D30-D31-D32-D33- D34-D35 D28-D27-D12-D26-D25-D24- D39-D38-D37-D36-D35 总站数 站数 换乘 次数 0 0 时间(分) 20 25 费用(元) 3 3 1 2 T1(上行) T2（下行） 9 11 8 10
b)再考虑公汽能否直达。
在第一问的解答中我们已经得出，仅考虑公汽线路题中所要求的六对站点之间是无法直达的。
(2)、考虑一次换乘
如果无法直达就考虑一次换乘，在一次换乘中有以下四种情况： 1)地地换乘，即不出地铁站在地铁的换乘点换乘 2)地公换乘，即由地铁站到公交站换乘公交 3)公地换乘，即由公交站到地铁站换乘地铁 4)公公换乘，仅考虑公汽线路的换乘
题中所求的六对站点，除了第六对站点的起点和终点在地铁站附近可以乘地铁外，其他五对站点的起点和终点都不可以直接转地铁所以前三种情况不能到达目的地。
对于情况四由于增加了地铁站，在公交换乘时可以从地铁站转乘地铁站邻近的公交站，增加的地铁站具有一定的交通中转站的作用，在增加的换乘方案中可能会找到比一问中更优的解。
通过计算机编程计算得出只有第四组站点可以通过在同一地铁站附近的公交站进行转乘，下表7给出了六种转乘情况，其他还有12种转乘方案由于行驶时间过长不予考虑。
10