2007全国大学生数学建模B题_公交查询系统特等奖

2007B题：乘公交，看奥运（数据有变化）我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。

这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。

针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。

为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。

请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。

并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。

(1)、S3769→S2857 (2)、S1557→S0481 (3)、S1879→S2322(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。

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 有少量更改）城市公交线路选择优化模型摘要本文针对城市公交线路选择问题建立了两个模型，一个是基于集合寻线算法模型，另一个是图论模型。

承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：重庆大学参赛队员(打印并签名) ：1. 熊国刚2. 王杰3. 黎明指导教师或指导教师组负责人(打印并签名)：龚劬日期： 2007年 9 月 21 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：乘公交，看奥运【摘要】本文要解决的问题是以即将举行的08年北京奥运会为背景而提出的。

人们为了能现场观看奥运会，必然会面对出行方式与路线选择的问题。

因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。

鉴于公交系统网络的复杂性，我们没有采用常规的Dijkstra算法，而采用了高效的广度优先算法。

其基本思想是从经过起（始）点的路线出发，搜寻出转乘次数不超过两次的可行路线，然后对可行解进行进一步处理。

为满足不同查询者要求，我们对三个问题都分别建立了以时间、转乘次数、费用最小为目标的优化模型。

针对问题一（只考虑公汽系统），我们建立了模型一并通过VC++编程得到了任意两个站点间的多种最优路线，并得出所求站点间最优路线的最优值，如下进里又建立了图论模型。

本文的主要特点在于，所用算法的效率十分显著。

07年全国数学建模竞赛试题解答（由于懒得将图⽚依次贴出，需要者可以下载相关附件）乘公交看奥运摘要本设计要解决的是合理给出两站点间的最佳路线选择问题，即给出⼀条经济且省时的路线。

在处理此问题之前，我们根据调查和分析，对影响线路选择的因素进⾏筛选，最终确定了以下三个影响较⼤的因素：第⼀是换乘次数；第⼆是乘车时间；第三是乘车费⽤。

依据各因素对路线选择的影响程度,我们按不同的权重对它们进⾏考虑。

从实际情况分析，⼈们通常宁愿多乘坐⼏站地也不愿换车，所以我们赋予换乘次数较⼤的权重。

为了解决换乘次数最少，乘车时间相对较短、乘车费⽤相对较少的问题，经过尝试与探索，我们采⽤了现代分析的⽅法，对起始站和终点站有⽆相交站点进⾏分类讨论，归纳出直达，换乘⼀次，换乘两次的情况（三次以上的情形可以类推），并通过Matlab编制程序，给出了任意两站点间的最佳乘车路线以及换车的地点，最后还提出了进⼀步的意见和建议。

关键词：最佳路线换乘次数乘车时间乘车费⽤⼀、问题的重述第29届奥运会明年8⽉将在北京举⾏，作为城市枢纽的公共交通承担着⾮常重的运输任务。

近年来，北京市的公交系统有很⼤的发展，公交线路的条数和公交车数量在迅速增多，给⼈民⽣活带来便利的同时，也⾯临多条线路得选择问题，有时出⾏往往还需要转乘多辆公交车才能到达⽬的地。

如何在短时间、换乘次数最少、成本最低的情况到达⽬的地，是⼈们所关注的问题。

因此，我们通过建⽴线路选择的模型与算法，设计⼀套⾃主查询计算机系统，查询到出⾏时所需的最佳公交路线及换乘⽅法，给⼈们出⾏节约更多的时间和⾦钱。

要求：1、仅考虑公汽线路，建⽴任意两公汽站点之间线路选择问题的数学模型与算法。

并求出以下6对起始站→终到站之间的最佳路线。

（1）S3359→S1828 （2）S1557→S0481 （3）S0971→S0485（4）S0008→S0073 （5）S0148→S0485 （6）S0087→S36762、同时考虑公汽与地铁线路，解决1中问题。

评注：以下是我校学生2007年参加全国大学生数学建模竞赛获省一等奖的论文，该文利用网络拓扑结构的有关理论，建立了公交线路的自主查询系统的数学模型，并给出了该模型的算法——改进了的Dijkstra 算法，得到了两个很好的公交线路查询系统的分级优先模型与统一模型。

公交线路查询系统的设计方案张 远，刘 骞，张文波指导教师 刘任河，罗 进摘 要本文根据题目的要求，利用网络拓扑结构的有关理论，建立了公交线路的自主查询系统的数学模型，并给出了该模型的算法——Dijkstra 算法。

为了确定任意两个站点之间的最佳路线，设立了三个判别标准，即耗时最少、耗费最少、转乘次数最少。

考虑到程序执行的复杂性以及现实情况，假设任意两个站点之间的路线所包含的转乘次数都不超过2次。

分别根据单一的判别标准，用VC++编程计算得到问题一中6对具体站点之间的最佳路线选择方案（见附件1），同时对所建立的数学模型及所得到的方案进行了清晰的评价说明。

在问题二的求解中，为将地铁线路与公交线路统一起来考虑，我们将两条地铁线看作是加入的两条新公交线，将与某地铁站点对应的所有公交站点更名为此地铁站名，相当于将这些公交站点与此地铁站点视为一个站点。

作此处理后，问题二就可转化为问题一来求解，只是在计算耗费时间与费用代价上略有不同而已。

在具体的计算过程中，只求出包含乘地铁的路线，再把得出的结果与问题一的结果结合起来进行比较，从而得出单一判别标准下的最优路线。

为综合考虑耗时与耗费对方案选择的影响，提出了三个浪费度的概念，即时间浪费度、费用浪费度与综合浪费度，从而巧妙地解决了具有不同量纲的时间与费用的统一度量问题，具体定义如下：假设某两站点间有n 条可达线路L 1，L 2，……，L n ，第i 条线路L i 上的耗时为T i ，耗费为P i ，分别称i ni i n i i n i i i T T T T ≤≤≤≤≤≤--=111min max min α， i n i i n i i ni i i P P P P ≤≤≤≤≤≤--=111min max min β，()i i i w βλλα-+=1.为第i 条线路L i 上的时间浪费度、费用浪费度与综合浪费度。

公交网络中的线路选择问题陈钢浒（计算机科学与技术）范传林（计算机科学与技术）戈卯卯（物流管理）全国二等奖摘要近年来，城市的公交系统有了很大发展，使得公众的出行更加通畅、便利。

本文分析了公交网络的特点，指出道路模型不适合公交网络模型。

通过对公交乘客出行心理分析，得到乘客的需求因素主要有三类：换乘次数、出行耗时、出行费用。

对问题一，我们建立了网络流模型，并据此模型构造一个类似邻接矩阵的0-1稀疏矩阵。

利用该矩阵的代数运算就可以方便地得到两给定站点换乘次数最小的线路。

为了综合考虑换乘次数最少与总时间最少，我们根据图论的最短路问题建立基于换乘次数最短单目标0-1整数规划模型，并提出一种以换乘次数最少为第一目标、时间最短为第二目标的最优路径算法。

该算法在求出两个站点之间最少换乘次数的所有可能路线的同时，还给出了其中总行驶时间最少的换乘路线。

对于题中所给的六对公交站点间的交通问题，得到一次换乘可达的线路为：(1)S3359→L436→S1784→L217→S1828 ；(3)S0971→L013→S0992→L417→S0485；(4)S0008→L159→S3614→L058→S0073 ；(6)S0087→L454→S3496→L209→S3676；两次换乘可达的线路为：(2)S1557→L084→S3389→L454→S1427→L447→S0481 ；(5)S0148→L308→S0036→L156→S2210→L417→S0485。

在问题二中同时考虑公汽与地铁线路。

将地铁站点与其临近得公交站点近似得看作一个整体站点可以得到一个增广的网络模型。

于是完全可以仿照问题1的算法来解决问题2。

基于换乘次数最小和时间最短为目标，选择路线如下：(1) S3359→L436→S1784→L217→S1828；(2)S1557→L084→S1919→T1→S3068→L072→S0481；(3)S0971→L119→S0567→T1→S0464→L469→S0485；(4) S0008→L159→S3614→L058→S0073；(5)S0148→L308→S0302→T1→S2512→L051→S0485；(6)S0087→T2→S3676。

全国数学建模大赛历年题目分析以及参赛成功方法数学建模竞赛的赛题分析1. CUMCM历年赛题简析2. “彩票中的数学”问题3. 长江水质的评估、预测与控制问题4. 煤矿瓦斯和煤尘的监测与控制问题5. 其他几个数学建模的问题数学建模竞赛的规模越来越大,水平越来越高；竞赛的水平主要体现在赛题水平；赛题的水平主要体现：（１）综合性、实用性、创新性、即时性等；（２）多种解题方法的创造性、灵活性、开放性等；（３）海量数据的复杂性、数学模型的多样性、求解结果的不唯一性等。

纵览16年的本科组32个题目(专科组13个)，从问题的实际意义、解决问题的方法和题型三个方面作一些简单的分析。

一、CUMCM历年赛题的简析1. CUMCM 的历年赛题浏览：1992年:(Ａ)作物生长的施肥效果问题(北理工：叶其孝）(B)化学试验室的实验数据分解问题（复旦：谭永基）1993年:(Ａ)通讯中非线性交调的频率设计问题（北大:谢衷洁）(Ｂ)足球甲级联赛排名问题（清华：蔡大用）1994年:(Ａ)山区修建公路的设计造价问题（西电大：何大可）(Ｂ)锁具的制造、销售和装箱问题（复旦:谭永基等）1995年:(Ａ)飞机的安全飞行管理调度问题（复旦:谭永基等）(Ｂ)天车与冶炼炉的作业调度问题（浙大:刘祥官等）一、CUMCM历年赛题的简析1. CUMCM 的历年赛题浏览：1996年:(A)最优捕鱼策略问题（北师大：刘来福）(B)节水洗衣机的程序设计问题（重大：付鹂）1997年:(A)零件参数优化设计问题（清华：姜启源）(B)金刚石截断切割问题（复旦：谭永基等）1998年:(A)投资的收益和风险问题（浙大：陈淑平）(B)灾情的巡视路线问题（上海海运学院:丁颂康）1999年:(A)自动化机床控制管理问题（北大：孙山泽）(B)地质堪探钻井布局问题（郑州大学：林诒勋）(C)煤矸石堆积问题（太原理工大学：贾晓峰）一、CUMCM历年赛题的简析1.CUMCM 的历年赛题浏览：2000年:(A)DNA序列的分类问题（北工大：孟大志）(B)钢管的订购和运输问题（武大：费甫生）(C)飞越北极问题（复旦：谭永基）(D)空洞探测问题（东北电力学院：关信）2001年:(A)三维血管的重建问题（浙大：汪国昭）(B)公交车的优化调度问题（清华：谭泽光）(C)基金使用计划问题（东南大学：陈恩水）2002年:(A)汽车车灯的优化设计问题（复旦:谭永基等）(B)彩票中的数学问题（信息工程大学：韩中庚）(D) 球队的赛程安排问题（清华大学：姜启源）一、CUMCM历年赛题的简析1.CUMCM 的历年赛题浏览2003年:(A)SARS的传播问题（集体）(B)露天矿生产的车辆安排问题（吉林大：方沛辰）(D)抢渡长江问题（华中农大：殷建肃）2004年:(A)奥运会临时超市网点设计问题(北工大：孟大志)(B)电力市场的输电阻塞管理问题(浙大:刘康生）(C)酒后开车问题（清华大学：姜启源）(D)公务员的招聘问题（信息工程大学：韩中庚）2005年:(A)长江水质的评价与预测问题（信息工大:韩中庚）(B)DVD在线租赁问题（清华大学：谢金星等）(C) 雨量预报方法的评价问题（复旦：谭永基）一、CUMCM历年赛题的简析1.CUMCM 的历年赛题浏览2006年:(A)出版社的资源管理问题（北工大:孟大志）(B)艾滋病疗法的评价及预测问题（天大：边馥萍）(C)易拉罐形状和尺寸的设计问题（北理工：叶其孝）(D)煤矿瓦斯和煤尘的监测与控制问题（信息工程大学：韩中庚）2007年:(A)中国人口增长预测问题（清华大学:唐云）(B)“乘公交，看奥运”问题（吉大：方沛辰，国防科大：吴孟达）(C)“手机套餐”优惠几何问题(信息工程大学:韩中庚)(D)体能测试时间的安排问题(首都师大:刘雨林)一、CUMCM历年赛题的简析一、CUMCM历年赛题的简析1.CUMCM 的历年赛题浏览2001年夏令营三个题:(A)三峡工程高坡开挖优化设计(三峡大学:李建林等）(B)城市交通拥阻的分析与治理(北京理工大学:叶其孝）(C)乳房癌的诊断问题（复旦大学:谭永基）2006年夏令营三个题:(A)教材出版业的市场调查、评估和预测方法问题（北工大:孟大志）(B)铁路大提速下的京沪线列车调度问题（信息工程大学:韩中庚）(C)旅游需求的预测预报问题（北京理工：叶其孝）2、从问题的实际意义分析32个问题从实际意义分析大体上可分为：工业、农业、工程设计、交通运输、经济管理、生物医学和社会事业等七个大类。

公交转车的最短时间模型及求解作者：叶军， 杨振华， YE Jun， YANG Zhen-hua作者单位：南京邮电大学,数理学院,江苏,南京,210003刊名：数学的实践与认识英文刊名：MATHEMATICS IN PRACTICE AND THEORY年，卷(期)：2008，38(14)被引用次数：0次1.2007年高教社杯全国大学生数学建模竞赛的B题评阅要点1.期刊论文周文峰.李珍萍.刘洪伟.王吉光.ZHOU Wen-feng.LI Zhen-ping.LIU Hong-wei.WANG Ji-Guang最优公交线路选择问题的数学模型及算法-运筹与管理2008,17(5)公交线路选择问题是城市公共交通信息查询的重要内容,本文建立了满足不同公交线路查询者需求的最优线路选择模型并给出了相应的算法.首先通过引入各条公交线路直达最短距离矩阵构造了公交网络直达关系图(直达矩阵),在直达关系周(直达矩阵)上,利用修改了的最短路算法,即可求得最优换乘路线.根据出行者的不同需求,通过在直达关系图上定义不同的权系数,可以分别求得换乘次数最少的公交出行线路、经过站点最少的公交出行线路;通过修改最短路算法,可以求得出行耗时最少的线路及出行费用最低的线路,另外,本模型还可以综合考虑出行者的需求情况,求得出行者满意度最大的出行路线.2.期刊论文张鸿艳.诸秉政.徐晶.李文宇.Zhang Hongyan.Zhu Bingzheng.Xu Jing.Li Wenyu奥运公交线路选择的数学模型-哈尔滨师范大学自然科学学报2008,24(3)采用改进的Dijkstra算法和多目标规划方法,综合考虑时间、费用等因素建立了公交线路选择模型,解决了奥运期间观众出行面临多条线路选择的问题,使得公众的出行更加通畅、便利,最后对模型进行了综合评判,指出该模型具有一定的实用价值.3.期刊论文侯晓利.薛伟坡.张军委公交线路选择问题的数学模型与算法-统计与决策2008,""(18)文章针对问题,分别就公汽、地铁、步行等出行方式建立了四个模型,并按具体需求将来客分为偏向时间和偏向费用两种类型,在尽量减少交通阻抗条件下制定最优路线.建立穷举模型和0-1规划模型对数据进行预处理,分别以时间和票价作为权重用有向图表示,构造邻接矩阵,建立Floyd模型.针对Floyd算法对时间要求较高,建立基于广度优先算法的最短路径模型,达到较好效果.用地铁站置换可转乘的公汽站,调整邻接关系,调用广度优先算法得出最优路线.4.期刊论文李鹏.贺勤.尹景本.王盈基于数据结构的最佳公交路线模型-河南科技学院学报（自然科学版）2008,36(1)本文为公交乘客设计了最佳线路数学模型,然后基于数据结构技术,求出了公交线路选择的最佳方案.通过对公交乘客出行心理的研究分析,发现换乘次数是大部分乘客出行时考虑的首要因素,而且乘车耗时和乘车费用在影响因素中也占重要地位.因此以这三个因素为优化目标建立了相应的数学模型.最后,分析讨论了所用模型及其算法的科学性和合理性,并针对本模型所存在的问题提出了新的改进方法和方向.5.期刊论文林玎.高瑷城市公交线路选择方案模型及其算法-吉林建筑工程学院学报2009,26(4)笔者基于乘客出行心理,从乘车的安全、舒适、快捷、准时、经济等因素考查,建立以乘换次数最少、出行距离最短、费用最少为目标的多目标线性规划数学模型.利用数据库技术,设计公交网络数据结构方案的计算机算法,采用广度搜索的算法,从数据中筛选出含有始点和终点的路线,建立两个数组.利用循环结构可同时输出转站点、乘车时间、乘车费用等.此外,结合绝大多数人选择出行线路的基本心理,引入人性化系数α,最终得出模糊随机最短路径的约束模型.本文链接：/Periodical_sxdsjyrs200814026.aspx授权使用：洛阳工学院（河南科技大学）(wflskd)，授权号：19eb9c3b-6311-4088-ba34-9dd800b0be3a下载时间：2010年8月20日。

2007年全国研究生数学建模竞赛获奖名单
自11月30日全国研究生数学建模竞赛拟获奖名单公示以来我们收到部分参赛研究生对拟获奖名单中学校名称、研究生姓名的输入错误要求进行改正的邮件，现在已经全部纠正。

在公示期间我们还组织力量对部分获奖论文进行复查并要求所有拟获一等奖的研究生队对自己的论文进行复核，在复核中发现与论文不一致的地方要做出可以接受的解释。

现在这项工作也已经完成，我们据此对获奖情况做了极个别的调整。

现将2007年全国研究生数学建模竞赛获奖名单正式公布。

全国研究生数学建模竞赛评审委员会
2007．12．16
A题获奖名单
B题获奖名单
C题获奖名单
D题获奖名单。

公交出行优化线路系统设计作者：王家玉来源：《新一代·上半月》2010年第08期摘要:本文给出了一种公交查询系统算法设计,在综合考虑出行人的心理因素前提下,选择以最少换乘次数为第一目标,以出行总花费为第二目标,建立公交优化模型,从而解决公众出行的最佳乘车路线问题。

关键词:交通网络;广度优先搜索;搜索树中图分类号: G421文献标识码:A文章编号:1003-2851(2010)08-0105-01一、引言在城市数字地图中,公共交通信息模块是必不可少,公交换乘信息的查询倍受用户的关注。

在现有的公共交通条件下,设计合理的公交出行路径有助于人们确定出发时间、出行线路和换乘方案等。

在本文中选择以最少换乘次数为第一目标,以出行总花费为第二目标。

首先将所有公汽线路作为一个节点,搜索出整个公汽线路的连通网络,然后再由出行起始站点A和终止站点B出发,考虑换乘次数有限的条件,用广度优先搜索出从站点A到站点B的局部连通网络,再利用深度优先搜索从站点A到站点B在局部连通网络中的所有可能的路径,并给出相应的效用值(换成次数,出行费用)从中找出各自目标下的最优出行路线。

二、出行系统模型设计步骤第一步:初始化公汽连通网络。

(1)将每一条公交线看成一个点,上、下行分别考虑,单线、环行均为双向行驶,作为两个点,记为No1,No2,……No;(2)判断任意两条公交线是否相连,任意取一条线路,按站点次序搜索,判断是否与其他线路连通,若连通将该线路标记在所取线路的neighbours中。

当所有线路搜索完毕则可以得到公汽连通网络,设l1,l2,...ln表示所有线路。

第二步:按广度优先搜索连接起始点A到终止点B在有限换乘下的连通网络。

(1)将所有包含起始站点A的线路作为一个start集,所有包含终止站点B的线路作为一个end集。

(2)标记start集中的各节点(线路),找出和start各个线路相连的节点(线路),start集中与之相连的节点为该节点的父节点。