地铁线路设计规划问题模型 19页

..地铁线路设计规划问题模型摘要随着中国城市化进程飞速开展，人们的通勤方式日新月异。人们从以前的步行的交通方式开场开展，出现了自行车，公交车，私家车等。到现在，城市规模越来越大，交通情况越来严峻。道路上的严重阻塞，导致原来方便快捷的交通方式失去了原有的优点。人们不得不又要去寻找更为方便快捷的交通方式。这时候地铁出现了。地铁是交通方式上的变革。和以往的交通方式不一样，它并不需要占用陆上其他交通方式的线路，它拥有只属于它自己的交通线路，交通站点。它不影响城市地上事物，它是一条穿梭于地下的一条巨龙。但是，正由于它的方便快捷，它穿梭于地底下，产生了高昂的建造费用，我们因此不得不考虑到各站点的分布问题，以修建最少的地铁站点减少费用，满足最多人们的使用需求。本文正是讨论城市区域中的地铁站点、线路建造问题。给出的问题是关于在一个不规那么的城市围选地铁站，然后用最短的路线把各站间地铁站连通。因此我们得出了以下的思路：1.每一个地铁站可以当作一个原点，它的覆盖围为一个圆，然后以某种规律的排布方式使城市被完全覆盖后每个圆排布后的有效覆盖面积最大。2.分析城市的图形，以1中找到的排布方式，以最少的图形填满该城市图形。图中排布的点即为所求的地铁站。3.根据所找到的地铁站，按最少生成树的方法〔prim〕寻找最短的路线。关键字：prim算法完全覆盖有效覆盖面积覆盖方式..word.zl. ..一.问题重述地铁线路设计规划某城市中心城区〔如图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。..word.zl. ..二，问题的分析和符号说明此题中规划的中心城区是一个不规那么的图形，所以地铁分布时不能简单的按规律建立。我们设想的是先建造一种拥有最正确有效面积的地铁站点。首先，我们利用微分的思想，以地铁站为圆心，800m为半径画圆再在圆画接多边形，希望最后能将两个圆接多边形重叠之后重叠的面积尽量少。之后，我们又从化学原子排列规律中得到了另一种模型，从中我们再比拟选出最正确的模型。之后，我们利用CAD按比例画出题目的图与地铁站点阵进展比拟，为了获取地铁站间的距离，我们用C语言编了一个程序计算出每个地铁站的距离矩阵，最后再利用Matlab画出地铁站点图的最小生成树，从中得出最正确路线。最正确有效面积以一个地铁站为中心，与其他地铁站相邻Y完全覆盖状态城市中的每个点都能被地铁站覆盖Y*临界覆盖状态城市中的每个点恰好被完全覆盖N非完全覆盖状态城市中存在没有被地铁站覆盖的点S名义覆盖面积一个地铁站的所有面积地铁站点阵以地铁站为点，最正确有效面积为图，如图〔1〕城市图题目给出的城市规划图〔1〕..word.zl. ..三，模型假设1.近似认为地铁站是不占面积，都是一个质点；2.城市上的地面是平坦的；3.认为城市中心的任意地方都是可以建立站点和线路的。四，模型建立这里，我们用到了两个模型。模型〔一〕思路：我们抛开这个城市的图形，以地铁站为圆心，800m为半径画圆，得图〔a〕。圆心Cr=800(a)然后，为了使所有两个地铁站能无缝地接在一起，我们把这个图尽可能多地划分成接多边形。如图〔b〕~〔e〕。....〔b〕〔c〕〔d〕〔e〕..word.zl. ..这里，我们又出现一个新的问题，要使接多边形能接在一起，接多边形的角度必须能整除360，n边形角和为，每个角为。满足整除360，只有n=3，4，6.现在，我们先假设n=3，那么这个点有效面积；n=4，那么这个点有效面积；n=6，那么这个点有效面积。所以可得，取n=6时，有效面积最大，即将地铁站看成接六边形时，两个地铁站之间衔接起来有效面积最大。..word.zl. ..模型〔二〕：思路:考虑到每个地铁站建成后都会覆盖附近面积为的区域。但由思路一可知，<，所以思路二的根本想法就是允许有适当重叠，并得到重叠时的Y*状态，然后算出Y*状态下的，通过比拟各种重合状态下的，选得最大的，就是我们要得到的最优设计。具体实现：1.考虑四个圆的圆心组成矩形的情况A可以看到，中间的A区域没有被覆盖，此时有两种解决方案，一是在A区域的中心在建一个站，覆盖掉空白的局部；二是直接使四个圆重叠，覆盖空白局部。一方案：二方案：如果借用化学中晶胞的概念，那么上两个图都可以提炼出各自的“..word.zl. ..晶胞〞，我们称之为“排列晶胞〞，如图：一方案和二方案的排列晶胞图是一样的：x····为正方形，其中x的值是，可计算出该排列晶胞下的有效覆盖面积.2.考虑四个圆的圆心组成菱形的情况：如果组成普通菱形〔锐角不是60度〕，和正方形相比，一样的多的点的有效覆盖面积减小〔一样长度边的正方形和菱形面积正方形的面积大〕。3.考虑锐角为60度的菱形：那么排列晶胞有所改变，如图：方案二：x是正六边形，其中,,方案二：·x··是正三角形，其中，。..word.zl. ..比拟三中情况的，那么第三种情况的是最优的。综合上述两种模型，最后得出的最正确有效面积皆为，因此，接下来，我们就把一个地铁站覆盖的面积定为。五，模型求解以一个地铁站的有效面积为。将原题的城市图按比例画进地铁站点阵中，然后再将城市图平移，旋转，比拟不同情况下，城市图所含的点最少是多少，下面给出其中的几种情况〔图部线段的长度表示图形所覆盖的地铁站数目〕。..word.zl. ..经过屡次的比拟，我们发现，城市图中最少包含点阵中32个点，所以得知最少要建32个地铁站才能完全铺满这个城市。..word.zl. ..我们得出了多个含有32个点的地铁站图，我们从中选取了其中一个进展标号，再用C语言计算每个点间的距离〔篇末附上了我们的C语言程序〕去设计最正确路线。如图〔z〕。〔z〕下面是我们用程序算出来每个点到1~32点的距离。〔文件中附上算出来的TXT文件〕第1点到1~32点的距离是0.001349.002757.001361.412357.303603.672400.942746.803611.733656.104132.414961.394800.264980.595520.566305.556034.367201.696894.907683.757200.287322.907697.0010825.538432.808424.048641.5810819.129706.669600.219692.521453.89第2点到1~32点的距离是1349.000.001408.001392.281379.282374.532786.592400.042753.633669.543663.664150.214999.724800.044993.885526.996041.398026.846339.906921.667337.347200.017329.5611000.758656.598430.218427.4810823.059995.539703.299600.011475.54第3点到1~32点的距离是2757.001408.000.002430.841403.561360.473706.072789.132400.704177.343672.873659.465560.515007.914800.094981.396361.529023.726034.046338.287732.927338.897200.0911352.979100.008663.648431.4911004.9510475.3510005.629704.602474.92第4点到1~32点的距离是1361.411392.282430.840.001386.002755.001394.311385.732380.572400.012771.463665.853666.093664.784159.69..word.zl. ..4983.464800.006666.325533.946349.856041.516039.896349.659699.547332.197200.007332.199600.008653.218429.628428.542500.01第5点到1~32点的距离是2357.301379.281403.561386.000.001369.002415.211385.731374.372773.962400.002770.964157.193667.423667.044147.724996.107693.124991.135542.426354.586039.896039.779992.207715.187333.527200.009699.549086.218656.598428.542854.63第6点到1~32点的距离是3603.672374.531360.472755.001369.000.003666.912385.761388.743657.542763.002400.054984.854152.203662.003665.725534.448804.504800.005000.566927.156344.436038.0710455.048305.897711.597328.999987.499691.129085.078649.383714.30第7点到1~32点的距离是2400.942786.593706.071394.312415.213666.910.001403.002766.001391.772415.213682.032400.062776.483683.264799.203669.355319.314995.936053.734800.005000.845550.948427.166037.966041.046355.578429.957328.817200.007335.423769.02第8点到1~32点的距离是2746.802400.042789.131385.731385.732385.761403.000.001363.001388.241385.732399.602771.462400.012773.963652.263666.096422.754148.224995.935000.004800.004995.828653.456349.986040.706039.898428.547714.827334.667200.003762.87第9点到1~32点的距离是3611.732753.632400.702380.571374.371388.742766.001363.000.002384.891374.371396.863649.252763.492400.162773.464145.747590.073667.044168.245538.434989.774800.059077.856917.186344.766037.298647.968302.417711.597327.884228.98第10点到1~32点的距离是3656.103669.544177.342400.012773.963657.541391.771388.242384.890.001391.002776.001383.241384.732409.133653.682400.015207.083656.794804.403667.813667.044159.197331.254994.714800.004997.497200.006348.026040.816040.464900.02第11点到1~32点的距离是4132.413663.663672.872771.462400.002763.002415.211385.731374.371391.000.001385.002400.471389.241388.242384.032771.466473.342762.503665.854164.213666.093665.917715.185542.924998.044800.007332.196928.15..word.zl. ..6354.256039.895090.08第12点到1~32点的距离是4961.394150.213659.463665.852770.962400.053682.032399.601396.862776.001385.000.003665.962405.671382.741376.823665.857776.612400.062771.465005.654156.693666.098313.886349.855545.924995.827714.827714.456934.666349.655625.32第13点到1~32点的距离是4800.264999.725560.513666.094157.194984.852400.062771.463649.251383.242400.473665.960.001379.002777.004139.001385.734111.993649.914996.252400.042771.463665.856039.893666.093664.784157.196039.894995.824800.024996.106140.15第14点到1~32点的距离是4980.594800.045007.913664.783667.424152.202776.482400.012763.491384.731389.242405.671379.000.001398.002760.001382.245445.862390.953672.582774.972400.012774.476347.694153.703666.093667.426039.095538.934997.774800.016137.56第15点到1~32点的距离是5520.564993.884800.094159.693667.043662.003683.262773.962400.162409.131388.241382.742777.001398.000.001362.002404.806816.461374.372395.273680.992773.962400.016931.155000.094163.213667.046351.626353.135551.954997.496443.58第16点到1~32点的距离是6305.555526.994981.394983.464147.723665.724799.203652.262773.463653.682384.031376.824139.002760.001362.000.003648.968160.711385.231394.824796.603652.262762.507703.786025.634988.314147.726919.177318.106346.585533.447002.13第17点到1~32点的距离是6034.366041.396361.524800.004996.105534.443669.353666.094145.742400.012771.463665.851385.731382.242404.803648.960.004626.002754.004157.001392.781385.732399.604996.102771.462400.012771.464800.004156.693668.573666.097300.00第18点到1~32点的距离是7201.698026.849023.726666.327693.128804.505319.316422.757590.075207.086473.347776.614111.995445.866816.468160.714626.000.007380.008783.004098.605452.686810.555791.174032.075205.306473.346666.324410.485322.266422.758646.62第19点到1~32点的距离是..word.zl. ..6894.906339.906034.045533.944991.134800.004995.934148.223667.043656.792762.502400.063649.912390.951374.371385.232754.007380.000.001403.003663.132384.891377.316338.744785.353658.292762.505533.946025.634993.164148.227799.39第20点到1~32点的距离是7683.756921.666338.286349.855542.425000.566053.734995.934168.244804.403665.852771.464996.253672.582395.271394.824157.008783.001403.000.005009.843665.962400.477332.456040.274806.133665.856349.857199.676050.524995.938396.68第21点到1~32点的距离是7200.287337.347732.926041.516354.586927.154800.005000.005538.433667.814164.215005.652400.042774.973680.994796.601392.784098.603663.135009.840.001400.002785.003663.471378.781389.242412.603668.772763.992400.002778.498530.02第22点到1~32点的距离是7322.907200.017338.896039.896039.896344.435000.844800.004989.773667.043666.094156.692771.462400.012773.963652.261385.735452.682384.893665.961400.000.001385.004157.192400.471389.241385.733666.093665.852777.992400.008527.56第23点到1~32点的距离是7697.007329.567200.096349.656039.776038.075550.944995.824800.054159.193665.913666.093665.852774.472400.012762.502399.606810.551377.312400.472785.001385.000.004995.933665.962405.671385.234156.694799.203675.682770.968748.42第24点到1~32点的距离是10825.5311000.7511352.979699.549992.2010455.048427.168653.459077.857331.257715.188313.886039.896347.696931.157703.784996.105791.176338.747332.453663.474157.194995.930.002400.002767.973666.601386.001385.231379.282400.4712180.03第25点到1~32点的距离是8432.808656.599100.007332.197715.188305.896037.966349.986917.184994.715542.926349.853666.094153.705000.096025.632771.464032.074785.356040.271378.782400.473665.962400.000.001379.002772.002771.461385.231379.282400.479799.65第26点到1~32点的距离是8424.048430.218663.647200.007333.527711.596041.046040.706344.764800.004998.045545.923664.783666.09..word.zl. ..4163.214988.312400.015205.303658.294806.131389.241389.242405.672767.971379.000.001393.002400.012393.541388.741389.249700.01第27点到1~32点的距离是8641.588427.488431.497332.197200.007328.996355.576039.896037.294997.494800.004995.824157.193667.423667.044147.722771.466473.342762.503665.852412.601385.731385.233666.602772.001393.000.002771.463665.962411.731385.739797.39第28点到1~32点的距离是10819.1210823.0511004.959600.009699.549987.498429.958428.548647.967200.007332.197714.826039.896039.096351.626919.174800.006666.325533.946349.853668.773666.094156.691386.002771.462400.012771.460.002399.601392.281385.7312100.00第29点到1~32点的距离是9706.669995.5310475.358653.219086.219691.127328.817714.828302.416348.026928.157714.454995.825538.936353.137318.104156.694410.486025.637199.672763.993665.854799.201385.231385.232393.543665.962399.600.001372.002771.0011097.81第30点到1~32点的距离是9600.219703.2910005.628429.628656.599085.077200.007334.667711.596040.816354.256934.664800.024997.775551.956346.583668.575322.264993.166050.522400.002777.993675.681379.281379.281388.742411.731392.281372.000.001399.0010923.36第31点到1~32点的距离是9692.529600.019704.608428.548428.548649.387335.427200.007327.886040.466039.896349.654996.104800.014997.495533.443666.096422.754148.224995.932778.492400.002770.962400.472400.471389.241385.731385.732771.001399.000.0010921.50第32点到1~32点的距离是1453.891475.542474.922500.012854.633714.303769.023762.874228.984900.025090.085625.326140.156137.566443.587002.137300.008646.627799.398396.688530.028527.568748.4212180.039799.659700.019797.3912100.0011097.8110923.3610921.500.00接下来，我们再利用Matlab处理上面的数据，利用PRIMF算法〔篇末我们附上了Matlab的代码〕得到最小生成树的数据。T=..word.zl. ..Columns1through9112565991124563981112Columns10through18121615192323221714161519232227171413Columns19through27132731282430302525103128243029252126Columns28through3110161257203218c=1.0e+003*Columns1through51.34901.36141.37931.36901.3605Columns6through101.37441.36301.37441.38501.3768Columns11through151.36201.37441.37731.38501.3852Columns16through201.38571.38221.37901.38321.3857Columns21through25..word.zl. ..1.38571.38601.37931.37201.3793Columns26through301.37881.37901.39181.39481.4539Column314.0321>>上述数据T表达意思是，需要将图中的点1与点2连线，点1与点4连线以此类推，图中数据c表达的意思是将各点间连线的距离。按上Matlab得出的结论，我们画出图。即为最终的设计路线。图中，我们用六边形的右上顶点代替了圆心的位置得到的地铁路线图。所以等于将城市图向六边形的右上角方向平移了800m，如以下图。..word.zl. ..所以我们的最终结果为32个地铁站，最正确地铁路线如下，总路线长度为45425m。图中有地铁站修到了城市外围，如果有必要的话，可将地铁站适当移，这里以上图为准。..word.zl. ..附录：利用C语言计算各点间距离的代码：#include#includeusingnamespacestd;voidmain(){FILE*fp;charch[10]={"1.txt"};fp=fopen(ch,"w+");doublea[100]={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};doubleb;for(inti=0;i<=62;i=i+2){cout<<"第"<a(i,j)min=a(i,j);b=a(i,j);s=i;d=j;endendendendlistV(d)=1;distance(e)=b;source(e)=s;destination(e)=d;e=e+1;endT=[source;destination];forg=1:e-1c(g)=a(T(1,g),T(2,g));endT=[source;destination]c(g)=a(T(1,g),T(2,g))ss=0;forn=1:31ss=ss+c(n);endss..word.zl.