地铁线路设计规划模型数学建模

1、地铁线路设计规划模型一、摘要二、问题重述某城市中心城区（如图1所示）规划修建地铁，要求从该中心城区任意一点出发，到最近的地铁站的直线距离不超过800米，试通过建立模型解决下列问题：（1）最少要建多少个地铁站？（2）按最少数量的地铁站分布，设计出最佳的地铁线路（要求不同的地铁线路换乘能互相到达）。(0, 2)(4, 2)(9. 7003, 0.2397)(11.4494, 2.4261)(7.5, 2)(5.7491, 6.9864)(0.5, 4.8)(4, 4.8)38.6598°2.9985)2.8图1：某城市中心城区的简化图，其中AGCB为梯形，DEFG为矩形，坐标A(0.5,

2、 4.8), B(0, 2), BC=7.5, AG=3.5,   DE=2.8, EF=7.3。图中每单位长度表示实际距离3km。三、名词和符号说明四、模型假设五、问题分析本题中规划的中心城区是一个不规则的图形，所以地铁分布时不能简单的按规律建立。我们设想的是先建造一种拥有最佳有效面积的地铁站点。首先，我们利用微分的思想，以地铁站为圆心，800m为半径画圆再在圆内画内接多边形，希望最后能将两个圆内内接多边形重叠之后重叠的面积尽量少。之后，我们又从化学原子排列规律中得到了另一种模型，从中我们再比较选出最佳的模型。之后，我们利用CAD按比例画出题目的图与地铁站点阵进行比较，为了获取地铁

3、站间的距离，我们用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），则每个点有效面积

4、； n=4（图5-4），则这个点有效面积 ； n=6（图5-5），则这个点有效面积。所以可得，取n=6时，有效面积最大，即将地铁站看成内接六边形时， 两个地铁站之间衔接起来有效面积最大。思路二: 考虑到每个地铁站建成后都会覆盖附近面积为的区域。但由思路一可知，所以思路二的基本想法就是允许有适当重叠，并得到重叠时的状态，然后算出重叠状态下对于每个站点与其他站点交盖的面积，通过比较各种重合状态下的，选得最小的，就是我们要得到的最优设计。具体实现：1. 考虑四个圆的圆心组成矩形的情况A 图 5-6 图 5-7 图 5-8可以看到，中间的A区域没有被覆盖，此时有两种解决方案，方案一是在A区域的中心在建

5、一个站，覆盖掉空白的部分，如图5-7；方案二是直接使四个圆重叠，覆盖空白部分，如图5-8。很容易发现，对于上面两种情况，每一个圆与其他圆共同交盖的面积都是，即阴影所示区域。2.考虑四个圆的圆心组成菱形的情况：如果组成普通菱形（锐角不是60度），和正方形相比，每一个圆的交盖面积增加。3.考虑锐角为60度的菱形： 图 5-9 图5-10方案三：如图5-9是正六边形，其中正六边形边长为,对每一个圆来说交盖面积为；方案四：如图5-10是正三角形，其中正三角形边长为，对每一个圆来说交盖面积为。 比较四种情况的，方案三的是最小的，从而有效面积。综合上述两种思路，最后得出的最佳有效面积皆为，因此，接下来我们

6、就选择将每个地铁站的覆盖面积视作正六边形。六、模型建立与优化问题一：最少要建多少个地铁站？ 以一个地铁站的有效面积为内接六边形，在 Auto CAD中将边长为800单位的正六边形用阵列方法排出20×20的矩阵。将原题的城市图中各端点的坐标求出并放大比例按坐标画进地铁站六边形矩阵阵中，然后将城市图平移，旋转，比较不同情况下，城市图所含盖的正六边形数目最少的情况。由于使用枚举法列举城市图与六边形之间关系的各种情况并清点城市图覆盖的六边形数目过于繁琐，我们考虑了一种优化方法。先让城市图的某一条边覆盖的正六边形数目最少，再考虑其他边覆盖的数目最少的情况，再通过平移等方法尽量减少七个边覆盖的正

7、六边形的数目，以此逼近最优解。数六边形数目的时候为防止人工数数出错，我们采用将范围内的六边形载入选区并由电脑技术的方法保证了数据的真实性和准确性。如下图6-1至图6-10列出了我们枚举的八种特殊情况。图 6-1 矩形短边横排233图 6-2 矩形短边斜排左对齐226图 6-3 矩形长边斜排左对齐226图 6-4 矩形长边斜排右对齐227图 6-5 矩形长边横排左对齐226图 6-6 矩形长边横排右对齐231图 6-7 梯形长边横排233图 6-8 梯形长边斜排230由以上八张截图可发现，图6-2，图6-3，图6-5的六边形数目均为226，因此可以得出最小覆盖正六边形的数目为226个的结论，即最

8、少要建226个地铁站才能完全铺满这个城市。经过多方比较，我们选取了最易于生成最小树的图6-5作为我们第二问的地铁线路设计目标。问题二：按最少数量的地铁站分布，设计出最佳的地铁线路（要求不同的地铁线路换乘能互相到达）我们在Auto CAD中将图6-5情况下的226个正六边形替换为800半径的圆并按一定的顺序编号（图6-9），并且利用Auto CAD的查询列表显示功能将226个圆的圆心坐标全部输出（输出内容见附件8.1），通过Word、Excel等一系列Office软件对数据的编辑操作，得到了226个点的有序坐标的txt格式文件（数据见附件8.2）。用Visual C+编程软件将txt文件中的所有

9、数据依次导入并编程（C+文件见附件8.3）计算每一个点到其他225个点的距离导出至新的txt文件（数据量过大不适合在附件中呈现）。用Matlab软件将距离值全部导入，并利用Primf最小生成树算法求出生成的最小树结果（结果与Primf代码见附件8.4）。最后在Auto CAD中绘出最小树（图6-10），并归纳了31条地铁线路（不拐弯的一条直线视为一条线路）共62组坐标点（见表6-1），在Visual C+中求出地铁线路总长度为311769m（编程代码见附件8.5）。22622522422322222122021921821721621521421321221121020920820720620

10、520420320220120019919819719619519419319219119018918818718618518418318218118118017917817717617517417317217117016916816716616516416316216116015915815715615515415315215115014914814714614514414314214114013913813713613513413313213113012912812712612512412312212112011911811711611511411311211111010910810710

11、610510410310210110099989796959493929190898887868584838281807978777675747373727170696867666463626160595856555453525149484746454442414039383735343332313065575043362928272625242322212019181716151413121110987654321图 6-9 226个地铁站按顺序编号图 6-10 最小生成树 地铁线路图表 6-1 31条地铁线的坐标值地铁站编号圆心x坐标圆心y坐标连接的地铁站编号圆心x坐标圆心y坐标14006

12、92.820374009006.66421400692.82032252920017320.50811400692.820381600024002078.46092212800018013.328434003464.10162222800019398.96944004849.74224976009006.664254006235.38293552009006.664264007621.02352128009006.66428160002242920015934.8674152800692.8203224000022400002263040015242.0471295200692.8203366

13、400036640002172800012470.7658437600692.820350880005088000172220007621.02355710000692.82036511200065112000171220006235.38297412400692.82038313600083136000170220004849.74229314800692.8203103160000103160000169220003464.101611517200692.8203127184000127184000168220002078.460914019600692.82031532080001532

14、0800016722000692.820363100009006.6642641000010392.3048641000010392.30482152680020091.78931131600013856.40651141600015242.04711141600015242.04712162680021477.431802200018706.14871812200020091.78931812200020091.78932082560022170.2503七、模型的评价与推广八、附录附录8.1：Auto CAD输出的226个圆的圆心坐标及其他命令: _list 找到 226 个 圆 图层:

15、0 空间: 模型空间 句柄 = 188e 圆心 点， X=30400.0000 Y=15242.0471 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1880 圆心 点， X=28000.0000 Y=19398.9690 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 187f 圆心 点， X=28000.0000 Y=18013.3284 Z= 0.0000 半径 800.0000 周长 50

16、26.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 187e 圆心 点， X=28000.0000 Y=16627.6878 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 187d 圆心 点， X=28000.0000 Y=15242.0471 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 187c 圆心 点， X=28000.0000 Y=13856.40

17、65 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 187b 圆心 点， X=28000.0000 Y=12470.7658 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1871 圆心 点， X=25600.0000 Y=22170.2503 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1870

18、 圆心 点， X=25600.0000 Y=20784.6097 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 186f 圆心 点， X=25600.0000 Y=19398.9690 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 186e 圆心 点， X=25600.0000 Y=18013.3284 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2

19、983 圆 图层: 0 空间: 模型空间 句柄 = 186d 圆心 点， X=25600.0000 Y=16627.6878 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 186c 圆心 点， X=25600.0000 Y=15242.0471 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 186b 圆心 点， X=25600.0000 Y=13856.4065 Z= 0.0000 半径 800.

20、0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 186a 圆心 点， X=25600.0000 Y=12470.7658 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1869 圆心 点， X=25600.0000 Y=11085.1252 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 185f 圆心 点， X=23200.0000

21、Y=20784.6097 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 185e 圆心 点， X=23200.0000 Y=19398.9690 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 185d 圆心 点， X=23200.0000 Y=18013.3284 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间

22、 句柄 = 185c 圆心 点， X=23200.0000 Y=16627.6878 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 185b 圆心 点， X=23200.0000 Y=15242.0471 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 185a 圆心 点， X=23200.0000 Y=13856.4065 Z= 0.0000 半径 800.0000 周长 5026.5482 面积

23、 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1859 圆心 点， X=23200.0000 Y=12470.7658 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1858 圆心 点， X=23200.0000 Y=11085.1252 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1857 圆心 点， X=23200.0000 Y=9699.4845 Z= 0.000

24、0 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 184c 圆心 点， X=20800.0000 Y=18013.3284 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 184b 圆心 点， X=20800.0000 Y=16627.6878 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 184a 圆心 点， X=20

25、800.0000 Y=15242.0471 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1849 圆心 点， X=20800.0000 Y=13856.4065 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1848 圆心 点， X=20800.0000 Y=12470.7658 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0

26、 空间: 模型空间 句柄 = 1847 圆心 点， X=20800.0000 Y=11085.1252 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1846 圆心 点， X=20800.0000 Y=9699.4845 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1845 圆心 点， X=20800.0000 Y=8313.8439 Z= 0.0000 半径 800.0000 周长 5026.

27、5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1844 圆心 点， X=20800.0000 Y=6928.2032 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1843 圆心 点， X=20800.0000 Y=5542.5626 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1842 圆心 点， X=20800.0000 Y=4156.9219 Z=

28、0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1841 圆心 点， X=20800.0000 Y=2771.2813 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1840 圆心 点， X=20800.0000 Y=1385.6406 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 183f 圆心 点， X

29、=20800.0000 Y= 0.0000 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 183a 圆心 点， X=18400.0000 Y=16627.6878 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1839 圆心 点， X=18400.0000 Y=15242.0471 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0

30、 空间: 模型空间 句柄 = 1838 圆心 点， X=18400.0000 Y=13856.4065 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1837 圆心 点， X=18400.0000 Y=12470.7658 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1836 圆心 点， X=18400.0000 Y=11085.1252 Z= 0.0000 半径 800.0000 周长 502

31、6.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1835 圆心 点， X=18400.0000 Y=9699.4845 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1834 圆心 点， X=18400.0000 Y=8313.8439 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1833 圆心 点， X=18400.0000 Y=6928.2032 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1832 圆心 点， X=18400.0000 Y=5542.5626 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1831 圆心 点， X=18400.0000 Y=4156.9219 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2010619.2983