《数学建模答辩》由会员分享，可在线阅读，更多相关《数学建模答辩（27页珍藏版）》请在金锄头文库上搜索。
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站：1元；2140站：2元40站以上：3元； 8、地铁票价：3元 9、查询者转乘公交的次数不超过两次； 10 、所有环行公交、地铁线T2线路都是双向的； 1
3、1、公交、列车均到站停车且都运行正常，不会发生堵车现象；,对于路线的评价，我们可以分别以总时间，总转乘次数，总费用为指标，也可以将三种指标标准化后赋以不同权值形成一个综合指标。,二、问题的理解与分析,本问题可归结为一个求最短路径的问题，但是传统的Dijkstra最短路径算法并不适用于本问题，为此我们采用了效率较高广度优先算法，其基本思路是每次搜索指定点，并将其所有未访问过的近邻点加入搜索队列，循环搜索过程直到队列为空,三、模型的建立与求解,问题一： 考虑到实际情况，转乘次数以不超过2次为佳，因此找出了任意两个公汽站点间的可行路线，就可以对这些路线按不同需求进行选择，找出最优路线了 模型一建立：
4、 1）以时间最短作为最优路线的模型：行程时间等于乘车时间与转车时间之和。 其中，第k路线是以上转乘路线中的一种或几种。,3）以费用最少作为最优路线的模型：,其中,2）以转乘次数最少作为最优路线的模型： 此模型等效为以上转乘路线按直达、转乘一次、两次的优先次序来考虑,（1）首先输入需要查询的两个站点（起始站，为终点站）；,我们采用广度优先算法找出任意两个站点间的可行路线，然后搜索出最优路线。现将此算法运用到该问题中，如下图：其中（a）、（b）、（c）图分别表示了从点到点直达、转乘一次、转乘两次的情况）,图6.2 公交直达、转乘图,模型一的求解：,（2）搜索出经过起始站的公交线路 和经过终点站的公
5、交 线路存入数据文件；判断是与是否存在相同路线，若有则该路线是换乘次数最少(的路线，若有多条直达路线，则可以在此基础上找出时间最省的路线；这样可以找出所有直达路线 （3）找出经过的起始站公交线路中的另一站点和经过终点站的公交线路中的另一站点。判断其中是否存在相同的点 （4）再搜索出经过起始站线路上除了站点的另一站点的公汽线路找出公汽线路上的其他站点；判断，如果与经过的公汽线路中的其他站点存在相同的点则与间有二次换乘的路线 （5）对上述存储的经过两个站点与的不同路线，根据不同模型进行最优路线进行搜索，得出查询者满意的最优路线。,最后根据以上算法和前面建立的模型一，用VC+进行编程就可以得出不同目
6、标下的最优路线,模型一的结果,1）以耗时最少的最优路线表,2）转乘次数最少的最优路线表,3）以费用最少为目标的最优路线,将公汽与地铁同时考虑，找出最优路线。对于地铁路，也可以将其作为公交线路，本质上没有什么区别，只是参数不一样。因此地铁站可等效为公交站，地铁和公交的转乘站即可作为两者的交汇点。因此该模型的公交换乘路线模型与模型一中的基本相同,模型二建立： 1）以时间最短的路线作为最优路线的模型：可行路线的总时间为乘公交（公汽和地铁）时间与公汽与地铁换乘、公汽间、地铁间换乘时间之和,其中，第k路线为同时考虑公汽与地铁的转乘路线中的一种或几种,问题二,2）以转乘次数最少的路线作为最优路线的模型：,
7、此模型等效为以上转乘路线按直达、转乘一次、两次（包括公交与地铁间的转乘）的优先次序来考虑。,3）以费用最少的路线作为最优路线的模型：,可行路线的费用为乘公交和地铁费用的总和。其中 仍满足模型一的约束条件,由题可知，问题一是问题二解的一部分在问题二中，新产生的最优解主要源于在通过换乘地铁、换乘附近相近站点的路线上，如图：,模型二的求解,从点A到B，图(a)表示的是通过两公交线路上相邻公汽站S1,S2进行一次转乘；图(b)表示利用地铁站进行二次转乘；图(c)表示利用另一条公汽路线为中介进行二次转乘。,图6.3 T1与T2铁路位置关系图,铁路线路引入给题目的求解增加了难度，为了形象了解为数不多的两条
8、铁路间的交叉关系，我们通过matlab编程作出了两条铁路的位置关系图，如图所示，图中的直线表示T1铁路线，圆表示T2铁路线，数值表示站点,同样将地铁线路等效为公交线路得出任意两个站点间的可行线路再将目标函数分别用模型二建立的模型表达式表达，用VC+进行编程求得出考虑地铁情况的最优路线,1）以转乘次数最少为目标的最优路线,模型二的答案,2）以耗时最少为目标的最优路线,3）最少费用的最优路线,将步行方式考虑在了出行方式当中，更符合实际。因为当出发点与换乘点、终点站或转乘站与转乘站之间只相隔几个站时，当然该段选择步行方式更优。 因此作出如下假设： 一、如果存在某段路线，其两端点站之间相隔站点数小等于
9、（即至多经过4个站点），则该段线路选择步行方式到达目的地。其他的情况用模型二来处理。 二、相邻公交站点（包括地铁站）间平均步行时间为5分钟。 三、如果在公汽线路上选择步行，则公汽间换乘次数减少1；如果在地铁线路上选择步行，则地铁间换乘次数减少1，直达线路除外。直达和转乘一次、两次的路线需要步行的路段示意图如图6.5所示。,问题三,图中（a）表示出发点A与终点站B间能直达；图中（b）表示出发点A与终点站B间通过一次换乘能到达，其中路段AC的站点数等于2所以选择步行,同样CB路段的站点数小等于2，则也采取步行的方式；,是否选择步行方式的函数：,图6.5 步行示意图,对于直达路线，如果出发点与终点站
10、之间相隔站点数小等于4则步行，否则乘车。对于需要转乘的路线的最优路线模型讨论如下：,1）以时间最短的路线作为最优路线的模型：路线总时间等于乘车时间加 上步行时间，再加上转乘时间,模型三建立：,3）以费用最少的路线作为最优路线的模型：,其中 仍满足模型一的约束条件，,2）以转乘次数最少的路线作为最优路线的模型：每步行一次就少换乘一次车,模型三的求解与一二相同，在此就不再细说,三、模型的评价与改进,（一）模型的优点： 1、模型是由简单到复杂一步步建立的，使得更贴近实际。 2、本文的模型简单，其算法直观，容易编程实现。 3、本文模型比较注重数据的处理和存储方式，大大提高了查询效率。 4、本文模型注重
11、效率的提高，通过大量的特征信息的提取，并结合有效的算法，使其完全可以满足实时系统的要求。,（二）模型的缺点： 在建模与编程过程中，使用的数据只是现实数据的一种近似，因而得出的结果可能与现实情况有一定的差距。,（三）模型改进,以上模型主要是从公交线路出发，寻找公交线路的交叉站作为换站点。我们也可以从公交站点的角度出发，用图论的方法建立有向赋权图如图所示,1）当以时间最短为目标时，给每条边赋上时间的权值。当某段线路的两段点间间隔站点数小等于3时，选择步行，该线路的权值等于步行时间。不同公汽和地铁间进行换乘时需要赋给不同的权值，以表示换乘时间找出任意两点间可行路线的路径长度后，再搜索出其中的最短路径
12、的的可行路线作为时间的最优路线,2）当以费用最省为目标时，则给每条边赋上费用的权值。 公汽站点间的边权赋值。同样可以找出任意两点间可行路线的路径长度，然后再搜索出最短路径作为费用的最优路线 从公交站点出发，将公交站点作为网络图中顶点，得出公交的拓扑结构，进而寻求不同目标下的最短路径，为我们提供了另外一种思路。但是从以上图形的结构，我们已经看得出其复杂程度是不可预知的，尤其随着数据的增多，图的复杂度随之上升。如果不寻求一个好的算法，而用常规的Dijkstra算法，将有可能在可以忍受的时间范围内得不出有效结果。 经过参考相关资料，我们发现用蚂蚁算法可能比较有效。该算法利用了蚂蚁寻食出行路径选择的行为特点，通过线路激素强度的更新机制,谢谢,
