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

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

摘要

随着中国城市化进程飞速发展，人们的通勤方式日新月异。人们从以前的步行的交通方式开始发展，出现了自行车，公交车，私家车等。到现在，城市规模越来越大，交通情况越来严峻。道路上的严重阻塞，导致原来方便快捷的交通方式失去了原有的优点。人们不得不又要去寻找更为方便快捷的交通方式。这时候地铁出现了。
地铁是交通方式上的变革。和以往的交通方式不一样，它并不需要占用陆上其他交通方式的线路，它拥有只属于它自己的交通线路，交通站点。它不影响城市地上事物，它是一条穿梭于地下的一条巨龙。
但是，正由于它的方便快捷，它穿梭于地底下，产生了高昂的建造费用，我们因此不得不考虑到各站点的分布问题，以修建最少的地铁站点减少费用，满足最多人们的使用需求。本文正是讨论城市区域中的地铁站点、线路建造问题。
给出的问题是关于在一个不规则的城市范围内选地铁站，然后用最短的路线把各站间地铁站连通。因此我们得出了以下的思路：
1. 每一个地铁站可以当作一个原点，它的覆盖范围为一个圆，然后以某种规律的排布方式使城市被完全覆盖后每个圆排布后的有效覆盖面积最大。
2. 分析城市的图形，以1中找到的排布方式，以最少的图形填满该城市图形。图中排布的点即为所求的地铁站。
3. 根据所找到的地铁站，按最少生成树的办法（prim）寻找最短的路线。
关键字： prim算法 完全覆盖 有效覆盖面积 覆盖方式

一.问题重述

地铁线路设计规划
某城市中心城区（如图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。

二，问题的分析和符号说明

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

最佳有效面积
以一个地铁站为中心，与其他地铁站相邻
Y完全覆盖状态
城市中的每个点都能被地铁站覆盖
Y*临界覆盖状态
城市中的每个点恰好被完全覆盖
N非完全覆盖状态
城市中存在没有被地铁站覆盖的点
S名义覆盖面积
一个地铁站的所有面积
地铁站点阵
以地铁站为点，最佳有效面积为图，如图（1）
城市图
题目给出的城市规划图

（1）

三，模型假设

1.近似认为地铁站是不占面积，都是一个质点；
2.城市上的地面是平坦的；
3.认为城市中心内的任意地方都是可以建设站点和线路的。

四，模型建立

这里，我们用到了两个模型。
模型（一）

思路：我们抛开这个城市的图形，以地铁站为圆心，800m为半径画圆，得图（a）。

圆心C

r=800

( a )

然后，为了使所有两个地铁站能无缝地接在一起，我们把这个图尽可能多地划分成内接多边形。如图（b）~（e）。

....

（b） （c） （d） （e）

这里，我们又出现一个新的问题，要使内接多边形能接在一起，内接多边形的角度必须能整除360，n边形内角和为，每个内角为。满足整除360，只有n=3，4，6.
现在，我们先假设
n=3，则这个点有效面积；

n=4，则这个点有效面积 ；

n=6，则这个点有效面积。

所以可得，取n=6时，有效面积最大，即将地铁站看成内接六边形时， 两个地铁站之间衔接起来有效面积最大。

模型（二）：
思路:
考虑到每个地铁站建成后都会覆盖附近面积为的区域。但由思路一可知，< ，所以思路二的基本想法就是允许有适当重叠，并得到重叠时的Y*状态，然后算出Y*状态下的，通过比较各种重合状态下的，选得最大的，就是我们要得到的最优设计。
具体实现：
1. 考虑四个圆的圆心组成矩形的情况

A

可以看到，中间的A区域没有被覆盖，此时有两种解决方案，一是在A 区域的中心在建一个站，覆盖掉空白的部分；二是直接使四个圆重叠，覆盖空白部分。

一方案：

二方案：

如果借用化学中晶胞的概念，那么上两个图都可以提炼出各自的“晶胞”，我们称之为“排列晶胞” ，如图：
一方案和二方案的排列晶胞图是相同的：

x
· ·

· ·

为正方形，其中x的值是 ，可计算出该排列晶胞下的有效覆盖面积.
2.考虑四个圆的圆心组成菱形的情况：
如果组成普通菱形（锐角不是60度），和正方形相比，相同的多的点的有效覆盖面积减小（相同长度边的正方形和菱形面积正方形的面积大）。
3.考虑锐角为60度的菱形：
则排列晶胞有所改变，如图：
方案二：

x

是正六边形，其中,,
方案二：
·

x

· ·

是正三角形，其中 ，。

比较三中情况的，则第三种情况的是最优的。

综合上述两种模型，最后得出的最佳有效面积皆为，因此，接下来，我们就把一个地铁站覆盖的面积定为。

五，模型求解

以一个地铁站的有效面积为。将原题的城市图按比例画进地铁站点阵中，然后再将城市图平移，旋转，比较不同情况下，城市图所含的点最少是多少，下面给出其中的几种情况（图内部线段的长度表示图形所覆盖的地铁站数目）。

经过多次的比较，我们发现，城市图中最少包含点阵中32个点，所以得知最少要建32个地铁站才能完全铺满这个城市。

我们得出了多个含有32个点的地铁站图，我们从中选取了其中一个进行标号，再用C语言计算每个点间的距离（篇末附上了我们的C语言程序）去设计最佳路线。如图（z）。

（z）

下面是我们用程序算出来每个点到1~32点的距离。（文件中附上算出来的TXT文件）

第1点到1~32点的距离是
0.00 1349.00 2757.00 1361.41 2357.30 3603.67 2400.94 2746.80 3611.73 3656.10 4132.41 4961.39 4800.26 4980.59 5520.56 6305.55 6034.36 7201.69 6894.90 7683.75 7200.28 7322.90 7697.00 10825.53 8432.80 8424.04 8641.58 10819.12 9706.66 9600.21 9692.52 1453.89
第2点到1~32点的距离是
1349.00 0.00 1408.00 1392.28 1379.28 2374.53 2786.59 2400.04 2753.63 3669.54 3663.66 4150.21 4999.72 4800.04 4993.88 5526.99 6041.39 8026.84 6339.90 6921.66 7337.34 7200.01 7329.56 11000.75 8656.59 8430.21 8427.48 10823.05 9995.53 9703.29 9600.01 1475.54
第3点到1~32点的距离是
2757.00 1408.00 0.00 2430.84 1403.56 1360.47 3706.07 2789.13 2400.70 4177.34 3672.87 3659.46 5560.51 5007.91 4800.09 4981.39 6361.52 9023.72 6034.04 6338.28 7732.92 7338.89 7200.09 11352.97 9100.00 8663.64 8431.49 11004.95 10475.35 10005.62 9704.60 2474.92
第4点到1~32点的距离是
1361.41 1392.28 2430.84 0.00 1386.00 2755.00 1394.31 1385.73 2380.57 2400.01 2771.46 3665.85 3666.09 3664.78 4159.69 4983.46 4800.00 6666.32 5533.94 6349.85 6041.51 6039.89 6349.65 9699.54 7332.19 7200.00 7332.19 9600.00 8653.21 8429.62 8428.54 2500.01
第5点到1~32点的距离是
2357.30 1379.28 1403.56 1386.00 0.00 1369.00 2415.21 1385.73 1374.37 2773.96 2400.00 2770.96 4157.19 3667.42 3667.04 4147.72 4996.10 7693.12 4991.13 5542.42 6354.58 6039.89 6039.77 9992.20 7715.18 7333.52 7200.00 9699.54 9086.21 8656.59 8428.54 2854.63
第6点到1~32点的距离是
3603.67 2374.53 1360.47 2755.00 1369.00 0.00 3666.91 2385.76 1388.74 3657.54 2763.00 2400.05 4984.85 4152.20 3662.00 3665.72 5534.44 8804.50 4800.00 5000.56 6927.15 6344.43 6038.07 10455.04 8305.89 7711.59 7328.99 9987.49 9691.12 9085.07 8649.38 3714.30
第7点到1~32点的距离是
2400.94 2786.59 3706.07 1394.31 2415.21 3666.91 0.00 1403.00 2766.00 1391.77 2415.21 3682.03 2400.06 2776.48 3683.26 4799.20 3669.35 5319.31 4995.93 6053.73 4800.00 5000.84 5550.94 8427.16 6037.96 6041.04 6355.57 8429.95 7328.81 7200.00 7335.42 3769.02
第8点到1~32点的距离是
2746.80 2400.04 2789.13 1385.73 1385.73 2385.76 1403.00 0.00 1363.00 1388.24 1385.73 2399.60 2771.46 2400.01 2773.96 3652.26 3666.09 6422.75 4148.22 4995.93 5000.00 4800.00 4995.82 8653.45 6349.98 6040.70 6039.89 8428.54 7714.82 7334.66 7200.00 3762.87
第9点到1~32点的距离是
3611.73 2753.63 2400.70 2380.57 1374.37 1388.74 2766.00 1363.00 0.00 2384.89 1374.37 1396.86 3649.25 2763.49 2400.16 2773.46 4145.74 7590.07 3667.04 4168.24 5538.43 4989.77 4800.05 9077.85 6917.18 6344.76 6037.29 8647.96 8302.41 7711.59 7327.88 4228.98
第10点到1~32点的距离是
3656.10 3669.54 4177.34 2400.01 2773.96 3657.54 1391.77 1388.24 2384.89 0.00 1391.00 2776.00 1383.24 1384.73 2409.13 3653.68 2400.01 5207.08 3656.79 4804.40 3667.81 3667.04 4159.19 7331.25 4994.71 4800.00 4997.49 7200.00 6348.02 6040.81 6040.46 4900.02
第11点到1~32点的距离是
4132.41 3663.66 3672.87 2771.46 2400.00 2763.00 2415.21 1385.73 1374.37 1391.00 0.00 1385.00 2400.47 1389.24 1388.24 2384.03 2771.46 6473.34 2762.50 3665.85 4164.21 3666.09 3665.91 7715.18 5542.92 4998.04 4800.00 7332.19 6928.15 6354.25 6039.89 5090.08
第12点到1~32点的距离是
4961.39 4150.21 3659.46 3665.85 2770.96 2400.05 3682.03 2399.60 1396.86 2776.00 1385.00 0.00 3665.96 2405.67 1382.74 1376.82 3665.85 7776.61 2400.06 2771.46 5005.65 4156.69 3666.09 8313.88 6349.85 5545.92 4995.82 7714.82 7714.45 6934.66 6349.65 5625.32
第13点到1~32点的距离是
4800.26 4999.72 5560.51 3666.09 4157.19 4984.85 2400.06 2771.46 3649.25 1383.24 2400.47 3665.96 0.00 1379.00 2777.00 4139.00 1385.73 4111.99 3649.91 4996.25 2400.04 2771.46 3665.85 6039.89 3666.09 3664.78 4157.19 6039.89 4995.82 4800.02 4996.10 6140.15
第14点到1~32点的距离是
4980.59 4800.04 5007.91 3664.78 3667.42 4152.20 2776.48 2400.01 2763.49 1384.73 1389.24 2405.67 1379.00 0.00 1398.00 2760.00 1382.24 5445.86 2390.95 3672.58 2774.97 2400.01 2774.47 6347.69 4153.70 3666.09 3667.42 6039.09 5538.93 4997.77 4800.01 6137.56
第15点到1~32点的距离是
5520.56 4993.88 4800.09 4159.69 3667.04 3662.00 3683.26 2773.96 2400.16 2409.13 1388.24 1382.74 2777.00 1398.00 0.00 1362.00 2404.80 6816.46 1374.37 2395.27 3680.99 2773.96 2400.01 6931.15 5000.09 4163.21 3667.04 6351.62 6353.13 5551.95 4997.49 6443.58
第16点到1~32点的距离是
6305.55 5526.99 4981.39 4983.46 4147.72 3665.72 4799.20 3652.26 2773.46 3653.68 2384.03 1376.82 4139.00 2760.00 1362.00 0.00 3648.96 8160.71 1385.23 1394.82 4796.60 3652.26 2762.50 7703.78 6025.63 4988.31 4147.72 6919.17 7318.10 6346.58 5533.44 7002.13
第17点到1~32点的距离是
6034.36 6041.39 6361.52 4800.00 4996.10 5534.44 3669.35 3666.09 4145.74 2400.01 2771.46 3665.85 1385.73 1382.24 2404.80 3648.96 0.00 4626.00 2754.00 4157.00 1392.78 1385.73 2399.60 4996.10 2771.46 2400.01 2771.46 4800.00 4156.69 3668.57 3666.09 7300.00
第18点到1~32点的距离是
7201.69 8026.84 9023.72 6666.32 7693.12 8804.50 5319.31 6422.75 7590.07 5207.08 6473.34 7776.61 4111.99 5445.86 6816.46 8160.71 4626.00 0.00 7380.00 8783.00 4098.60 5452.68 6810.55 5791.17 4032.07 5205.30 6473.34 6666.32 4410.48 5322.26 6422.75 8646.62
第19点到1~32点的距离是
6894.90 6339.90 6034.04 5533.94 4991.13 4800.00 4995.93 4148.22 3667.04 3656.79 2762.50 2400.06 3649.91 2390.95 1374.37 1385.23 2754.00 7380.00 0.00 1403.00 3663.13 2384.89 1377.31 6338.74 4785.35 3658.29 2762.50 5533.94 6025.63 4993.16 4148.22 7799.39
第20点到1~32点的距离是
7683.75 6921.66 6338.28 6349.85 5542.42 5000.56 6053.73 4995.93 4168.24 4804.40 3665.85 2771.46 4996.25 3672.58 2395.27 1394.82 4157.00 8783.00 1403.00 0.00 5009.84 3665.96 2400.47 7332.45 6040.27 4806.13 3665.85 6349.85 7199.67 6050.52 4995.93 8396.68
第21点到1~32点的距离是
7200.28 7337.34 7732.92 6041.51 6354.58 6927.15 4800.00 5000.00 5538.43 3667.81 4164.21 5005.65 2400.04 2774.97 3680.99 4796.60 1392.78 4098.60 3663.13 5009.84 0.00 1400.00 2785.00 3663.47 1378.78 1389.24 2412.60 3668.77 2763.99 2400.00 2778.49 8530.02
第22点到1~32点的距离是
7322.90 7200.01 7338.89 6039.89 6039.89 6344.43 5000.84 4800.00 4989.77 3667.04 3666.09 4156.69 2771.46 2400.01 2773.96 3652.26 1385.73 5452.68 2384.89 3665.96 1400.00 0.00 1385.00 4157.19 2400.47 1389.24 1385.73 3666.09 3665.85 2777.99 2400.00 8527.56
第23点到1~32点的距离是
7697.00 7329.56 7200.09 6349.65 6039.77 6038.07 5550.94 4995.82 4800.05 4159.19 3665.91 3666.09 3665.85 2774.47 2400.01 2762.50 2399.60 6810.55 1377.31 2400.47 2785.00 1385.00 0.00 4995.93 3665.96 2405.67 1385.23 4156.69 4799.20 3675.68 2770.96 8748.42
第24点到1~32点的距离是
10825.53 11000.75 11352.97 9699.54 9992.20 10455.04 8427.16 8653.45 9077.85 7331.25 7715.18 8313.88 6039.89 6347.69 6931.15 7703.78 4996.10 5791.17 6338.74 7332.45 3663.47 4157.19 4995.93 0.00 2400.00 2767.97 3666.60 1386.00 1385.23 1379.28 2400.47 12180.03
第25点到1~32点的距离是
8432.80 8656.59 9100.00 7332.19 7715.18 8305.89 6037.96 6349.98 6917.18 4994.71 5542.92 6349.85 3666.09 4153.70 5000.09 6025.63 2771.46 4032.07 4785.35 6040.27 1378.78 2400.47 3665.96 2400.00 0.00 1379.00 2772.00 2771.46 1385.23 1379.28 2400.47 9799.65
第26点到1~32点的距离是
8424.04 8430.21 8663.64 7200.00 7333.52 7711.59 6041.04 6040.70 6344.76 4800.00 4998.04 5545.92 3664.78 3666.09 4163.21 4988.31 2400.01 5205.30 3658.29 4806.13 1389.24 1389.24 2405.67 2767.97 1379.00 0.00 1393.00 2400.01 2393.54 1388.74 1389.24 9700.01
第27点到1~32点的距离是
8641.58 8427.48 8431.49 7332.19 7200.00 7328.99 6355.57 6039.89 6037.29 4997.49 4800.00 4995.82 4157.19 3667.42 3667.04 4147.72 2771.46 6473.34 2762.50 3665.85 2412.60 1385.73 1385.23 3666.60 2772.00 1393.00 0.00 2771.46 3665.96 2411.73 1385.73 9797.39
第28点到1~32点的距离是
10819.12 10823.05 11004.95 9600.00 9699.54 9987.49 8429.95 8428.54 8647.96 7200.00 7332.19 7714.82 6039.89 6039.09 6351.62 6919.17 4800.00 6666.32 5533.94 6349.85 3668.77 3666.09 4156.69 1386.00 2771.46 2400.01 2771.46 0.00 2399.60 1392.28 1385.73 12100.00
第29点到1~32点的距离是
9706.66 9995.53 10475.35 8653.21 9086.21 9691.12 7328.81 7714.82 8302.41 6348.02 6928.15 7714.45 4995.82 5538.93 6353.13 7318.10 4156.69 4410.48 6025.63 7199.67 2763.99 3665.85 4799.20 1385.23 1385.23 2393.54 3665.96 2399.60 0.00 1372.00 2771.00 11097.81
第30点到1~32点的距离是
9600.21 9703.29 10005.62 8429.62 8656.59 9085.07 7200.00 7334.66 7711.59 6040.81 6354.25 6934.66 4800.02 4997.77 5551.95 6346.58 3668.57 5322.26 4993.16 6050.52 2400.00 2777.99 3675.68 1379.28 1379.28 1388.74 2411.73 1392.28 1372.00 0.00 1399.00 10923.36
第31点到1~32点的距离是
9692.52 9600.01 9704.60 8428.54 8428.54 8649.38 7335.42 7200.00 7327.88 6040.46 6039.89 6349.65 4996.10 4800.01 4997.49 5533.44 3666.09 6422.75 4148.22 4995.93 2778.49 2400.00 2770.96 2400.47 2400.47 1389.24 1385.73 1385.73 2771.00 1399.00 0.00 10921.50
第32点到1~32点的距离是
1453.89 1475.54 2474.92 2500.01 2854.63 3714.30 3769.02 3762.87 4228.98 4900.02 5090.08 5625.32 6140.15 6137.56 6443.58 7002.13 7300.00 8646.62 7799.39 8396.68 8530.02 8527.56 8748.42 12180.03 9799.65 9700.01 9797.39 12100.00 11097.81 10923.36 10921.50 0.00

接下来，我们再利用Matlab处理上面的数据，利用PRIMF算法（篇末我们附上了Matlab的代码）得到最小生成树的数据。

T =

Columns 1 through 9

1 1 2 5 6 5 9 9 11
2 4 5 6 3 9 8 11 12

Columns 10 through 18

12 16 15 19 23 23 22 17 14
16 15 19 23 22 27 17 14 13

Columns 19 through 27

13 27 31 28 24 30 30 25 25
10 31 28 24 30 29 25 21 26

Columns 28 through 31

10 16 1 25
7 20 32 18

c =

1.0e+003 *

Columns 1 through 5

1.3490 1.3614 1.3793 1.3690 1.3605

Columns 6 through 10

1.3744 1.3630 1.3744 1.3850 1.3768

Columns 11 through 15

1.3620 1.3744 1.3773 1.3850 1.3852

Columns 16 through 20

1.3857 1.3822 1.3790 1.3832 1.3857

Columns 21 through 25

1.3857 1.3860 1.3793 1.3720 1.3793

Columns 26 through 30

1.3788 1.3790 1.3918 1.3948 1.4539

Column 31

4.0321

>>

上述数据T表达意思是，需要将图中的点1与点2连线，点1与点4连线以此类推，图中数据c表达的意思是将各点间连线的距离。

按上Matlab得出的结论，我们画出图。即为最终的设计路线。

图中，我们用六边形的右上顶点代替了圆心的位置得到的地铁路线图。所以等于将城市图向六边形的右上角方向平移了800m，如下图。

所以我们的最终结果为32个地铁站，最佳地铁路线如下，总路线长度为45425m。

图中有地铁站修到了城市外围，如果有必要的话，可将地铁站适当内移，这里以上图为准。

附录：
利用C语言计算各点间距离的代码：
#include<iostream>
#include<math.h>
using namespace std;
void main(){
FILE *fp;
char ch[10]={"1.txt"};
fp=fopen(ch,"w+");
double a[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.