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

《地铁线路设计规划问题模型.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、.地铁线路设计规划问题模型摘要随着中国城市化进程飞速发展，人们的通勤方式日新月异。人们从以前的步行的交通方式开始发展，出现了自行车，公交车，私家车等。到现在，城市规模越来越大，交通情况越来严峻。道路上的严重阻塞，导致原来方便快捷的交通方式失去了原有的优点。人们不得不又要去寻找更为方便快捷的交通方式。这时候地铁出现了。地铁是交通方式上的变革。和以往的交通方式不一样，它并不需要占用陆上其他交通方式的线路，它拥有只属于它自己的交通线路，交通站点。它不影响城市地上事物，它是一条穿梭于地下的一条巨龙。但是，正由于它的方便快捷，它穿梭于地底下，产生了高昂的建造费用，我们

2、因此不得不考虑到各站点的分布问题，以修建最少的地铁站点减少费用，满足最多人们的使用需求。本文正是讨论城市区域中的地铁站点、线路建造问题。给出的问题是关于在一个不规则的城市范围内选地铁站，然后用最短的路线把各站间地铁站连通。因此我们得出了以下的思路：1.每一个地铁站可以当作一个原点，它的覆盖范围为一个圆，然后以某种规律的排布方式使城市被完全覆盖后每个圆排布后的有效覆盖面积最大。2.分析城市的图形，以1中找到的排布方式，以最少的图形填满该城市图形。图中排布的点即为所求的地铁站。3.根据所找到的地铁站，按最少生成树的办法（prim）寻找最短的路线。关键字：prim

3、算法完全覆盖有效覆盖面积覆盖方式..一.问题重述地铁线路设计规划某城市中心城区（如图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。..二，问题的分析和符号说明本题中规划的中心

4、城区是一个不规则的图形，所以地铁分布时不能简单的按规律建立。我们设想的是先建造一种拥有最佳有效面积的地铁站点。首先，我们利用微分的思想，以地铁站为圆心，800m为半径画圆再在圆内画内接多边形，希望最后能将两个圆内内接多边形重叠之后重叠的面积尽量少。之后，我们又从化学原子排列规律中得到了另一种模型，从中我们再比较选出最佳的模型。之后，我们利用CAD按比例画出题目的图与地铁站点阵进行比较，为了获取地铁站间的距离，我们用C语言编了一个程序计算出每个地铁站的距离矩阵，最后再利用Matlab画出地铁站点图的最小生成树，从中得出最佳路线。最佳有效面积以一个地铁站为中心，

5、与其他地铁站相邻Y完全覆盖状态城市中的每个点都能被地铁站覆盖Y*临界覆盖状态城市中的每个点恰好被完全覆盖N非完全覆盖状态城市中存在没有被地铁站覆盖的点S名义覆盖面积一个地铁站的所有面积地铁站点阵以地铁站为点，最佳有效面积为图，如图（1）城市图题目给出的城市规划图（1）..三，模型假设1.近似认为地铁站是不占面积，都是一个质点；2.城市上的地面是平坦的；3.认为城市中心内的任意地方都是可以建设站点和线路的。四，模型建立这里，我们用到了两个模型。模型（一）思路：我们抛开这个城市的图形，以地铁站为圆心，800m为半径画圆，得图（a）。圆心Cr=800(a)然后，为

6、了使所有两个地铁站能无缝地接在一起，我们把这个图尽可能多地划分成内接多边形。如图（b）~（e）。....（b）（c）（d）（e）..这里，我们又出现一个新的问题，要使内接多边形能接在一起，内接多边形的角度必须能整除360，n边形内角和为，每个内角为。满足整除360，只有n=3，4，6.现在，我们先假设n=3，则这个点有效面积；n=4，则这个点有效面积；n=6，则这个点有效面积。所以可得，取n=6时，有效面积最大，即将地铁站看成内接六边形时，两个地铁站之间衔接起来有效面积最大。..模型（二）：思路:考虑到每个地铁站建成后都会覆盖附近面积为的区域。但由思路一可知

7、，<，所以思路二的基本想法就是允许有适当重叠，并得到重叠时的Y*状态，然后算出Y*状态下的，通过比较各种重合状态下的，选得最大的，就是我们要得到的最优设计。具体实现：1.考虑四个圆的圆心组成矩形的情况A可以看到，中间的A区域没有被覆盖，此时有两种解决方案，一是在A区域的中心在建一个站，覆盖掉空白的部分；二是直接使四个圆重叠，覆盖空白部分。一方案：二方案：如果借用化学中晶胞的概念，那么上两个图都可以提炼出各自的“晶胞”..，我们称之为“排列晶胞”，如图：一方案和二方案的排列晶胞图是相同的：x····为正方形，其中x的值是，可计算出该排列晶胞下的有效覆盖面积.2

8、.考虑四个圆的圆心组成菱形的情况：如果组成普通菱形（