表7：第四组站点过地铁站转乘公交部分方案
起点所乘线路 下车站 地铁站 上车站 S2633 S0400 S0856 S2633 S0400 转乘线路 L474(上行) L474(上行) L474(上行) L474(上行) L474(上行) A-C C-B 10 10 9 11 11 15 8 16 17 15 16 总站数 25 26 26 26 26 27 费用(元) 时间(分) L159（下行） S0400 D13 L159（下行） S0291 D39 L159（下行） S0400 D13 L159（下行） S0854 D28 L159（下行） S2633 D13 L159（下行） S2633 D13
2 2 2 2 2 2 80 83 83 83 83 86 S0291 L058（下行） 18 注：表中A—C表示起点到中转站的站数，C-D表示中转站到终点的站数。 两次换乘的情况会很多，我们先来考虑两大类简单的情况：
(3)、第一大类情况是不乘坐地铁
“公公换乘”方式即仅通过公交站和地铁站来换乘公交其中又分为四种情况。 情况1中途经过两个公交站转车，这种情况下的结果同问题一中转乘两次的结果。 情况2第一次换乘时由公交站到地铁站再到公交站换车，第二次换乘直接在公交站车。
情况3第一次换乘直接在公交站，第二次换乘时由公交站到地铁站再到公交站换车。 情况4两次换乘时都通过地铁站中转换车。
对情况2-4我们根据题目中给的关于地铁线换乘公汽信息数据信息，将所有在同一个地铁站附近的公交站点假设成一个新的站点，并用其替换原有的相邻站点，这样将该问题转化为问题一中直接通过公交车站二次换乘的情况。将公交线路数据修改后，直接代入问题一中二次换乘的程序，计算出可经过地铁站进行二次换乘的乘车方案，但其计算结果与直接在公交车站进行转乘的换乘方式向一致，说明在经过地铁站进行转乘对于本题目所给出的6对站点来说，不能进一步优化。但理论上它能够增加公交换乘的可能性，必然能够得到更优化的结果。
(4)、第二大类情况是乘坐地铁 a) 只乘坐地铁时的两次换乘
不出地铁站地铁与地铁之间实现换乘。地铁单行线路T1和地铁环形线路T2有且仅有两个共同经过的两个站点D12和D18，D12和D18为地铁一号线和地铁二号线的中转站，如果要在地铁站内部实现换乘必须换乘两次。第一问中的第六对站点就有了第三种乘车方案，即在D12和D18换乘。
综合考虑一问中第六对站点的乘车方案得出下表8
表8：第六组站点经过地铁转乘的乘车方案 方案 乘坐的线路 途经的站点 D27-D12(换T1)-D13-D14-D15-D16- D17-D18(换T2)-D33-D34-D35 总站数 站数 换乘 次数 2 时间（分） 29 费用（元） 3 1 T1\\T2换乘 11 10 但是从表中可以看出从距离、换乘次数、时间、和费用等因素来看直接乘坐地铁T2线直达是最优的。
11
b) 乘坐地铁又乘坐公交时的两次换乘，
由于题中除第六组站点之外其余五组站点的起点和终点均无法直接乘坐地铁，所以我们仅考虑中途换乘地铁的情况，即乘公交到公交站，由公交站到地铁站乘坐地铁，再由地铁站到公交站乘坐公交到达目的地。根据以上转乘方案得出从第一组到第五组的最有换乘方案，由于文章篇幅有限仅给出部分数据如下表9所示。
表9：一到五组站点乘坐地铁两次换乘时的最优方案 组数 1 1 2 2 3 3 4 4 5 5 起点所乘公交线 下车站 上地铁站 D8 D8 D32 D20 D1 D1 D15 D30 D2 D2 下地铁站 D38 D38 D24 D24 D21 D21 D25 D25 D21 D21 上车站 转乘公交线 公交公交地铁站数 9 9 9 10 20 20 5 6 19 19 地铁运行时间 26.5 26.5 22.5 29 50 50 16.5 15 47.5 47.5 总时间(分) 84.5 87.5 116.5 117 96 96 53.5 55 87.5 87.5 总费用(元) 5 5 5 5 5 5 5 5 5 5 站数 时间 15 16 27 25 11 11 8 9 9 9 45 48 81 75 33 33 24 27 27 27 L015(上行) S3068 L015(上行) S0616 S3262 L041(上行) S3262 L041(上行) S0537 L516(上行) S0537 L516(上行) S0464 L469(下行) S0466 L051(上行) S0525 L103(上行) S0525 L103(上行) S0464 L469(下行) S0466 L051(上行) L084(下行) S0978 L084(下行) S1919 L094(上行) S0567 L094(上行) S0567 L200(上行) S2534 L150(下行) S3874 L024(下行) S1487 L024(下行) S1487 3、对第三问的解答
如果考虑可以步行一段路程，根据实际情况，我们约定在到达公交车站或到达目的地时最多可以步行一站路，则我们提出了“步行—公交—步行”模型，即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)为终点的所有公交线路），存入W矩阵。
v. 若W的行数>0，则存在AB之间没有直达的但通过步行仅需乘坐一次公交车即
可到达的线路。
然后，我们还可以通过最多一站的步行进行一次公交换乘或公交与地铁换乘、二次公交换乘或公交和地铁的交叉换乘情况，每种情况只需按照上述算法稍加修改即可得到换乘方案。
对于“步行—公交—步行”模型，经过编程计算我们得到了前面五组站点的换乘方案，如表10所示。而对于第六组站点，由于可以直接通过地铁到达，故不再考虑这种方式。
12
表10：步行—公交—步行”模型换乘部分方案
组号 1 4 4 4 6 6 6 A的临近站出发点C S2903 S2743 S3412 S0008 (即A点) S0088 S0630 S0854 B的临近点D C到D公交线号 C-D站点数 S1671 S1671 S1671 S1671 S0427 S0427 S0427 L201上行 L159下行 L159下行 L159下行 L231上行 L381上行 L231上行 19 24 25 26 10 11 11 公交车 运行时间 57 72 75 78 30 33 33 票价 步行站数 总时间 1 2 2 2 1 1 1 2 2 2 1 2 2 2 2k+57 2k+72 2k+75 1k+78 2k+30 2k+33 2k+33 其中：A的临近点表示距离A点不超过一站公交车距离的点，k表示人步行一站路所需要的平均时间。
五、总结
通过以上论述我们所建立的公交网络中的最优路径的模型，可以解决题目中所要求的三个问题。对于第一问，仅考虑公汽线路时。在优先考虑换乘最少的的情况下得出六组站点之间的最优路径，一次换乘时有两组结点不能到达，二在考虑两次换乘时不但都找到了换乘方案，而且得出比在一次换乘的情况下时间、路径、更少的解。第二问，同时考虑地铁线路时，一方面我们可以把问题转化第一问的情况来讨论，另一方面，在原始中数据增加新的数据并把问题有可能出现的情况进行分类讨论。得出了每组站点之间乘车方式。问题三中由于给出了任意两点间的步行时间，考虑步行因素，在换乘方式中除了公汽、地铁又多了一种步行。我们将站点线路图抽象为网络拓扑图，将不同位置的相邻节点归并为一个抽象点。并就“步行—公汽—步行”模型给出了具体结果。
但是文章中还有很多地方值得进一步研究，比如在考虑转乘次数时，如果转乘的次数上限增加，则如何才能减低算法的复杂度，以及考虑步行时还可以在转乘公交或地铁之前先走一段路，再找到更合适的转乘方式。
参考文献
【1】. 【2】. 【3】. 【4】. 【5】.
扈震 张发勇 刘书良.《城市公交换乘数据模型研究及算法实现》《电信网技术》2007年4月第4期
陆忠 钱翔东 张登荣.《基于最短路径查询的城市公交网络拓扑建模研究》 王朝辉 杨洁《公交线路中最由线路的查询算法设计》 冯琰 毕俊《多类型交通系统中的路径分析算法分析》2007
梁虹 袁小群 刘蕊《一中新的公交数据模型与公交查询系统实现》计算机工程与应用2007，43（3）
13
附录：
324(a)S3359S2023S2027201S1327S1842328S0609S0483103S0604S0525S3162S007346711S2703485S1784217167S1828
线路1 方案一
324(a)S3359S2023S2027S1327S1842201S0609S0483328S0604
103S0525S3162S007346711S2703485S1784217167S1828
线路1 方案二
363(a)S1557S3158S2628441(b)S0028S0055395S3544S1788S1787S0051130S1919S2840S3408S1985348S2563189S1402S3186485S2703S0480S2682290(c)167(d)S1783254(e)S1784S0955S1768S0903S2101S0481线路2
14
119143S3565S3333S1180485S1523S1520S2992S0903S1768S0955S0480S3493S0971S3341S2237501(a)S2703S1784132(b)S3409S3241S2480S1783130S1787428S1961400413S0427280S0584289360189S1404S1495S077151(c)S0485
线路3
355S0008S3412S2744S1839378S3685S1008326(a)S094040617S2085S0609S0483328S0604S0525103S3162S0073
线路4 方案一
355S0008S3412S274440617 S2085S0609S0483S0604S1839378S3685S1008S0940362(a)328S0525103S3162S0073
线路4 方案二
15
308S0148S0462S0361S1797S2221S0302427S0710308S0128S2268S1308S1391S2272499S2270S184229321S0087S0630247159S3874189243S2534156S023951(a)S0497470S1921157294S2480S1404S1495S0771线路5
S0485
21S0087S0630247159S3874297S016747S0059286S2336462S0242506S2402S1103S0082209S3676线路6
16