当前位置：文档之家 › 2007数模竞赛B题-城市公交线路选择优化模型你要的

2007数模竞赛B题-城市公交线路选择优化模型你要的

  • 格式：doc
  • 大小：592.50 KB
  • 文档页数：16

2007B题：乘公交，看奥运（数据有变化） 我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3769→S2857 (2)、S1557→S0481 (3)、S1879→S2322 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑公汽与地铁线路，解决以上问题。 3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。

【附录1】基本参数设定 相邻公汽站平均行驶时间(包括停站时间)： 3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时： 6分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时： 5分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： 8分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元 地铁票价：3元（无论地铁线路间是否换乘） 注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。

【附录2】公交线路及相关信息 （见公汽线路信息，对原数据文件B2007data.rar有少量更改） 城市公交线路选择优化模型 摘 要 本文针对城市公交线路选择问题建立了两个模型，一个是基于集合寻线算法模型，另一个是图论模型。 基于集合寻线算法模型中，首先固定换乘次数n，通过集合论的相关知识把确定换乘点的具体位置, 转化成确定一些集合间的交集，从而建立集合寻线算法，再根据集合相关公式，得到所有可行线路；进一步考虑时间和费用等因素，对可行线路进行处理比较，得出最佳线路。 图论模型中，通过图论的知识将整个北京市交通线路构建出一个有向图，每个站点与有向图的顶点一一对应，同一线路上的相邻站点对应为有向边，通过不同目标（时间、费用）给有向图进行不同的赋权，分别将不同目标转化为赋权有向图寻找最短有向路，根据最短路径算法，得到最佳线路。最后综合评价了两个模型的优缺点。 关键词：集合寻线算法；最短路算法；换乘点；赋权有向图 1 问题提出 北京将于2008年举行奥运会，届时会有从四面八方而来观看奥运比赛观众，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。随着现代化的步伐加快，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。在现实生活中，公交线路以及其相应经过的站点非常多且密，乘客往往难以知道如何选择公交线路，所以针对市场需求以及公交线路选择上的问题，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 该系统的核心在于线路选择的模型与算法，应该从实际情况出发，满足查询者的各种不同需求。根据附录1、附录2，解决如下问题： 1.仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用建立的模型与算法，求出以下6对起始站→终到站之间的最佳线路。 (1) S3359→S1828 (2) S1557→S0481 (3) S0971→S0485 (4) S0008→S0073 (5) S0148→S0485 (6) S0087→S3676 2.同时考虑公汽与地铁线路，解决以上问题。 3.假设知道所有站点之间步行时间，给出任意两站点之间线路选择的数学模型。 2 问题分析 为了研制开发一个解决公交线路最佳选择（即乘客在多条公交线路中根据自己的需求获得最适合自己的线路）问题的自主查询计算机系统，只要乘客给出起点站A和终点站B两个站点，系统就给出最佳交通线路，使得公众出行更加通畅、便利。而问题核心是如何在多条线路选择中获得最佳线路。 乘客往往不能只乘一辆公交便直达终点，而是要通过换乘一辆或多辆公交才能到达终点站，但若多次换乘公交，可能导致乘客所花时间及其费用的增加，更会给乘客造成不便。在奥运将在北京举行的背景下，我们知道乘客前往观看奥运比赛时，主要注重的是能否及时到达，所以在为乘客选择线路时，力求乘坐花费的时间尽可能少以及路程尽可能短的线路，同时考虑换乘车辆以及乘车费用尽量少的最佳线路，而现实是很难同时满足上面三个目标的。为了使问题简单化， 我们分别以乘车时间、乘车费用以及换乘次数为目标函数，得到各自的较优线路，再通过对比，有效地处理这些线路，最终得出查询系统给出的结果。

、 3 模型准备 3.1 模型假设 1.假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘（无需支付地铁费）； 2.假设所有交通线路都不出现停运或者线路变动； 3.假设公汽的环行行驶线路是单向的。 3.2 符号约定 c：相邻公汽站平均行驶时间（包括停站时间），min3c； d：相邻地铁站平均行驶时间（包括停站时间），min5.2d； e：公汽换乘公汽平均耗时，min5e（其中步行时间2min）； f：地铁换乘地铁平均耗时，min4f（其中步行时间2min）； g：地铁换乘公汽平均耗时，min7g（其中步行时间4min）； h：公汽换乘地铁平均耗时，min6h（其中步行时间4min）；

ijt：交通工具与交通工具换乘所需时间；

k：地铁票价，3k元； n：换乘次数；

ijN：乘客在可选择的从起始站到终点站线路中第i条线路的换乘点（包括始点和

终点），1,,2,1,0nj，0iN为起点，1,niN为终点；

jM：乘客从第1j换乘点上车到第j换乘点的下车所付的票价，1,,2,1nj；

jW：公交车从第1j换乘点到第j换乘点经过的站点数（含第j换乘点）

1,,2,1nj；

jC：公交车在第i线路上从第j换乘点到第1j换乘点线路；

ijk：公交车在第i线路上从第1j换乘点到第j换乘点经过每站所需时间；

niT：只换乘n次乘客从起始站到终点站选择第i条线路所需要的总时间；

niS：只换乘n次乘客从起始站到终点站选择第i条线路所需要的总费用。 4 基于集合寻线算法的模型 4.1 集合寻线算法的建立 现实乘客换乘的次数n很小，公司在设计一个城市公交线路时，为了使线路更合理，一般不会使乘客要通过多次换乘（超过3次）才到达终点站。则不妨假设换乘次数2,0n，Zn。 我们可以看到问题中关键要解决的是找出换乘点ijN的具体位置，显然换乘点是公交线路的交叉点，或者说站点至少要有两条公交线路经过。由于公交线路不是一条直线段或者有一定几何规律的曲线，所以我们通过代数的相关知识，把具有同一属性的站点放入同一集合中，这样就把问题转化成代数问题。基于此思想，我们建立以下集合寻线算法： 步骤1：找出经过终点B站的所有公交线路jB存放到集合}|{jjBBBY，

以及这些线路jB经过的所有站点存放到集合Q。 步骤2：找出经过起始站A的所有公交线路iA，存放到集合}|{iiAAAX，以及这些公交线路iA经过的站点存放到集合P。 步骤3：判断X和Y的关系： 1．若YX，即存在Zji,，使得jiBA，表示起始站A到终点站B之间有一条或几条直达线路，乘客不必换乘公交车，算出这些直达线路各自所需要的时间和票价；通过比较大小，得到该情况下的乘车最少时间minT和最少费用

minS，以及其相应的线路。 2．若YX，则说明起始站A与终点站B之间不存在公交车直达的情况，只能通过换乘才能到达终点站B，则要寻找换乘点。 步骤4：查找公交线路iA与公交线路jB的所有共同站点a，存放到集合

}|{jiBAaaI。集合I中的元素是换乘点。

步骤5：判断集合I： 1．如果集合I，即乘客可以通过一次换乘就能到达终点站。记录换乘点及其相应线路。 2．如果集合I，即乘客不能通过一次换乘到达终点站，则要选取新的起始点。 步骤6：选取新的起始点： 从集合P中任取一站点A（AA），即遍历集合P中所有的元素，以站点A代替原来的起始站A。转到步骤2，这样就能找出所有经过两次换乘的线路。 步骤7：通过重复上面的6个步骤可得经过n次换乘的所有可能线路。 4.2 模型的建立 4.2.1 时间及费用计算 我们固定换乘次数n，通过集合寻线算法，得到通过n次换乘的所有可达线路，再对这些线路进行下面的运算： 从起点站A到终点站B，iA：经过起点站A的第i条公交线路；

jB：经过终点站B的第j条公交线路；

只通过n次换乘到达可选择的线路共有U条，设第i条乘坐线路的换乘点为ijN,1,,1,0nj，0iN为起点，1,niN为终点,第i条线路上从第j换乘点到第

1j换乘点线路为ijC，其途径的站点数ijW，inj,,1,0，所付的票价ijM,相

合集下载

数学建模历年竞赛试题

数学建模历年竞赛试题

目录前言 ............................................................................................................. 错误!未定义书签。

目录 ..........................................................................................................................................- 0 - 一、什么是数学模型...........................................................................................................- 3 -2001年B题……公交车调度.....................................................................................- 4 - 2001年C题……基金使用计划............................................................................. - 10 - 2002年A题……车灯线光源的优化设计........................................................... - 12 - 2002年B题……彩票中的数学............................................................................. - 13 - 2003年A题……SARS的传播............................................................................... - 18 - 2003年B题……露天矿生产的车辆安排........................................................... - 29 - 2003年D题……抢渡长江...................................................................................... - 33 - 2004年C题……饮酒驾车...................................................................................... - 36 - 2004年B题……电力市场的输电阻塞管理 ...................................................... - 38 - 电力市场交易规则： ..................................................................................... - 39 -输电阻塞管理原则： ..................................................................................... - 40 -表1各机组出力方案（单位：兆瓦，记作MW）............................... - 43 -表2各线路的潮流值（各方案与表1相对应，单位：MW）......... - 45 -表3各机组的段容量（单位：MW） ...................................................... - 46 -表4各机组的段价（单位：元/兆瓦小时，记作元/MWh）............ - 47 -表5各机组的爬坡速率（单位：MW/分钟）....................................... - 48 -表6各线路的潮流限值（单位：MW）和相对安全裕度.................. - 49 -2008年B题……高等教育学费标准探讨........................................................... - 49 - 2008年D题……NBA赛程的分析与评价.......................................................... - 50 - 2009年A题……制动器试验台的控制方法分析............................................. - 52 - 2009年B题……眼科病床的合理安排 ............................................................... - 55 - 【附录】2008-07-13到2008-09-11的病人信息.............................. - 56 - 2009年D题……会议筹备...................................................................................... - 94 - 附表1……10家备选宾馆的有关数据........................................................ - 95 -附表2……本届会议的代表回执中有关住房要求的信息（单位：人）- 97 -附表3……以往几届会议代表回执和与会情况....................................... - 97 -附图（其中500等数字是两宾馆间距，单位为米）.......................... - 98 -二、为什么要学习数学模型........................................................................................ - 100 -1、数学模型无处不在，我们的生活、工作、学习都离不开它............. - 100 -例1买房贷款问题........................................................................................ - 100 -例2物体冷却过程的数学模型................................................................. - 101 -2、是学好数学用好数学的必经之路............................................................... - 103 -3、是数学教学改革的重要手段和有效路径................................................. - 105 -4、数学建模竞赛所提唱的团队精神是现代大学生必须具备素质........ - 108 -5、数学建模竞赛鼓励学生用跳跃式的、发散式的形象思维方法，这有利于培养学生的创新意识。

07年全国数学建模优秀论文

07年全国数学建模优秀论文

基于网络拓扑的公交查询方案摘 要公交、地铁线路和站点组成了一个极其复杂的网络结构，如何从这个网络的任意两 个节点找到一条最优的乘车方案，传统遍历算法是很费时甚至不可行的，必须采取一种 高效的方法。

本文运用了网络拓扑的知识来分析问题，结合隐含枚举，双向搜索遍历， 动态规划方法减少运算量，较好的解决了这一问题。

对于问题一，我们采用了网络拓扑进行分析，采用隐含枚举，双向搜索的方法，建 立了两点之间线路搜索的动态规划多目标模型，设计了基于直达站点间点—点最优距离 的广度优先搜索算法，得出了较好的结果，如：L436L176 311L15L201L41 4135S3359S1828S3359S 1784S 1828 S3359S 1327S 1790S 1828 ® ¾¾¾®¾¾¾® ¾¾®¾¾¾®¾¾¾ ® ： 对于问题二，我们在问题一已经给出的纯公交路径基础上，采取了增加地铁连通站 点集合（两两可达）的方法，建立了求经地铁中转的最优线路的多目标模型，设计了基 于搜索地铁出入站点的最优路径算法，得到了令人满意的结果，如：T2 8S0087S3676S0087D27D36S3676 ® ®¾¾®® ： 对于问题三，我们采用了网络拓扑进行分析，确立了两点之间的距离正比于步行时 间的原则，在此基础上，建立了基于归并相邻站点的最优线路的改良模型。

综合我们使用的各种方法，可以把原来很难实现的求解过程复杂度缩小数个数量 级，使算法可行并可以搜索更多的区域，最终得到了令人满意的路径。

关键词：网络拓扑 隐含遍历 动态规划 点—点最优距离 广度优先搜索 最优路径1.问题提出与分析2008年奥运会在京举行期间，将有大量游客到北京，北京公共交通系统的发展极大 的满足了游客们在京的出行需求，同时也产生了多条公交线路的选择问题。

公交车数学建模[整理版]

公交车数学建模[整理版]

摘要本文是为了开发一个解决长沙市公交线路选择问题的自主查询计算机系统。

在充分理解题意的基础上，我们从总体上把握，一致认为这是运筹学中的最短路问题。

我们所提供的这个系统，对于当乘客输入起始站和终点站，点击查询结果后，查询机就能很快地给出乘车路线及乘车所需要的最短时间，并且还可以给出相应的乘车费用。

也可以在有多个乘车站点的情况下，自主选择出最优乘车顺序以及相应的乘车最短时间和乘车费用。

公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。

针对市场需求，我们设计了一个解决公交线路选择问题的自主查询计算机系统。

其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。

对于问题一，在仅仅考虑公共汽车的换乘的时候，我们以最短的乘车时间和最优的乘车费用作为两个目标函数，建立相应的双目标规划模型：()Tmin和()Mmin。

对于问题二，在问题一的基础上，我们添加了排列组合模型，全列出所有的乘车顺序情况，由问题一所建模型求出各种情况下的最优时间和最优路费，然后综合比较选出所有情况中的最优乘车顺序。

利用Dijkstra算法解出我们所需要的结果。

我们同样利用了双目标函数的统筹规划原理，在Dijkstra的算法下，解决了在公共汽车换乘的问题，求得最短时间问题，找到了最合适的公交路线，均为最短的乘车时间和最优的乘车费用，从而更加完善了我们的公交系统。

本文的特点是在建立模型和算法的基础上，进行编程，使其具备系统查询功能，克服了人工查询数据的繁杂过程，使得到的结果更为准确，同时，此程序可以进行推广使用，为解决日常生活中最优路径的选择问题提供了方法，给人们的出行带来方便。

关键词：最短行程双目标网络模型 Dijkstra算法排列组合一、问题重述公共交通作为长沙市交通网络中的重要组成部分，由于公共交通对资源的高效利用，使得通过大力发展公共交通，实行公交优先成为缓解日趋严重的道路交通紧张状况的必然选择。

然而，面对迅速发展和不断更新的长沙市公共交通网，如何快速的寻找一条合理的乘车路线或换乘方案，成为长沙市居民和外地游客一个比较困惑的问题。

乘客公汽线路选择优化模型

乘客公汽线路选择优化模型

乘客公汽线路选择优化模型刘国英曹才子吴华香（三峡大学湖北·宜昌443000）摘要公汽是整个城市交通系统中的一个重要组成部分，在方便人们出行的同时也给乘客带来了线路选择的困扰。

本文给出任意两公汽站点之间线路选择问题的一般数学模型与算法，首先利用图论思想建立邻接矩阵，将其转化为有向最短线路问题，再根据公众出行对时间、费用和换乘次数的不同需求，建立单目标优化模型，得出单目标最优方案；此外通过建立多目标优化模型，还提供了同时考虑三种因素的综合最优方案，供乘客选择符合自己乘车需求的路线。

关键词图论思想最短线路单目标优化模型多目标优化模型中图分类号：TP301文献标识码：A1公汽线路选择分析1.1公汽线路的三种情况本文依据公汽行驶的轨迹，综合考虑实际情况后将公汽线路主要划分为三种类型：（1）上行线、下行线原路返回：这种线路有两个端点站，在两个端点站之间双向行车，而且两个方向上的行车路线相同，经过同样的站点序列。

由于路线的方向不同，因此上行线和下行线可抽象成两条线路处理，线路号与收费规则相同。

（2）环行线：对于环形线路，一次线路无重复经过的站点，以城市中心为基点，从始发站绕市中心行驶一圈到终点站，且始发站与终点站相同。

（3）往返线路不一致：上行线、下行线经过的站点不完全一致。

1.2公汽线路选择的影响因素随着城市化的加速，城市交通线路逐渐四通八达，公汽作为城市重要的交通方式之一，在优化城市交通，方便市民出行，发展城市经济等方面均发挥着重要的作用。

在实际生活中，公众乘坐公汽主要考虑步行时间、转乘次数、行程时间、车站始发情况、负载量及乘车费用等因素，其中转乘次数、时间、车费三个因素对乘客公汽线路的选择影响最大，因此本文主要基于这三个因素建立优化模型来设计不同的乘车方案以满足乘客不同的出行需求。

其中对于换乘次数，本文把换乘次数限制在转乘两次之内，这符合大多数乘客的乘车习惯，换乘次数分别为直达、一次换乘和两次换乘；时间由乘车时间和换乘时间决定，换乘时间包含步行时间和等车时间；费用的差别主要由换乘次数决定，换乘次数越多费用越高。