公交转车模型.doc

2013高教社杯全国大学生数学建模竞赛承 诺 书 我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 24 所属学校（请填写完整的全名）： 南京理工大学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 2013 年 8 月 19 日赛区评阅编号（由赛区组委会评阅前进行编号）：编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：公交转车模型摘要这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。为满足乘客查询乘车路线时的不同需求，本文主要从时间最省和费用最小以及转车次数最小三个方面来考虑，以转车次数最少为主要方面来建立模型。对于问题一，我们首先利用和软件对所给数据进行分析、查询、统计并整理数据信息，将公交线路做成一个101887的矩阵，其中上行和下行分开考虑，环形看成是一直循环下去的。然后利用建立一个时间矩阵,采用寻求任意两公汽站点之间行车时间最少的方法，最后由行车时间最少所经过乘车路线的站点来确定时间最短的乘车路线，费用最小的模型与此相似。通过这两个模型得出时间最短和费用最少的最佳路线，再在此基础上得到转车次数尽可能少的最佳路线。对于问题二，同时考虑公汽与地铁，可以把地铁站点看作公汽站点，扩大公汽矩阵，将公汽与公汽之间的时间及费用参数改为公汽与地铁和地铁与地铁两站点间的参数。同样建立矩阵，对于问题三，我们假设已知所有站点之间的步行时间，构造一个关于站点之间的步行时间矩阵，然后通过元素替换构造任意两站点之间线路的数学模型并求解得出最佳乘车路线。关键词：矩阵 搜索法 最短路问题 matlab241 问题重述我国人民翘首企盼的第29届奥运会明年8月在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。 【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间)： 3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。二 问题分析 结合实际情况，公交问题我们以转车次数、乘车费用、乘车时间三个目标建立目标函数比较合理。设计线路选择模型与算法，以满足查询者的各种不同需求。问题可以归结为多目标优化问题。 问题一：仅考虑公汽线路，给出任意两公汽站点之间线路选择的一般模型与算法。解决此类问题最为有效的是floyd算法，求最小路径问题。建立费用最小模型用同样方法即可求出。但是考虑到换车次数多带给乘客的麻烦，本文以为，要求任意两点间乘车路线使得所用时间最少或者费用最低，并不能单纯套用floyd最短路算法模型，而是要在乘客换车次数尽量少的前提下去选择时间最短路线。所以应在乘客换车次数尽量少的前提下，以时间最短或费用最低为目标，分别建立一个时间矩阵和一个费用矩阵，再利用以及软件对矩阵分析求解，得出任意两站点间的最短时间和最低费用的乘车路线。 问题二：同时考虑公汽与地铁，可以把地铁站点看作公汽站点，扩大公汽矩阵，将公汽与公汽之间的时间及费用参数改为公汽与地铁和地铁与地铁两站点间的参数。同样建立矩阵，横行表示公汽和地铁站站点，纵行也表示公汽和地铁站站点。地铁与公汽换乘时，每个地铁站对应几个公汽站，那么我们在建立模型时，可以考虑到对应地铁线上的几个特殊点。具体算法与上一问相同。问题三：有两种途径可以到达目的地：（1）转乘能够到达另外一个转乘站点的车；（2）在离转乘站最近的一个站下车，步行到达转乘站点。有些情况下步行到某一站点比换乘车辆更节约时间，那么我们把所有公交站点连接起来，假设通车。通过步行到达的线路行使费计为0，时间设为已知。三 模型假设1、 “附录”中的数据来源准确、可信、科学。2、不考虑交通堵塞、车辆损坏和乘客的满意度。 3、公众乘车都考虑转车次数尽量少，即选择路线时优先考虑直达或转车次数尽可能少，我们这里假设转车次数不超过3次。 4、假设城市交通畅通，便利，车辆在站与站之间行驶时间是相等的。四 符号说明：第站点到第站点所用的时间；：第站点到第点所用的费用；：矩阵的元素，表示公汽第i站点到第j站点直达车所用的时间；：矩阵的元素，表示公汽第i站点到第j站点直达所用的费用； ：地铁第站点到第点所用的时间；五 模型的建立与求解问题一 假设任意两公汽站点可以到达，所换车次数也不是太多，现以不同变量建立模型。参考附录所给数据，利用软件，可以得出乘坐任意两点所用时间的矩阵，记为时间矩阵，即：时间矩阵 与上面类似，以任意两个车站间所需要费用为元素，建立费用矩阵，即费用矩阵 分别以经过起点和终点的车次组成集合，再利用循环搜索，对每一个起点车次集合中的元素，都让它与所有终点车次比较，如果相同则说明起点能直达终点，否则就求两个车次的交点，说明该起点经过一次转车可到达终点，交点为转乘车点，如果没有交点，则在站点车次矩阵中寻求一个同时与起点集合和终点集合相交的车次，两点为转车两次的转乘点，依次，进行递归，可以求出所有转乘点和转乘方案。依据从始发站到终点站所用时间最少来确立模型,在公汽线路中，建立乘坐公交车在任意两站点所用行驶时间的模型如下 （1）若任意两站点可直达时，则（2）若任意两站点不能直达且考虑途中转一次车时，则（3）若任意两站点不能直达且考虑途中转两次车时，则 依次类推，总可以求出任意两站点所用时间最短的乘车路线，则在公汽线路中，考虑任意两站点间行驶所花费的费用，建立模型如下（1）若任意两站点可直达时，则 （2）若任意两站点不能直达且考虑途中转一次车时，则（3）若任意两站点不能直达且考虑途中转两次车时，则依次类推，总可以求出任意两站点所用费用最短的乘车路线，则表一 时间最少的最佳乘车方案始站到站时间最少的最佳乘车线路时间(分钟)表二 费用最少的乘车方案始站到站费用最少的乘车线路费用（元）3332232一般来说，人们在出行时，除乘坐公交车、地铁外，可供选择的交通工具很多，如出租车等，其费用往往远大于公交的费用，可以说不同的乘车方案中微小的费用差距，远不如时间差异带来的影响大，而另一方面，出行时选择换车次数较少的乘车方案，却是人们比较注重的，（如果单纯为节省时间，而导致换车次数过多，费用也相应增加，一部分人就会考虑改乘出租车等其他方案）所以在乘车时，换乘次数最小往往是人们要特别考虑的一个重要因素，当然，单纯换乘次数最小的最优解往往和单纯费用最优解一样，也有很多个，再在此基础上求出时间最短的最优解，得到如下方案表三 考虑到尽量少换车的最快乘车方案起点终点最佳路线时 间（分钟）1011288310665可以看出，这样一个换乘时间最优解，同是也是一个费用的最优解，这也与乘车次数较少以及现行的公交票价制度有关。问题二在原有的公交运行网络系统上，增加地铁的运行方式，给人们乘车带来了更多的选择方式和乘车路线，因此，选择一种换车次数少、节省时间和经济的线路是我们的目的。同时考虑地铁和公汽，把地铁站看作一个公汽站，就把问题转化为第一问的情况，只需要改变相应的参数就可以了。但在这里有几种特殊情况需要我们考虑：地铁换乘时，在地铁对应的几个公汽站点之间选择最优点时，总耗车费不变。相反，在耗费不变情况下，可以选择使用时间最短一点。在问题一的基础之上又增加了地铁、线路，似乎问题复杂化了，其实，我们也可以将地铁看成是公交车，只是价格和换车时间与普通公交车不同。也即在问题一的任意两公共汽车站点之间所用时间矩阵基础上，增加了地铁、线路的站点，并且将地铁站与公交站点之间的不同转车时间看成是地铁到公交站的运行时间：将地铁站点续在原公交站点的时间矩阵后，即如：，依次类推，直到；当从地铁到公交车有：，当从公交车到地铁有：因此可有：和等。对任意两公汽与地铁站点之间线路的讨论：在问题一的基础之上又增加了地铁线路，似乎问题复杂化了，其实是在问题一所考虑乘坐在任意两站点所用时间矩阵基础上增加了地铁线路的站点，考虑到几种特殊情况，公汽换公汽，公汽换乘地铁，地铁换乘公汽，地铁换乘地铁。假设不通过步行到达要换车的站点。建立两种模型说明换车情况:（这里的i和j既可以表示公交站也可以表示地铁站）没有步行情况，于是建立乘坐在任意两公汽与地铁站点所用时间的目标函数是 如果两公汽站是相邻的且两站点正好间隔一个地铁站，因为地铁站下有人行通道，从人行通道走省时又省费，经过分析，从各个换乘时间中粗略估计出经过地铁站行通人道11分钟。建立以费用最小建立目标函数：类似第一问的方法，建立matlab的M文件，并运行求解（程序见附录二），可以解得：表五 时间最小的结果表始站到站最佳乘车线路总时间（分）71991056745.520从上表可以看出，在跟第一问的比较发现，乘车总时间也少于没有地铁时的情况，也即，在增加了地铁运行线路后，不仅给人们的出行带来方便，而且节省了时间，所以，城市建设地铁有其合理性，能给我们的生活带来便利。问题三在假设知道所有站点之间的步行时间的前提下，构造一个关于站点之间的步行时间距阵，即距阵，且任意一个步行时间元素，用这个时间元素去替换任意两站点之间的任何一个元素，则根据问题一的解题思路便可以构造任意两站点之间线路的数学模型如下（1）若任意两站点可直达时，则 那么，此时步行时间可以直接替换。（2）若任意两站点不能直达且考虑途中转一次车时，则 那么，此时可以用或去替换步行时间距阵中的任何一个元素，在假设条件成立的条件下， （3）若任意两站点不能直达且考虑途中转两次车时，则 那么，此时可以用去替换，中的任何一个便可以构成如下3个模型中为任何一个任意两站点之间线路选择的数学模型 依次类推，总可以求出任意两站点所用时间的数学模型如下注意一点：由于本题任意两站点之间所用费与问题二中任意两站点之间所用费用数学模型相同，所以就不必去考虑任意两站点之间所用费用问题。六 模型分析与评价1模型的优点（1）采用较为成熟的数学理论建立模型，可信度比较高，可行性和合理性较强。（2）在没有建立模型之前，首先对模型数据进行分析，使结果比较准确而且少走了许多弯路。（3）模型不是单纯来求解线路最短、费用最小，而是在此基础上求得转车次数最少的乘车路线，使模型结果更加具有实用性。（4）同时采用搜索法和查询，互相印证和对比，分析所得结果的合理性和可行性。（5）考虑换乘次数最多为三次，能使时间相对较短、费用相对较低，路线能更优化以便达到乘客的需求。2模型的缺点（1）模型虽然考虑了很多因素，但为了建立模型，还是理想化了许多因素，具有一定的局限性，得到的最优方案可能与实际有一定的出入。（2）在在整体规划过程中，存在很多的因素，考虑不全，使得结果与实际有一定的差距。（3）模型数据多，计算量过大，在一定程度上影响了模型的应用和推广。（4）模型采用循环搜索，数据过多时，运行时间急剧增加。七、参考文献 1 姜启源.数学模型. 北京：高等教育出版社， 1987附录附录一 一个时间优化模型的多种方案（一）路线起点终点最佳路线时间（分钟）78所用费用最小时的最佳路线（一）路线起点终点最佳路线费用（元）22附录二2.1 计算同时经过给定两点的时间，费用function chec=checi(e,f)bb=load(data1.mat);load1=fieldnames(bb);bb=bb.(load11);g=1;for i=4:4:2080 for w=i-1:i for j=2:87 if bb(w,j)=e for k=j+1:87 if bb(w,k)=f c(g)=bb(i-3,1); D(g)=k-j; T(g)=D(g)*3; flag(g)=bb(i,1); fm(g)=bb(i-2); if fm(g)=1 money(g)=1; else if D(g)=20 money(g)=1; else if D(g)=40 money(g)=2; else money(g)=3; end end end g=g+1; break end end end end endend2.2 对原数据进行处理clear;clc;a=xlsread(d:Program FilesMATLABR2006aworkgjxx.xls); %导入excel数据%定义变量和变量初始化global bb;global tt=1000;%将上行和下行的数据补齐for i=1:2080 if isnan(a(i,1)=1 for j=1:86 if isnan(a(i-1,j)=1 m=j-1; break else m=86; end end k=m; for j=1:m a(i,j)=a(i-1,k); k=k-1; end endend%嵌套循环求时间矩阵for i=1:2080 if isnan(a(i,2)=1 for j=1:86 if isnan(a(i,j)=1 m=j-1; break end end for k=1:m for j=1:85-k if isnan(a(i,j+k)=1 b1(a(i,j),a(i,j+k)=3*k; end end end endend%填充矩阵for i=1:3957 for j=1:3957 if b1(i,j)=0 if i=j j=j+1; else b1(i,j)=1000; end end endendbb=int32(b1);2.3 对任意给定的两点求转车在两次以内的乘车路线时间和费用function qz=data1(e,f)bb=load(matlab0.mat);load1=fieldnames(bb);bb=bb.(load11);%所有经过起点的车k=1;for i=4:4:2080 for w=i-1:i for j=2:87 if bb(w,j)=e s(k)=bb(i-3,1); position_s(k)=j; u=k; k=k+1; break end end endend%所有经过终点的车k=1;for i=4:4:2080 for w=i-1:i for j=2:87 if bb(w,j)=f e(k)=bb(i-3,1); position_e(k)=j; v=k; k=k+1; break end end endend%同时经过起点和终点的车，即直接可到达的车k