地铁线路设计规划问题模型.doc

地铁线路设计规划问题模型摘要 随着中国城市化进程飞速发展，人们的通勤方式日新月异。人们从以前的步行的交通方式开始发展，出现了自行车，公交车，私家车等。到现在，城市规模越来越大，交通情况越来严峻。道路上的严重阻塞，导致原来方便快捷的交通方式失去了原有的优点。人们不得不又要去寻找更为方便快捷的交通方式。这时候地铁出现了。 地铁是交通方式上的变革。和以往的交通方式不一样，它并不需要占用陆上其他交通方式的线路，它拥有只属于它自己的交通线路，交通站点。它不影响城市地上事物，它是一条穿梭于地下的一条巨龙。但是，正由于它的方便快捷，它穿梭于地底下，产生了高昂的建造费用，我们因此不得不考虑到各站点的分布问题，以修建最少的地铁站点减少费用，满足最多人们的使用需求。本文正是讨论城市区域中的地铁站点、线路建造问题。 给出的问题是关于在一个不规则的城市范围内选地铁站，然后用最短的路线把各站间地铁站连通。因此我们得出了以下的思路： 1. 每一个地铁站可以当作一个原点，它的覆盖范围为一个圆，然后以某种规律的排布方式使城市被完全覆盖后每个圆排布后的有效覆盖面积最大。2. 分析城市的图形，以1中找到的排布方式，以最少的图形填满该城市图形。图中排布的点即为所求的地铁站。3. 根据所找到的地铁站，按最少生成树的办法（prim）寻找最短的路线。关键字： prim算法 完全覆盖 有效覆盖面积 覆盖方式一.问题重述地铁线路设计规划某城市中心城区（如图1所示）规划修建地铁，要求从该中心城区任意一点出发，到最近的地铁站的直线距离不超过800米，试通过建立模型解决下列问题：（1）最少要建多少个地铁站？（2）按最少数量的地铁站分布，设计出最佳的地铁线路（要求不同的地铁线路换乘能互相到达）。图1：某城市中心城区的简化图，其中AGCB为梯形，DEFG为矩形，坐标A(0.5,4.8),B(0,2), BC=7.5, AG=3.5, DE=2.8, EF=7.3。图中每单位长度表示实际距离3km。二，问题的分析和符号说明 本题中规划的中心城区是一个不规则的图形，所以地铁分布时不能简单的按规律建立。我们设想的是先建造一种拥有最佳有效面积的地铁站点。首先，我们利用微分的思想，以地铁站为圆心，800m为半径画圆再在圆内画内接多边形，希望最后能将两个圆内内接多边形重叠之后重叠的面积尽量少。之后，我们又从化学原子排列规律中得到了另一种模型，从中我们再比较选出最佳的模型。之后，我们利用CAD按比例画出题目的图与地铁站点阵进行比较，为了获取地铁站间的距离，我们用C语言编了一个程序计算出每个地铁站的距离矩阵，最后再利用Matlab画出地铁站点图的最小生成树，从中得出最佳路线。最佳有效面积以一个地铁站为中心，与其他地铁站相邻Y完全覆盖状态城市中的每个点都能被地铁站覆盖Y*临界覆盖状态城市中的每个点恰好被完全覆盖N非完全覆盖状态城市中存在没有被地铁站覆盖的点S名义覆盖面积一个地铁站的所有面积地铁站点阵以地铁站为点，最佳有效面积为图，如图（1）城市图题目给出的城市规划图 （1）三，模型假设 1.近似认为地铁站是不占面积，都是一个质点；2.城市上的地面是平坦的；3.认为城市中心内的任意地方都是可以建设站点和线路的。四，模型建立 这里，我们用到了两个模型。 模型（一）思路：我们抛开这个城市的图形，以地铁站为圆心，800m为半径画圆，得图（a）。圆心Cr=800( a )然后，为了使所有两个地铁站能无缝地接在一起，我们把这个图尽可能多地划分成内接多边形。如图（b）（e）。. （b） （c） （d） （e） 这里，我们又出现一个新的问题，要使内接多边形能接在一起，内接多边形的角度必须能整除360，n边形内角和为，每个内角为。满足整除360，只有n=3，4，6. 现在，我们先假设 n=3，则这个点有效面积； n=4，则这个点有效面积 ； n=6，则这个点有效面积。所以可得，取n=6时，有效面积最大，即将地铁站看成内接六边形时， 两个地铁站之间衔接起来有效面积最大。模型（二）：思路: 考虑到每个地铁站建成后都会覆盖附近面积为的区域。但由思路一可知， 上述数据T表达意思是，需要将图中的点1与点2连线，点1与点4连线以此类推，图中数据c表达的意思是将各点间连线的距离。按上Matlab得出的结论，我们画出图。即为最终的设计路线。 图中，我们用六边形的右上顶点代替了圆心的位置得到的地铁路线图。所以等于将城市图向六边形的右上角方向平移了800m，如下图。所以我们的最终结果为32个地铁站，最佳地铁路线如下，总路线长度为45425m。图中有地铁站修到了城市外围，如果有必要的话，可将地铁站适当内移，这里以上图为准。附录： 利用C语言计算各点间距离的代码：#include#includeusing namespace std;void main()FILE *fp;char ch10=1.txt;fp=fopen(ch,w+);double a100=426,343.77,426,357.26,426,371.34, 438,350.20,438,364.06,438,377.75, 450,343.10,450,357.13,450,370.76, 462,350.15,462,364.06,462,377.91, 474,343.27,474,357.06,474,371.04,474,384.66, 486,350.20,486,303.94,486,377.74,486,391.77, 498,343.13,498,357.13,498,370.98, 534.00,336.34, 510,336.34,510,350.13,510,364.06, 534,350.20, 522,329.42,522,343.14,522,357.13, 413,350.28;double b;for(int i=0;i=62;i=i+2)cout第i/2+1点到1-32点的距离是endl;fprintf(fp,第%d点到1-32点的距离是n,i/2+1);for(int j=0;j=62;j=j+2)b=sqrt(ai-aj)*(ai-aj)+(ai+1-aj+1)*(ai+1-aj+1);printf(%.2f ,b*100);fprintf(fp,%.2f ,b*100);coutendl;fprintf(fp,n);fclose(fp); 利用Matlab 的primf算法代码：function T,c=Primf(a)l=length(a);a(a=0)=inf;k=1:l;listV(k)=0;listV(1)=1;e=1;while(ea(i,j) min=a(i,j); b=a(i,j); s=i; d=j; end end end end listV(d)=1; distance(e)=b; source(e)=s; destinatio