南京邮电大学专业实践报告

理学院专业实践报告题目：南京市公交转车优化问题专业学生姓名班级学号指导教师实习单位日期2013-3-7

问题描述问题3对准备建设的其它地铁，相关部门的计划线路是否合理，你认为应该如何设置？问题分析地铁规划的合理性研究问题实为在节约建设成本、让居民出行的便利最大化、覆盖市区面积最广的基础上，选择出理想的地铁站点和地铁线路。其核心在将地铁规划这一大问题逐步转化为在考虑交通客流量，对城区现有的发展和将来的规划不会造成影响的因素下，选择理想的地铁站点和地铁线路。为了使复杂问题简单化，我们可以从“点-线-面”这个概念出发层层深入考虑地铁的合理规划。首先，在衡量地铁规划合理与否时，我们考虑交通客流量这一关键因素，因为建设地铁的最终目标就是为了舒缓客流量，方便居民的出行。我们可以通过RP和SP调查问卷的形式，采集南京地铁一号线路附近的交通现状数据、调查了人们对地铁的看法。并在这些数据的基础上根据四阶段法思想对交通客流量进行预测，聚类分析法预测该交通小区的生成及吸引的交通量，用重力模型法预测了该交通小区交通量的分布。从而使建立的模型具有高适用性，以给以后的问题提供较准确的数据支持。接着，从“点”出发，考虑各种因素对一个地铁站点的选择的影响，其中包括站点建设成本、带动区域的经济效益、站址周边环境、施工风险、区域产业布局、舒缓客流度等关键因素，根据这些因素，建立方案评价指标体系。通过层次分析法和熵权法的结合，得到综合权重，最后得到对该站点的总的评价，从而建立起地铁站点选址的模型。然后，我们从“线”的角度出发，为了求出地起始站点与目的地站点间的最佳路径，将地铁站点抽象为节点，将地铁线路抽象为连接线路各站点的有向边，构造一地铁网络有向图，用边上的权值反应影响地铁线路选择的关键因素，从而将求解最佳路径问题转化为求解图中起始节点与目的地节点间的最优路径的问题，建立基于点搜索的多目标优化模型，运用Dijkstra算法筛点求解。最后，我们进行“面”的分析。首先从各方面分析主城区交通需求，然后经过“面”、“点”、“线”的层次分析，通过宏观层次的定性论证，用面点线多模块网络层次分析法规划了五个快速轨道交通线网预选方案，画出各预选方案的规划图。建模分析地铁站点评价指标的建立根据对于地铁站点综合评价的决定因素的调查情况，我们从中选取了一级评价指标3个，二级评价指标8个，具体的评价指标如下表：表1南京地铁站点评价指标一级指标二级指标经济性B1站点建设成本C1带动的经济效益C2环境性B2站址周边环境C3区域产业布局C4环境保护度C5施工风险（地质、地下管道）C6便利性B3舒缓该区客流度C7提高出行时间效率C8对于交通有关数据的调查，由于现状各种交通方式之间的属性关系已经确定，因此RP调查方法处理现状交通问题，即主要用于对现状交通问题的反映与诊断上；而作为一种新型交通方式的轨道交通（地铁）加入到交通网络里，这种方案是未来式，轨道交通属性也是待定的，而SP方法可以自由设计属性、水平值，可以将各属性的效果分开来处理当前不存在的方案，因此SP调查方法和数据处理可以用在对未来交通问题的预测上。综合地铁网络的特点，同时参考地铁乘客出行心理的调查，考虑方便、舒适程度等影响地铁出行的重要因素，以及地铁建设的成本花费，可得地铁规划中建立最佳线路的方法是：1)先确定地铁线的起点和终点。2）从地铁中途要经过的各特定的区域中选出几个地铁备选站点；（选取方法由模型6.2具体给出）2)要求在各个特定区域的地铁备选站点中分别确定出最后的地铁站点，使最后连接各个地铁站点的总线路能够最短。3)地铁的总线路最短，既能够使地铁建设的成本尽量缩短，又能够使乘客到达目的地的时间最短。图1地铁线路选取简化图由图1，假设地铁途径的区域为A，B，C，D四个区，每个区域中已经各自选出了若干个地铁备选站点。不同相邻区域中的地铁备选站点分别进行连线，每条连线上根据实际路径的长度，标上数值，显示其两个站点间的距离，最后对各种连线进行比较，求出最短路线。最后选出的地铁备选站点即为该区域确定的地铁站点。(要求在各个区域中必须只能选取一个地铁备选站点作为地铁站点进行连线)（2）地铁网络的数学描述地铁网络是由地铁线路及地铁站点组合而成，它包括出行区域、线路和地铁站点。首先将地铁网络抽象成一个图．图的顶点表示站点，图的边表示连接相邻站点的线路。当选择出行起点到出行终的一条通路时，则依次从起点开始寻找相邻站点，通过边将经过的站点连接起来点，构成起点与终点的一条路线。为了方便路线集合、图以及换乘矩阵、线路矩阵的表示，设该地铁网络共N个地铁站点（每个区域中选取一个），S为所有地铁备选站点集合，。（3）模型的分析与建立1）．图论基本概念图的定义：有序三元组称为一个图，其中：(1)是有穷非空集，称为顶点集，其元素叫做图的顶点；(2)E称为边集，其元素叫做图的边；(3)是从边集E到顶点集V的有序或者无序对集合的影射，称为关联函数。图的分类：在图G中，与V中的有序偶对应的边称为图的有向边(或弧)，而与V中顶点的无序偶对应的边称为图形的无向边，每一条边都是无向边的图，叫做无向图，记为G=(V，E)；每一条边都是有向边的图叫做有向图，记为D=(V，E)；既有无向边又有有向边的图叫做混合图。该铁路线问题中讨论的是无向图。权：如果图G中任意一条边上都附有一个数，则称这样的图G为赋权图，称为边上的权。2）．最短路径问题综合分析最短路径问题是图论中的一个基本问题。在赋权图中，每条边都有一个数值(长度、成本、时间等)，找出两节点之间总权和最小的路径就是最短路径问题。最短路径问题，通常归属为三类：(1)单源最短路径问题：包括确定起点的最短路径问题和确定终点的最短路径问题。(2)确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。(3)全局最短路径问题：求图中所有的最短路径。该问题研究的是全局最短路径问题。用Dijkstra算法来求解最短铁路路径。当所有的权数≥0时，Dijkstra算法是目前公认的最好的算法。其基本思想是从起点出发，逐步向外发展。探索过程中，每到一个点，都记录下路径与路程，称为这个点的标号。故Dijkstra算法也称为标号法。具体标号由两部分构成，第一部分是一个字母，表示前面的一个点的符号，说明从哪里来；第二部分是一个数字，表示从起点到目前位置的距离，说明有多远。标号被分成临时标号和永久标号两种。前者是可以修改的，后者是不变的。开始的时候，所有的标号都是临时标号，每一次算法循环，将其中的某一个临时标号改变为永久标号。因此，最多经过n-1次，可以求出从起点到终点的最短路径和路程。Dijkstra的算法步骤为：设起点为。，终点为，(1)起点标号(--，0)，邻点标号(，)，其他标号。令V=V一。(2)如果V=，终止算法。(3)选择∈V，具有最小标号。如果，终止算法；否则，将的标号改成永久标号，令。。(4)检查的邻点，如果，则给标号，并返回步骤(2)。要寻找地铁网络中任意两点（起点和终点）间的最佳路线，且要能经过各个指定的区域。其核心是线路选择的模型与算法，包括起始站到终点站之间的最佳路线，及换乘地点，乘车所用的时间，地铁建设费用等。线路矩阵A的提取根据电子科技大学第十一届大学生数学建模竞赛题所给的7条地铁线路和现已确定的36个地铁站点，设该地铁网络共可以构成条线路，为所有地铁线路集合，，运用Excel，Word，Access软件对每条线路，依次将线路上的站点号提取出来，按照线路的标号构成行下标，而第行的元素则是经过线路的所有站点。这样就构成含有线路号和每一条线路上的所有站点的链路矩阵A，A(i，：)表示第i号公交线经过的所有有序站点。问题解决及总结我们对地铁一号线站点的选择做重点研究图3南京地铁规划图图4南京地铁规划图图5一号线线路依据1号线现有的27个站点：高力家具港·迈皋桥、红山动物园、南京站、新模范马路、南京国际广场·玄武门、农业银行·鼓楼、珠江路、德基广场·新街口、张府园、三山街、中华门、时光澔韵·安德门、天隆寺、软件大道、花神庙、南京南站、双龙大道、河定桥、胜太路、1912·百家湖、台湾广场·小龙湾站、竹山路、天印大道、龙眠大道、南医大·江苏经贸学院站、江苏海院·南京交院、中国药科大学对各站点进行区域划分，每个站点分别在各自不同的区域。一共划分成27个区域。先对27个区域做简化，考虑其中的三个区域的路线选择方案。图6-3-3地铁站点选择抽象图图6-3-4中A，B，C分别为划分的27个区域中相邻的三个，A1，A2，A3，A4，A5为A区中的地铁备选站点（这些地铁备选站点的选取方法由模型6-2给出），同理B1,B2,B3,B4,B5为B区中的地铁备选站点，C1,C2,C3,C4,C5为C区中的地铁备选站点。三个区中各点分别和相邻的区域中各点进行连线（连线方式由图6-3-4给出）。三个区域中总共的路径数：=5×5×5=125再分别对每条路径求长度：以A1-B1-C1线为例，实际A1,B1间距离记为，实际B1,C1间距离记为，A1-B1-C1线总长:分别对125条路径求总长，进行比较，得出最短路径，该最短路径上的地铁备选站点即为所要选择的站点。按照上述方法对27个区进行推广，即可得出相应的路线。进而能够确定各区域的地铁备选站点。选取相邻的三个区，倪家桥站区，桐梓林站区，火车南站区做为例子进行计算。表6-3-1所选区中各站点符号对应表区域名站点名符号代替玄武门站区玄武门站D1南京站D2珠江路站D3安德门站区安德门站E1奥体中心站E2南京南站站E3龙眠大道区龙眠大道站F1百家湖站F2中国医科大学站F3通过对地图的测量，测出相邻区域内最优值的距离。令D1，E1间的距离为表6-3-2相邻区间最优值间的距离表3.1×300=930（m）3.8×300=1140（m）2.9×300=870（m）3.2×300=960（m）4.1×300=1230（m）3.0×300=900（m）1.9×300=570（m）2.8×300=840（m）1.8×300=540（m）4.2×300=1260（m）4.8×300=1440（m）3.5×300=1050（m）3.9×300=1170（m）4.8×300=1440（m）3.0×300=900（m）4.8×300=1440（m）5.2×300=1560（m）3.9×300=1170（m）（注：所选用的地图比例尺为1：30000，实际距离是地图上两点间距离的30000倍）根据上面相邻区间最优值间的距离表，可以分别求出各路径的总长度，，，，共27条路径长度，比较可得出的路径最短，即玉洁街站-桐梓林站-农贸市场站路径为连接这三个区域路径的最大值。结果及分析由于每个区中的地铁备选站点其距离范围不大，因此同一个区域中的各地铁备选站点地理环境，客流量，地下设置等情况均相似，因此评估选取地铁站的优劣，主要考虑地铁线在通过各特定区域情况下的最短路径，地铁路径短不仅可以节省地铁线的建设成本，还可以提高乘客的出行效率。通过模型所得到的最优路径和实际地铁站的选取基本吻合，但其中百家湖站和火车站和建模计算结果相违背，建议将这两站分别用玉洁街站，农贸市场站代替，在不影响客流运送，环境保护等的因素下，可以节省地铁线的建设成本，提高乘客的出行效率。附录1：用Matlab求解各指标的权重functionf(A)%以下为权重的计算，A为判断矩阵！A=input('A=');[n,n]=size(A);x=ones(n,100);y=ones(n,100);m=zeros(1,100);m(1)=max(x(:,1));y(:,1)=x(:,1);x(:,2)=A*y(:,1);m(2)=max(x(:,2));y(:,2)=x(:,2)/m(2);p=0.0001;i=2;k=abs(m(2)-m(1));whilek>pi=i+1;x(:,i)=A*y(:,i-1);m(i)=max(x(:,i));y(:,i)=x(:,i)/m(i);k=abs(m(i)-m(i-1));enda=sum(y(:,i));w=y(:,i)/a;t=m(i);disp('特征向量为');disp(w);disp('最大特征值为');disp(t);CI=(t-n)/(n-1);RI=[000.520.891.121.261.361.411.461.491.521.541.561.581.59];CR=CI/RI(n);ifCR<0.10disp('满足一致性要求');disp('CI=');disp(CI);disp('CR=');disp(CR);elsedisp('不满足一致性要求');end附录2：Dijkstra的matlab实现代码function[d,DD]=dijkstra(D,s)%Dijkstra最短路算法Matlab程序用于求从起始点s到其它各点的最短路%D为赋权邻接矩阵%d为s到其它各点最短路径的长度%DD记载了最短路径生成树[m,n]=size(D);d=inf.*ones(1,m);d(1,s)=0;dd=zeros(1,m);dd(1,s)=1;y=s;DD=zeros(m,m);DD(y,y)=1;counter=1;whilelength(find(dd==1))<Mfori=1:mifdd(i)==0d(i)=min(d(i),d(y)+D(y,i));endendddd=inf;fori=1:mifdd(i)==0&&d(i)<DDDddd=d(i);endendyy=find(d==ddd);counter=counter+1;DD(y,yy(1