数学建模答辩省名师优质课赛课获奖课件市赛课一等奖课件.ppt

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