关于公民出行的最佳公交线路选择问题.pdf

关于公民出行的最佳公交线路选择问题 （2007 年数学建模 B 题） 题目：我国人民翘首企盼的第 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，设出发站为A，目的站为B。首先如果想从A通过乘公汽车到达B，会 先看A有没有直接到达B的公交线路，若有，就可以直接乘坐。若无，则再看B有什么 车经过，经过A的车和经过B的车在线路上有没有交叉点？若有，则可在交叉点处转车。 从而可以先从 A 乘公汽到达交叉点，再从交叉点换车直接乘公汽到 B。若无，则乘坐经 过A的公汽到某一站C下车，经过C的公汽与经过B的公汽在线路上有没有交叉点？若 1 有，则在交叉点转车。这样就可以找到 A、B 站之间换乘次数最少的路线，这样的路线 可能会很多，接下来就要以最少时间来衡量这些路线中的最优路线。 对于问题 2，由于加入了地铁线路，那么乘客的可选路线会增加一部分，这样会出 现更多可选的换乘站点。经过分析把地铁站（一条地铁线上的）可以换乘的公汽站作为 一个大的集合，这样的集合有两个。如果两个站点同时存在于其中一个集合之中，那就 可以通过地铁线直接到达；如果两个站点A、B，只有A存在于其中一个集合之中，而经 过 B 的公汽线路上的站点 C 也存在于这个集合，那可以从 A 乘车到 C 再换车乘车到 B； 如果两个站点不同时存在于其中一个集合之中，而经过A的公汽线路上的站点C与经过 B 的公汽线路上的站点 D，那可以从 A 乘车到 C，再换车乘车到 D，再换车乘车到 B。而 多余两次换车就不在考虑。