优秀数学建模设计方案.doc

最佳路径选择方案的优化模型 摘 要 本文对乘公交、看奥运这一实际问题进行了深入的研究，首先对公交乘客进行了心理分析，得出影响乘客出行的三个主要因素分别为：换乘次数、出行时间、出行费用，通过调查研究，得出换乘次数最少是乘客出行考虑的最主要因素，其次是出行时间和出行费用。然后利用公交乘客的出行过程抽象为站点—线路的交替转换的思想，建立了站点—线路序列模型，从而确定了出行者对路线的所有选择方案。 针对问题一：仅考虑公汽的情况下，以换乘次数最少为第一目标、出行时间为第二目标建立了优化模型一，再以换乘次数最少为第一目标、出行费用为第二目标建立了优化模型二，从而满足了两类不同乘客的需求。并依靠站点—线路序列模型采用图论中计算方法，分别得到了公交乘客的最少换乘次数，所经过的站点，出行时间、出行费用以及相应的算法。 针对问题二：在问题一的基础上再考虑地铁线路，建立了对应的两组优化模型，并推导出相应的改进算法。 针对问题三：在问题一、二的基础上，考虑出行者可以通过步行到达相邻的公交站点的情况，同样建立了两组相应的优化模型，并给出了相应的计算方法。 然后利用基于换乘次数最少的最优路径改进算法思想，借助MATLAB软件编程分别对问题一和二进行了求解，得到的结果见模型的求解（正文第21、22页）。 最后对所求得的结果进行了对比分析和检验，根据各参数的变化关系，进行了灵敏性分析，本模型主要抓住了乘客的心理需求，实用性强，具有较强的现实意义。 关键词：站点—线路序列 最优路径改进算法 公交一、问题的提出 1.1基本情况 我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择（包括不同线路上的换乘交通工具的路径选择等）问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 1.2基本参数设定： 1）相邻公汽站平均行驶时间(包括停站时间)： 3分钟； 2）相邻地铁站平均行驶时间(包括停站时间)：2.5分钟； 3）公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)； 4）地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)； 5）地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)； 6）公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)； 7）公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元； 21～40站：2元； 40站以上：3元。 地铁票价：3元（无论地铁线路间是否换乘）。 注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。 1.3相关信息（详见附件） 【附件1】公汽和地铁线路信息数据文件格式说明； 【附件1.1】公汽线路及相关信息； 【附件1.2】地铁线路及相关信息； 【附件2】地铁换乘公汽信息数据文件格式说明； 【附件2.1】地铁T1线换乘公汽信息； 【附件2.2】地铁T2线换乘公汽信息。 1.4需解决的问题 为了设计这样一个公交线路选择的自助查询计算机系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，以满足查询者的各种不同需求。进而需要解决如下问题： 问题一、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附件中的相关数据，利用所得到的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 问题二、同时考虑公汽与地铁线路，解决以上问题。 问题三、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。 二、基本假设 2.1出行者对公交线路的选择是理性的且能够顺利正常的到达目的地。 2.2出行者在所经过的站点中，不允许两次经过相同的站点。 2.3公交与地铁换乘距离固定，换乘步行时间为常数。 2.4同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费。 2.5出行者换乘时，不受人群拥挤、交通堵塞等现象的影响且均能乘到相应线路的公汽或地铁。 2.6出行者换乘交通工具时的平均耗时包括出行者到站的等待时间和换乘的步行时间； 2.7公汽线路上的单一制票价为1元，分段计价的票价为：0~20个站：1元；21～40站：2元；40站以上：3元；地铁票价：3元（无论地铁线路间是否换乘）。 2.8附件所给数据准确无误。 （注：本文中针对相应问题的假设将