1??ajXi?2
i?05203当Xi?1，?aj?Xi表示所选路线中第i条线路所经过的所有站点数。在选
j?13957取的任何一条线路上，都必须坐一站路以上，即必须有两个站点。故约束条件为：
3957j?1?aj?Xi?2
最终，模型如下所示：
3957minT?minf?minZ??(aj?1j?1)?3?(?Xi?1)?5i?1520??i?1520i?1520iXii?X?1
520?时，1??ajXi?2?当aj?1?i?0?3957??a?X?2ji?j?1?
1.4 模型求解
由于题目所给的数据量很大，利用lingo求解优化模型是几乎不可能的，因此，考虑采取优化算法，对模型进行求解。
1.5算法实现
方法1.搜索算法 （1）算法思想：
假设乘客从A 站乘公交车去B站，首先，看A站是否有公交车直接到B站。如果有一条或多条直达公交线路，则从中选择线路时间最短和费用最小的公交车。如果没有，则看经过A 站的公交车和经过B站的公交车有没有交叉点，若有交叉点C，则选择在交叉点C转车到达B 站。如果经过A站的公交车和经过B站的公交车没有交叉点，则先乘经过A站的某一路公交车到达某一站C，看经过C 站的公交车与经过B站的公交车有没有交叉点D， 若有， 则在D 站转车到达B站。另外，有可能存在多种两次换乘的方案，此时，需要判断所用时间最短和费用最小的方案。如果经过c 站的公交车与经过B 站的公交车没有交叉点，说
6
明经过两次换乘还不能从A站到达B 站。按照这样的原则，可以计算换乘n次的最优线路。
（2）计算方法及步骤：
第一步：找出与A直接连通的所有站点的集合A(0)(i)，同理，找出与B
（0）直接连通的所有站点的集合B(0)(j)，判断A(i)中是否包含B，如果包含，
则表示不用转车A站点与B 站点即可相连。找出所有满足条件的线路中时间最少和费用最少的线路。继续进行下一步。
第二步：找出所有与A(0)(i)直接连通的所有站点的集合A(1)(i)，判断
A(1)(i)中是否包含B站点，如果包含，则表示通过一次转车，即可由A站点到
达B站点。找出所有满足条件的线路中时间最少和费用最少的线路。继续进行下一步。
第三步：重复上述步骤。
（3）算法复杂度：：可以看出，随着转车次数的增加，A(0)(i)中包含的元素个数是呈几何级数增加的，相应的，计算的复杂程度也是呈几何级数增加的，即
o(an)。该算法在多次运算时的速度会明显降低。
（4）算法评价：该算法的计算复杂度随着换乘次数的增加是呈几何级数增加的，在计算换乘三次以下时，可以较快的给出结果，但是，在计算三次及三次以上换乘时，花费时间很长。在实际中，已经不再适用。但是，乘客的需求往往是多方面的，有些乘客为了尽快的到达目的地很可能会换乘两次以上。
（5）算法的适用模型：因此，该算法只适用于固定的起始站到终点站在有限换乘次数限制下的求解。
（6）模型求解：结果以及评价说明见1.6模型结果，程序见附录一，
方法2．Floyd算法 （1） 算法思想：
从图的带权邻接矩阵A?[a(i,j)]n?n开始，递归地进行n次更新，即由矩阵D(0)?A，按一个公式，构造出矩阵D(1)；又由D(1)用同样的公式构造出矩阵D(2)；最后由又D(n?1)用同样的公式构造出矩阵D(n)。矩阵D(n)的第i行j列便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵。
其递推公式为： D(0)?A D(1)?[dij(1)]n?n 其中dij(1)?min{dij(0),dik(0)?dkj(0)}
7
D(2)?[dij(2)]n?n 其中dij(2)?min{dij(1),dik(1)?dkj(1)} ?
? D(n)?[dij(n)]n?n其中dij(n)?min{dij(n?1),dik(n?1)?dkj(n?1)}
（2）最短到达时间的计算方法及步骤： 具体实现步骤如下：
第一步：生成带权的初始联结矩阵A?[d(0)(i,j)]n?n，其中，d(0)(i,j)表示不经过转车从i站点到j站点的时间。如果可以从i点不用转车可以直接到j点，则
d(0)(i,j)为i，j之间的乘车站数乘以3。如果从i点不可以直接到j点，则使得
d(0)(i,j)???，表示不经过转车不可以从i点直接到j点。
第二步：允许转车1次，即要求i站点经过k站点转车到达j站点。如果经过一次转车，所花费的时间为从i站点到k站点的时间之和，即dik(0)?dkj(0)+W。循环k站点，找到最小的dik(0)?dkj(0)+W，如果其小于dij(0)，则表示在k站点转车后，其花费时间小于不转车所花费的时间dij(0)，令dij(1)=dik(0)?dkj(0)?W，否则，
dij(1)仍然为dij(0)。合并dij(1)生成矩阵D(1)
第三步：允许在D(1)的基础之上再换乘一次，采用类似第二步的算法，循环
()k站点，找到最小的dik(1)?dkj(1)?W ，如果其小于dik(1)，则dij2=dik(1)?dkj(1)?W，
否则，dij(2)仍然等于dij(1)。合并dij(2)生成矩阵D(2)。经过该次迭代，所允许的最大换乘次数为1×2＋1＝3次。
第四步：不断重复上述步骤，直到dij(n)=dij(n?1)，即两个联结矩阵D(n)与D(n?1)完全相同，称此时的D(n)为最优邻接矩阵。这说明经过进一步的迭代，两个站点之间转车次数增加，但是最短到达时间并没有相应减少。这时，迭代已经没有意义，停止迭代。得到第n个联结矩阵时，相应允许的最大换乘次数为2n?1。
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