高教杯数学建模竞赛——最优公交线路选择模型【数学建模】.doc

最优公交线路选择模型 摘 要 本文讨论了公众出行时多条线路选择的问题，给出了在已知公交系统中任意两公交站点之间线路选择的模型和算法，使得出行时的时间、费用和换乘次数都尽量的少。 在问题1中，我们仅考虑公汽线路，将520条公汽线路信息读入到两个矩阵当中，利用矩阵表示站点间的直达经过站数和线路，用matlab编程求解分别得到换乘1次和换乘2次时6对起始站→终到站之间的最佳路线。仅在此给出S3359→S1828的最佳路线，其余结果见正文。 表1：换乘1次时S3359→S1828的最优线路方案 起点站 终点站 线路1 中转站 线路2 时间（分） 费用（元） S3359 S1828 L436(下) S1784 L167(下) 101 3 表2：换乘2次时S3359→S1828的最优线路方案 起点站 终点站 线路1 中转站1 线路2 中转站2 线路3 时间 费用 S3359 S1828 L015(下) S2903 L027(环) S1784 L167(下) 73 3 问题2要求同时考虑公汽与地铁线路，我们首先将增加的地铁线路信息添加到问题1建立的两个矩阵中，利用与问题1相似的编程思路，求解得到换乘1次和换乘2次时6对起始站→终到站之间的最佳路线。S3359→S1828的最佳路线与问题1的相同，其余结果见正文 问题3要求同时考虑公汽、地铁和步行，我们建立了全局替换模型和局部替换模型。 最后我们对模型进行了推广，给出了线路“满载度”的定义，在考虑“满载度”之后，建立了新的模型。 关键词： 多目标规划 最少时间 相关矩阵 满载度 一、问题提出 我国人民翘首企盼的第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、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。 【附录1】基本参数设定 相邻公汽站平均行驶时间(包括停站时间)： 3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元 地铁票价：3元（无论地铁线路间是否换乘） 注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。 【附录2】公交线路及相关信息 （见数据文件B2007data.rar） 二、问题假设 1．假设题目给定的公交线路均合理有效； 2．假设题目中所给的基本参数合理有效，不会对最终结果的准确性造成影响； 3．假设不存在因公汽或地铁满载，使公交到站后，等车的乘客无法上车的情况； 4．假设公交行驶过程中不受地形、天气、路况和上车人数的影响，相邻公交站的平均行驶时间（包括停站时间）固定不变； 5．假设乘客选择乘车路线时仅考虑三个因素：时间、费用和换乘次数； 6．假设每个乘客从出发地到达目的地最多乘坐3辆公交车（在能够到达的情况下）； 7．假设环行的公汽没有始发站和终点站，在客观情况允许的情况下，会绕着环行线路一直开下去，即乘客上车后无需下车再乘，就可以从环行线路的一站到达环行线路其他任意站； 8．假设地铁直接换乘地铁时只需购买一次地铁票，花费3元，当地铁换乘公汽后再换乘地铁时需要购买两次地铁票，花费6元。 三、符号约定 ：仅考虑公汽线路时，从公汽站i到公汽站j（ij）直达（只乘坐一辆公交就可到达）行驶所经过最少的路段（相邻两公交站的路程称为一个