《乘公交看亚运(含代码程序)》由会员分享,可在线阅读,更多相关《乘公交看亚运(含代码程序)(21页珍藏版)》请在金锄头文库上搜索。
1、5 组 于金龙 王超 焦艳彬乘公交,看亚运摘要本文研究的是广州亚运会期间公交线路选择及交通困难的问题,需要解决只考虑公交线路的出行线路选择问题,以及在考虑公交和地铁同时运行时,筛选交通困难地区并提出解决措施(包括增开专线、公交和地铁线路)的问题。未解决这些问题,本文建立了多目标优化模型和双向搜索模型,并得到了比较满意的结果。对于问题一,我们建立了以换乘次数、乘车时间及乘车费用为目标的多目标优化模型,考虑到乘客对三者的偏爱程度,本文结合 MATLAB 设计出了最多转乘 1 次的公交线路查询系统。当乘客输入始发站和终点站时,系统会首先搜索是否有直达的线路,如果有则输出线路、乘车时间和乘车费用。然后
2、搜索出乘车时间最少的一次换乘线路,输出始发线路、抵达线路、转乘站点、乘车时间和费用。乘客可以根据自己的偏好进行选择出行公交线路,对于问题一中的三条路线任选一条最优线路如下(其他见表 1 和表 3):线路(条)初始站111211 换乘站 (换乘站 ) 公 汽 线 路 公 汽 线 路 公 汽 线 路终点站时间(分) 金钱(元)1 越秀桥312411 山村84 69 1.52 越秀桥512611 芳村隧道口 山村90 908 41 3对于问题二,根据题目中所给资料以及网络搜索资料,从 3108 个站点当中筛选出了亚运会期间交通压力相对大的若干地区,并引入了交通困难系数,对交通困难情况进行了分类:一是
3、站点线路过剩,二是站点线路过少。并定义当交通困难系数小于 0 时为线路过少的交通困难情况,当困难系数大于 0 时为站点过剩的交通困难情况,当为 0 时交通状况良好。最后运用 MATLAB 和 Excel对相关站点的数据进行处理,得到了交通困难的若干站点及地区,部分结果如下:站点 奥林匹克体育中心体育馆 横沥客运站中山八路 动物园南门东圃镇困难系数 5.67 9 4.75 0.32 0.24 -0.2对于问题三和问题四,其实是对问题二所提出的解决措施,通过在亚运会前拟建专线或者增开公交和地铁线路来缓解交通困难地区的交通压力。对于期间客流量大并且公汽线路少的地区增开公交和地铁,并根据运行时间设置合
4、理的收费标准,会缓解这些地区的交通困难。关键字:多目标优化 公交线路查询系统 交通困难系数 双向搜索1.问题重述2010 年 11 月 12 日第 16 届亚运会在广州举行,为了让全体市民更好看亚运会,广州市政府决定在亚运期间放假 3 天、以及全体市民可在亚运及亚残运会期间免费坐公交、地铁 30 个工作日等惠民政策,这一政策的施行在很大程度上加剧了广州市交通出行的困难。附件一,附件二是广州市公交(包括地铁)的一些信息,为了方便游客看亚运会,请你用数学建模的方法,为广州市设计一个公交线路查询系统,满足查询者的各种不同需求。请你们解决如下问题:1、在亚运会开幕前,仅考虑公汽线路,给出任意两公汽站点
5、之间线路选择问题的一般数学模型与算法。并根据附录数据,利用你们的模型与算法,求出以下 3 对起始站终到站之间的最佳路线(要有清晰的评价说明) 。(1)、华穗路 交通大厦 (2)、越秀桥山村 (3)、江南大道北策边村2、在亚运会期间考虑公交和地铁的情况下,哪些地区的交通困难,并说明原因。3、在亚运会开幕前现拟建专线,请合理设置专线的路线,运行时间,以及收费标准。4、如何增加公交,地铁或者专线,缓解交通困难。注:交通困难以某条线路上的最困难作为指标基本参数设定见附录一公交线路及相关信息见附录二2.问题分析本文要处理的问题是交通查询系统乘车最佳路线的选择问题。对于文中所提出的问题,主要考虑三种交通工
6、具:公汽、地铁和专线。寻找一条乘车最佳路线的问题就是在公交网络各种不同的换乘或直达路线中找到一条最佳的路线。从实际情况考虑,乘客的需求是多方面的。在选择出行路线时,通常会考虑以下几种因素:“换乘次数” 、 “出行距离” 、 “出行时间” 、 “出行费用” 。由于没有给出“出行距离” ,可以不将距离作为一项指标单独考虑。但是由于给出的“出行时间”均为平均值,实际上就是距离的一种反映。那么下面就针对“换乘次数” 、 “出行时间” 、 “出行费用”三项需求进行分析。为乘客提供一个针对上述三种因素的较好的出行路线是非常现实而又重要的。2.1 多目标需求的出行方案在实际情况中,大多数乘客的需求是多方面的
7、,可能是对单个目标的需求也可能对多个目标均有需求,如既希望换乘次数少,乘车时间较少,又希望能在上述两种需求满足下花最少的钱,对于一个实用的自动查询系统来说,满足乘客的不同需求是最重要的功能。因此针对乘客的多方面需求,给出一个既针对单个目标又能综合权衡各种因素的好的路线是很重要的。2.2 单目标需求的出行方案现实生活中有一部分乘客,他们仅有特定的单方面需求。比如有的人希望出行方便 ,希望查询到一个换乘次数最少的出行路线。而有的人则希望在最短的时间内到达目的地,例如赶上看亚运会比赛等,他们希望出行耗时最少,而宁愿多花点钱或者选择中途转站。另外,还有的人会出于经济方面考虑,由于临时身上没带足够的现金
8、等原因,希望能花最少的钱到达目的地。这些人在查询过程中只要求一种需求满足即可,其他方面不是最好的也可以接受甚至可以不予以考虑。针对这一类乘客,我们的模型要为他们提供单一需求下的最优出行路线,以供乘客出行时参考。在这种情况下,我们就可以单一分析各种需求情况。这样,在模型中,我们将分别为要求换乘次数最少,要求出行耗时最少和要求出行费用最少三种不同的单一需求的乘客给出三个单一目标的最优解,从而给不同需求的乘客一个满意的出行线路。针对上述需求分析,立足于从简单到复杂的求解过程,我们建立从单一目标求最优路线到综合考虑多种目标求出最优路线的模型,逐一进行求解。3.问题假设和符号说明3.1 问题假设1.对于
9、需要换乘 2 次以上的乘车路线不予以考虑。2.每条线路上的交通工具的发车和到站的时间间隔为定值。3.道路畅通,不考虑堵车及交通故障对乘车时间和选择路线的影响。4.公交准点到达,不考虑红绿灯等待时间。5.各路径上公交车发车频度相同。3.2 符号说明 N换乘次数m乘车数T乘车时间1it公汽站点间平均行驶时间2i转乘时间il第 次乘车走过站点数iF 乘车费用iL从起始站到终到站经过线路的集合iS从起始站到终到站经过站点的集合K为交通困难系数某个站点的重要程度系数n为通过某个站点的公交(含地铁)的线路数4.模型前的准备4.1 对各个站点进行编号处理由于题目所给的公交线路相关信息都是汉字形式,为了方便下
10、一步操作,我们利用 matlab 编程(程序见附录一)将所有站点进行编号处理,由此可知共有 3108 个站点、1108 条线路。按照所给附录一中的要求可知共有 9 条地铁线路,具体代码及结果见附录。4.2 基本参量的设定1 行驶时间相邻公汽站平均行驶时间(包括停站时间): 3 分钟相邻地铁站平均行驶时间(包括停站时间): 2.5 分钟2 换乘时间公汽换乘公汽平均耗时: 5 分钟(其中步行时间 2 分钟)地铁换乘地铁平均耗时: 4 分钟(其中步行时间 2 分钟)地铁换乘公汽平均耗时: 7 分钟(其中步行时间 4 分钟)公汽换乘地铁平均耗时: 6 分钟(其中步行时间 4 分钟)由此可得出公汽等车时
11、间为 3 分钟,地铁等车时间为 2 分钟。3 公交票价公汽票价:车站站点数小于 6 的线路为 2.5 元票价车站站点数小于 10 的线路为 2.0 元票价车站站点数大于等于 10 的线路为 1.5 元票价地铁票价:3 元(无论地铁线路间是否换乘)4 线路规定1)以下 40 条线路是环线:39 15 68 8 7 62 35 28 43 81 37 76 64 12 82 52 56 51 31 17 21 49 65 29 63 66 79 45 23 50 2 19 16 73 59 75 5 78 44 61由此我们对这 40 条环路进行处理,将始发站复制到终点站之后,以示其为环路。2)车
12、站站点数超过 47 的为地铁,由此我们可知共有 9 条地铁线路,它们是:139 142 212 397 528 682 687 937 10003)车站站点数为 2 的拟建专线由此我们可以知道拟建专线共有 8 条,它们是:34 35 36 168 243 424 448 8035.三种公汽线路的抽象处理根据题中信息,公汽线路分三种,下面将这三种线路进行数据处理:a. 题目中给出的环形路线中,有的路线除了首点和尾点之外还有相同的站点,即环形路线自身存在交叉点。根据我国大多数城市建立环形公路的方式(例如北京,南京等地区) ,环形公路分为内环与外环,我们可以简单的理解为,环形公路也是双向的。b.上行
13、线路只能从首站方向开往终站方向而不能返回,即为单向路线。下行线路亦然。上,下行线路为单向路线,单条线路的站点次序不能颠倒,但可以通过两条线路公共站点的换乘来达到。S1S7S3S2S6S5S4c.当下行线与上行线经过站点不同时,需要抽象成两条线路处理。5.模型的建立与求解5.1 公汽站点之间线路选择模型5.1.1 模型的分析在外出乘公交的实际问题中,由于公交费用有限,乘车时间变动范围也是一定的,尤其是对于不熟悉地理位置的出行者来说,转乘次数少,外出方便成为了第一选择路线的因素,互联网上大量的外出路线选择调查也表明人们在外出时,首先注重的是转乘次数最少,其次才考虑时间和费用。另外,由于公汽的分段定
14、价和单一票价式售票方式,转乘次数最少在一定概率上减少了乘车时间和费用。考虑到上述情况,我们以转乘次数最少为前提,在本模型中,将转乘次数控制在 2 次以内(转乘 3 次及以上与转乘 2 次原理一样,因为这种情况发生很少,故本文不予考虑) ,然后再在其基础上考虑时间和费用最优。其中,由于公交费用不高,约束弱,所以在时间和费用上,首先考虑时间最少,其次再考虑费用。现在不同需求下推荐最佳路线: 通畅、便利目标:换乘次数最少; 不同的行程需求:行程耗时最少;行程费用最少;5.1.2 模型的建立1、决策变量为方便模型的建立,用 L 表示各乘车路线,用 S表示各个站点,设总乘车次数为 m,则有起始点为 ,终
15、到点为 所乘车次按先后依次为:1S1m( 属于 L001L1108),12,.mLi各转车地点分别为: ( 属于 S0001S3108),121,.miS则乘车路线可表示为: SL2、目标函数1)转乘次数 N 最少,转乘次数 = 所乘车数 1:min N(L,S) = m(L,S) 12)旅途时间 T 最短,旅途时间 = 乘车时间之和(与站点数有关) + 转乘时间之和。min T(L,S) = + 1()itl12it3)乘车费用 F 最少,乘车费用取决于所乘车次的收费方式。min 1(,)miFLS3、约束条件1)每次乘车时间与所过站点数成正比,乘车时间 =所过站点数 公汽站点间itil平均行驶时间 。3min(i = 1,2m-1)1()3iitl其中 由 , 决定。L1S2)转乘时间为公汽换乘公汽平均耗时 。由所给资料可知2it(i = 1,2m-1)25init3)乘车费用取决于所乘车次的收费方式,分段定价类的收费方式的乘车费用又与所乘站点数有关。(i = 1,2m)0,0;2.56,1;471.30,iii illFl 4)每次乘车所过站点数由乘车线路决定,所过站点数 = 从上车地点到下车地点乘车所过站数(包括下车地点) 。(i =