《乘公交看奥运方案设计(方案计划书)》由会员分享，可在线阅读，更多相关《乘公交看奥运方案设计(方案计划书)（30页珍藏版）》请在金锄头文库上搜索。
1、承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的
2、全名） 黔南民族师范学院 参赛队员 (打印并签名) ：1. 曹龙 2. 彭开连 3. 陈勇 指导教师或指导教师组负责人 (打印并签名)： 薛先贵 日期： 2011年 8 月 15 日乘公交,看奥运摘要:本文将公交线路（3957个公汽站点和520条公汽线路、39个地铁站点和2条地铁线路、地铁与公汽间转换关系）关系抽象为有向赋权图，并建立时间直达矩阵、费用直达矩阵、换乘直达线路数矩阵，利用最短路模型、搜索法及0-1整数规划模型进行解答。对于问题一，在只考虑公汽的情况下，我们用修改floyd算法求出最小转乘次数、最少费用、最少时间，并由搜索法得出最优线路；对于问题二，在考虑公汽和地铁的情况下，同样，
3、我们也用修改floyd算法求出最小转乘次数、最少费用、最少时间，并由搜索法得出最优线路；对于第三问题，我们则需要考虑步行时间进去，在问题二的基础上并利用0-1整数规划模型进行优化组合取得最优线路。关键字:线路选择 有向赋权图 修改floyd算法 搜索法 优化模型一、问题重述:奥运会是世界上举行的一项重大的赛事活动.第29届奥运会明年8月将在我国北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。近年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需
4、求，我们准备研制开发一个解决公交线路选择问题的自主查询计算机系统,关键在于线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。具体问题如下:1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给
5、出任意两站点之间线路选择问题的数学模型。基本时间参数设定:相邻公汽站平均行驶时间(包括停站时间)相邻地铁站平均行驶时间(包括停站时间)公汽换公汽平均耗时/(步行时间)地铁换地铁平均耗时/(步行时间)公汽换地铁平均耗时/(步行时间)地铁换公汽平均耗时/(步行时间)时间(分钟)32.55/(2)4/(2)6/(4)7/(4)即:换乘公汽等待分钟，换乘地铁等待分钟.公汽站地铁站（通道）公汽站.换乘耗时11分钟：步行4+4=8分钟, 等车3分钟.公交票价方式基本票价参数设定:单一计价分段计价公汽1元020站：1元；2140站：2元；40站以上：3元地铁3元（无论地铁线路间是否换乘）公交线路及相关信息
6、（见数据文件B2007data.rar）二、问题分析: 本论文主要研究公交线路选择的问题，即要求:a 如何换车.b 车与车之间的关系.c 满足乘车人关心的问题： 1）换乘次数最少； 2）费用最低； 3）时间最短（初始等车时间2(3)min也不包括在内，最后结果可加 上。）； . 在众多的条件中，为了切合人们的实际需要，优先考虑是否有直达,若无直达公汽,则我们主要从最方便、最经济、最快捷等出发，建立以换乘次数、费用、时间为最优的数学模型。三、模型假设:1、所有公交线路的每天的工作始末时间相同;2、公汽、地铁均到站停车;3、各公交车都运行正常，不会发生堵车现象;4、环线可以看作以任意站作为起点站和
7、终点站，并且是双向的,并且经过终点后 要重新收费;5、假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁费；6、人们对换乘车次数尽量少的偏好程度总是大于对花费时间相对短和花费金钱相对少的偏好程度;7 初始等车时间2(或3)min也不包括在内;8、 同一公交线的往返路线视为两条单行线;9、 考虑两地铁之间不通过公汽乘换（即只：公汽站地铁站（通道）公汽站）。四、模型建立: 对于公交线路选择，我们主要考、虑乘换次数、费用、时间各因素最优。 在线路选择问题中，将公交路线关系抽象成一个有向赋权图，当从i可直达j时（同为公汽或地铁站点），定义弧(i,j)；其上的权为：。表示由i直达j
8、付出的代价，可以为时间或费用 (不包括换乘代价；多条线路可达时只保留最小代价)； 公交乘换方式：公汽公汽，公汽地铁，地铁公汽，地铁地铁，公汽地铁公汽。 A） i站点是公汽站点，j站点为地铁站点：（1）若j站点对应的所有换乘(公汽)站点k，均不能从i直达(不在i站点所在公汽线路L上)，则 =;（2） 若j站点对应的换乘（公汽）站点k, 可从i站点直达k，则费用为 = ； 注：对于时间则需要加上k到j的步行时间. (若有多种选择，取最小成本者即可)B） j站点是公汽站点，i站点为地铁站点：（1）若从i站点对应的任何换乘(公汽)站点k，均不能直达j站点，则 =. （2）若从i站点对应的换乘(公汽)站
9、点k，能直达j站点， 则费用为 =；注：对于时间则需要加上i到k的步行时间.定义：矩阵算子“”如下：设D（k-1）、D均为n阶方阵， D(k) = D（k-1） D (考虑换乘代价)当考虑费用矩阵间的运算时，=0；当考虑时间矩阵间的运算时，表示在k的换乘时间。 D(k)= D(k-1)D表示k次换乘的最低代价(费用或时间)，即通过修改floyd算法求解。i,j,k表示换乘时间 ：i = j 或k = i，j时，i,j,k = 0其他情形：若不可换乘(当i ，j为公汽站点而k为地铁站点，或者i ，j为地铁站点而k为公汽站点时)，则 i,j,k = 0若可换乘，则：问题一模型 ： 因为仅考虑公汽线
10、路，为了能得到两站点之间的最好选择线路，将题中所提供的公汽网络抽象成一个有向赋权图,建立直达矩阵D =。当D为时间直达矩阵时，按D(k)= D(k-1) D式重复地进行运算得到，当，时，表示从 i站点到 j站点最少换乘k次能够到达，且即表示换乘k次到达所需的最短时间。 当D为费用直达矩阵时，按D(k)= D(k-1) D重复地进行运算得到，运算适当次数后若 D(k)= D(k-1)，则表示已得到所有站点间的最小费用，即表示从i站点到j站点所需的最少费用。 根据最少乘换次数等约束条件，再利用图的邻接搜索法可得出两站点之间的选择线路。问题二模型 ： 当还需要考虑地铁时，为了能得到两站点之间的最好选
11、择线路，同样，将题中所提供的公汽（含地铁转换的公汽）网络抽象成一个有向赋权图,建立直达矩阵D =。算法设计基本与模型一相当。 当D为时间直达矩阵时，按D(k)= D(k-1) D式重复地进行运算得到，当，时，表示从 i站点到 j站点最少换乘k次能够到达，且即表示换乘k次到达所需的最短时间。 当D为费用直达矩阵时，按D(k)= D(k-1) D重复地进行运算得到，运算适当次数后若 D(k)= D(k-1)，则表示已得到所有站点间的最小费用，即表示从i站点到j站点所需的最少费用。根据最少乘换次数等约束条件，再利用图的邻接搜索法可得出两站点之间的选择线路。问题三模型： 问题三是在模型二的基础上添加步
12、行时间进行考虑。 优先考虑乘换次数。对直达时间矩阵按D(k)= D(k-1) D式重复地进行运算得到，当，时，表示从 i站点到 j站点最少换乘k次能够到达。在运算过程中可记录下换乘站点信息，随之可得到相关线路信息。若有若干条最小换乘路线，则比较另外两个目标选择最佳线路（即建立0-1整数规划模型）。 设共有m条单行公交线，构造一个m+2个点构成的完全图。 点：a为起点（出发点），b为终点（目的地），此外每条公交线也视为一个点。 边：边表示两点之间的步行关系。 边权：步行时间为边权。针对不同的边可分为上车前、下车后和换车时步行时间，构成步行时间矩阵 。行：依次表示的是m条公交线与起点，列：依次表示
13、的是m条公交线与终点。 点权：第个公交线点还有三个信息为点权。 1）公交线名称及上行或下行； 2）类型及票价方式； 3）乘车站数表矩阵 ，其中 表示从c到d经过i号公交线时需要乘车的站数,c到d利用不上i时取无穷大。这个矩阵的行列表示用S。 于是原问题转化为在这个图上求a到b的最短路。 最短的可以理解为换乘车数最少、乘车的总站数最少、总的步行时间最少、总车费最少这样几个目标的各种组合方式。 可以用0-1整数规划解决这个问题，方法是分出恰乘一次公交车，恰乘两次公交车，恰乘三次公交车等等情况分别求出下列模型解然后比较得出最优解。 优化模型：恰乘一次公交车的模型如下：变量全部是0-1变量，共有3*(m)个。 表示选不选择去第i条公交线的路； 表示选不选择乘第i线公交车； 表示选不选择从第i条公交车下车后走到目的地的路。 (它们都是取1表示选择而取0表示不选择。)恰乘一次公交车的模型如下： 目标函数：据用户选择的情况用点权和边权构造，共同点都是最小值。 ( 1)步行时间最少: 目标函数 (2)总时间最少: 目标函数 其中，(3)车费最少: 目标函数： 约束条件（共2m+1个）： 只选择一条公交线； 要乘第i条公交线就要走相应的两条路。恰乘两次公交车的模型如下：步行时间:时间最少：费用最少：约束条件：
