07年B题最优公交线路问题(6)

当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