乘公交 看奥运 数学建模

《乘公交 看奥运 数学建模》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京市公交查询系统方案设计摘要本文要解决的问题是以即将举行的08年8月北京奥运会为背景而提出的，人们为了能现场观看奥运会，必然会面对出行方式与路线选择的问题。因此如何快速、高效地从众多可行路线中选出满足各类需求的最优路线成为了解决此问题的关键。显然，本文属于分层优化问题（即LSP问题）。需要解决的是在遍历所有可行路线的情况下寻找出能满足不同查询者需求的路线，为此我们建立了宽容完全分层序列模型和蚁群算法模型，采用了高效的广度优先算法和局部搜索枚举法对数据进行搜索，其基本思想是从经过起（始）点的路线出发

2、，搜寻出转乘次数不超过两次的可行路线，然后在可行解中搜索出对应不同目标的最优解。为满足不同查询者要求，我们对三个问题都分别建立了以转乘次数最少、时间最短、费用最低目标的优化模型。对于问题一，在数据处理阶段将所有车次的路线都处理成上下行线路的形式，然后针对实际生活中换乘次数不会超过两次建立了直达库，一次中转库和两次中转库，每当输入出发站和目的站时便依次在数据库中进行局部搜索寻求各种最佳路线，在此基础上有依据的以换乘次数为主要约束，以时间最短，花费最低为目标，建立宽容完全分层序列模型，并给出求解方法和结

3、果。对于问题二，考虑公汽和地铁混排的方案，首先，我们将个地铁站点和其周围相邻近的公汽站点虚拟为一个新的站点。把已知公汽到达都映射到新站点，计算新的直达库，一次中转库和两次中转库，再结合地铁费用与与地汽换乘等待时间就可以把地铁与公汽线结合，利用和问题一一样的模型和解法，建立宽容完全分层序列模型，并给出求解方法和结果。对于问题三，题目中说明假设已知所有站点之间的步行时间，也就是步行者不一定必须按照公汽或地铁的路线行走，我们根据实际情况，做出一次步行不超过十分钟的假设，综合考虑所有站点间步行与乘车等情况，

4、发现如果还是利用问题一、二的局部搜索的模型将会给求解带来很大的局限性，而利用蚁群算法进行遍历搜索可以很大程度上减少运算时间，提高结果的准确性，于是我们在已有数据库的基础上，构造邻接矩阵，采用蚁群算法求解遍历下的较优解问题，并给出详细算法流程和求解结果。本文的最后，我们对模型进行了评价，并根据实际情况给出了改进方案。关键字：宽容完全分层序列广度优先算法局部搜索枚举法蚁群算法1.问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工

5、具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站

6、→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2.模型的假设与符号说明2.1模型的假设1：假设各线路上公交车发车的频率相同；2：假设不出现交通阻塞，公交运行顺畅；3：假设不出现车辆故障及道路交通事故

7、；4：假设不考虑红绿灯时间，公交车准时出发和到达；5：假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费).2.2符号说明j第j号汽车的第n站xn1A第j号汽车上行线的所有站数集合j2A第j号汽车下行线的所有站数集合j1P属于分段计费的第j号汽车j2P属于单一计费的第j号汽车j3.问题分析本文是解决在三种不同情况下任意两站点之间线路选择问题。根据查询者主要的考虑因素包括换乘次数，时间长短，花费，乘坐压力以及起始站距离等，对查询者的不同需求提供对应的最佳路线。为此，我们做了以下几

8、个方面的分析。3.1乘客心理分析通过对乘客的出行心理、行为的调查研究发现公交乘客选择路径主要受到以下几个因素的作用：“换乘次数”、“时间长短”、“乘车费用”。换乘次数是指乘客从出发地到目的地的过程中转车的次数；时间的长短包括乘车时间和换乘时间。调查结果表明，一般情况下，优先考虑换乘次数的乘客占51.9%，优先考虑时间长短的占35.5%，优先考虑费用多少的占9.8%，优先考虑其他因素的占2.8%表3-1优先考虑因素比例表优先考虑因素换乘次数时间长短费用多少其他因素比例（