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

1、,word ,一 完美整理版摘要：明年8月第29届奥运会将在北京举行，届时有大量观众到现场观看奥运比赛，这将对北京的交通带来 巨大的影响。本文以给出的北京地区公交路线为参考资料，根据公交网络换乘问题构建了公共交通网络模 型。对三个问题的解决方案如下：（1）针对问题1,本文首先利用 MATLAB编程将公交线路读出，求出各站点间的邻接矩阵。再根据所求 的邻接矩阵。对求得的邻接矩阵进行处理；判断起点和终点之间有没有直达的线路，如有就确定为最优线 路，没有就在通过程序寻找一个合适的数值（记为M）作为限制（即找出邻接点最多的那部分站点），找出通过次数超过这个数值的站点。下一步则寻找换乘站点。通过把求得的

2、站点与要求的起点和终点，建立循环逐个修改开始站点与最终站点 的值可求出通过各站点的路线，再将经过所求得的站点的路线与经过起点和终点的路线进行比较，寻找相 同的路线，若存在，则这个站点可以作为所给的这对起点与终点的中转站（但根据人们乘车的习惯，假设 中转的次数不超过2次）。如果的站点中无法找到中转站，则调整 M的值，直到可以找到可行的乘车路线 为止。根据得到的可行乘车线路， 利用路过分别与费用和时间的函数关系，计算出按照吸收较小转车次数的原则，比较用钱少、费时少的线路，最终得到最优的乘车方案。（2）针对问题2,将换乘地铁站和公汽站为对等的，与问题1相似，利用相同的方法求出最优线路，但是情况比问题

3、1更复杂，特别是地铁与地铁之间还可以换乘，这需要单独进行考虑。此时，站点数、费用 和时间的函数发生了变化，因此，利用新的函数表达式求解再比较得到最优线路。（3）针对问题3,考虑步行时，可先利用图论中的 Floyd算法求出任意两站点间的最短道路，并在此基础 上求出这段路步行所需要的时间。再在第二问的基础上，对时间加一个阈值To当计算出的两点间最短路的步行时间阈值T时，就选择步行，否则，选择问题2中求得的最优线路。本文所考虑的算法，可以查询任意两个站点间的乘车最优路径。关键词：MATLAB程序、公交换乘、限制求解、Floyd算法、最优线路一、问题重述北京申奥的成功，对北京市的交通系统提出了更高的要

4、求。依据国外举办奥运会的经验教训来看，奥运期间交通状况是否良好，交通管理是否高效，是关系奥运盛会能否圆满成功举办的举足轻重的条件之一。因此，必须在全面调研基础上，制定切实可行的交通规划及管理策略，为奥运会的成功保驾护航。在观众的交通行为中，轨道站点、外围停车场和专用巴士的换乘，是整个交通链的重要环节，一旦出现交通瓶颈，其向上游反馈形成的阻塞波 （或者称为交通扰动）会溯源而上并且影响加剧，最终造成主会场人员 疏散的延误和交通设施服务水平的降低以及一定程度上的混乱和连带的不可估量的经济损失、负面的社会 影响。因此应从系统全局考虑进行换乘系统规划，保证观众出行全过程的流畅。二、模型假设1、乘客到起始

5、站可以直接选择公汽或地铁班次上车，即不记在起始站的等待时间。2、在实际过程中，对于公交（包括公汽与地铁）可能要换车2次以上，用户已无法容忍，视为无法到达。（因为如果他们之间换乘就使得费用增大了很多，这是人们不愿意看到的，且一般只坐地铁是无法到达终点站的，所以还要再换乘其他的工具，换乘次数太大我们也不再将其纳入考虑的范围）。3、相邻地铁站平均行驶时间（包括停站时间）：2.5分钟。4、相邻公汽站平均行驶时间（包括停站时间）：3分钟。5、公汽换乘公汽平均耗时:6、地铁换乘地铁平均耗时:7、地铁换乘公汽平均耗时:8、公汽换乘地铁平均耗时:5分钟（其中步行时间2分钟）。4分钟（其中步行时间2分钟）。7分

6、钟（其中步行时间4分钟）。020站：1元；216分钟（其中步行时间4分钟）。9、公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价票价为: 40站：2元；40站以上：3元 10、地铁票价：3元（无论地铁线路间是否换乘）。11、已知所有站点之间的步行时间。（无需支付地铁费）12、同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘13、郊县和繁华地区公交车站的间隔大概一致。三、符号说明1、表示第一问中从起点站到终点站所用的总时间。2、表示表示第一问中从起点站到终点站经过的总站点数。3、M表示求取局部最优解的限制值。4、T表示判断是坐车还是步行的阈值，但这个值因人而易四、问题的分析文

7、献2对公交乘客的出行心理进行了研究，其结果表明，换乘次数”是大部分公交乘客在选择出行路线时首先考虑的因素，其次是出行耗时和距离长短。而出行耗费的时间与换乘的次数，及等车的时间以及距离 的长短密切相关。因此，对于出行耗时和距离长短，转化为换乘次数最少的基础上出行距离最短的问题。 对公交换乘的问题进行研究，首先就是要解决公共交通网络模型如何合理地表述；其次是公交换乘问题的解决思想。公共交通网 络不同于一般的道路交通网络，在许多书籍文献中都对公共交通网络的特点进行了阐述，如网络的连通性 不同于普通道路网，结点有其空间位置特性和一对多的属性等，并分析了弧段的特性及有向线的性质。对 于公交网络的特点不再

8、赘述。在 GIS网络分析中，公共交通网络可以映射为一个有向图。根据公共交通网 络的特点，把公交网络模型映射为，其中， G为有向赋权图；V表示网络上所有结点即公交站点的集合， 一个公交站点可能是多条公交线路的上下客站点；表示网络边（连接公交线路上两个公交站点之间的弧段）的集合，若A站点与B站点是n条线路的相邻上下客站点，那么 A与B之间至多有2n条连接边：R表示 网络上连接起始点和目标点间所有结点的公交线路的集合；是结点的非负权值；是边的非负权值4。最优出行路径就是指乘客从起始点到目标点所选择的一系列连通结点组成的距离最短的路段及最少换乘的公交 线路的集合。3在GIS中道路网络的基本框架是 结点

9、一弧段”模型。但对于弧段包含的属性是一对多的关系、弧段使用线型系统而不是二维坐标确定点的位置、弧段中的属性需要分段处理等情况，这种模型显得无能为力。这里将交通网络模型采用 结点一弧段（可有多条弧段）一有向线”的数据结构（如图1）来存储网络图。按照公 共汽车线路选择所经过的站点一路线一站点”形成路径分析中的有向线。所以以分支多的站点作为求解换乘站点的突破点。由对与各站点邻接的站点的个数的统计，如图2所示（其中14表示的是含有邻接点个数为 16的情况），可以断定邻接点个数较小的站点的比列较大，在大部分站点处换乘机会存在的可能性很小，所以我们并没有必要多所有的站点进行搜索，找寻换乘点；而只需在含有邻

10、接点个数较大的站点中找寻，从而产生了限 制性的搜索方法。五、模型的建立5.1 只考虑公汽的情形：由于公交车站的间隔大概在 1000m左右（郊县和繁华地区可能略有差别，所以忽略这种差别），因此在换 乘次数尽量最少的原则之下，以从出发地点到达目的地点的总乘车站数为基准，找出换乘车前后总乘车站 数为最少的作为系统的推荐线路，这样即符合常规，也可能是最优线路2。对于任意的起点和终点，可能存在以下四种情况：（1）、起点与终点在同一线路上，不需要换车（即存在直达路线）；（2）、起点与终点不在同一线路上，需要换车1次；（3）、起点与终点不在同一线路上，需要换车2次；（4）、起点与终点不在同一线路上，需要换车

11、次数大于2次，视为通过换车无法达到（见模型假设2）为尽量满足使换乘次数达到最少，首先利用递归的方式，判断起点和终点之间是否有直达路线，如有就比较其用时与费用，选择花费时间与金钱都最少的路线作为最优路线；否则，就确定 M的值，选择含有邻接 站点个数大于M的那些站点进行考虑（即采取限制求解的方法），在他们中间寻找换乘站点，而不是对所 有的路线进行考虑。具体方法是：把求得的站点与要求的起点和终点，利用附录：（三），建立循环逐个修改begin_s与end_s的值可求出通过各站点的路线，再将经过所求得的站点的路线与经过起点和终点的路线进行比较， 寻找相同的路线，若存在，则这个站点可以作为所给的这对起点与

12、终点的中转站（但根据人们乘车的习惯，假设中转的次数不超过 2次。如果求得的站点中无法找到中转站，就调整M的值，依上面的步骤继续进行，直到可以找到可行的乘车路线为止。根据得到的可行乘车线路，利用路过分别与费用和时间的函数关系， 计算出按照吸较小转车次数的原则, 比较用钱少、费时少的线路，最终得到最优的乘车方案。如所走线路与时间的函数关系为：5.1同时考虑公汽与地铁线路的情形：因为公汽与地铁之间可以换乘，所以当同时考虑公汽与地铁线路时，可以将可换乘的地铁站和公汽站 视为对等的，这样就与第一小问相同了，可利用相同的方法来解决。虽然仍只是先求出可行线路，但情况 要更复杂了，特别是地铁与地铁之间的换乘，

13、这还需要单独进行考虑。此外，此时站数分别与费用和时间 的函数却发生了变化，需利用新的函数表达式求解再比较得到最优线路。新的站数与时间的函数如下：设n表示走地铁所经过的站数其中：a式表示从起点经过地铁直达终点所费时间；b式表示从起点经过公交和地铁到达终点所费时间；c式表示从起点经过公交和地铁，再经过公交到达终点所费时间。由条件可知，T1是上行，下行站完全相同的一条地铁，而 T2是一条环路，且他们之间在 D12站点可以 相互换乘，即是说两条地铁的结构图可能为螃蟹型。5.3、当已知所有站点之间的步行时间时的情形：可先利用图论中的Floyd算法1求出任意两站点间的最短道路，并在此基础上求出这段路步行所

14、需要 的时间。再在第二问的基础上，对时间加一个阈值To、当计算出的两点间最短路的步行时间阈值T时，就选择步行，走得到的最短道路；、当计算出的两点间最短路的步行时间阈值T时，就选择第二问中求得的最优线路。六、模型的求解6.1、 只考虑公汽的情形求解结果得：针对问题1 ,运用本文所述算法，求得 6条线路的乘车公交线路如下：(1)、S335AS1828换乘一次起点站 班次 中转站 班次 终点站 时间 总费用S3359 L436 S2606L217 S18281303S3359 L436S1784 L167S1828 1013(其中粗线条的行表示求得的最优公汽线路)(2)、S155*S0481换乘两次

15、起点站班次中转站一班次中转站二班次终点站时间总费用S1557L84S0028 L348S2361 L312S04811574S1557L84S0055 L348S2361L312S04811603S1557L84 S0978L206S1511L460S04811624S1557L84S0978 L212S3409L460S04811333S1557L84S1919 L189S3186L460S04811063S1557L84S1921L279S0618L72S04811694S1557L84S1921L279S0327L72S04811603S1557L84S1921L80S0618L72S0

16、4811694S1557L84S1921L58S3878L239S04811964S1557L84S1921L58S3878L514S04811934S1557L84S1921L80S1327L72S04811603S1557L84S1919L80S0618L72S04811604S1557L84S1919L80S1327L72S04811513(3)、S097CS0485换乘一次起点站 班次 中转站 班次 终点站 时间 总费用S0971 L13S0992 L417S0485 1313(4)、S0008S0073换乘一次起点站班次中转站班次终点站时间总费用S0008L159S3919L103S

17、00731493S0008L198S1383L282S00731133S0008L198S3766L282S00731133S0008L355S2302L57S0073862S0008L463S1383L282S00731133S0008L463S2083L170S0073922S0008L463S2084L170S0073922(5)、S0148S0485换乘两次起点站班次中转站一 班次中转站二班次终点站时间总费用S0148L308S0128L276S1671L395S04-852326(6)、S008*S3676换乘一次起点站 班次 中转站 班次 终点站 时间 总费用S0087L454S3

18、496L209S367610026.2、 同时考虑地铁的情形求解结果得：对于问题（1）、（ 2）、（ 3）、（ 4）,加入地铁后的所有线路，由于需要换乘的次数较多，超过了人们可以承受的换乘次数，且如果采纳这样的路线行使，会使金钱上的花费巨大，所以不采用这类方案，而直接采用一种交通工具即公汽。那么在这种情形下，问题（1）、（ 2）、（ 3）、（4）的最优路线并没有改变，即上面表格统计的结果。针对问题2,与问题1相比，其中的第（5）和（6）的乘车线路有变化：（5）、S014AS0485公汽地铁公汽起点站班次中转站一中转站二班次中转站三中转站四班次终点站时间总费用S0148L24S1487D2T1D

19、21S0464L469S048587.55(6)、S008*S3676坐地铁 T2 直达起点站中转站班次中转站终点站时间总费用S0087D27T2D36S36762936.3、 当已知所有站点之间的步行时间时的情形：1、可先利用图论中的Floyd算法1求出任意两站点间的最短道路，并在此基础上求出这段路步行所需要的时间。2、再在第二问的基础上，对时间加一个阈值 To、当计算出的两点间最短路的步行时间阈值T时，就选择步行，走得到的最短道路；、当计算出的两点间最短路的步行时间阈值T时，就选择第二问中求得的最优线路。七、模型的评价一方面，因为我们采取的措施是限制求解，所以求得的结果不一定是全局最优解。

20、但所得结果一定是 局部最优解，且具有较强的适用性，可以缓解计算机因为数据过多而无法运行或死机等问题。除此以外他 还可以节约计算机运行的时间。另一方面，即使说求出来的是全局最优解， 那也只是限于对题目中所给的数据而已，在实际生活中，往往还有许多影响人们行使路线的因素，且每个人对金钱和时间的考虑都不同，所以这也只对大部分人适用。再者，虽然我们得到的是局部最优解，但事实上在很多时候是不需要采取全局最优解的方案的。原因是如果这个地区的人都采取这样的方案来实施，那么就会使资源分配不均，造成很多新的现象(如堵车等)来影响这个措施的实施过程，使其答不到他预期的效果，而相反的，局部最优解相对而言在资源的配置方

21、面就更具有可实施性。八、模型的改进方向显然这个模型如上面所提到的，还有一些不足之处，如对不同人群的实用性的解决，我建议可以设定两 个参数：在人们心目中金钱与时间所占的比重。即利用层次分析法的原理，在模型的最后一步，确定最优解时，可根据人们自己的需求来选择。使其基本满足每个人的需求，消除个体差异性对模型结果实用性的影响。参考文献：1赵静，但琦，数学建模与数学实验，北京：高等教育出版社，2000.2城市规划学刊，北京奥运交通组织规划初探，/topic/olympic/research/200708/1949_2.html , 200苏爱华，施

22、法中，公交网络换乘问题的实现，工程图学学报，2005年第4期：55, 59, 2004.4翁敏，公交线路网络分析的若干关键技术研究D,武汉：武汉测绘科技大学，2000.附录(一)、求解各个站点间的邻接矩阵：%function y=sxjm_cs_line_1111(x)clear all%产生上行和下行的两个520 *200的矩阵，行号表示线路号，列号表示线路的每个站点，一条线路从第一列开始放置，后面不足的为0。up_line=zeros(520,200);% 保存上行线down_line=zeros(520,200);%保存下行线%读线路文件，fid=fopen(D:MATLAB6P5wor

23、k11line.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;endcol=2;while down_line(i,col)0% 将下行线中的线路输入邻接矩阵relation_matrix(down_line(i,col-1),down_line(i,col)=relati

24、on_matrix(down_line(i,col-1),down_line(i, col)+1；col=col+1;endend(二)、对3957 *3957的邻接矩阵进行处理，用下面标记的红色数值作为限制，找出通过次数超过其的 站点：max_station=3957;re=zeros(1,3957);for i=1:3957t=1;for j=1:3957if relation_matrix(i,j)0t=t+1;endendre(1,i)=t;endmax=1;t=1;for i=1:3957if re(1,i)9it=t+1;endendtmax;re_dec=zeros(3957,m

25、ax);%max=16for i=1:3957tt=1;for j=1:3957k=relation_matrix(i,j);if k0re_dec(i,tt)=j;tt=tt+1;endendend(三)、把求得的站点和要求的起点和终点，利用下面的程序诿个修改标记部分，可求出通过各站点的路 线，再将经过所求得的站点的路线与经过起点和终点的路线进行比较，寻找相同的路线，若存在，则这个 站点可以作为所给的这对起点与终点的中转站。从而就找到了这条线路可能的乘车路线。clear all%产生上行和下行的两个520 * 100的矩阵，行号表示线路号，列号表示线路的每个站点，一条线路从第一列开始放置，后

26、面不足的为 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

27、(1,i);endtt=1;for i=m:-1:1%保存第四行，原路返回”中的下行线。down_line(line_num,tt)=B(1,i);tt=tt+1;endA=fgetl(fid);%读第四行：下行线路，为空行，是第三行的反过程。else%保存上下行线”和环线”m,n=size(A);BB=A(1,7:n);B=str2num(BB);m,n=size(B);for i=1:mup_line(line_num,i)=B(1,i);% 保存第三行，包括环线和上下行线”中的上行线。endA=fgetl(fid);%读第四行：如为 环线”，则第四行为空。此时，下面的if语句不执行。如为 上下行线则执行。if size(A)%第四行：下行线信息，以 下行：”开头，之后为站点信息。m,n=size(A);B=s