数学建模答辩PPT

乘公交，看奥运问题的探索乘公交看奥运问题的探索为了迎接08年奥运会北京的公交线路已达800条以上，为满足公众查询公交线路的选择问题，因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。鉴于公交系统网络的复杂性，我们没有采用常规的Dijkstra算法，而采用了高效的广度优先算法针对问题一（只考虑公汽系统），我们建立了模型一并通过VC++编程得到了任意两个站点间的多种最优路线，并得出所求站点间最优路线的最优值模型二是根据问题二（同时考虑公汽和地铁系统）建立的，同样用VC++编程得到所求站点间的最优路线对问题三（将步行考虑在内）我们建立了模型三的优化模型，然后在模型改进里又建立了图论模型。摘要乘公交看奥运问题的探索主要内容一、模型假设二、问题的理解与分析三、模型的建立与求解四、模型的评价与改进乘公交看奥运问题的探索一、模型假设1、相邻公汽站平均行驶时间(包括停站时间)：3分钟2、相邻地铁站平均行驶时间(包括停站时间)：2.5分钟3、公汽换乘公汽平均耗时：5分钟(其中步行2分钟)4、地铁换乘地铁平均耗时：4分钟(其中步行分钟)5、地铁换乘公汽平均耗时：7分钟(其中步行4分钟)6、公汽换乘地铁平均耗时：6分钟(其中步行分钟)7、公汽票价：0～20站：1元；21～40站：2元40站以上：3元；8、地铁票价：3元9、查询者转乘公交的次数不超过两次；10、所有环行公交、地铁线T2线路都是双向的；11、公交、列车均到站停车且都运行正常，不会发生堵车现象；乘公交看奥运问题的探索对于路线的评价，我们可以分别以总时间，总转乘次数，总费用为指标，也可以将三种指标标准化后赋以不同权值形成一个综合指标。二、问题的理解与分析本问题可归结为一个求最短路径的问题，但是传统的Dijkstra最短路径算法并不适用于本问题，为此我们采用了效率较高广度优先算法，其基本思路是每次搜索指定点，并将其所有未访问过的近邻点加入搜索队列，循环搜索过程直到队列为空乘公交看奥运问题的探索三、模型的建立与求解问题一：考虑到实际情况，转乘次数以不超过2次为佳，因此找出了任意两个公汽站点间的可行路线，就可以对这些路线按不同需求进行选择，找出最优路线了模型一建立：1）以时间最短作为最优路线的模型：行程时间等于乘车时间与转车时间之和。其中，第k路线是以上转乘路线中的一种或几种。°N11kk,mkm1kkMinT3(MS1)5N1m1,2,,N11;k1,2,,kgggggg乘公交看奥运问题的探索3）以费用最少作为最优路线的模型：kk,mmMinCCLk,mk,mk,mk,mk,m1W1W2,202W2,40CL3W2,k,mk,mk,m或0MS21MS40MS其中2）以转乘次数最少作为最优路线的模型：此模型等效为以上转乘路线按直达、转乘一次、两次的优先次序来考虑kMinN1乘公交看奥运问题的探索（1）首先输入需要查询的两个站点（起始站，为终点站）；我们采用广度优先算法找出任意两个站点间的可行路线，然后搜索出最优路线。现将此算法运用到该问题中，如下图：其中（a）、（b）、（c）图分别表示了从点到点直达、转乘一次、转乘两次的情况）图6.2公交直达、转乘图模型一的求解：乘公交看奥运问题的探索（2）搜索出经过起始站的公交线路和经过终点站的公交线路存入数据文件；判断是与是否存在相同路线，若有则该路线是换乘次数最少(的路线，若有多条直达路线，则可以在此基础上找出时间最省的路线；这样可以找出所有直达路线（3）找出经过的起始站公交线路中的另一站点和经过终点站的公交线路中的另一站点。判断其中是否存在相同的点（4）再搜索出经过起始站线路上除了站点的另一站点的公汽线路找出公汽线路上的其他站点；判断，如果与经过的公汽线路中的其他站点存在相同的点则与间有二次换乘的路线（5）对上述存储的经过两个站点与的不同路线，根据不同模型进行最优路线进行搜索，得出查询者满意的最优路线。乘公交看奥运问题的探索起始站耗时最少（min）最优路线（条）S3359→S18286428S1557→S04811062S0971→S04851062S0008→S0073672S0148→S0481063S0087→S3674612最后根据以上算法和前面建立的模型一，用VC++进行编程就可以得出不同目标下的最优路线模型一的结果1）以耗时最少的最优路线表乘公交看奥运问题的探索起始站公汽线路中转站公汽线路终到站耗时所需费用S3359L0956S1784L0687S18281013S3359L0956S1784L0737S18281013S0971L0533S2184L0937S04851283S0008L0679S0291L0578S0073832S0008L0679S0491L0578S0073832S0008L0679S2559L0578S0073832S0008L0679S2683L0578S0073832S0008L0679S3614L0578S0073832S0008L0875S2263L0345S0073832S0008L0875S2303L0345S0073832S0008L0875S3917L0345S0073832S0008L0983S2083L0057S00738322）转乘次数最少的最优路线表乘公交看奥运问题的探索3）以费用最少为目标的最优路线起始站费用（元）路线（条）备注S3359→S182833028条路线需64min，转乘2次，另两条路线需101min，转乘1次S1557→S048132所需时间为106min，转乘2次；S0971→S048533两条路线需106min，转乘2次，另一条需128min，转乘1次S0008→S007329所需时间为83min，转乘1次S0148→S04833所需时间为106min，转乘2次S0087→S367312所需时间为46min，转乘2次乘公交看奥运问题的探索将公汽与地铁同时考虑，找出最优路线。对于地铁路，也可以将其作为公交线路，本质上没有什么区别，只是参数不一样。因此地铁站可等效为公交站，地铁和公交的转乘站即可作为两者的交汇点。因此该模型的公交换乘路线模型与模型一中的基本相同模型二建立：1）以时间最短的路线作为最优路线的模型：可行路线的总时间为乘公交（公汽和地铁）时间与公汽与地铁换乘、公汽间、地铁间换乘时间之和kk,mk,nkmnkkkMinT3(MS1)2.5(MD1)5N14N27N36N4其中，第k路线为同时考虑公汽与地铁的转乘路线中的一种或几种问题二乘公交看奥运问题的探索2）以转乘次数最少的路线作为最优路线的模型：kkkkMinN1N2N3N4此模型等效为以上转乘路线按直达、转乘一次、两次（包括公交与地铁间的转乘）的优先次序来考虑。kk,mkmMinCCL3N43）以费用最少的路线作为最优路线的模型：可行路线的费用为乘公交和地铁费用的总和。其中仍满足模型一的约束条件k,mCL乘公交看奥运问题的探索由题可知，问题一是问题二解的一部分在问题二中，新产生的最优解主要源于在通过换乘地铁、换乘附近相近站点的路线上，如图：模型二的求解从点A到B，图(a)表示的是通过两公交线路上相邻公汽站S1,S2进行一次转乘；图(b)表示利用地铁站进行二次转乘；图(c)表示利用另一条公汽路线为中介进行二次转乘。乘公交看奥运问题的探索图6.3T1与T2铁路位置关系图铁路线路引入给题目的求解增加了难度，为了形象了解为数不多的两条铁路间的交叉关系，我们通过matlab编程作出了两条铁路的位置关系图，如图所示，图中的直线表示T1铁路线，圆表示T2铁路线，数值表示站点乘公交看奥运问题的探索同样将地铁线路等效为公交线路得出任意两个站点间的可行线路再将目标函数分别用模型二建立的模型表达式表达，用VC++进行编程求得出考虑地铁情况的最优路线1）以转乘次数最少为目标的最优路线模型二的答案起始站转乘次数路线（条）S3359→S182811S1557→S048101S0971→S0485210S0008→S0073220S0148→S048217S0087→S36722乘公交看奥运问题的探索2）以耗时最少为目标的最优路线起始站耗时（min））路线（条）S3359→S18286428S1557→S048110917S0971→S0485963S0008→S0073553S0148→S04887.510S0087→S367331乘公交看奥运问题的探索3）最少费用的最优路线起始站费用（元）路线（条）S3359→S182832S1557→S0481317S0971→S048551S0008→S0073210S0148→S04851S0087→S367210乘公交看奥运问题的探索将步行方式考虑在了出行方式当中，更符合实际。因为当出发点与换乘点、终点站或转乘站与转乘站之间只相隔几个站时，当然该段选择步行方式更优。因此作出如下假设：一、如果存在某段路线，其两端点站之间相隔站点数小等于２（即至多经过4个站点），则该段线路选择步行方式到达目的地。其他的情况用模型二来处理。二、相邻公交站点（包括地铁站）间平均步行时间为5分钟。三、如果在公汽线路上选择步行，则公汽间换乘次数减少1；如果在地铁线路上选择步行，则地铁间换乘次数减少1，直达线路除外。直达和转乘一次、两次的路线需要步行的路段示意图如图6.5所示。问题三图中（a）表示出发点A与终点站B间能直达；图中（b）表示出发点A与终点站B间通过一次换乘能到达，其中路段AC的站点数等于2所以选择步行,同样CB路段的站点数小等于2，则也采取步行的方式；是否选择步行方式的函数：图6.5步行示意图kmk,m1MS4FS0，其他k,nk,n1MD4FD0其他乘公交看奥运问题的探索对于直达路线，如果出发点与终点站之间相隔站点数小等于4则步行，否则乘车。对于需要转乘的路线的最优路线模型讨论如下：kk,mk,mk,nk,nmnk,mk,mk,nk,nmnkk,mkk,nkkmnk,mk,mk,nk,nmnkkMinT3(1FS)(MS1)2.5(1FD)(MD1)5FS(MS1)5FD(MD1)5(N1FS)4(N2FD)7N36N4(32FS)(MS1)(2.52.5FD)(MD1)5(N1FS,mkk,nkkmn)4(N2FD)7N36N41）以时间最短的路线作为最优路线的模型：路线总时间等于乘车时间加上步行时间，再加上转乘时间模型三建立：乘公交看奥运问题的探索3）以费用最少的路线作为最优路线的模型：kk,mk,mkmMinC(1FS)CL3N4其中仍满足模型一的约束条件，k,mCL2）以转乘次数最少的路线作为最优路线的模型：每步行一次就少换乘一次车kk,mkk,nkkmnMinN1FSN2FDN3N4模型三的求解与一二相同，在此就不再细说乘公交看奥运问题的探索三、模型的评价与改进（一）模型的优点：1、模型是由简单到复杂一步步建立的，使得更贴近实际。2、本文的模型简单，其算法直观，容易编程实现。3、本文模型比较注重数据的处理和存储方式，大大提高了查询效率。4、本文模型注重效率的提高，通过大量的特征信息的提取，并结合有效的算法，使其完全可以满足实时系统的要求。（二）模型的缺点：在建模与编程过程中，使用的数据只是现实数据的一种近似，因而得出的结果可能与现实情况有一定的差距。乘公交看奥运问题的探索（三）模型改进以上模型主要是从公交线路出发，寻找公交线路的交叉站作为换站点。我们也可以从公交站点的角度出发，用图论的方法建立有向赋权图如图所示1）当以时间最短为目标时，给每条边赋上时间的权值。当某段线路的两段点间间隔站点数小等于3时，选择步行，该线路的权值等于步行时间。不同公汽和地铁间进行换乘时需要赋给不同的权值，以表示换乘时间找出任意两点间