数学建模第六轮乘公交-看亚运

乘公交,看亚运摘要本文解决的是最正确乘车路线问题,分析乘车路线选择的主要影响因素建立了相应的求解模型,确定不同情况下的最正确乘车路线.并分析各线路的交通情况,给出了缓解交通困难的方案.对于问题一:根据题目所给出的公交线路信息数据,利用逐步搜索法求出任意两公汽站点间的直达线路,在最少换乘次数的根底上以时间为主要目标并考虑乘车费用建立多目标优化模型.通过编程找出三对站点的最正确方案,均需要换乘1次,总花费均为3元,详细结果见下表:华穗路→交通大厦越秀桥→山村江南大道北→策边村换乘方案由408路转到1047路由184路转到893路由235路转到192路换乘站点江南大道口芳村隧道口动物园花费时间116分钟38分钟140分钟对于问题二:以分别到达所有亚运场馆的总换乘次数最多和所需时间最长为困难地区的评判标准,建立新的多目标优化模型,利用MATLAB软件编程求解得到结果. 对于问题三:在模型二的根底上,建立以总时间最少作为目标的单目标模型.将专线的路线设置分为两种处理方法:一,对可在公交或地铁线路中得到路线的四条线路用模型三求解;二,对不可在公交或地铁线路中得到路线的直接搜索相关资料得到两站的最短路程再换算成时间.最后统一给定根据行驶时间的收费标准得到专线具体设置情况. 对于问题四:以过站点的线路最少为交通困难目标建立相应的整数规划模型,并用MATLAB软件求解得到交通困难区,在增加公交、地铁或专线时重点考虑求得的交通困难区.本文分析考虑不同问题的需求建立了四个相应的模型,但由于时间原因,局部模型没有求得结果.关键词:逐步搜索法多目标规划整数规划

1.问题重述1.1问题背景:2010年11月12日第16届亚运会在广州举行,为了让全体市民更好观看亚运会,广州市政府决定在亚运期间放假3天、以及全体市民可在亚运及亚残运会期间免费坐公交、地铁30个工作日等惠民政策,这一政策的施行在很大程度上加剧了广州市交通出行的困难.为了方便游客看亚运会,请你用数学建模的方法1.2题目所给信息交通困难以某条线路上的最困难作为指标;根本参数设定见附录一;公交线路及相关信息见附录二.1.3本文需解决的问题有:问题一:在亚运会开幕前,仅考虑公汽线路,给出任意两公汽站点之间线路选择问题的一般数学模型与算法.并根据附录数据,利用你们的模型与算法,求出以下3对起始站→终到站之间的最正确路线〔要有清晰的评价说明〕.(1)、华穗路→交通大厦(2)、越秀桥→山村(3)、江南大道北→策边村问题二:在亚运会期间考虑公交和地铁的情况下,哪些地区的交通困难,并说明原因.问题三:在亚运会开幕前现拟建专线,请合理设置专线的路线,运行时间,以及收费标准.问题四:如何增加公交,地铁或者专线,缓解交通困难.2.模型的假设与符号说明2.1模型的假设假设1:各路径上的公交车发车平度相同;假设2:相邻站点的平均行驶时间一定;假设3:不出现交通阻塞,公交运行顺畅;假设4:不出现车辆故障及交通事故;假设5:公交准点到达,不考虑红绿灯等待时间;假设6:除环形线路外其他线路均是单向行驶.2.2符号说明符号符号说明公汽网的有向赋权图站点号直达线路数矩阵引入的中间矩阵最少换乘数矩阵第个站点到第个站点的直达线路数第个站点到第个站点的最少换乘次数,弧是否在该路径上总站点数两站点的直达线路数,站点的最短乘车时间站点的总乘车费用表示站点的过站数人为设定参数,乘客可接受的最多换乘次数公汽地铁网的有向赋权图亚运六个主场馆的站点集合始发的等待时间总的乘车时间总的等待时间总的步行时间换乘时步行的时间站点在线路上3.问题分析为了设计一个公交线路查询系统去满足查询者的各种需求,我们分析题目要求,先对题目给出的公交线路各站点名按一定的顺序进行标号,以便后面的求解表达.再分析主要的影响因素——换乘次数、行驶时间、乘车费用等,建立相应的求解模型,确定不同情况的最正确乘车路线.并分析各线路的交通情况,给出缓解交通困难的方案.对问题的具体分析如下.针对问题一:只考虑公交车线路的情况下,要给出任意两公汽站点之间线路选择.首先,我们根据题目所给出的公交线路信息,利用逐步搜索法求出任意两公汽站点间的直达线路,并用矩阵表示出直达线路的条数,这是为后面的目标及约束的考虑做准备.再考虑换乘次数,在最少换乘次数的根底上先后考虑行驶时间及乘车费用,并以它们建立相应的目标函数.通过编程找出供选的多种参考方案.并以时间为主要目标建立任意两站点的行驶时间最短的最优化模型.针对问题二:在亚运会期间,考虑公交和地铁的情况下,将地铁站点与其对应的公交站点视为一个站点处理.另外,由于亚运期间乘公交地铁免费,故此问少了问题一中的最少乘车费用的目标.但由于要考察地区的交通困难情况,所以在问题一的根底上要增加新的目标函数.交通困难是以某条线路上的最困难作为指标,通过查询我们知道广州亚运的主场馆在六个站点〔奥林匹克体育中心、体育中心、大学城体育中心、广州体育馆、黄埔体育馆、增城体育馆〕附近,所以我们定义站点的交通困难为分别到达所有亚运场馆的总换乘次数最多和所需时间最长.而增加了地铁后,换乘的情况也相应变化,特别是换乘时间,这对总时间和换乘次数的目标函数都有影响,约束条件根本不变,这样建立新的优化模型,再用matlab编程求解.针对问题三:要设置合理的专线线路,我们在问题二的根底上,考虑专线设置的总路程最短即耗时最少作为线路设置指标,可直接将问题二的模型改成总时间最少的单目标,并对相应约束条件进行调整得到优化模型三.但考虑到有四条拟建专线的站点不能在公交或地铁线路中得到路线,所以我们将专线的路线设置分为两种处理方法:对可在公交或地铁线路中得到路线的四条线路用模型三求解;对不可在公交或地铁线路中得到路线的直接搜索相关资料得到两站的最短路程再换算成时间.最后统一给定根据行驶时间的收费标准.针对问题四:要增加公交、地铁或者专线,缓解交通困难,我们以过站点的线路最少的作为交通困难区,建立相应的整数规划模型,并用MATLAB软件求解得到交通困难区,在增加公交、地铁或专线时重点考虑求得的交通困难区,这样可缓解交通压力.4.数据分析 把题目所给数据信息分类整理:整理一:将题目所给附录二中的同条线路上的两个相同站点名改后一个为“站名+2”,如第五条线路的“江夏〔安华灯饰城〕”就在此条线路中出现了两次,我们将第二次出现的改名为“江夏〔安华灯饰城〕2整理二:根据题目的站点数归类原那么,将题中附录二中的线路按:0—2拟建专线;3—47公交线;47—55地铁线进行归类.最后得到:公交线路1052条,其中环线39条;地铁线路9条;拟建专线8条.将上述结果制成下列图,即:图4-1:附录一的线路分类结果从图中可以看出:广州市以公交线路为主,其中包括局部+环线公交,地铁和专线数都很少,这主要与城市的交通及需要有关. 整理三:将题中附录二的线路按附录一中的票价标准进行票价分类,即:站点数小于6的线路为2.5元票价;站点数小于10的线路为2.0元票价;站点数大于等于10的线路为1.5元票价;地铁票价为3元.统计结果见下表〔源程序参见附录三〕:表4-1:票价统计结果表票价〔元〕3.02.52.01.5线路数〔条〕920261044从上表我们看出:大局部线路的票价为1.5元.接着,我们将每条线路的站点数目进行统方案分得到下面的站点数分布图,即:图4-2:线路的站点数分布图 从上图我们可以看出:大局部线路的站点数在15—30之间,站点数大于30的线路数比站点数小于15的线路数多.可见,广州市的站点线路设置还是比拟合理的,根本符合线路覆盖面广和地铁数量合理的原那么.5．问题一的解答针对问题一,我们建立了以时间为主要目标的任意两站点的行驶时间最短的最优化模型一.5.1模型的准备准备一:引用图论相关知识,将题目所提供的公汽网络抽象成一个有向赋权图,中每个顶点代表不同的站点,如果到有直达路线,那么这两点之间就用有向边相连,记做,相应用表示该有向边的权,这样公汽网络就抽象为了一个有向赋权图.准备二:问题分析中我们提出为了方便乘客乘车,考虑到换乘既存在时间消耗又有增加乘车费用,所以我们在最少换乘次数的根底上考虑公众对其他因素的需求.所以,我们首先确定最少换乘次数.第一步,构造直达线路数矩阵:通过求得任意两点的直达线路并构造两两间直达路线数目的直达路线数矩阵.其矩阵元素表示第个站点到第个站点的直达线路数,其中,当时,,即:以所有公汽所经过的站点总数为,那么直达线路数矩阵可表示为:第二步,建立换乘线路数矩阵:根据矩阵运算法那么,的元素可表示为:假设上式中等号右边仅,其余为0,说明仅第一个站点可直到达第三个站点,第三个站点可直到达第二个站点,那么,即第一个站点可通过一次换乘到达第二个站点,换乘站点为3.通过上面的例子我们发现,可以用表示第个站点到第个站点通过1次换乘的路线数.依次类推,用表示方阵的次幂,为站点的直达路线数,那么:其中,元素为通过次换乘从站点的线路数.如:表示从站点4到站点3有1条两次换乘路线,其换乘站点可通过运算参数记录得到.第三步,建立最少换乘次数矩阵:先引入矩阵,其矩阵元素为使得的的最小值,,即:那么表示从站点必要的最少换乘次数,以矩阵表示最少换乘次数矩阵,元素表示从站点必要的最少换乘次数,那么:5.2模型一的建立5.2在问题分析中我们已经提出,要满足乘客的不同需求,主要分三个因素考虑:换乘次数、行驶时间、乘车费用.并且,我们在最少换乘次数的根底上考虑公众对其他因素的需求.这样目标函数就有三个,即:换乘次数最少在模型准备中我们建立了公汽网的有向赋权图,在此,我们引入0-1决策变量表示弧是否在起点与终点的路上,即:假设与之间无直接相连的弧,但可以通过中间节点跳转,说明站点与之间不可直达,但可通过转乘到达,那么两点的转乘次数为经过的总弧数减一,即:行驶时间最短以第个站点到第个站点的时间为元素建立时间权值矩阵:那么乘车总时间就为:由公汽换公汽的时间固定为5分钟,那么换乘时间为:包含起始站等待时间3分钟的行驶总时间最短为:所需花费最少依题意,的直达费用满足:得到行程费用最少为:5.2约束一,换乘次数的约束 之前的分析中已经提到,应尽量减少换乘次数,但不同的乘客可能承受的换乘次数不同,所以我们用〔且为整数〕表示乘客所能接受的最大换乘次数,得到换乘次数的约束为: 参数为人为设定值,分以下三种情况:当时,严格约束不能换乘;当时,无换乘次数约束,可无限换乘;当为不为0的常数时,约束换乘次数在次以内的情况.假设单从模型的通用性考虑,可取到正无穷;假设从实际情况出发,查询系统中应由查询者自行设定,当最小换乘次数小于时输出无解.约束二,最短路始末点的约束 因为有向图中,顶点分为了:起点、中间点、终点,对于起点只有出的边而无入的边,对于中间点既有入的也有出的边,对于终点只有入的没有出的边. 那么,用进入第个顶点的边和出第个顶点的边表示两顶点的最短路径中三类点的约束为:综上所述,得到问题一的最优化模型:5.3模型一的求解按照以上模型,利用以换乘次数最少为根本目标的逐步搜寻法,把问题一中的三对起始站→终到站输入算法程序〔参见附录四〕中,即得到基于最少换乘次数的选择方式的乘车路线.由于可行方案较多,为了得到最优可行方案,根据以下原那么进行筛选:原那么一,乘车费用和乘车耗时都大的先剔除;原那么二,三个目标都相同的方案任选其一,其他剔除.按上诉原那么进行筛选后,给出最正确选择方案如下:表5-2:模型一的求解结果华穗路→交通大厦越秀桥→山村江南大道北→策边村换乘次数111换乘方案由408路转到1047路由184路转到893路由235路转到192路换乘站点江南大道口芳村隧道口动物园花费时间116分钟38分钟140分钟乘车费用3元3元3元5.4结果分析:通过上面的结果我们看出,题目所求的三对站点都无法直接到达,需要至少换乘一次才能到达,但考虑到多数人可能不会接受屡次换乘,故在此以换乘次数最少为第一目标,得到三对站点的一次换乘结果.此结果中的一次换乘方案中华穗路→交通大厦需要的总时间为116分钟,江南大道北→策边村需要的总时间为140分钟,这两个时间都很长,所以在乘客希望更省时间的情况下,考虑两次的换乘可能更符合乘客要求.另外,在乘车费用的角度来讲,一次换乘是既可到达目的地又最省钱的,都只需3元.6．问题二的解答针对问题二我们在问题一模型的根底上建立了新的多目标优化模型,即模型二.6.1模型的准备用模型一准备中相同的方法将公汽、地铁混合网络抽象成一个有向赋权图,图中的含义同模型一.再用模型一准备中相同的方法确定最少换乘次数,得到含义与模型一相同的表达式,即:6.2模型二的建立6.问题二是在亚运期间考虑地铁的情况下求交通困难的地区,考虑到亚运期间乘车免费,所以去掉费用的目标,以总的行驶时间最长和分别到达所有亚运场馆的总换乘次数最多为目标函数,即:分别到达所有亚运场馆的总换乘次数最多在此模型的准备中我们同样建立了公汽网的有向赋权图,在此,我们同样引入0-1决策变量表示弧是否在起点与终点的路上,即:同样得到两站点的最少换乘次数:不同的是,我们需要给定六个亚运场馆〔奥林匹克体育中心、体育中心、大学城体育中心、广州体育馆、黄埔体育馆、增城体育馆〕作为终点站,以分别到达所有亚运场馆的总换乘次数最多为目标函数,即:总的行驶时间最长先求到达每个亚运场管的最短时间.在问题一的目标二根底上,由于增加了地铁,所以,换乘的时间上就有所改变,且给定了终点站.首先,在考虑地铁后,第个站点到第个站点的时间为元素建立时间权值矩阵:得到总的乘车时间为:始发的等待时间满足:得到总的等待时间为:根据题目所给的两两间的换乘所步行的时间知道,步行时间与换乘的交通工具是否相同有关,即:从上面知道,根底步行时间为2分钟,再加上不同交通工具间换乘多步行的2分钟.得到总的步行时间为:综上所述,得到总的乘车时间最长的目标函数为:5.2问题分析中已经知道,本问的约束条件根本不变,即:综上所述,得到问题二的最优化模型:6.3模型二的求解6.4结果分析:7．问题三的解答针对问题三我们建立了新的收益最大的规划模型,即模型三.7.1模型三的建立确定目标函数在问题二的根底上,考虑专线设置的总路程最短即耗时最少作为线路设置指标,可直接将问题二的模型改成总时间最少的单目标,即:确定约束条件 因为限定了四条可求的拟建专线,那么它们的起点站终点站都以确定,它们的编号分别为,那么:综上所述,得到问题三的单目标优化模型:7.2模型三的求解7.3结果分析:8．问题四的解答针对问题四我们建立了一个经过此站点的线路数最少的整数规划模型,即模型四.8.1模型四的建立 引进0-1变量,且以经过站点的线路数最少为目标函数,即:综上所述,得到问题四的模型:8.2模型四的求解根据建立的整数规划模型,编写相应的MATLAB程序〔源程序参见附录五〕,求得交通困难的站点〔具体结果见附录五〕.8.3结果分析:

9.模型的评价9.1模型优点:优点一:问题一中我们综合考虑了转车次数、乘车费用、乘车时间建立了多目标的快速公交模型,能提供多种可行方案同时给出推荐比拟好的乘车方案,可以更好满足人们乘车需要.优点二:在问题一的根底上将地铁线路参加到乘车网络当中在模型一的情况下很容易就能查找相关乘车方案,再去讨论后面的问题,模型简单且容易求解.优点三:在对题目复杂数据的处理方面,我们先将个站点进行编号,同时巧妙处理环路和非环路的两种情况,有利于模型的建立和求解.优点四:在考虑亚运会开幕前和亚运会期间的问题时以亚运场馆为基准点向周围搜索,方向比拟明确,使模型更为简单.9.2模型缺点缺点一:建立的模型在综合考虑各方面的因素时,查询算法不够高高效,程序运行时间比拟长.缺点二:在考虑交通困难等方面的问题时,没有结合各站点人流量等实际情况综合各方面因素考虑交通的困难程度.10.模型的改良及推广10.1模型改良改良一:定义新的直达矩阵,建立一种基于矩阵运算的高效公交查询算法.改良二:交通困难并不仅仅是有些地区线路上无法到达目的地还应包括局部地区经过的车次比拟多造成交通比拟拥挤的情况,我们应该建立综合考虑二者的数学模型.改良三:通过实地调研广州市各站点人流量的情况,对模型进行改良.10.2模型推广 本文所建立的公交查询模型能很快的查得广州市各地区的乘车方案,能很好的满足广阔广州市民的生活需求,同时建立了评判交通困难的模型,以及给出了减小交通困难的具体解决方法.这也可以应用于其它城市公交线路的查询和公交线路的优化以及对城市的交通作出合理的指导.参考文献[1]宋来忠,王志明,《数学建模与实验》,北京:科学出版社,2005.[2]运筹学教材编写组编,《运筹学(3版)》,北京:清华大学出版社,2005.6[3]张志涌,杨祖缨,《matlab教程R2011a》,北京:航空航天大学出版社,2011.7

附录附录一:题目所给附录一说明〔略〕附录二:题目所给附录二线路〔略〕附录三:数据分析整理三的MATLAB源程序clcclearloadpath[a,data]=xlsread('data.xls');b=path;station=unique(data);station(1)=[];[n1,n2]=size(b);C=zeros(1108,1);fori=1:1108C(i)=sum((b(i,:)~=0));enddisp('票价2.5')ind=find(C<6&C>2)C(ind)n1=length(ind)disp('票价2.0')ind1=find(C<10&C>=6)C(ind1)n2=length(ind1)disp('票价1.5')ind2=find(C<48&C>=10)C(ind2)n3=length(ind2)disp('票价3')ind3=find(C>=48)C(ind3)n4=length(ind3)n=max(C);D=zeros(n-1,1);fori=2:nD(i-1,1)=length(find(C==i));endx=[2:n];plot(x,D','-*b')gridon,axisequalaxis([2,55,0,61])xlabel('线路站点数目'),ylabel('线路条数')运行结果:'上下九步行街''东乡村口''东环路(东怡新村)''东风中学''东风小学''中医院东''中医院东门''中央酒店''乐捷图广场''五''仁济西路''傍东村''傍江东坊''光属纤维厂''勒竹新村''勒竹村''北斗星''北村路''区星海青少年宫(城北公园)总站''华南工商学院''华工大牌坊''南华东路''南华广场新世纪东''南浦中路''南浦大桥北''南浦大桥南''名雅公司''塘埗西''多宝路(市二医院)''大学城中部枢纽〔共54站〕''大新路''大石桥底''大龙桥''天成路''姬棠商业街''富华市场〔下行〕