minf???i?1520i?1520iXi???mTmm?122minT?Tr?TcminZ?(?Xi?1)??Sm?1i?1395739??Tr??(aj?1)?3?(?dn?1)?2.5j?1i?1??Tc?T1?T2?T3?T4?520520?当ajXi?1时1??ajXi?2??i?0i?0?3957???aj?Xi?2?j?12?1时1??Sm?dn?2?当dn＝m?0??39??Sm?dn?2 ?n?1
2.2 模型的求解
在加入了地铁之后，同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费，由于乘客关心的是两个汽车站点之间的路线，地铁线路就可以看作汽车站内部之间特殊的通路，原来不连通的站点之间可能变的可以直接到达，乘客也可以考虑同时乘坐地铁和公交车以方便出行。依然考虑采用第一问的模型解法：
方法1．搜索算法
处理方法与问题一中的搜索算法的可按照同样的原理处理 模型求解：结果以及评价说明看2.3模型结果，程序见附录4
方法2．Floyd算法：
关于最短到达时间的计算方法及步骤：
(1)算法思想：基本算法思想如第一问。在加入了地铁之后，同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费，由于乘客关心的是两个汽车站点之间的路线，地铁线路就可以看作汽车站内部之间特殊的通路，原来不连通的站点之间可能变的可以直接到达，乘客可以通过地铁直接在两个公交站点之间进行换乘，也可以乘坐地铁后换乘，这样，就改变了原有的初始矩阵。这样可以大大简化运算的中转次数，减少其运算的复杂程度，提高运算速度，如果两个公交均对应地铁车站，则地铁线路可以看成两个公交车站内部特殊的通路。
16
(2) 计算方法及步骤：
第一步，将地铁内部看作一个系统，生成各站点之间的初始带权邻接矩阵
C?[c(0)(i,j)]n?n，其中，c(0)(i,j)表示不经过转车从i站点到j站点的时间。如果从i点不用转车可以直接到j点，则c(0)(i,j)为i，j之间的乘车站数乘以2.5。如果从i点不可以直接到j点，则使得d(0)(i,j)???，表示不经过转车不可以从i点直接到j点。同样按照利用Floyd算法，很快得到地铁内部的最优邻接矩阵C(n)，得到任意两个地铁站点之间的最短时间。
第二步：生成两个公交站点之间只能乘坐地铁的带权联结矩阵其中，e(0)(i,j)表示只通过地铁第i个公交站点到达第j个公E(0)?[e(0)(i,j)]n?n，
交站点所用的时间。如果可以从i点通过不同的地铁站连接直接到j点，则
e(0)(i,j)为通过地铁最短到达时间c(n)(i,j)＋4＋6。其中6分钟为汽车站走入地铁站的时间，其中4分钟为地铁站走出到汽车站的时间。如果从第i个公交站点不可以通过地铁连接直接到第j个公交站点，则使得e(0)(i,j)???。如果可以从i点通过相同的地铁站连接直接到j点，则e(0)(i,j)＝0
第三步：合并E(0)与没有地铁时两个公交站点之间的初始连通矩阵。如果
e(0)(i,j)?d(0)(i,j)，表示通过乘坐地铁，不转乘公交时两个公交站点之间的最短到达时间变小了，则e(1)(i,j)?e(0)(i,j)。否则，说明乘坐地铁对这两个站点的初始连接状况没有影响，依然有
e(1)(i,j)?d(0)(i,j)
第四步：现在如果两个汽车站中间需要通过汽车站进行中转才能连通，其转乘的时间与第一问转乘时间并不完全相同，因为虽然是汽车站与汽车站之间的转乘，但是现在两个联通的汽车站内部还有可能存在地铁这种情况，所以分4种情况讨论。
当Sij需要在Sk车站中转，由Sik与Skj进行连通时，
1中转站Sk的前后两站均是汽车站
17
Si?......?Sm1?Sk?Sn?......?Sj
跟第一题相同，都是汽车站之间的转换的情况，在Sk车站中转时间是5分钟，W=5（W表示等待时间）
2中转站Sk的前面一站是地铁站，后面一站是汽车站 Si?......?Dm1?Sk?Sn?......?Sj
由于从地铁站Dm出站走到汽车站Sk的步行4分钟，已经在处理初始矩阵时，计算入Sik的时间以内，而Sk到Sn的车行时间3分钟已经在处理初始矩阵时算入Skj的时间以内，在Sk车站中转时间只算等车的3分钟，W=3
3中转站Sk的前面一站是汽车站，后面一站是地铁站 Si?......?Sm?Sk?Dn?......?Sj
由于从汽车站Sm车行到汽车站Sk的3分钟，已经在处理初始矩阵时，计算入Sik的时间以内，而汽车站Sk转到地铁站Dn的6分钟已经在处理初始矩阵时算入Skj的时间以内，所以在Sk车站转乘时，没有中转时间，W=0
4中转站Sk的前后一站是地铁站
Si?......?Dm1?Sk?Dn?......?Sj
由于从地铁站Dm出站走到汽车站Sk的步行4分钟，已经在处理初始矩阵时，计算入Sik的时间以内，而汽车站Sk转到地铁站Dn的6分钟已经在处理初始矩阵时算入Skj的时间以内，所以在Sk车站转乘时，没有中转时间，W=0
第五步：所以，为了解决这个问题我们引入标识矩阵
其中F矩阵中的fij表示连接i，j站点的通路中i站点后面那个站点的状态
i站点后面那个站点是地铁站?1 fij??
0i站点后面那个站点是汽车站? 18
其中G矩阵中的gij表示连接i，j站点的通路中j站点前面那个站点的状态
j站点前面那个站点是地铁站?1 gij??
j站点前面那个站点是汽车站?0连接i，j站点的通路中i站点后面的那个站点是地铁 当Sij需要在Sk车站中转，由Sik与Skj进行连通时，
1中转站Sk的前后两站均是汽车站 Si?......?Sm1?Sk?Sn?......?Sj
既fkj?0，gik?0，W=5
2中转站Sk的前面一站是地铁站，后面一站是汽车站
Si?......?Dm1?Sk?Sn?......?Sj 既fkj?0，gik?1，W＝3
3中转站Sk的前后一站是地铁站
Si?......?Dm1?Sk?Dn?......?Sj 既 fkj?1，gik?0，W=0
4中转站Sk的前后一站是地铁站
Si?......?Dm1?Sk?Dn?......?Sj 既，fkj?1，gik?1，W＝0
每迭代一次，如果Sij没有发生变化，则对应的fij(1)?fij，gij(1)?gij（fij(1)表示新生成的标识矩阵的元素）
如果Sij在站点Sk车站中转时，两地运行时间变小，则Si，Sj之间需通过Sk中转
fij(1)?fik，gij(1)?gkj
由于每次的中转时间都必须由中转站前后车站的状态决定，所以新一个的
一个时间矩阵必须由旧的时间矩阵，两个标识矩阵决定。
19
其余迭代的算法除了换乘时间的处理与第一问的不同以外，其他步骤完全相同
第六步：允许在E(1)的基础之上换乘公交车一次，采用与上面类似的Floyd算法进行迭代。由于这时每两个公交站点之间的连接情况都加入了地铁的影响，因此，迭代优化换乘公交车站的最短到达时间即可。
（3）模型求解：求解结果以及评价说明在2.3，程序见附录5
最小费用的计算方法及步骤：
第一步：生成两个公交站点之间只能乘坐地铁的以费用为权的联结矩阵
G(0)?[g(0)(i,j)]n?n，其中，g(0)(i,j)表示只能通过地铁的情况下，第i个公交站点到达第j个公交站点的费用。如果从第i个公交站到第j个公交站只用通过地铁换乘而不用坐地铁，g(0)(i,j)?0。如果从第i个公交站到第j个公交站需要乘坐地铁，则g(0)(i,j)?3。如果从第i个公交站到第j个公交站不能通过地铁连通，g(0)(i,j)?＋?
第二步：合并G(0)与没有地铁时两个公交站点之间的初始费用矩阵。如果表示通过乘坐地铁，不转乘公交时两个公交站点之间的费用g(0)(i,j)?f(0)(i,j)，
变小了，则g(1)(i,j)?g(0)(i,j)。否则，说明乘坐地铁对这两个站点的费用状况没有影响，依然有g(1)(i,j)?f(0)(i,j)
第三步：允许在G(1)的基础之上换乘公交车一次，采用与上面类似的Floyd算法进行迭代。由于这时每两个公交站点之间的连接情况都加入了地铁的影响，因此，迭代优化换乘公交车站的最小费用即可
（4）算法复杂度：本问在一开始就把两个公交站点之间通过地铁相连的情况考虑在内，改变的仅仅是初始矩阵，迭代步骤与上一问类似。因此，并没有增加算法复杂度，在较短时间内，可以求的任意两个站点之间通过地铁和公交车相连的最短到达时间和最小费用。
20