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

（5）算法评价：该算法分别对i，j ，k进行循环，同时还要对标识矩阵进行判断，会比第一个问题的Floyd算法花费更长的时间，但是确保了算法的复杂度并没有随着换乘次数的增加而增加，可以在有限的时间内求得所有站点之间的最短时间和最小费用，且得到的结果是全局最优解。记录最后的联结矩阵之后，可以对所有的站点进行查询。

（6）模型求解：求解结果以及评价说明见2.3，程序见附录6

2.3 模型结果

（S表示汽车站点，L表示乘车的线路，T表示地铁线路，D表示地铁站点） （1） 转时乘费路线类型 S3359-S1828 间 次用 数 S3359-L324-S2027-L201-S0609-D12-T2-D37-S19时间最短 62 4 7 61-L428-S1671-L041-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 最小 推荐线路S3359-L324-S1746-L027-S1784-L167-S1828，转乘次数最小的线路，其耗费时间过大，虽然少转一次车，但是比推荐线路多了近半小时。时间最小的线路虽然比推荐线路少耗费了11分钟，但是需要多转2次车，对一般人来说难以接受。

21

（2） 路线类型 S1557-S0481 时间 转乘费次用 数 S1557-L363(或时间最短 L084)-S1919-L189-S3186-L317-S0902-L31299 3 4 -S0481 S1557-L363(或费用最小 106 2 3 L084)-S1919-L189-S3186-L460-S0481 时间S1557-L363(或106 2 3 转乘最短 L084)-S1919-L189-S3186-L460-S0481 最少 费用S1557-L363(或106 2 3 最小 L084)-S1919-L189-S3186-L460-S0481 时间S1557-L363(或106 2 3 转乘最短 L084)-S1919-L189-S3186-L460-S0481 两次 费用S1557-L363(或106 2 3 最小 L084)-S1919-L189-S3186-L460-S0481 推荐线路S1557-L363(或L084)-S1919-L189-S3186-L460-S0481，比起时间最短的线路多花了7分钟的时间，但是转乘次数少了一次，并且费用相应的少了一元。

（3） 时转乘费路线类型 S0971-S0485 间 次数 用 S0971-L094-S567-D01-T1-D15-S2534-L156-S时间最短 95 3 6 2210-L417-S0485 费用最小 S0971-L013-S2184-L417-S0485 128 1 3 时间S0971-L013-S2184-L417-S0485 128 1 3 转乘最短 最少 费用S0971-L013-S2184-L417-S0485 128 1 3 最小 时间S0971-L094-S0567-D01-T1-D21-S0466-L051-96 2 5 转乘最短 S0485 两次 费用S0971-L013-S2184-L417-S0485 128 1 3 最小 推荐线路S0971-L094-S0567-D01-T1-D21-S0466-L051-S0485，该线路虽然比起最短到达的线路多花了一分钟，但是少转了一次车，并且节省了费用。比起费用最小的线路而言，该线路节省了半个多小时的时间，对绝大多数人来说是划算的。

22

（4） 路线类型 时间最短 S0008-S0073 S0008-L200-S2534-D15-T1-D12-T2-D25-S525-L103-S0073 S0008-L159-S0291-L085-S0073 时间 53.5 转乘费次数 用 2 5 费用最小 83 1 2 时间S0008-L159-S0291-L085-S0073 83 1 2 转乘最短 最少 费用S0008-L159-S0291-L085-S0073 83 1 2 最小 时间S0008-L159-S0854-D28-T2-D25-S0525-L56 2 5 转乘最短 103-S0073 两次 费用S0008-L159-S0291-L085-S0073 83 1 2 最小 两条线路S0008-L200-S2534-D15-T1-D12-T2-D25-S525-L103-S0073和S0008-L159-S0291-L085-S0073各有优势。考虑不同的情况下可以采用不同的线路。如果有急事需要赶时间，推荐线路S0008-L200-S2534-D15-T1-D12-T2-D25-S525-L103-S0073，一般情况下，推荐线路S0008-L159-S0291-L085-S0073。

（5） 转乘费路线类型 S0148-S0485 时间 次数 用 S0148-L024-S1487-D02-T1-D15-S2534-L1时间最短 86.5 3 6 56-S3351-L417-S0485 S0148-L308-S0036-L156-S2210-L417-S04费用最小 106 2 3 85 时间S0148-L024-S1487-D02-T1-D20-S2079-L491 2 5 转乘最短 17-S0485 最少 费用S0148-L308-S0036-L156-S2210-L417-S04106 2 3 最小 85 时间S0148-L024-S1487-D02-T1-D20-S2079-L491 2 5 转乘最短 17-S0485 两次 费用S0148-L308-S0036-L156-S2210-L417-S04106 2 3 最小 85 推荐选择线路S0148-L024-S1487-D02-T1-D20-S2079-L417-S0485，该线路虽然比时间最短的线路多花费了四分钟，但是，少转了一次车并且节省了一元钱。比起费用最小的线路来说，虽然多花了两元钱，但是节省了15分钟。

23

（6） 路线类型 时间最短 费用最小 S0087-S3676 S0087-D27-T2-D36-S3676 S0087-D27-S0088-L231-S427-D36-S3676 时转乘次费间 数 用 30 0 3 49 2 1 时间最S0087-D27-T2-D36-S3676 30 0 3 转乘最短 少 费用最S0087-D27-T2-D36-S3676 30 0 3 小 时间最S0087-D27-T2-D36-S3676 30 0 3 转乘两短 次 费用最S0087-D27-S0088-L231-S427-D36-S49 2 1 小 3676 推荐选择线路S0087-D27-T2-D36-S3676，该线路不用转车，且耗费时间也小的多，虽然多花了2元钱，但是仍让可以接受。

2.4运算结果在实际生活中的运用

本模型已经计算出了任意两站点之间最短运行时间和最小花费的具体数值，为了提高查询速率，避免每次查询都重新进行计算，可以建立数据库进行点对点查询系统。由于全市有总共3957个公交车站，在数据库中建立一个3957*3957的矩阵表格，并矩阵中的每个元素保存编号与之相对应的两个公交车站间的路线，到达时间，价格等信息。建立6个这样的矩阵，分别对应：

1、最快到达需求下不乘坐地铁。 2、最经济到达需求下不乘坐地铁。 3、最轻松到达需求下不乘坐地铁。 4、最快到达需求下乘坐地铁。 5、最经济到达需求下乘坐地铁。 6、最轻松到达需求下乘坐地铁。

把计算出的最优结果都导入数据库中，以Microsoft SQL Sever2005为数据库服务器，Microsoft Visual Studio C# 2005为前台开发语言，可制作出带有图形界面的公交查询系统。

如图所示：

24

用户可根据自己的需要输入信息并将信息提交给公交查询系统，而系统则通过用户输入的信息查询数据库中相对应的乘车路线，进而返回给用户以供使用。

（三）问题三：考虑步行的情况

(1)目标函数

普通人对于在选择路径时，一般不会选取极端情况，都会在时间，金钱，便利三者之间进行平衡，所以我们引入权重系数，?表示对钱的偏爱程度，?表示对时间的偏爱程度，?表示对便利的偏爱程度，M表示出行的代价，取三者权衡以后最小：

minM???f???T???Z

（2） 约束条件

普通人一般会对转车次数，步行时间，车费比较过敏，过高的转车次数，步行时间，车费都会影响他们对路线的选择，所以不能过高

?kY?A，Z?B，f?C

其中A,B,C均为常数，Y表示步行的段数，ki表示步行对应段数的时间 关于费用的函数f由于加入步行后，步行不会带来钱的损失

f???iXi???mSm

i?1m?15202 25