2007年数学建模B题_乘公交_看奥运一等奖.doc

2007年数学建模B题_乘公交_看奥运一等奖.doc

ID:51905038

大小:1.04 MB

页数:57页

时间:2020-03-18

2007年数学建模B题_乘公交_看奥运一等奖.doc_第1页
2007年数学建模B题_乘公交_看奥运一等奖.doc_第2页
2007年数学建模B题_乘公交_看奥运一等奖.doc_第3页
2007年数学建模B题_乘公交_看奥运一等奖.doc_第4页
2007年数学建模B题_乘公交_看奥运一等奖.doc_第5页
资源描述:

《2007年数学建模B题_乘公交_看奥运一等奖.doc》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、乘公交,看奥运【摘要】本文要解决的问题是以即将举行的08年北京奥运会为背景而提出的。人们为了能现场观看奥运会,必然会面对出行方式与路线选择的问题。因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。鉴于公交系统网络的复杂性,我们没有采用常规的Dijkstra算法,而采用了高效的广度优先算法。其基本思想是从经过起(始)点的路线出发,搜寻出转乘次数不超过两次的可行路线,然后对可行解进行进一步处理。为满足不同查询者要求,我们对三个问题都分别建立了以时间、转乘次数、费用最小为目标的优化模型。针对问题一(

2、只考虑公汽系统),我们建立了模型一并通过VC++编程得到了任意两个站点间的多种最优路线,并得出所求站点间最优路线的最优值,如下表所示:出发站终点站S3359S1828S1557S0481S0971S0485S0008S0073S0148S0485S0087S3676最短耗时(min)641061066710646最少转乘次数(次)121122最少费用(元)333233模型二是根据问题二(同时考虑公汽和地铁系统)建立的,同样用VC++编程得到所求站点间的最优路线,如下表所示:出发站终点站S3359S1828S1557

3、S0481S0971S0485S0008S0073S0148S0485S0087S3676最短耗时(min)64106965587.533最少转乘次数(次)121120最少费用(元)333233对问题三(将步行考虑在内)我们建立了模型三的优化模型,然后在模型改进里又建立了图论模型。本文的主要特点在于,所用算法的效率十分显著。在对原始数据仅做简单预处理的条件下,搜索任意站点间的最优路线所需的平均时间不超过0.5秒。另外,本文所建立的模型简单、所用算法比较清晰,易于程序实现,对公交线路自主查询计算机系统的实现具有现实指

4、导作用。关键字:转乘次数广度优先算法查询效率实时系统57一问题的重述传承华夏五千年的文明,梦圆十三亿华夏儿女的畅想,2008年8月8日这个不平凡的日子终于离我们越来越近了!在观看奥运的众多方式之中,现场观看无疑是最激动人心的。为了迎接2008年奥运会,北京公交做了充分的准备,首都的公交车大都焕然一新,增强了交通的安全性和舒适性,公交线路已达800条以上,使得公众的出行更加通畅、便利。但同时也面临多条线路的选择问题。为满足公众查询公交线路的选择问题,某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。这个

5、系统的核心是线路选择的模型与算法,另外还应该从实际情况出发考虑,满足查询者的各种不同需求。需要解决的问题有:1、仅考虑公汽线路,给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据,利用模型算法,求出以下6对起始站到终到站最佳路线。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路,解决以上问题。3、假设又知道所有站点之间的步行时间,请你给出任

6、意两站点之间线路选择问题的数学模型。二符号说明:第i条公汽线路标号,i=1,2…10400,当时,表示上行公汽路线,当时,表示与上行路线相对应的下行公汽路线;:经过第i条公汽路线的第g个公汽站点标号;:第j条地铁路线标号,j=1,2;:经过第j条地铁线路的第h个地铁站点标号;:转乘n次的路线;:选择第k种路线的总时间;:选择第k种路线公汽换乘公汽的换乘次数;:选择第k种路线地铁换乘地铁的换乘次数;:选择第k种路线地铁换乘公汽的换乘次数;:选择第k种路线公汽换乘地铁的换乘次数;57:第k种路线、乘坐第m辆公汽的计费方

7、式,其中:表示实行单一票价,表示实行分段计价;:第k种路线,乘坐第m辆公汽的费用;:选择第k种路线的总费用;:选择第k种路线,乘坐第m辆公汽需要经过的公汽站个点数;:选择第k种路线,乘坐第n路地铁需要经过的地铁站个点数;:表示对于第k种路线的第m路公汽的路线是否选择步行,为0-1变量,表示不选择步行,表示选择步行;:对于第k种路线的第n路地铁的路线是否选择步行,为0-1变量,表示不选择步行,表示选择步行;三模型假设3.1基本假设1、相邻公汽站平均行驶时间(包括停站时间):3分钟2、相邻地铁站平均行驶时间(包括停站时

8、间):2.5分钟3、公汽换乘公汽平均耗时:5分钟(其中步行时间2分钟)4、地铁换乘地铁平均耗时:4分钟(其中步行时间2分钟)5、地铁换乘公汽平均耗时:7分钟(其中步行时间4分钟)6、公汽换乘地铁平均耗时:6分钟(其中步行时间4分钟)7、公汽票价:分为单一票价与分段计价两种;单一票价:1元其中分段计价的票价为:0~20站:1元21~40站:2元40站以上:3元

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。