1.本发明涉及计算机技术领域，尤其涉及一种基于模拟退火和蒙特卡洛方法的公共设施选址方法。
背景技术：
2.在计算机辅助设计领域，选址技术是指能够从大量数据点位中找出最佳的位置，这就要求有一个高效而精确的算法。目前常用的选址算法有基于随机过程的算法、基于穷举的算法和基于优化的算法，但这三种算法存在以下问题：
3.1、基于随机过程的算法是一种基于概率理论分析的方法，根据资源可用性和性能要求，从重要性和可用性角度来分析数据，最终实现最优选址。这种算法的缺点是于确定性问题转化成随机性问题做的估值处理，会使结果丧失精确性，并且对复杂问题难以建立准确的边界条件。
4.2、基于穷举的算法，通过枚举所有可能的解来寻找最优解。这种方法的优点是简单易懂，实现容易，对于小规模问题可以得到精确解。然而，穷举算法的缺点也很明显，随着问题规模的增大，搜索空间呈指数级增长，计算复杂度非常高，对于大规模问题不适用。
5.3、基于优化算法可以有效实现产品按照自身性能特征最优选址，一般通过采用模拟退火、遗传算法、神经网络等方法，将大量复杂数据简化，从而使算法有效高效地实现。缺点在于算法对参数设置敏感，解释性差，难以保证收敛在最优点。
技术实现要素：
6.本发明提供一种基于模拟退火和蒙特卡洛方法的公共设施选址方法，基于动态人口数据和地理信息数据，选择最佳公共资源设施地址的技术方案，在可控的时间复杂度内利用优化算法，尽可能提高设施选址的准确度。
7.本发明提供一种基于模拟退火和蒙特卡洛方法的公共设施选址方法，包括以下步骤：
8.对地理数据信息进行离散化处理，得到区域网格数据；
9.输入动态人口数据点点位信息，进行人口加权赋值；
10.根据公共设施覆盖范围与规划区域划定搜索范围，进行网格化遍历搜索，得到候选选址点；
11.使用蒙特卡洛法从所述候选选址点计算出最佳候选点集；
12.使用模拟退火方法对所述最佳候选点集进行优化，得到人口距离加权和最小候选点结果集。
13.进一步的，所述对地理数据信息进行离散化处理，得到区域网格数据，具体为：
14.通过地理信息化系统将储存为数据的地理信息转化为目标区域shapefile地图数据；
15.将地图数据文件通过geopandas导入，加载并处理相关数据点至少相对位置、经纬
度、权重的信息；
16.指定地图数据文件的坐标参考系统crs为全球定位系统坐标系epsg:4326，输入空间参考，进行数据标准化；
17.定义地图边界，并设置纵横栅格数量，确定地图生成方式、精度与生成边界条件；
18.绘制生成栅格化地图。
19.进一步的，所述输入动态人口数据点点位信息，进行人口加权赋值，具体为：
20.导入动态人口数据点，并根据人口数量对数据点进行1:1加权赋值,人口越多该数据点权重值越高，在地图网格上得到一系列人口加权质心w1,w2,w3,w4…
。
21.进一步的，所述根据公共设施覆盖范围与规划区域划定搜索范围，进行网格化遍历搜索，得到候选选址点，具体为：
22.以人口数据点为圆心，代表这个点为人口的聚集点，其中的人口数量代表所述聚集点的人口热度，人口数量越多所述聚集点的权重值越高，指定公共设施最大覆盖范围为半径画圆，并剔除圆内部分不可用规划区域，以此为可用规划区域，在可用规划区域的范围内生成搜索区域，并切分成数据网格，对其中数据网格进行遍历，获得包含选址点和其包含的聚集点列表，生成选址候选点集。
23.进一步的，所述使用蒙特卡洛法从所述候选选址点计算出最佳候选点集，具体为：
24.在选址范围内人口权重值之和不超过公共设施容量上限的情况下，记录该情况下的候选点坐标和其覆盖的人口数据点情况，以此得出所有可行的候选点集；
25.以所有候选点集可能的覆盖人口点组合为输入，在每个点上随机取一个能包含他的圆，得到对应圆的随机样本，同时得到所述随机样本的距离权重值；
26.每个点都存在a到b个圆心，基于每个随机样本得到一个近似的面积值，大小为f(xi)*(b-a)，其中f(xi)代表每个样本的面积值，a和b代表着这堆随机样本的前后范围，完成蒙特卡洛积分，得到随机样本的平均结果s，该公式帮助我们理解利用蒙特卡洛积分来实现选址，公式为：
[0027][0028]
进一步推断n个点中每个点采样随机样本，通过均匀分布进行采样得到概率分布，其中θ代表着能得到的最优结果：
[0029][0030]
进一步的，所述使用模拟退火方法对所述最佳候选点集进行优化，得到人口距离加权和最小候选点结果集，具体为：
[0031]
以最优点集组合为输入，使用模拟退火算法进一步优化候选点选位，结合概率突跳特性在解空间中随机寻找目标函数的全局最优，如果新解比当前解更优，则接受新解，否则基于metropolis准则，如果δe《0(新解更优)，则接受新解，将其作为当前解；如果δe》0(新解较差)，则以概率exp(-δe/t)接受新解。生成一个[0,1]之间的随机数r，如果r小于等于exp(-δe/t)，则接受新解，否则，保持当前解不变。其接受概率公式为：
[0032][0033]
其中，p表示迭代概率，kt为系统温度系数，et为上一次迭代系统能量值，et 1位本次迭代系统能量值。
[0034]
本发明实施例采用的上述至少一个技术方案能够达到以下有益效果：
[0035]
1、通过对地理数据信息离散化处理和非确定性问题的分步式建模，利用了射线法的方式，能够解决在现实条件下，需剔除特殊地点等场景，保证了本发明在复杂外部条件下的适用性。
[0036]
2、使用蒙特卡洛法计算可能的选址点组合，极大优化了非确定性问题的计算效率，对比遍历方式极大减少计算时间，可满足大数量的公共资源选址规划需求。
[0037]
3、结合模拟退火算法优化选址点位，保证选址结果的地理覆盖率和公众可及度，防止出现部分地区覆盖度高设施密集的情况。
附图说明
[0038]
此处所说明的附图用来提供对本发明的进一步理解，构成本发明的一部分，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。在附图中：
[0039]
图1为本发明实施例的方法流程图。
[0040]
图2为本发明使用蒙特卡洛法计算出能覆盖全部人口数据点示意图。
[0041]
图3为本发明剔除部分无法让公共设施进行选址的地区的坐标示意图。
具体实施方式
[0042]
为使本发明的目的、技术方案和优点更加清楚，下面将结合本发明具体实施例及相应的附图对本发明技术方案进行清楚、完整地描述。显然，所描述的实施例仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0043]
以下结合附图，详细说明本发明各实施例提供的技术方案。
[0044]
如图1所示。本发明提供一种基于模拟退火和蒙特卡洛方法的公共设施选址方法，包括以下步骤：
[0045]
对地理数据信息进行离散化处理，得到区域网格数据；
[0046]
输入动态人口数据点点位信息，进行人口加权赋值；
[0047]
根据公共设施覆盖范围与规划区域划定搜索范围，进行网格化遍历搜索，得到候选选址点；
[0048]
使用蒙特卡洛法从所述候选选址点计算出最佳候选点集；
[0049]
使用模拟退火方法对所述最佳候选点集进行优化，得到人口距离加权和最小候选点结果集。
[0050]
本发明旨在不超过公共设施最高承载上限的情况下找到公共设施最优建址点，可约化为如下方程：
[0051][0052]
3个方程含义分别为：单个选址圈内人口加权值总和不超过改选址区域承载上限；在能够覆盖所有人口点位的情况下，尽可能选择需要建造公共设施数量最小的i个选址点；在确定需要i个选址点的情况下使得人口数据点人口加权值与人口数据点到公共设施距离的乘积和最小。
[0053]
首先，根据地图比例信息与业务需求，对区域地理信息数据进行离散化处理，将可用规划区域生成为栅格矩阵，操作示例如下：
[0054]
(1)通过地理信息化系统将储存为数据的地理信息转化为目标区域shapefile地图数据；
[0055]
(2)将地图数据文件通过geopandas导入，加载并处理相关数据点相对位置、经纬度、权重等信息；
[0056]
(3)指定地图数据文件的坐标参考系统(crs)为全球定位系统坐标系(epsg:4326)，输入空间参考，进行数据标准化；
[0057]
(4)定义地图边界，并设置纵横栅格数量，确定地图生成方式、精度与生成边界条件；
[0058]
(5)绘制生成栅格化地图。
[0059]
其次，导入动态人口数据点，并根据人口数量对数据点进行1:1加权赋值,人口越多该数据点权重值越高，在地图网格上得到一系列人口加权质心w1,w2,w3,w4…
。
[0060]
以人口质心为圆心，指定公共设施最大覆盖范围为半径画圆，同可用规划区域的并集生成搜索区域，对其中数据网格进行遍历，生成选址候选点，同时对部分特殊地区做规避处理，通过射线法的方式，以目标点为端点引一条射线，计算这条射线和多边形所有边的交点数目。如果交点个数为奇数，则点在多边形部，反之则在多边形外部。通过这个方法，来剔除部分可能无法让公共设施进行选址的地区，结合图3，具体实现过程如下：
[0061]
1.确定一个从点p向右射出的射线，计算该射线与多边形的每条边的交点，并统计交点的个数。
[0062]
2.如果交点的个数是奇数，则点p在多边形内部；如果交点的个数是偶数，则点p在多边形外部。
[0063]
3.在计算交点时，只有当射线与边有交点时才需要进行计算，此时需要判断交点是否在点p的左侧通过向量之间叉积的方式来判断线段之间是否有相关的重合，a和b分别代表一个公共设施对外辐射出去的一个延伸向量，而b代表了一个区域的边界，a和b两个向量叉积的计算公式为
[0064]a×
b＝|a||b|sinθ
[0065]
通过过叉积结果的不同值，我们能确认延伸向量与边界是否产生焦点，判断是否在指定的范围内。
[0066]
伪代码示例如下：
[0067][0068]
接着，在选址范围内人口权重值之和不超过公共设施容量上限的情况下，记录该情况下的候选点坐标和其覆盖的人口数据点情况，以此得出所有可行的候选点集。
[0069]
伪代码如下：
[0070][0071][0072]
然后，以所有候选点集可能的覆盖人口点组合为输入，使用蒙特卡洛法计算出能覆盖全部人口数据点情况下公共区域候选点最少的候选点集组合，这里的蒙特卡洛法是用在每个点都存在有至少一个能包含它的圆，在每个点上随机取一个能包含他的圆，如图2所示，以点1为圆心的圆，包含了点1和点2，
[0073]
每个点都存在a到b个圆心，基于每个随机样本得到一个近似的面积值，大小为f(xi)*(b-a)，其中f(xi)代表每个样本的面积值，a和b代表着这堆随机样本的前后范围，完成蒙特卡洛积分，得到随机样本的平均结果s，该公式帮助我们理解利用蒙特卡洛积分来实现选址，公式为：
[0074][0075]
假设，当前有四个点需要最优方案的计算，得到四个圆的随机样本x1，x2，x3，x4，同时也能得到这四个样本的距离权重值f(x1)、f(x2)、f(x3)、f(x4)。则蒙特卡洛积分为：
[0076][0077]
进一步推断n个点中每个点采样随机样本，通过均匀分布进行采样得到概率分布，其中θ代表着能得到的最优结果：
[0078][0079]
并且当采样点越多，估计值也会越来越接近，也就越接近我们想要得到的最优的圆心方案。
[0080]
伪代码如下：
[0081][0082]
#输出候选点坐标和距离
·
人口的加权和
[0083]
最后，以最优点集组合为输入，使用模拟退火算法进一步优化候选点选位，使得人口加权值乘以相距距离的总和最小，达到效率最优的规划目的。结合概率突跳特性在解空间中随机寻找目标函数的全局最优，如果新解比当前解更优，则接受新解，否则基于metropolis准则，如果δe《0(新解更优)，则接受新解，将其作为当前解；如果δe》0(新解较差)，则以概率exp(-δe/t)接受新解。生成一个[0,1]之间的随机数r，如果r小于等于exp(-δe/t)，则接受新解，否则，保持当前解不变。
[0084][0085]
在上述公式中，p表示迭代概率，kt为系统温度系数，et为上一次迭代系统能量值，et 1位本次迭代系统能量值。举例来说，在迭代过程中，假设开始状态为a，随着迭代次数系统更新到b状态，此时整体系统能量比a要低，则说明接近最优解，因此百分百转移；若状态到达b后，发现下一步能量上升了，而这里会以概率exp(-δe/t)决定是否跳出状态b到达c，并又会继续以一定的概率到达一系列后继状态，最终趋于稳定。获得所需的全局最优的选点信息。
[0086]
这一过程伪代码如下：
[0087]
[0088][0089]
根据随机生成的测试集在实际地图网格中的测试，使用五十个随机的数据点，本算法可以在较短时间内的得出较少且优化选址点位，同时兼顾效率与社会成本：
[0090]
算法类型需要时间结果选址点数量人口距离加权和遍历法8312.7秒215882.09贪心算法312秒343409.12本发明601.2秒225513.85
[0091]
综上，本发明生成尽可能优化的选址方案同时尽可能避免陷入局部最优解，降低选址成本，提高算法设施选址优化算法的效率，所有计算过程在可控的时间内完成；能够适配复杂的地理环境与动态人口数据。例如在选址阶段，可通过控制选址精度，扩大或缩小单次选址的步长，可满足详细或者大致的选址需求；在最终的选址候选点中，通过蒙特卡洛方法将选址输出结果的时间可控并且得到的结果也相对较优，最后退火算法保证选址结果是当前结果全局最优解。
[0092]
以上所述仅为本发明的实施例而已，并不用于限制本发明。对于本领域技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原理之内所作的任何修改、等同替换、改进等，均应包含在本发明的权利要求范围之内。