数学建模答辩课件.ppt

《数学建模答辩课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、乘公交，看奥运问题的探索为了迎接08年奥运会北京的公交线路已达800条以上，为满足公众查询公交线路的选择问题，因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。鉴于公交系统网络的复杂性，我们没有采用常规的Dijkstra算法，而采用了高效的广度优先算法针对问题一（只考虑公汽系统），我们建立了模型一并通过VC++编程得到了任意两个站点间的多种最优路线，并得出所求站点间最优路线的最优值模型二是根据问题二（同时考虑公汽和地铁系统）建立的，同样用VC++编程得到所求站点间的最优路线对问

2、题三（将步行考虑在内）我们建立了模型三的优化模型，然后在模型改进里又建立了图论模型。摘要主要内容一、模型假设二、问题的理解与分析三、模型的建立与求解四、模型的评价与改进一、模型假设1、相邻公汽站平均行驶时间(包括停站时间)：3分钟2、相邻地铁站平均行驶时间(包括停站时间)：2.5分钟3、公汽换乘公汽平均耗时：5分钟(其中步行2分钟)4、地铁换乘地铁平均耗时：4分钟(其中步行分钟)5、地铁换乘公汽平均耗时：7分钟(其中步行4分钟)6、公汽换乘地铁平均耗时：6分钟(其中步行分钟)7、公汽票价：0～20站

3、：1元；21～40站：2元40站以上：3元；8、地铁票价：3元9、查询者转乘公交的次数不超过两次；10、所有环行公交、地铁线T2线路都是双向的；11、公交、列车均到站停车且都运行正常，不会发生堵车现象；对于路线的评价，我们可以分别以总时间，总转乘次数，总费用为指标，也可以将三种指标标准化后赋以不同权值形成一个综合指标。二、问题的理解与分析本问题可归结为一个求最短路径的问题，但是传统的Dijkstra最短路径算法并不适用于本问题，为此我们采用了效率较高广度优先算法，其基本思路是每次搜索指定点，并将其所

4、有未访问过的近邻点加入搜索队列，循环搜索过程直到队列为空三、模型的建立与求解问题一：考虑到实际情况，转乘次数以不超过2次为佳，因此找出了任意两个公汽站点间的可行路线，就可以对这些路线按不同需求进行选择，找出最优路线了模型一建立：1）以时间最短作为最优路线的模型：行程时间等于乘车时间与转车时间之和。其中，第k路线是以上转乘路线中的一种或几种。3）以费用最少作为最优路线的模型：其中2）以转乘次数最少作为最优路线的模型：此模型等效为以上转乘路线按直达、转乘一次、两次的优先次序来考虑（1）首先输入需要查询的

5、两个站点（起始站，为终点站）；我们采用广度优先算法找出任意两个站点间的可行路线，然后搜索出最优路线。现将此算法运用到该问题中，如下图：其中（a）、（b）、（c）图分别表示了从点到点直达、转乘一次、转乘两次的情况）图6.2公交直达、转乘图模型一的求解：（2）搜索出经过起始站的公交线路和经过终点站的公交线路存入数据文件；判断是与是否存在相同路线，若有则该路线是换乘次数最少(的路线，若有多条直达路线，则可以在此基础上找出时间最省的路线；这样可以找出所有直达路线（3）找出经过的起始站公交线路中的另一站点和经

6、过终点站的公交线路中的另一站点。判断其中是否存在相同的点（4）再搜索出经过起始站线路上除了站点的另一站点的公汽线路找出公汽线路上的其他站点；判断，如果与经过的公汽线路中的其他站点存在相同的点则与间有二次换乘的路线（5）对上述存储的经过两个站点与的不同路线，根据不同模型进行最优路线进行搜索，得出查询者满意的最优路线。起始站耗时最少（min）最优路线（条）S3359→S18286428S1557→S04811062S0971→S04851062S0008→S0073672S0148→S0481063S0

7、087→S3674612最后根据以上算法和前面建立的模型一，用VC++进行编程就可以得出不同目标下的最优路线模型一的结果1）以耗时最少的最优路线表起始站公汽线路中转站公汽线路终到站耗时所需费用S3359L0956S1784L0687S18281013S3359L0956S1784L0737S18281013S0971L0533S2184L0937S04851283S0008L0679S0291L0578S0073832S0008L0679S0491L0578S0073832S0008L0679S25

8、59L0578S0073832S0008L0679S2683L0578S0073832S0008L0679S3614L0578S0073832S0008L0875S2263L0345S0073832S0008L0875S2303L0345S0073832S0008L0875S3917L0345S0073832S0008L0983S2083L0057S00738322）转乘次数最少的最优路线表3）以费用最少为目标的最优路线起始站费用（元）路线（条）备注S3359→S18