2007年大学生数学建模B题优秀论文 公共交通网络模型.doc

摘 要： 明年8月第29届奥运会将在北京举行，届时有大量观众到现场观看奥运比赛，这将对北京的交通带来巨大的影响。本文以给出的北京地区公交路线为参考资料，根据公交网络换乘问题构建了公共交通网络模型。对三个问题的解决方案如下：（1）针对问题1，本文首先利用MATLAB编程将公交线路读出，求出各站点间的邻接矩阵。再根据所求的邻接矩阵。对求得的邻接矩阵进行处理；判断起点和终点之间有没有直达的线路，如有就确定为最优线路，没有就在通过程序寻找一个合适的数值（记为M）作为限制（即找出邻接点最多的那部分站点），找出通过次数超过这个数值的站点。下一步则寻找换乘站点。通过把求得的站点与要求的起点和终点，建立循环逐个修改开始站点与最终站点的值可求出通过各站点的路线，再将经过所求得的站点的路线与经过起点和终点的路线进行比较，寻找相同的路线，若存在，则这个站点可以作为所给的这对起点与终点的中转站（但根据人们乘车的习惯，假设中转的次数不超过2次）。如果的站点中无法找到中转站，则调整M的值，直到可以找到可行的乘车路线为止。根据得到的可行乘车线路，利用路过分别与费用和时间的函数关系，计算出按照吸收较小转车次数的原则，比较用钱少、费时少的线路，最终得到最优的乘车方案。（2）针对问题2，将换乘地铁站和公汽站视为对等的，与问题1相似，利用相同的方法求出最优线路，但是情况比问题1更复杂，特别是地铁与地铁之间还可以换乘，这需要单独进行考虑。此时，站点数、费用和时间的函数发生了变化，因此，利用新的函数表达式求解再比较得到最优线路。（3）针对问题3，考虑步行时，可先利用图论中的Floyd算法求出任意两站点间的最短道路，并在此基础上求出这段路步行所需要的时间。再在第二问的基础上，对时间加一个阈值T。当计算出的两点间最短路的步行时间阈值T时，就选择步行，否则，选择问题2中求得的最优线路。本文所考虑的算法，可以查询任意两个站点间的乘车最优路径。关键词：MATLAB程序、公交换乘、限制求解、Floyd算法、最优线路一、问题重述 北京申奥的成功，对北京市的交通系统提出了更高的要求。依据国外举办奥运会的经验教训来看，奥运期间交通状况是否良好，交通管理是否高效，是关系奥运盛会能否圆满成功举办的举足轻重的条件之一。因此，必须在全面调研基础上，制定切实可行的交通规划及管理策略，为奥运会的成功保驾护航。在观众的交通行为中，轨道站点、外围停车场和专用巴士的换乘，是整个交通链的重要环节，一旦出现交通瓶颈，其向上游反馈形成的阻塞波(或者称为交通扰动)会溯源而上并且影响加剧，最终造成主会场人员疏散的延误和交通设施服务水平的降低以及一定程度上的混乱和连带的不可估量的经济损失、负面的社会影响。因此应从系统全局考虑进行换乘系统规划，保证观众出行全过程的流畅。二、模型假设1、乘客到起始站可以直接选择公汽或地铁班次上车，即不记在起始站的等待时间。2、在实际过程中，对于公交（包括公汽与地铁）可能要换车2次以上，用户已无法容忍，视为无法到达。（因为如果他们之间换乘就使得费用增大了很多，这是人们不愿意看到的，且一般只坐地铁是无法到达终点站的，所以还要再换乘其他的工具，换乘次数太大我们也不再将其纳入考虑的范围）。3、相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟。4、相邻公汽站平均行驶时间(包括停站时间)： 3分钟。5、公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)。6、地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)。7、地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)。8、公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)。9、公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价票价为：020站：1元；2140站：2元；40站以上：3元。10、地铁票价：3元（无论地铁线路间是否换乘）。11、已知所有站点之间的步行时间。12、同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)。13、郊县和繁华地区公交车站的间隔大概一致。三、符号说明1、 表示第一问中从起点站到终点站所用的总时间。2、 表示表示第一问中从起点站到终点站经过的总站点数。3、M表示求取局部最优解的限制值。4、T表示判断是坐车还是步行的阈值，但这个值因人而易。四、问题的分析文献2对公交乘客的出行心理进行了研究，其结果表明，“换乘次数”是大部分公交乘客在选择出行路线时首先考虑的因素，其次是出行耗时和距离长短。而出行耗费的时间与换乘的次数，及等车的时间以及距离的长短密切相关。因此，对于出行耗时和距离长短，转化为换乘次数最少的基础上出行距离最短的问题。对公交换乘的问题进行研究，首先就是要解决公共交通网络模型如何合理地表述；其次是公交换乘问题的解决思想。公共交通网络不同于一般的道路交通网络，在许多书籍文献中都对公共交通网络的特点进行了阐述，如网络的连通性不同于普通道路网，结点有其空间位置特性和一对多的属性等，并分析了弧段的特性及有向线的性质。对于公交网络的特点不再赘述。在GIS网络分析中，公共交通网络可以映射为一个有向图。根据公共交通网络的特点，把公交网络模型映射为，其中，G为有向赋权图；V表示网络上所有结点即公交站点的集合，一个公交站点可能是多条公交线路的上下客站点；表示网络边(连接公交线路上两个公交站点之间的弧段)的集合，若A站点与B站点是n条线路的相邻上下客站点，那么A与B之间至多有2n条连接边：R表示网络上连接起始点和目标点间所有结点的公交线路的集合； 是结点的非负权值；是边的非负权值4。最优出行路径就是指乘客从起始点到目标点所选择的一系列连通结点组成的距离最短的路段及最少换乘的公交线路的集合。3 在GIS中道路网络的基本框架是“结点一弧段”模型。但对于弧段包含的属性是一对多的关系、弧段使用线型系统而不是二维坐标确定点的位置、弧段中的属性需要分段处理等情况，这种模型显得无能为力。这里将交通网络模型采用“结点一弧段(可有多条弧段)一有向线”的数据结构（如图1）来存储网络图。按照公共汽车线路选择所经过的“站点一路线一站点”形成路径分析中的有向线。所以以分支多的站点作为求解换乘站点的突破点。 由对与各站点邻接的站点的个数的统计，如图2所示（其中14表示的是含有邻接点个数为16的情况），可以断定邻接点个数较小的站点的比列较大，在大部分站点处换乘机会存在的可能性很小，所以我们并没有必要多所有的站点进行搜索，找寻换乘点；而只需在含有邻接点个数较大的站点中找寻，从而产生了限制性的搜索方法。五、模型的建立5.1只考虑公汽的情形：由于公交车站的间隔大概在1000m左右（郊县和繁华地区可能略有差别，所以忽略这种差别），因此在换乘次数尽量最少的原则之下，以从出发地点到达目的地点的总乘车站数为基准，找出换乘车前后总乘车站数为最少的作为系统的推荐线路，这样即符合常规，也可能是最优线路2。对于任意的起点和终点，可能存在以下四种情况：（1）、起点与终点在同一线路上，不需要换车（即存在直达路线）；（2）、起点与终点不在同一线路上，需要换车1次；（3）、起点与终点不在同一线路上，需要换车2次；（4）、起点与终点不在同一线路上，需要换车次数大于2次，视为通过换车无法达到（见模型假设2）。为尽量满足使换乘次数达到最少，首先利用递归的方式，判断起点和终点之间是否有直达路线，如有就比较其用时与费用，选择花费时间与金钱都最少的路线作为最优路线；否则，就确定M的值，选择含有邻接站点个数大于M的那些站点进行考虑（即采取限制求解的方法），在他们中间寻找换乘站点，而不是对所有的路线进行考虑。 具体方法是：把求得的站点与要求的起点和终点，利用附录：（三），建立循环诼个修改begin_s与end_s的值可求出通过各站点的路线，再将经过所求得的站点的路线与经过起点和终点的路线进行比较，寻找相同的路线，若存在，则这个站点可以作为所给的这对起点与终点的中转站（但根据人们乘车的习惯，假设中转的次数不超过2次。如果求得的站点中无法找到中转站，就调整M的值，依上面的步骤继续进行，直到可以找到可行的乘车路线为止。 根据得到的可行乘车线路，利用路过分别与费用和时间的函数关系，计算出按照吸较小转车次数的原则，比较用钱少、费时少的线路，最终得到最优的乘车方案。如所走线路与时间的函数关系为：5.1同时考虑公汽与地铁线路的情形： 因为公汽与地铁之间可以换乘，所以当同时考虑公汽与地铁线路时，可以将可换乘的地铁站和公汽站视为对等的，这样就与第一小问相同了，可利用相同的方法来解决。虽然仍只是先求出可行线路，但情况要更复杂了，特别是地铁与地铁之间的换乘，这还需要单独进行考虑。此外，此时站数分别与费用和时间的函数却发生了变化，需利用新的函数表达式求解再比较得到最优线路。新的站数与时间的函数如下：设n表示走地铁所经过的站数其中：a式表示从起点经过地铁直达终点所费时间；b式表示从起点经过公交和地铁到达终点所费时间；c式表示从起点经过公交和地铁，再经过公交到达终点所费时间。由条件可知， T1是上行，下行站完全相同的一条地铁，而T2是一条环路，且他们之间在D12站点可以相互换乘，即是说两条地铁的结构图可能为螃蟹型。5.3、当已知所有站点之间的步行时间时的情形： 可先利用图论中的Floyd算法1求出任意两站点间的最短道路，并在此基础上求出这段路步行所需要的时间。再在第二问的基础上，对时间加一个阈值T。、当计算出的两点间最短路的步行时间阈值T时，就选择第二问中求得的最优线路。六、模型的求解 6.1、只考虑公汽的情形求解结果得：针对问题1，运用本文所述算法，求得6条线路的乘车公交线路如下：（1）、S3359S1828 换乘一次起点站班次中转站班次终点站时间总费用S3359L436S2606L217S18281303S3359L436S1784L167S18281013（其中粗线条的行表示求得的最优公汽线路）（2）、S1557S0481 换乘两次起点站班次中转站一班次中转站二班次终点站时间总费用S1557L84S0028L348S2361L312S04811574S1557L84S0055L348S2361L312S04811603S1557L84S0978L206S1511L460S04811624S1557L84S0978L212S3409L460S04811333S1557L84S1919L189S3186L460S04811063S1557L84S1921L279S0618L72S04811694S1557L84S1921L279S0327L72S04811603S1557L84S1921L80S0618L72S04811694S1557L84S1921L58S3878L239S04811964S1557L84S1921L58S3878L514S04811934S1557L84S1921L80S1327L72S04811603S1557L84S1919L80S0618L72S04811604S1557L84S1919L80S1327L72S04811513（3）、S0971S0485 换乘一次起点站班次中转站班次终点站时间总费用S0971L13S0992L417S04851313（4）、S0008S0073 换乘一次起点站班次中转站班次终点站时间总费用S0008L159S3919L103S00731493S0008L198S1383L282S00731133S0008L198S3766L282S00731133S0008L355S2302L57S0073862S0008L463S1383L282S00731133S0008L463S2083L170S0073922S0008L463S2084L170S0073922（5）、S0148S0485 换乘两次起点站班次中转站一班次中转站二班次终点站时间总费用S0148L308S0128L276S1671L395S04-852326（6）、S0087S3676 换乘一次起点站班次中转站班次终点站时间总费用S0087L454S3496L209S367610026.2 、同时考虑地铁的情形求解结果得：对于问题（1）、（2）、（3）、（4），加入地铁后的所有线路，由于需要换乘的次数较多，超过了人们可以承受的换乘次数，且如果采纳这样的路线行使，会使金钱上的花费巨大，所以不采用这类方案，而直接采用一种交通工具即公汽。那么在这种情形下，问题（1）、（2）、（3）、（4）的最优路线并没有改变，即上面表格统计的结果。针对问题2，与问题1相比，其中的第（5）和（6）的乘车线路有变化：（5）、S0148S0485 公汽地铁公汽起点站班次中转站一中转站二班次中转站三中转站四班次终点站时间总费用S0148L24S1487D2T1D21S0464L469S048587.55（6）、S0087S3676 坐地铁T2直达起点站中转站班次中转站终点站时间总费用S0087D27T2D36S36762936.3 、当已知所有站点之间的步行时间时的情形：1、可先利用图论中的Floyd算法1求出任意两站点间的最短道路，并在此基础上求出这段路步行所需要的时间。2、再在第二问的基础上，对时间加一个阈值T。、当计算出的两点间最短路的步行时间阈值T时，就选择第二问中求得的最优线路。七、模型的评价 一方面，因为我们采取的措施是限制求解，所以求得的结果不一定是全局最优解。但所得结果一定是局部最优解，且具有较强的适用性，可以缓解计算机因为数据过多而无法运行或死机等问题。除此以外他还可以节约计算机运行的时间。 另一方面，即使说求出来的是全局最优解，那也只是限于对题目中所给的数据而已，在实际生活中，往往还有许多影响人们行使路线的因素，且每个人对金钱和时间的考虑都不同，所以这也只对大部分人适用。 再者，虽然我们得到的是局部最优解，但事实上在很多时候是不需要采取全局最优解的方案的。原因是如果这个地区的人都采取这样的方案来实施，那么就会使资源分配不均，造成很多新的现象（如堵车等）来影响这个措施的实施过程，使其答不到他预期的效果，而相反的，局部最优解相对而言在资源的配置方面就更具有可实施性。八、模型的改进方向 显然这个模型如上面所提到的，还有一些不足之处，如对不同人群的实用性的解决，我建议可以设定两个参数：在人们心目中金钱与时间所占的比重。即利用层次分析法的原理，在模型的最后一步，确定最优解时，可根据人们自己的需求来选择。使其基本满足每个人的需求，消除个体差异性对模型结果实用性的影响。参考文献：1 赵静，但琦，数学建模与数学实验，北京：高等教育出版社，2000.2 城市规划学刊，北京奥运交通组织规划初探，/topic /olympic/research/200708/1949_2.html，200 苏爱华，施法中，公交网络换乘问题的实现，工程图学学报，2005年第4期：55，59，2004.4 翁敏，公交线路网络分析的若干关键技术研究D，武汉：武汉测绘科技大学，2000.附 录（一）、求解各个站点间的邻接矩阵：%function y=sxjm_cs_line_1111(x)clear all%产生上行和下行的两个520200的矩阵，行号表示线路号，列号表示线路的每个站点，一条线路从第一列开始放置，后面不足的为0。up_line=zeros(520,200);%保存上行线down_line=zeros(520,200);%保存下行线%读线路文件，fid=fopen(D:MATLAB6p5work11line.txt,r);%执行时，修改其中的路径为所读取的文件line_num=1;while line_num=0 & A(1,1)0%将上行线中的线路输入邻接矩阵 relation_matrix(up_line(i,col-1),up_line(i,col)=relation_matrix(up_line(i,col-1),up_line(i,col)+1; col=col+1; end col=2; while down_line(i,col)0%将下行线中的线路输入邻接矩阵 relation_matrix(down_line(i,col-1),down_line(i,col)=relation_matrix(down_line(i,col-1),down_line(i,col)+1; col=col+1; endend（二）、对39573957的邻接矩阵进行处理，用下面标记的红色数值作为限制，找出通过次数超过其的站点：max_station=3957;re=zeros(1,3957);for i=1:3957 t=1; for j=1:3957 if relation_matrix(i,j)0 t=t+1; end end re(1,i)=t;endmax=1;t=1;for i=1:3957 if re(1,i)9 i t=t+1; endendtmax;re_dec=zeros(3957,max);%max=16for i=1:3957 tt=1; for j=1:3957 k=relation_matrix(i,j); if k0 re_dec(i,tt)=j; tt=tt+1; end endend（三）、把求得的站点和要求的起点和终点，利用下面的程序诼个修改标记部分，可求出通过各站点的路线，再将经过所求得的站点的路线与经过起点和终点的路线进行比较，寻找相同的路线，若存在，则这个站点可以作为所给的这对起点与终点的中转站。从而就找到了这条线路可能的乘车路线。clear all%产生上行和下行的两个520100的矩阵，行号表示线路号，列号表示线路的每个站点，一条线路从第一列开始放置，后面不足的为0。up_line=zeros(520,100);%保存上行线down_line=zeros(520,100);%保存下行线%读线路文件，fid=fopen(C:MATLAB6p5work11line.txt,r);%执行时，修改其中的路径为所读取的文件line_num=1;while line_num=0 & A(1,1)=9 %下行线是“上行线原路返回”（站点名完全相同），则第四行为空，仅有第三行有数据，且直接以始发站编号开头。 B=str2num(A); m,n=size(B); for i=1:m%保存第三行，“原路返回”中的上行线。 up_line(line_num,i)=B(1,i); end tt=1; for i=m:-1:1%保存第四行，“原路返回”中的下行线。 down_line(line_num,tt)=B(1,i); tt=tt+1; end A=fgetl(fid);%读第四行：下行线路，为空行，是第三行的反过程。 else %保存“上下行线”和“环线” m,n=size(A); BB=A(1,7:n); B=str2num(BB); m,n=size(B); for i=1:m up_line(line_num,i)=B(1,i);%保存第三行，包括“环线”和“上下行线”中的上行线。 end A=fgetl(fid);%读第四行：如为“环线”，则第四行为空。此时，下面的if语句不执行。如为“上下行线”则执行。 if size(A)%第四行：下行线信息，以“下行：”开头，之后为站点信息。 m,n=size(A); B=str2num(A(1,7:n)