数学建模论文-乘公交，看奥运的最佳路径选择.doc

乘公交，看奥运的最佳路径选择 摘要 本文通过数学建模的方法解决了乘公交，看奥运最佳路径的选择问题。首先我们把问题看做是求最短路径的问题，并分别尝试利用传统的最短路径算法——Dijkstra算法、蚂蚁算法来分析计算本题，但发现前面两种算法在解决本问题中存在很多缺点特别是在大量数据的情况下计算很繁琐，速度很慢，难以满足系统设计要求的需要在较短时间内完成。因此我们在结合Dijkstra算法、蚂蚁算法的思想，提出了解决城市公交线路最短路径选择的一般算法。 在问题一上，我们通过分析公交系统，在仅仅考虑公共汽车线路，对于任意的起点与终点，分别讨论各种不同的换乘次数所选择的路径，并引入交通阻抗函数求解最优路径的模型及算法，并运用模型及算法编写了相应的MATLAB程序，求解计算出题目中要求的6对站点的最优路径。 在问题二上，当同时考虑公共汽车与地铁线路，人们选择路线的方式又会有所不同，因为地铁具有独特的优势，特别是其速度快，往往得到人们出行的选择的青睐。本文以讨论站点在公交系统中的各种位置情况分层次讨论求解出最佳路线，最后交通阻抗函数对考虑地铁存在的情况供人们选择的各种路径的阻抗值。阻抗值越小，该路径越优。在运用模型与算法求解题目中所给的6对站点，我们发现当同时考虑地铁的因素时，只有公汽地铁公汽的情况，即为算法中的8.3.1.1算法。因此，我们在问题一的基础上，先考虑直达的情况，后考虑一次换乘的情况（不考虑换乘两次以上的情况）。编写MATLAB程序，计算其结果。 在问题三上，首先又假设可知当考虑步行时共有八种不同情况，又由解决问题二的算法可求出对于任意两站点的最佳路径的最小交通阻抗值，又由题设知道每两个站点的步行时间已知，所以都可求，由模型知道交通阻抗值越小，路径越优，进而计算出最佳路径。 关键词：最短路径；最优路径；交通阻抗值函数；交通阻抗值 一、问题的重述 我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。首先我们将解决如下问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑公汽与地铁线路，解决以上问题。 3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。 二、问题的分析 公共交通系统是城市交通系统的重要组成部分，可作为公共交通网络优化的核心同时也是现代城市的动脉与国民经济、人民生活密切相关。正因为如此，建立一个科学、合理的公共交通系统来引导人们出行选择提供快捷、简便的交通路线也逐步成为社会的一个热点。由于公共交通对交通资源的高效利用,使得通过大力发展公共交通,实行公交优先成为缓解日趋严重的道路交通紧张状况的必然选择. 在路径选择时,公交出行者总希望选择最快捷的线路(即综合考虑时间、费用的交通阻抗值最小的线路) 出行,可称之为最短路因素. 但由于交通阻抗值大小很难直观判定,使路径选择带有不确定性,称之为随机因素. 两者主次地位取决于供选择路径间交通阻抗差值大小. 公交线路交通阻抗值是指乘客在公交线路上出行的出行时间、费用、方便性(如换乘) 等综合费用指标,是乘客选择公交线路的依据 . 人们在讨论城市道路交通线路问题时,着重考虑任意2 个节点间最短路径. 只要2 个节点有道路连接,就可进行有哪些信誉好的足球投注网站,而不考虑该路径换乘问题,这就可能造成有哪些信誉好的足球投注网站到的路径需多次换乘. 因换乘带来的换乘时间和车票费用会增加交通阻抗. 因此对司机来讲的最短路径,对乘客却并不是最佳选择. 在一个公交网络中寻找2 个节点间最佳路径,要综合考虑出行时间、费用和换乘等相关因素,使交通阻抗最小. 人们公交出行需求是人们对公交服务的期望，为了进一步说明这一问题，在此特别引入交通阻抗函数这一概念，交通阻抗主要指乘客对某一交通系统（线路）的阻抗程度，影响交通阻抗的因素主要有：出行者换乘次数、出行耗时、出行费用、出行距离等因素。石家庄近期在市内