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

minf???i?1520i?1520iXi???mTmm?122minT?Tr?TcminZ?(?Xi?1)??Sm?1i?1395739??Tr??(aj?1)?3?(?dn?1)?2.5j?1i?1??Tc?T1?T2?T3?T4?520520?当ajXi?1时1??ajXi?2??i?0i?0?3957???aj?Xi?2?j?12?1时1??Sm?dn?2?当dn＝m?0??39??Sm?dn?2 ?n?1

2.2 模型的求解

在加入了地铁之后，同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费，由于乘客关心的是两个汽车站点之间的路线，地铁线路就可以看作汽车站内部之间特殊的通路，原来不连通的站点之间可能变的可以直接到达，乘客也可以考虑同时乘坐地铁和公交车以方便出行。依然考虑采用第一问的模型解法：

方法1．搜索算法

处理方法与问题一中的搜索算法的可按照同样的原理处理 模型求解：结果以及评价说明看2.3模型结果，程序见附录4

方法2．Floyd算法：

关于最短到达时间的计算方法及步骤：

(1)算法思想：基本算法思想如第一问。在加入了地铁之后，同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费，由于乘客关心的是两个汽车站点之间的路线，地铁线路就可以看作汽车站内部之间特殊的通路，原来不连通的站点之间可能变的可以直接到达，乘客可以通过地铁直接在两个公交站点之间进行换乘，也可以乘坐地铁后换乘，这样，就改变了原有的初始矩阵。这样可以大大简化运算的中转次数，减少其运算的复杂程度，提高运算速度，如果两个公交均对应地铁车站，则地铁线路可以看成两个公交车站内部特殊的通路。

16

(2) 计算方法及步骤：

第一步，将地铁内部看作一个系统，生成各站点之间的初始带权邻接矩阵

C?[c(0)(i,j)]n?n，其中，c(0)(i,j)表示不经过转车从i站点到j站点的时间。如果从i点不用转车可以直接到j点，则c(0)(i,j)为i，j之间的乘车站数乘以2.5。如果从i点不可以直接到j点，则使得d(0)(i,j)???，表示不经过转车不可以从i点直接到j点。同样按照利用Floyd算法，很快得到地铁内部的最优邻接矩阵C(n)，得到任意两个地铁站点之间的最短时间。

第二步：生成两个公交站点之间只能乘坐地铁的带权联结矩阵其中，e(0)(i,j)表示只通过地铁第i个公交站点到达第j个公E(0)?[e(0)(i,j)]n?n，

交站点所用的时间。如果可以从i点通过不同的地铁站连接直接到j点，则

e(0)(i,j)为通过地铁最短到达时间c(n)(i,j)＋4＋6。其中6分钟为汽车站走入地铁站的时间，其中4分钟为地铁站走出到汽车站的时间。如果从第i个公交站点不可以通过地铁连接直接到第j个公交站点，则使得e(0)(i,j)???。如果可以从i点通过相同的地铁站连接直接到j点，则e(0)(i,j)＝0

第三步：合并E(0)与没有地铁时两个公交站点之间的初始连通矩阵。如果

e(0)(i,j)?d(0)(i,j)，表示通过乘坐地铁，不转乘公交时两个公交站点之间的最短到达时间变小了，则e(1)(i,j)?e(0)(i,j)。否则，说明乘坐地铁对这两个站点的初始连接状况没有影响，依然有

e(1)(i,j)?d(0)(i,j)

第四步：现在如果两个汽车站中间需要通过汽车站进行中转才能连通，其转乘的时间与第一问转乘时间并不完全相同，因为虽然是汽车站与汽车站之间的转乘，但是现在两个联通的汽车站内部还有可能存在地铁这种情况，所以分4种情况讨论。