文档介绍：地铁线路设计规划模型
一、摘要
二、问题重述
某城市中心城区(如图1所示)规划修建地铁,要求从该中心城区任意一点出发,到最近的地铁站的直线距离不超过800米,试通过建立模型解决下列问题:(1)最少要建多少个地铁站?(2)按最少数量的地铁站分布,设计出最佳的地铁线路(要求不同的地铁线路换乘能互相到达)。
(0, 2)
(4, 2)
(9. 7003, )
(, )
(, 2)
(, )
(, )
(4, )
α≈°
)

α
α
图1:某城市中心城区的简化图,其中AGCB为梯形,DEFG为矩形,坐标A(, ), B(0, 2), BC=, AG=,   DE=, EF=。图中每单位长度表示实际距离3km。
三、名词和符号说明
四、模型假设
五、问题分析
本题中规划的中心城区是一个不规则的图形,所以地铁分布时不能简单的按规律建立。我们设想的是先建造一种拥有最佳有效面积的地铁站点。首先,我们利用微分的思想,以地铁站为圆心,800m为半径画圆再在圆内画内接多边形,希望最后能将两个圆内内接多边形重叠之后重叠的面积尽量少。之后,我们又从化学原子排列规律中得到了另一种模型,从中我们再比较选出最佳的模型。之后,我们利用CAD按比例画出题目的图与地铁站点阵进行比较,为了获取地铁站间的距离,我们用C语言编了一个程序计算出每个地铁站的距离矩阵,最后再利用Matlab画出地铁站点图的最小生成树,从中得出最佳路线。
思路一:我们抛开这个城市的图形,以地铁站为圆心,800m为半径画圆,如图5-1。
R=800
圆心C
图 5-1
然后,为了使所有两个地铁站能无缝地接在一起,我们把这个图尽可能多地划分成内接多边形。如图(b)~(e)。
....

图 5-2 图5-3 图 5-4 图 5-5
这里,我们又出现一个新的问题,要使内接多边形能接在一起,内接多边形的角度必须能整除360,n边形内角和为,每个内角为。满足整除360,只有n=3,4,6。
现在,我们先假设
n=3(图5-3),则每个点有效面积;
n=4(图5-4),则这个点有效面积;
n=6(图5-5),则这个点有效面积。
所以可得,取n=6时,有效面积最大,即将地铁站看成内接六边形时, 两个地铁站之间衔接起来有效面积最大。
思路二:
考虑到每个地铁站建成后都会覆盖附近面积为的区域。但由思路一可知,,所以思路二的基本想法就是允许有适当重叠,并得到重叠时的状态,然后算出重叠状态下对于每个站点与其他站点交盖的面积,通过比较各种重合状态下的,选得最小的,就是我们要得到的最优设计。
具体实现:
考虑四个圆的圆心组成矩形的情况
A

图 5-6 图 5-7 图 5-8
可以看到,中间的A区域没有被覆盖,此时有两种解决方案,方案一是在A区域的中心在建一个站,覆盖掉空白的部分,如图5-7;方案二是直接使四个圆重叠,覆盖空白部分,如图5-8。
很容易发现,对于上面两种情况,每一个圆与其他圆共同交盖的面积都是,即阴影所示区域。
:
如果组成普通菱形(锐角不是60度),和正方形相比,每一个圆的交盖面积增加。
:
图 5-9 图5-10
方案三:如图5-9是正六边形,其中正六边形边长为,对每一个圆来说交盖面积为;
方案四:如图5-10是正三角形,其中正三角形边长为,对每一个圆来说交盖面积为。
比较四种情况的,方案三的是最小的,从而有效面积。
综合上述两种思路,最后得出的最佳有效面积皆为,因此,接下来我们就选择将每个地铁站的覆盖面积视作正六边形。
六、模型建立与优化
问题一:最少要建多少个地铁站?
以一个地铁站的有效面积为内接六边形,在 Auto CAD中将边长为800单位的正六边形用阵列方法排出20×20的矩阵。将原题的城市图中各端点的坐标求出并放大比例按坐标画进地铁站六边形矩阵阵中,然后将城市图平移,旋转,比较不同情况下,城市图所含盖的正六边形数目最少的情况。
由于使用枚举法列举城市图与六边形之间关系的各种情况并清点城市图覆盖的六边形数目过于繁琐,我们考虑了一种优化方法。先让城市图的某一条边覆盖的正六边形数目最少,再考虑其他边覆盖的数目最少的情况,再通过平移等方法尽量减少七个边覆盖的正六边形的数目,以此逼近最优解。数六边形数目的时候为防止人工数数出错,我们采用将范围内的六边形载入选区并由电脑技术的方法保证了数据的真实性和准确性。
如下图6-1至图6-10列出了我们枚举的八种