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

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。 …… 此处隐藏：432字，全部文档内容请下载后查看。喜欢就下载吧 ……