《数学建模答辩ppt课件》由会员分享，可在线阅读，更多相关《数学建模答辩ppt课件（27页珍藏版）》请在金锄头文库上搜索。
1、乘公交，看奥运乘公交，看奥运问题的探索问题的探索 乘公交看奥运问题的探索乘公交看奥运问题的探索 为了迎接为了迎接0808年奥运会北京的公交线路已达年奥运会北京的公交线路已达800800条以上，为满足公条以上，为满足公众查询公交线路的选择问题，因此如何快速、高效地从众多可行路众查询公交线路的选择问题，因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。鉴于公交系统网络的线中选出最优路线成为了解决此问题的关键。鉴于公交系统网络的复杂性，我们没有采用常规的复杂性，我们没有采用常规的DijkstraDijkstra算法，而采用了高效的广度算法，而采用了高效的广度优先算法优先算法 针
2、对问题一（只考虑公汽系统），我们建立了模型一并通过针对问题一（只考虑公汽系统），我们建立了模型一并通过VC+VC+编程得到了任意两个站点间的多种最优路线，并得出所求站点编程得到了任意两个站点间的多种最优路线，并得出所求站点间最优路线的最优值间最优路线的最优值 模型二是根据问题二（同时考虑公汽和地铁系统）建立的，同模型二是根据问题二（同时考虑公汽和地铁系统）建立的，同样用样用VC+VC+编程得到所求站点间的最优路线编程得到所求站点间的最优路线 对问题三（将步行考虑在内）我们建立了模型三的优化模型，对问题三（将步行考虑在内）我们建立了模型三的优化模型，然后在模型改进里又建立了图论模型。然后在模型改
3、进里又建立了图论模型。摘要乘公交看奥运问题的探索乘公交看奥运问题的探索主要内容主要内容一、模型假设一、模型假设二、问题的理解与分析二、问题的理解与分析三、模型的建立与求解三、模型的建立与求解四、模型的评价与改进四、模型的评价与改进乘公交看奥运问题的探索乘公交看奥运问题的探索一、模型假设一、模型假设1 1、相邻公汽站平均行驶时间、相邻公汽站平均行驶时间( (包括停站时间包括停站时间) )： 3 3分钟分钟2 2、相邻地铁站平均行驶时间、相邻地铁站平均行驶时间( (包括停站时间包括停站时间) )： 2.52.5分钟分钟3 3、公汽换乘公汽平均耗时：、公汽换乘公汽平均耗时：5 5分钟分钟( (其中步
4、行其中步行2 2分钟分钟) )4 4、地铁换乘地铁平均耗时：、地铁换乘地铁平均耗时：4 4分钟分钟( (其中步行分钟其中步行分钟) )5 5、地铁换乘公汽平均耗时：、地铁换乘公汽平均耗时：7 7分钟分钟( (其中步行其中步行4 4分钟分钟) )6 6、公汽换乘地铁平均耗时：、公汽换乘地铁平均耗时：6 6分钟分钟( (其中步行分钟其中步行分钟) )7 7、公汽票价：、公汽票价：0 0 2020站：站：1 1元；元；21214040站：站：2 2元元4040站以上：站以上：3 3元；元；8 8、地铁票价：、地铁票价：3 3元元9 9、查询者转乘公交的次数不超过两次；、查询者转乘公交的次数不超过两次
5、；1010 、所有环行公交、地铁线、所有环行公交、地铁线T2T2线路都是双向的；线路都是双向的；1111、公交、列车均到站停车且都运行正常，不会发生堵车现象；、公交、列车均到站停车且都运行正常，不会发生堵车现象；乘公交看奥运问题的探索乘公交看奥运问题的探索对于路线的评价，我们可以分别以总时间，总转乘次数，总费用为对于路线的评价，我们可以分别以总时间，总转乘次数，总费用为指标，也可以将三种指标标准化后赋以不同权值形成一个综合指标。指标，也可以将三种指标标准化后赋以不同权值形成一个综合指标。二、问题的理解与分析二、问题的理解与分析本问题可归结为一个求最短路径的问题，但是传统的本问题可归结为一个求最
6、短路径的问题，但是传统的Dijkstra最短路径算法最短路径算法并不适用于本问题，为此我们采用了效率较高广度优先算法，其基本思路并不适用于本问题，为此我们采用了效率较高广度优先算法，其基本思路是每次搜索指定点，并将其所有未访问过的近邻点加入搜索队列，循环搜是每次搜索指定点，并将其所有未访问过的近邻点加入搜索队列，循环搜索过程直到队列为空索过程直到队列为空乘公交看奥运问题的探索乘公交看奥运问题的探索三、模型的建立与求解三、模型的建立与求解问题一：问题一： 考虑到实际情况，转乘次数以不超过考虑到实际情况，转乘次数以不超过2 2次为佳，因此找出了任意两次为佳，因此找出了任意两个公汽站点间的可行路线，
7、就可以对这些路线按不同需求进行选择，找个公汽站点间的可行路线，就可以对这些路线按不同需求进行选择，找出最优路线了出最优路线了模型一建立：模型一建立：1 1）以时间最短作为最优路线的模型：行程时间等于乘车时间与转车时）以时间最短作为最优路线的模型：行程时间等于乘车时间与转车时间之和。间之和。 其中，第其中，第k k路线是以上转乘路线中的一种或几种。路线是以上转乘路线中的一种或几种。乘公交看奥运问题的探索乘公交看奥运问题的探索3 3）以费用最少作为最优路线的模型：）以费用最少作为最优路线的模型：其中其中 2 2）以转乘次数最少作为最优路线的模型：）以转乘次数最少作为最优路线的模型：此模型等效为以上
8、转乘路线按直达、转乘一次、两次的优先次序来考虑此模型等效为以上转乘路线按直达、转乘一次、两次的优先次序来考虑 乘公交看奥运问题的探索乘公交看奥运问题的探索 （1 1）首先输入需要查询的两个站点（起始站，为终点站）；）首先输入需要查询的两个站点（起始站，为终点站）；我们采用广度优先算法找出任意两个站点间的可行路线，然后搜索我们采用广度优先算法找出任意两个站点间的可行路线，然后搜索出最优路线。现将此算法运用到该问题中，如下图：其中（出最优路线。现将此算法运用到该问题中，如下图：其中（a a）、）、（b b）、（）、（c c）图分别表示了从点到点直达、转乘一次、转乘两次的）图分别表示了从点到点直达、
9、转乘一次、转乘两次的情况）情况）图6.2 公交直达、转乘图模型一的求解：模型一的求解：乘公交看奥运问题的探索乘公交看奥运问题的探索（2 2）搜索出经过起始站的公交线路）搜索出经过起始站的公交线路 和经过终点站的公交和经过终点站的公交 线线路存入数据文件；判断是与是否存在相同路线，若有则该路线是路存入数据文件；判断是与是否存在相同路线，若有则该路线是换乘次数最少换乘次数最少( (的路线，若有多条直达路线，则可以在此基础上的路线，若有多条直达路线，则可以在此基础上找出时间最省的路线；这样可以找出所有直达路线找出时间最省的路线；这样可以找出所有直达路线（3 3）找出经过的起始站公交线路中的另一站点和
10、经过终点站的公交）找出经过的起始站公交线路中的另一站点和经过终点站的公交线路中的另一站点。判断其中是否存在相同的点线路中的另一站点。判断其中是否存在相同的点（4 4）再搜索出经过起始站线路上除了站点的另一站点的公汽线路找）再搜索出经过起始站线路上除了站点的另一站点的公汽线路找出公汽线路上的其他站点；判断，如果与经过的公汽线路中的其出公汽线路上的其他站点；判断，如果与经过的公汽线路中的其他站点存在相同的点则与间有二次换乘的路线他站点存在相同的点则与间有二次换乘的路线（5 5）对上述存储的经过两个站点与的不同路线，根据不同模型进行）对上述存储的经过两个站点与的不同路线，根据不同模型进行最优路线进行
11、搜索，得出查询者满意的最优路线。最优路线进行搜索，得出查询者满意的最优路线。乘公交看奥运问题的探索乘公交看奥运问题的探索起始站起始站耗时最少（耗时最少（minmin）最优路线（条）最优路线（条）S3359 S1828S3359 S182864642828S1557 S0481S1557 S04811061062 2S0971 S0485S0971 S04851061062 2S0008 S0073S0008 S007367672 2S0148 S048S0148 S0481061063 3S0087 S367S0087 S36746461212最后根据以上算法和前面建立的模型一，用最后根据以上
12、算法和前面建立的模型一，用VC+VC+进行编程就可进行编程就可以得出不同目标下的最优路线以得出不同目标下的最优路线 模型一的结果模型一的结果1）以耗时最少的最优路线表）以耗时最少的最优路线表乘公交看奥运问题的探索乘公交看奥运问题的探索起始站公汽线路中转站公汽线路终到站耗时所需费用S3359L0956S1784L0687S18281013S3359L0956S1784L0737S18281013S0971L0533S2184L0937S04851283S0008L0679S0291L0578S0073832S0008L0679S0491L0578S0073832S0008L0679S2559L0
13、578S0073832S0008L0679S2683L0578S0073832S0008L0679S3614L0578S0073832S0008L0875S2263L0345S0073832S0008L0875S2303L0345S0073832S0008L0875S3917L0345S0073832S0008L0983S2083L0057S00738322 2）转乘次数最少的最优路线表）转乘次数最少的最优路线表乘公交看奥运问题的探索乘公交看奥运问题的探索3 3）以费用最少为目标的最优路线）以费用最少为目标的最优路线起始站起始站费用（元）用（元）路路线（条）（条）备注注S3359 S1828S
14、3359 S18283 330302828条路条路线需需64 min64 min，转乘乘2 2次，另两条路次，另两条路线需需101 min101 min，转乘乘1 1次次S1557 S0481S1557 S04813 32 2所需所需时间为106 min106 min，转乘乘2 2次；次；S0971 S0485S0971 S04853 33 3两条路两条路线需需106 min106 min，转乘乘2 2次，另一条次，另一条需需128 min128 min，转乘乘1 1次次S0008 S0073S0008 S00732 29 9所需所需时间为83 min83 min，转乘乘1 1次次S0148
15、S048S0148 S0483 33 3所需所需时间为106min106min，转乘乘2 2次次S0087 S367S0087 S3673 31212所需所需时间为46 min46 min，转乘乘2 2次次乘公交看奥运问题的探索乘公交看奥运问题的探索 将公汽与地铁同时考虑，找出最优路线。对于地铁路，也可以将其作为将公汽与地铁同时考虑，找出最优路线。对于地铁路，也可以将其作为公交线路，本质上没有什么区别，只是参数不一样。因此地铁站可等效公交线路，本质上没有什么区别，只是参数不一样。因此地铁站可等效为公交站，地铁和公交的转乘站即可作为两者的交汇点。因此该模型的为公交站，地铁和公交的转乘站即可作为两
16、者的交汇点。因此该模型的公交换乘路线模型与模型一中的基本相同公交换乘路线模型与模型一中的基本相同模型二建立：模型二建立：1 1）以时间最短的路线作为最优路线的模型：可行路线的总时间为乘公）以时间最短的路线作为最优路线的模型：可行路线的总时间为乘公交（公汽和地铁）时间与公汽与地铁换乘、公汽间、地铁间换乘时间交（公汽和地铁）时间与公汽与地铁换乘、公汽间、地铁间换乘时间之和之和其中，第其中，第k k路线为同时考虑公汽与地铁的转乘路线中的一种或几种路线为同时考虑公汽与地铁的转乘路线中的一种或几种 问题二问题二乘公交看奥运问题的探索乘公交看奥运问题的探索2 2）以转乘次数最少的路线作为最优路线的模型）以
17、转乘次数最少的路线作为最优路线的模型：此模型等效为以上转乘路线按直达、转乘一次、两次（包括公交与此模型等效为以上转乘路线按直达、转乘一次、两次（包括公交与地铁间的转乘）的优先次序来考虑。地铁间的转乘）的优先次序来考虑。3 3）以费用最少的路线作为最优路线的模型：）以费用最少的路线作为最优路线的模型：可行路线的费用为乘公交和地铁费用的总和。其中可行路线的费用为乘公交和地铁费用的总和。其中 仍满足仍满足模型一的约束条件模型一的约束条件乘公交看奥运问题的探索乘公交看奥运问题的探索 由题可知，问题一是问题二解的一部分在问题二中，新由题可知，问题一是问题二解的一部分在问题二中，新产生的最优解主要源于在通
18、过换乘地铁、换乘附近相近站点产生的最优解主要源于在通过换乘地铁、换乘附近相近站点的路线上，如图：的路线上，如图： 模型二的求解模型二的求解 从点从点A A到到B B，图，图(a)(a)表示的是通过两公交线路上相邻公汽站表示的是通过两公交线路上相邻公汽站S1,S2S1,S2进行一次转乘；图进行一次转乘；图(b)(b)表示利用地铁站进行二次转乘；图表示利用地铁站进行二次转乘；图(c)(c)表示利用另一条公汽路线为中介进行二次转乘。表示利用另一条公汽路线为中介进行二次转乘。乘公交看奥运问题的探索乘公交看奥运问题的探索图6.3 T1与T2铁路位置关系图铁路线路引入给题目的求解增加了难度，为了形象了解为
19、数不多的两条铁铁路线路引入给题目的求解增加了难度，为了形象了解为数不多的两条铁路间的交叉关系，我们通过路间的交叉关系，我们通过matlab编程作出了两条铁路的位置关系图，如编程作出了两条铁路的位置关系图，如图所示，图所示，图中的直线表示图中的直线表示T1T1铁路线，圆表示铁路线，圆表示T2T2铁路线，数值表示站铁路线，数值表示站点点乘公交看奥运问题的探索乘公交看奥运问题的探索同样将地铁线路等效为公交线路得出任意两个站点间的可行线路同样将地铁线路等效为公交线路得出任意两个站点间的可行线路再将目标函数分别用模型二建立的模型表达式表达，用再将目标函数分别用模型二建立的模型表达式表达，用VC+VC+进
20、行进行编程求得出考虑地铁情况的最优路线编程求得出考虑地铁情况的最优路线1 1）以转乘次数最少为目标的最优路线）以转乘次数最少为目标的最优路线模型二的答案模型二的答案起始站起始站转乘次数乘次数路路线（条）（条）S3359 S1828S3359 S18281 11 1S1557 S0481S1557 S04810 01 1S0971 S0485S0971 S04852 21010S0008 S0073S0008 S00732 22020S0148 S048S0148 S0482 21717S0087 S367S0087 S3672 22 2乘公交看奥运问题的探索乘公交看奥运问题的探索2 2）以耗时
21、最少为目标的最优路线）以耗时最少为目标的最优路线起始站起始站耗耗时（minmin）路路线（条）（条）S3359 S1828S3359 S182864642828S1557 S0481S1557 S04811091091717S0971 S0485S0971 S048596963 3S0008 S0073S0008 S007355553 3S0148 S048S0148 S04887.587.51010S0087 S367S0087 S36733331 1乘公交看奥运问题的探索乘公交看奥运问题的探索3 3）最少费用的最优路线）最少费用的最优路线起始站起始站费用（元）用（元）路路线（条）（条）S3
22、359 S1828S3359 S18283 32 2S1557 S0481S1557 S04813 31717S0971 S0485S0971 S04855 51 1S0008 S0073S0008 S00732 21010S0148 S048S0148 S0485 51 1S0087 S367S0087 S3672 21010乘公交看奥运问题的探索乘公交看奥运问题的探索将步行方式考虑在了出行方式当中，更符合实际。因为当出发点将步行方式考虑在了出行方式当中，更符合实际。因为当出发点与换乘点、终点站或转乘站与转乘站之间只相隔几个站时，当然与换乘点、终点站或转乘站与转乘站之间只相隔几个站时，当然该
23、段选择步行方式更优。该段选择步行方式更优。因此作出如下假设：因此作出如下假设：一、如果存在某段路线，其两端点站之间相隔站点数小等于一、如果存在某段路线，其两端点站之间相隔站点数小等于（即至多经过（即至多经过4 4个站点），则该段线路选择步行方式到达目的地。个站点），则该段线路选择步行方式到达目的地。其他的情况用模型二来处理。其他的情况用模型二来处理。二、相邻公交站点（包括地铁站）间平均步行时间为二、相邻公交站点（包括地铁站）间平均步行时间为5 5分钟。分钟。三、如果在公汽线路上选择步行，则公汽间换乘次数减少三、如果在公汽线路上选择步行，则公汽间换乘次数减少1 1；如果；如果在地铁线路上选择步行
24、，则地铁间换乘次数减少在地铁线路上选择步行，则地铁间换乘次数减少1 1，直达线路除外。，直达线路除外。直达和转乘一次、两次的路线需要步行的路段示意图如图直达和转乘一次、两次的路线需要步行的路段示意图如图6.56.5所示。所示。问题三问题三图中（图中（a）表示出发点）表示出发点A与终点站与终点站B间能直达；图中（间能直达；图中（b）表示出发点）表示出发点A与终与终点站点站B间通过一次换乘能到达，其中路段间通过一次换乘能到达，其中路段AC的站点数等于的站点数等于2所以选择步行所以选择步行,同样同样CB路段的站点数小等于路段的站点数小等于2，则也采取步行的方式；，则也采取步行的方式；是否选择步行方式
25、的函数：是否选择步行方式的函数： 图6.5 步行示意图乘公交看奥运问题的探索乘公交看奥运问题的探索对于直达路线，如果出发点与终点站之间相隔站点数小等于对于直达路线，如果出发点与终点站之间相隔站点数小等于4 4则步行，则步行，否则乘车。对于需要转乘的路线的最优路线模型讨论如下：否则乘车。对于需要转乘的路线的最优路线模型讨论如下：1 1）以时间最短的路线作为最优路线的模型：路线总时间等于乘车时）以时间最短的路线作为最优路线的模型：路线总时间等于乘车时间加间加 上步行时间，再加上转乘时间上步行时间，再加上转乘时间模型三建立：模型三建立：乘公交看奥运问题的探索乘公交看奥运问题的探索3 3）以费用最少的
26、路线作为最优路线的模型：）以费用最少的路线作为最优路线的模型：其中其中 仍满足模型一的约束条件仍满足模型一的约束条件，2 2）以转乘次数最少的路线作为最优路线的模型：每步行一次就）以转乘次数最少的路线作为最优路线的模型：每步行一次就少换乘一次车少换乘一次车 模型三的求解与一二相同，在此就不再细说模型三的求解与一二相同，在此就不再细说乘公交看奥运问题的探索乘公交看奥运问题的探索三、模型的评价与改进三、模型的评价与改进（一）模型的优点：（一）模型的优点：1 1、模型是由简单到复杂一步步建立的，使得更贴近实际。、模型是由简单到复杂一步步建立的，使得更贴近实际。2 2、本文的模型简单，其算法直观，容易
27、编程实现。、本文的模型简单，其算法直观，容易编程实现。3 3、本文模型比较注重数据的处理和存储方式，大大提高了查询效率。、本文模型比较注重数据的处理和存储方式，大大提高了查询效率。4 4、本文模型注重效率的提高，通过大量的特征信息的提取，并结合、本文模型注重效率的提高，通过大量的特征信息的提取，并结合有效的算法，使其完全可以满足实时系统的要求。有效的算法，使其完全可以满足实时系统的要求。（二）模型的缺点：（二）模型的缺点：在建模与编程过程中，使用的数据只是现实数据的一种近似，因而得在建模与编程过程中，使用的数据只是现实数据的一种近似，因而得出的结果可能与现实情况有一定的差距。出的结果可能与现实
28、情况有一定的差距。乘公交看奥运问题的探索乘公交看奥运问题的探索（三）模型改进（三）模型改进 以上模型主要是从公交线路出发，寻找公交线路的交叉站作为换站以上模型主要是从公交线路出发，寻找公交线路的交叉站作为换站点。我们也可以从公交站点的角度出发，用图论的方法建立有向赋点。我们也可以从公交站点的角度出发，用图论的方法建立有向赋权图如图所示权图如图所示1 1）当以时间最短为目标时，）当以时间最短为目标时，给每条边赋上时间的权值。给每条边赋上时间的权值。当某段线路的两段点间间隔当某段线路的两段点间间隔站点数小等于站点数小等于3 3时，选择步行，时，选择步行，该线路的权值等于步行时间。该线路的权值等于步
29、行时间。不同公汽和地铁间进行换乘不同公汽和地铁间进行换乘时需要赋给不同的权值，以时需要赋给不同的权值，以表示换乘时间表示换乘时间找出任意两点找出任意两点间可行路线的路径长度后，间可行路线的路径长度后，再搜索出其中的最短路径的再搜索出其中的最短路径的的可行路线作为时间的最优的可行路线作为时间的最优路线路线乘公交看奥运问题的探索乘公交看奥运问题的探索2 2）当以费用最省为目标时，则给每条边赋上费用的权值。）当以费用最省为目标时，则给每条边赋上费用的权值。公汽站点间的边权赋值。同样可以找出任意两点间可行路线的路公汽站点间的边权赋值。同样可以找出任意两点间可行路线的路径长度，然后再搜索出最短路径作为费
30、用的最优路线径长度，然后再搜索出最短路径作为费用的最优路线 从公交站点出发，将公交站点作为网络图中顶点，得出公交从公交站点出发，将公交站点作为网络图中顶点，得出公交的拓扑结构，进而寻求不同目标下的最短路径，为我们提供了另的拓扑结构，进而寻求不同目标下的最短路径，为我们提供了另外一种思路。但是从以上图形的结构，我们已经看得出其复杂程外一种思路。但是从以上图形的结构，我们已经看得出其复杂程度是不可预知的，尤其随着数据的增多，图的复杂度随之上升。度是不可预知的，尤其随着数据的增多，图的复杂度随之上升。如果不寻求一个好的算法，而用常规的如果不寻求一个好的算法，而用常规的DijkstraDijkstra算法，将有可能算法，将有可能在可以忍受的时间范围内得不出有效结果。在可以忍受的时间范围内得不出有效结果。 经过参考相关资料，我们发现用蚂蚁算法可能比较有效。该经过参考相关资料，我们发现用蚂蚁算法可能比较有效。该算法利用了蚂蚁寻食出行路径选择的行为特点，通过线路激素强算法利用了蚂蚁寻食出行路径选择的行为特点，通过线路激素强度的更新机制度的更新机制乘公交看奥运问题的探索乘公交看奥运问题的探索
