2022年数模mathorcup中的D题移动通信网络站址规划和区域 ...

mypro334

4.16 D题模型分析更新

更新一下D题的全部解题模型和大致的结果把，总的来说这次比赛D题是相对容易的一道题，选择的人也是最多，想要获奖最终还是要看大家构建模型和写论文的水平。 本文的所有内容只适合借鉴，不要直接抄！不要直接抄！不要直接抄！（提醒三遍） 直接进入正题了  

<hr/>
1.问题分析

1.1问题一的分析
问题一要求我们对基站进行选择，基站的选择只有选择和不选择，因此属于0-1背包规划问题，我们需要在一定的重量范围内选择价值最高的物品，也就优先选择服务量最大的基站，并通过启发式算法求解目标函数 第一步分析：首先根据二分数的公式对现有基站之间的距离和现有基站与弱覆盖点之间的距离进行欧式距离的判断，对数据进行清洗，筛选出不符合要求的数据 第二步分析：将问题归类于零一整数背包规划问题，确定好背包问题中的成本与重量，以及门限和距离等约束条件。 第三步分析：使用启发式算法，如模拟退火算法，遗传算法，粒子群算法等求解出最大服务量，最小成本的目标函数，并将求得到的服务量除以总服务量，观察是否大于90% 1.2 问题二的分析 问题二需要我们在问题一的基础上对所选基站的坐标进行深入分析，覆盖区域由原来的圆形变成三个扇形区域，对角度变化范围进行判断，观察总服务量是否仍然大于90% 第一步分析：首先对问题一中所求到的新增基站的坐标。进行统计分析，求得与。坐标最近点的弱覆盖点之间的欧式距离。 第二步分析：给出不同角度扇形区域的覆盖范围变化趋势，求解出。欧式距离与半径，半径的一半之间的变化关系。 第三步分析:对不满足的基站点重新进行规划，建立目标函数约束条件，决策变量，使用启发式算法进行求解。 1.3 问题三的分析 问题三，需要我们对弱覆盖点进行聚类，选择一种合适的方法进行聚类，并分析聚类过程中的相关参数从而计算时间复杂度，对模型进行评价。 第一步分析：将两个弱覆盖点之间的欧式距离小于20的点归为一类，使用聚类算法将全部点进行归类。 第二步分析：计算归类过程中，时间复杂度等参数，使用多种聚类算法对模型进行评价，选择出时间复杂度最低的模型。 问题一模型的建立与求解 2.问题一模型的建立与求解 2.1 问题分析 问题一要求我们对基站进行选择，基站的选择只有选择和不选择，因此属于0-1背包规划问题，我们需要在一定的重量范围内选择价值最高的物品，也就优先选择服务量最大的基站，并通过启发式算法求解目标函数，问题一求解流程图如图所示：     



问题一求解流程图

2.2 数据清洗 首先根据二范数公式，对现有基站的坐标进行清洗，根据公式：   


计算结果如下表所示：   

X坐标	Y坐标	1	2	3	4	5	6	7	8
713	2013	105.2331	0	2345.154	61.39218	366.1912	1331.152	1235.142	1030.327
2305	291	2280.485	2345.154	0	2310.469	2418.003	1076.004	1226.731	1548.903
700	1953	135.6945	61.39218	2310.469	0	421.4273	1308.057	1218.224	974.7666
949	2293	302.8036	366.1912	2418.003	421.4273	0	1352.156	1222.434	1287.126
1796	1239	1251.577	1331.152	1076.004	1308.057	1352.156	0	164.2468	895.8315
1787	1403	1148.76	1235.142	1226.731	1218.224	1222.434	164.2468	0	943.5809
931	1006	1020.277	1030.327	1548.903	974.7666	1287.126	895.8315	943.5809	0

表2.1 现有基站求解欧氏距离

表2.1 现有基站求解欧氏距离 清洗后的数据可视化如下图所示：   





图2.2 数据清洗先后可视化对比

2.3 模型的建立
我们需要选择n个基站，基站j的服务量为wj，成本为sj。 我们假设基站的服务量和服务成本都是非负的，且最大总服务量为w 使得弱覆盖点总业务量的90%倍规划基站覆盖。其中对选择宏基站还是微基站进行规划，引入0-1变量：pi，qi 使其满足：   


过程较多，按照这个方向建模即可，此处略过部分...... 2.4 模拟退火算法求解动态规划模型 针对本文问题的特殊性，我们选择模拟退火算法作为求解方法，模拟退火算法有两层循环；循环一，反复迭代产生新解，在降温的过程中的任一温度下通过随机扰动产生新解，并计算目标函数值的变化，决定是否被接受。循环二，缓慢降温重复迭代过程，在固定温度下迭代完成后缓慢的降低温度，让算法最终可能收敛到全局最优解。 由于算法初始温度比较高，通过循环一的反复迭代过程，让使E增大的新解在初始时也可能被以一定的概率接受，因而能跳出局部极小值。并且，虽然在低温时接收函数已经非常小了，但仍不排除有接受更差的解的可能，因此我们把退火过程中碰到的最好的可行解（历史最优解）也记录了下来，并让它与终止算法前的最后一个被接受解一并输出，防止遗漏最优解。 而在本问的应用中退火的过程由一组初始参数，即冷却进度表（cooling schedule）控制，它的核心是尽量使系统达到准平衡，使算法在有限的时间内逼近最优解。   





图2.3 模拟退火算法的求解流程图

参数的选择......
3.问题二模型的建立与求解
问题二需要我们在问题一的基础上对所选基站的坐标进行深入分析，覆盖区域由原来的圆形变成三个扇形区域，对角度变化范围进行判断，观察总服务量是否仍然大于90%，以角度为自变量建立规划模型，使用贪心算法求解。   进一步考虑，实际中，每个站并不是完全的圆形覆盖，而是每个站上有 3 个扇区，每个扇区指向一个方向。每个扇区在主方向上覆盖范围最大（宏基站为 30，微基站为 10），在主方向左右 60 度的范围内可以覆盖，覆盖范围按线性逐渐缩小，在 60 度的时候，覆盖范围为主方向覆盖范围的一半。超过 60 度，则无法被该扇区覆盖，由此我们分析出不同角度变化时的覆盖范围情况，我们建立极坐标系如下图所示：  



图3.1 不同角度覆盖范围情况

4.问题三模型的建立与求解 ...... 更多内容后期更新，
前面详细的解答可以关注公众号：UST数模社，回复思路！！！
<hr/><hr/>思路一：
移动通信技术规模飞速发展，运营规模也越来越大，导致带来的通信网络溅来越复杂。随着5G的发展，       通信的带宽越来越大但基站的能覆盖范围越来越小，使得覆盖同样的屡域，需要的基站数量变的更多。另外，基站和天线的种类也变多了。这就使得通信网络的规划特别是金址选择的问题变得越来越复杂。站址选择问题是?根据现网天线的覆盖情况，给出现网的弱覆盖区域，选择一定数量的点，使得在这些点上新建基站后，可以解决现网的弱覆盖区域的覆盖问题。例如，下图为某城市某区域的现网覆盖情况，其中红色的区域表示为弱覆盖区域。


背景分析∶这段话点出了一个之后可能需要建模讨论的问题∶站址选择问题。需要考虑的条件是：现网天线的覆盖情况（建模得到现网的弱覆盖区域），选择一定数量的点（这就是站址选择问题），目标∶这些点上新建基站后，可以解决现网的弱覆盖区域的覆盖问题。
在实际网络规拼中，考虑基站的建设成本和一些其他因素，有时候可能无法把所有弱覆盖区域都解决，这时候就需要考虑业务量的因素，尽量优先解决业务量高的弱覆盖区域。
背景分析∶这一段主要是说明，在选址时，如果无法将所有弱覆盖区域都解决，那么这时需要让目标新增"建设成本（也就是能让点尽可能少，而这些点的业务量总和尽可能高）。
为了便于计算，将给定的区域用很小的栅格进行划分，只考虑每个棚格的中心点，即往给一个区域，都可以划分成有限个点。每个点有一些属性值，包括∶坐标，是否为弱覆盖点，业务量等。站址也只能选择区域内的点。某个点是否被规划基站覆盖可以按如下方法判断：
设选择基站的覆盖范围为d，基站所规划的点的坐标为∶p0（x0，y0），则对于坐标为 P（x，y）的点，若
||p-p0||≤d，则认为该点被该基站覆盖，否则认该点没有被该基站覆盖。
背景分析∶这两段一起来看，这是题目的假设定义，之后都要基于此做任务。这也就是说，比如选的基站为
p0点，一个中心点为p，基站的覆盖范围为一个圆，半径为d，如果两公间的距离小于等于d则覆盖。
同时，实际中还需要考虑一个约束条斜，即新建站址之间以及新建站址和现有站址之间的距离不能小于等于给定门限。

问题一分析∶首先，在看问题一分析之前，大家先看本思路的附1 数据集的分析与签理，然后再来看这道题的分析。
题目中给到的宏基递和微基站的覆盖面积比（简单计算后）为9∶1，而成本为10∶1。门限为10表示已经有的站点到你想新建站点之间的最小距离为10，当一个站点新建后，这个站点应该加入进它有站点的集合之内。在附1    数据集的分析与处理中，给出了3种可行的选址方案和一些可行的可视化方法。
下面是其中其中三种选址方案（现有的最优方案并不淮下面，后续会进行优化改进）
（1）根据业务量多少进行排序，优先考虑业务量多的点，以这一点a为圆心，分别以10和30为非径，将其内所有点划分入可选选址点（这是一个集合）中。建立基站选择模型，给宏基站和微基站达到的业务值分别设立一个阈值，如果超过这一阈值，则选择这个点作为基站，宏基站和微基站哪个超过的阈值百分比高则选择哪种基站。
在选择基站后需要将范围内的点进径剔除，然后再选择合适的。另外，这里要注意一点，建议在选择阈值时，不要给定常量，而是定义一个a的业务量的比例，比如a点业务量为100，则阈值为100*c参这个c就是一个阈值系数，比如200%等，这个系数的确立可以用数学模型建立，最好的方式是在用代碘用不同的阈值仿真后，根据仿真结果给阈值一个合适的范围。
（2）计算出附件1中每一个点为不同站址的收益，得到新的两张表根据收益表放置基站，先计算算所有现有基站的收益，再适当增加基站，满足（复杂度高）
不小于总业务量的90%
基站数尽可能的少，成本尽可能的低......

思路二：

Task1：针对问题一，除了考虑到基站是否可以被覆盖（也就是题目的初步要求，将覆盖程度达到90%以上），着很明显是一个单规划问题，也就是成本最小情况下使得覆盖率以及其他约束条件成立。但是题目真的这么简单吗？我从以下几个创新点入手，进行解析：
创新点1：将以有的数据制作热力图，也就是把信号覆盖程度差的地方用热力图去表示，体现论文可视化程度。这里不仅包括已有基站的覆盖，也有信号缺失区域的情况，作为背景引入。
创新点2：设定目标函数的时候，不仅仅是成本最低，还可以设置类似于“居民宜居性指标”比如覆盖程度的提高程度，或者信号极低的地方的覆盖程度，通过设定max函数，低覆盖信号区域解决的越多，表明效率更好。
创新点3：不仅需要考虑到覆盖区域，还需要考虑到被重复覆盖的区域所带来的成本增加，在设定目标函数还可以设定覆盖重复情况最小的min约束条件。
在满足了以上两点以上的创新度后，通过设定目标函数和约束条件，使得基站覆盖达到要求，目标函数即为：成本最低（如果可以的话，添加第二个目标函数）。约束条件：覆盖广度需要达到90%；不同类型基站的覆盖范围有所差异；基站设定的重复区域应该更小，使用0/1变量表示是否在x、y进行了站点设立。基于已经建立的目标函数与约束条件，鉴于本问题为“图论”经典问题，这里应该采取优化算法进行求解。例如：基础算法有，模拟退火、遗传算法、蚁群算法；进阶算法：帝国竞争算法、布谷鸟算法、灰狼算法、人工鱼群算法，算法类型比较多，选择自己使用过即可，请务必展示算法的收敛程度与部分细节，针对算法的介绍可以多参考文献，但是建议篇幅不要写太长，重点放在论文结果的可视化与实际情况的展示。（通过将实际结果）进行绘图
备注：这里为核心题目，建议写作长度为6-9页。在模型求解板块尽量使用展示多个目标函数下的不同结果，对结果进行区别分析。

Task2：针对问题二，这是一个过渡的题目，其实重点在于约束条件的优化，及基站的覆盖信号不是圆形，而是残缺的圆，这里就需要进一步优化约束条件。并进行重复的运算，求得在多种目标函数的情况下，不同结果的确定。这里有以下两组创新点：
（1） 创新点：用示意图形式，画出问题2所描述的基站的情况，使用visio、process on进行绘制。
（2） 创新点：依然考虑问题一多种情况的目标函数，多种目标函数下的不同结果可以更加印证实际过程中的真实情况，而算法多么“厉害”其实不是本题重点。
在对问题2进行解答，需要注意的是，目标函数和约束条件的展示规范如下图所示：



图1 案例展示（约束条件展示，不是本题结果！）

Task3：针对问题三，这里题目画风突变，进行第覆盖区域聚类，这里基本上可以理解为图论中的商旅行问题，也就是区域的划分，可以理解为每个城市的分区管理。这里需要从两个方面进行创新：
创新点：虽然本次聚类对象是信号区域不好的地方......
更多思路大家可以再MB多上观看：还包括数据处理
D题思路分析：
问题一分析∶首先，在看问题一分析之前，大家先看本思路的附 1 数据集的分析与签理，然后再来看这道题的分析。
题目中给到的宏基递和微基站的覆盖面积比（简单计算后）为    9∶1，而成本为 10∶1。门限为 10 表示已经有的站点到你想新建站点之间的最小距离为    10，当一个站点新建后，这个站点应该加入进它有站点的集合之内。在附 1 数据集的分析与处理中，给出了 3    种可行的选址方案和一些可行的可视化方法。
下面是其中其中三种选址方案
（1）根据业务量多少进行排序，优先考虑业务量多的点，以这一点    a 为圆心，分别以 10 和 30    为非径，将其内所有点划分入可选选址点（这是一个集合）中。建立基站选择模型，给宏基站和微基站达到的业务值分别设立一个阈值，如果超过这一阈值，则选择这个点作为基站，宏基站和微基站哪个超过的阈值百分比高则选择哪种基站。   
在选择基站后需要将范围内的点进径剔除，然后再选择合适的。另外，这里要注意一点，建议在选择阈值时，不要给定常量，而是定义一个    a 的业务量的比例，比如 a 点业务量为 100，则阈值为 100*c 参这个 c 就是一个阈值系数，比如    200%等，这个系数的确立可以用数学模型建立，最好的方式是在用代碘用不同的阈值仿真后，根据仿真结果给阈值一个合适的范围。
（2）计算出附件 1 中每一个点为不同站址的收益，得到新的两张表根据收益表放置基站，先计算算所有现有基站的收益，再适当增加基站，满足（复杂度高）
不小于总业务量的 90%
基站数尽可能的少，成本尽可能的低
现有基站和新建基站之间的最小距离为 10

第二问比第一问又上升一个难度，相当于在       x，y,业务量基础上又加了一个变量，扇区。但是此时，如果细考虑，业务量反而没那么重要，可以退而求其次，因为第一问已经重点考虑业务量问题。所以，如果细分析，这问其实还是三个数据指标，即    x，y, 扇区。（若都考虑，计算量大是肯定的，其次，反而解不出来，干扰思路，需要学会取舍）
其次，问题问的是在最优站址和扇区角度的条件下，新建站能否覆盖弱覆盖点总业务量的       90%。这里显然还是和业务量有关，但是这个业务量更应该是在找到最佳扇区角度的基础上，去评判的一个指标，而不是限制条件，这点要弄明白。无论最终结果是否满足总业务量的       90%，都是可以的，自圆其说即可。只要保证在第一问的基础上，即：先去噪点，然后第一问得到一个最优选址，在这两个基础上考虑扇区，最后计算业务量是多少，然后总结即可，重点是扇区问题。   
最后，分析这个扇区计算问题，这个问题在第一问基础上建模进行，我认为有点偏最优化问题，即还是数学问题，而不是偏图像问题，若重点考虑成图像问题，基本无从下手，因此转换成数学语言去考虑。最优化计算时，目标函数即：最优选址和扇区角度；约束条件包括：......
更多D题思路参考：