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

8

（3）最小乘车费用的计算方法及步骤

第一步：生成带权的初始联结矩阵B?[f(0)(i,j)]n?n，其中，f(0)(i,j)表示不经过转车从i站点到j站点的费用。如果可以从i站点不转车可以直接到j站点，则f(0)(i,j)为i，j站点之间的乘车费用。否则，令f(0)(i,j)???，表示不经过转车从i站点不可以直接到j站点。

第二步：允许转车一次，即要求i站点经过k站点转车到达j站点。如果经过一次转车，则所花费的费用为从i站点到k站点的费用之和，即fik(0)?fkj(0)。循环k站点，找到最小的fik(0)?fkj(0)，如果其小于fij(0)，则表示转车后，其费用小于不转车的费用，令fij(1)=fik(0)?fkj(0)，否则，fij(1)仍然为fij(0)。合并fij(1)生成矩阵B(1)

第三步：允许在B(1)的基础之上再换乘一次，采用类似第二步的算法，循环k站点，找到最小的fik(1)?fkj(1) ，如果其小于fik(1)，则fij(2)=fik(1)?fkj(1)，否则，

fij(2)仍然等于fij(1)。合并fij(2)生成矩阵B(2)。经过该次迭代，所允许的最大换乘次数为3次。

第四步：不断重复上述步骤，直到fij(n)=fij(n?1)，即两个联结矩阵B(n)与B(n?1)完全相同。这说明经过进一步的迭代，两个站点之间转车次数增加，但是最小费用并没有相应减少。这时，迭代已经没有意义，停止迭代。得到第n个联结矩阵时，相应允许的最大换乘次数为n2?1

（4）算法复杂度：本算法在构造初始矩阵的基础上进行迭代，第n次迭代可以计算出第n2?1次换乘情况下的最小到达时间。每次迭代的算法复杂度并没有增加，且在有限的时间内，可以求出任意两点之间的最短到达时间。

（5）算法评价：该算法分别对i，j ，k进行循环，会有一定的时间损失，但是确保了算法的复杂度并没有随着换乘次数的增加而增加，可以在有限的时间内求

9

得所有站点之间的最短时间和最小费用，且得到的结果是全局最优解。记录最后的联结矩阵之后，可以对所有的站点进行查询。

（6）算法的适用模型：该算法适用对最短乘车时间和最小乘车费用的计算。

（7）模型求解：模型结果以及评价说明见1.6，程序见附录2，3

1.6 模型结果

利用搜索算法，可以较轻松的计算出两个站点之间最小转乘次数，并且，可以比较不同转乘方法的时间和费用，在其中选取教合理的线路。

利用Floyd算法，可以计算出任意两个站点之间的最小到达时间和最小费用，乘客可以根据自己的需求不同查询不同的线路。

下面是题目给出的六个线路之间的运算结果：（S表示站点，L表示乘车的线路） （1） 转乘费路线类型 S3359-S1828 时间 次用 数 S3359-L015-S1327-L328-S0525-L103-S0073-L480时间最短 67 5 6 -S2704-L027-S1784-L167-S1828 费用最小 S3359-L436-S1784-L167-S1828 101 1 3 时间S3359-L436-S1784-L167-S1828 101 1 3 转乘最短 最少 费用S3359-L436-S1784-L167-S1828 101 1 3 最小 时间S3359-L324-S1746-L027-S1784-L167-S1828 73 2 3 最多最短 转乘费用两次 S3359-L324-S1746-L027-S1784-L167-S1828 73 2 3 最小 评价说明：时间最短的线路，其最短时间仅需67分钟，但是需要转乘5次，花费6元钱，转乘次数较高，花费较多，一般人不会选择。费用最少的路线虽然转车次数少，但是时间比时间最短的线路多了50％，一般人也不会选择。推荐S3359-L324-S1746-L027-S1784-L167-S1828，耗费钱最少，转乘次数和耗费时间也不多。

10