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

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

2、EFG为矩形，坐标 A(0.5,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 边形内角和为 (n2)180 ，每个内角为 (n2)180n 。满足整除

4、360，只有 n=3，4，6。现在，我们先假设.n=3（图 5-3），则每个点有效面积 Sa33r2 ；4n=4（图 5-4），则这个点有效面积 Sa2r 2；n=6（图 5-5），则这个点有效面积 Sa33r2 。2所以可得，取 n=6 时，有效面积 Sa 最大，即将地铁站看成内接六边形时，两个地铁站之间衔接起来有效面积最大。思路二 :考虑到每个地铁站建成后都会覆盖附近面积为S 的区域。但由思路一可知，SaS ，所以思路二的基本想法就是允许S 有适当重叠，并得到重叠时的状态，然后算出重叠状态下对于每个站点与其他站点交盖的面积Sa ' ，通过比较各种重合状态下的 Sa ' ，选

5、得最小的，就是我们要得到的最优设计。具体实现：1. 考虑四个圆的圆心组成矩形的情况A图 5-6图 5-7图 5-8可以看到，中间的A 区域没有被覆盖，此时有两种解决方案，方案一是在A区域的中心在建一个站，覆盖掉空白的部分，如图5-7；方案二是直接使四个圆重叠，覆盖空白部分，如图5-8。很容易发现，对于上面两种情况，每一个圆与其他圆共同交盖的面积都是2r 24r 22.2832 ，即阴影所示区域。2. 考虑四个圆的圆心组成菱形的情况：如果组成普通菱形 （锐角不是 60 度），和正方形相比， 每一个圆的交盖面积Sa ' 增加。.3. 考虑锐角为 60 度的菱形：图 5-9图 5-10方案三

6、：如图 5-9是正六边形，其中正六边形边长为r , 对每一个圆来说交盖面积 Sa ' 为 2 r 23 3r 21.0870 ；方案四：如图 5-10是正三角形，其中正三角形边长为3r ，对每一个圆来说交盖面积 Sa ' 为 2r 233 r 23.6851 。2比 较 四 种 情 况 的 Sa ' ， 方 案 三 的 Sa ' 是 最 小 的 ， 从 而 有 效 面 积SaSSa '3 3 r 2 。22综合上述两种思路， 最后得出的最佳有效面积皆为 Sa3 3 r 2 ，因此，接下2来我们就选择将每个地铁站的覆盖面积视作正六边形。六、模型建立与优化问

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

8、最优解。 数六边形数目的时候为防止人工数数出错， 我们采用将范围内的六边形载入选区并由电脑技术的方法保证了数据的真实性和准确性。如下图 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 个的结

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

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

11、189206222180197214152166188205221225179196213126139165187204220224151178195212114138164186203219226125150177194211223102113137163185202218124149176193210921121361621842012177382101123148161175192209819111113518320064100122147160174191721497280901101341822835566399121146173614427179891091331592027344

12、855629812014517213417088108132158519263347546178971191441571714123240697787107131182546536096118143156170113968861061303172431455259769511714215516910386785105129216233044515875941161411681929376674841041281541671522435057931151401538366583103127图 6-9226 个地铁站按顺序编号.图 6-10最小生成树地铁线路图表 6-131 条地铁线的坐标值地铁站

13、圆心 x 坐标圆心 y 坐标连接的地铁圆心 y 坐标编号圆心 x 坐标站编号1400692.820374009006.66421400692.82032252920017320.50811400692.820381600024002078.46092212800018013.328434003464.10162222800019398.96944004849.74224976009006.664254006235.38293552009006.664264007621.02352128009006.66428160002242920015934.8674152800692.8203224000

14、022400002263040015242.0471295200692.8203366400036640002172800012470.7658437600692.820350880005088000172220007621.02355710000692.82036511200065112000171220006235.38297412400692.82038313600083136000170220004849.7422.9314800692.8203103160000103160000169220003464.101611517200692.820312718400012718400016

15、8220002078.460914019600692.820315320800015320800016722000692.820363100009006.6642641000010392.3048641000010392.30482152680020091.78931131600013856.40651141600015242.04711141600015242.04712162680021477.431802200018706.14871812200020091.78931812200020091.78932082560022170.2503七、模型的评价与推广八、附录附录 8.1：Auto

16、 CAD 输出的 226 个圆的圆心坐标及其他命令 : _list 找到 226 个圆图层:0空间 : 模型空间句柄= 188e圆心 点，X=30400.0000Y=15242.0471Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1880圆心 点，X=28000.0000Y=19398.9690Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 187f圆心 点，X=28000.0000Y=18013.3284Z=0.0000.半径800.0000

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

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

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

20、=25600.0000Y=15242.0471Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 186b圆心 点，X=25600.0000Y=13856.4065Z=0.0000.半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 186a圆心 点，X=25600.0000Y=12470.7658Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1869圆心 点，X=25600.0000Y=1108

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

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

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

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

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

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

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

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

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

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

31、5626Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1831圆心 点，X=18400.0000Y=4156.9219Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1830圆心 点，X=18400.0000Y=2771.2813Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 182f圆心 点，X=18400.0000Y=1385.6406Z=0.0000半径800.000

32、0周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 182e圆心 点，X=18400.0000Y=0.0000Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0.空间 : 模型空间句柄= 1828圆心 点，X=16000.0000Y=15242.0471Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1827圆心 点，X=16000.0000Y=13856.4065Z=0.0000半径800.0000周长5026.5482面积2010619

33、.2983圆图层:0空间 : 模型空间句柄= 1826圆心 点，X=16000.0000Y=12470.7658Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1825圆心 点，X=16000.0000Y=11085.1252Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1824圆心 点，X=16000.0000Y=9699.4845Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间

34、句柄= 1823圆心 点，X=16000.0000Y=8313.8439Z=0.0000半径800.0000.周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1822圆心 点，X=16000.0000Y=6928.2032Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1821圆心 点，X=16000.0000Y=5542.5626Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1820圆心 点，X=16000

35、.0000Y=4156.9219Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 181f圆心 点，X=16000.0000Y=2771.2813Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 181e圆心 点，X=16000.0000Y=1385.6406Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0.空间 : 模型空间句柄= 181d圆心 点，X=16000.0000Y=0.0000Z=0.000

36、0半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1815圆心 点，X=13600.0000Y=12470.7658Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1814圆心 点，X=13600.0000Y=11085.1252Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1813圆心 点，X=13600.0000Y=9699.4845Z=0.0000半径800.0000周长5026.5

37、482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1812圆心 点，X=13600.0000Y=8313.8439Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 1811圆心 点，X=13600.0000Y=6928.2032Z=0.0000半径800.0000周长5026.5482.面积2010619.2983圆图层:0空间 : 模型空间句柄= 1810圆心 点，X=13600.0000Y=5542.5626Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 180f圆心 点，X=13600.0000Y=4156.9219Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 180e圆心 点，X=13600.0000Y=2771.2813Z=0.0000半径800.0000周长5026.5482面积2010619.2983圆图层:0空间 : 模型空间句柄= 180d圆心 点，