基于需求密度感知与GNG的移动设施动态选址方法

Mobile Facilities Dynamic Location Based on Demand Density Perception and GNG

摘要: 针对社会设施的动态选址问题，本文提出一种基于需求密度感知和Growing Neural Gas Networks (GNG)的设施动态选址方案。该方法主要有以下三方面，第一、对区域进行划分；第二、获取区域的资源需求密度，并对低密度区域进行过滤；第三：基于区域的需求密度对有限的信息资源进行合理分配。本文方法与Kmeans进行了对比，实验结果表明所提方法可有效对区域需求进行拓扑感知，并可对有限的可移动设施进行合理性规划。

Abstract: For the problem of facilities dynamic location, a method based on demand density perception and growing neural gas networks (GNG) was proposed. This method can be organized into three parts: firstly, divide the region into many unit areas; secondly, obtain the demand density of each unit area and filter out the areas with low-density; thirdly, allocate the limited information resources reasonably based on the demand density. An experiment comparison with Kmeans was done. The results show that the method proposed can effectively realize the topological perception of regional demand, and can reasonably plan the limited mobile facility dynamic.

1. 引言

社会资源规划所涉范围极其广泛，从城市、产业带、经济技术开发区、跨国经济集团分公司到机场、水利设施、人类居住区、销售网点以及仓库、配送中心等的区位决策都是选址问题研究的范畴，涉及经济、政治、社会、管理、心理及工程地质等多门学科。设施指与生产、商业流通及人类生活有关的具体网点。在该问题中，有两类模型，第一类是单设施选址，有中值模型 [1]、树状网模型 [2] [3] [4]、需求不确定模型 [5]、马尔科夫模型 [6]、需求随机增长模型 [7]，基于背包问题以及随机排列的模型 [6] [7] [8] [9] [10]，基于成本期望最小的方法 [11] [12] [13] 等。这些模型将区域资源等问题考虑考虑了进去，但是不能解决多设施的选址问题。随着城市效应不但扩大，更多目光聚焦于多设施的科学选址，大概可分为以下三类：最优化方法 [14] [15] [16] [17]，此类方法是将区域的连续性作为约束条件，运用线性最优化算法得出最优解，可是此类方法会忽略部分最优解，并且当涉及非线性、多目标问题的时效果较差。智能类算法 [18] [19] [20] [21]，主要有遗传算法(Genetic Algorithm: GA)、模拟退火算法(Simulated Annealing: SA)、蚁群算法(Ant Colony Optimization: ACO)等算法模型，算法模型可在启发式的引导下得到近似最优解，这些方法中蚁群算法具有较强的自组织性、鲁棒性以及可进行分布式计算等特征，但是该类型方法当数据点较多时时间复杂度较高，运行效率有待于提高。聚类算法 [22] [23] [24] [25] [26]，此类算法以Kmeans为主，先把在一个区域内建多个设施问题转化为在多个区域内分别建设单一设施的问题，然后利用重心法确定各子区域设施的具体位置，但是该类问题容易造成子区域的选址结果，可能使得多个节点重合。

以上方法无论单设施选址还是多设施选址方法，设施一旦建设后就不能再移动，可是随着智慧城市的不断建设，区域变化不断加剧，这就使得可移动设施越来越受到关注，即，如何根据短期的资源需求对移动设施的方位进行调整，所以本文提出一种基于需求密度感知与Growing Neural Gas Networks (GNG) [27] 的移动设施动态选址方法，如图1所示，该方法用有限的感知单元对学习目标进行集合拓扑感知，对整个城区可移动设施资源的需求进行实时检测与分析，对有限的移动设施资源进行区域部署，从而达到节约资源的目的。本文方法首先将某区域划分为单位网状结构，统计每个单位区域内在单位时间内对可移动设施资源的需求次数和时间长度，依据阈值确定是否在该区域设置需求点，然后通过Delaunay算法对需求点进行紧邻分析，去除连接密度较低的需求点；最后基于GNG算法对剩余的点进行几何拓扑感知从而得到移动设施的区域部署。在实验中本文方法与聚类方法Kmeans进行了对比。

Figure 1. Algorithm flow chart

图1. 算法流程图

2. 方法

2.1. 需求密度的过滤

Figure 2. Communication density of an area

图2. 某区域的通信密度

在本文中，需求密度为单位区域内每次可移动设施的使用持续时间(s)之和。例如，某单位区域的面积为100*100 m，若某月在该区域内共发生N次需求，而每次需求中可移动设施的使用持续时间为 $T=\left\{t_1,t_2,\cdots ,t_N\right\}$，则该区域的可移动设施资源的需求密度 $\rho$ 为：

$\rho ={\displaystyle \underset{i=1}{\overset{N}{\sum }}{t}_i}$ (1)

图2中有9个单位区域的需求密度，若将1000设定为阈值，经需求密度过滤后如图3所示。

Figure3. The filtered result in Figure 2

图3. 在图2中经需求密度过滤

2.2. 三角剖析(Delaunay)

Delaunay [28] [29] 又称为三角剖析，它用三角链接将点与紧邻点连接：首先，遍历所有点，得到集合中的包盒，并将集凸壳的初始三角形置入三角形的链表中；然后，集合中的点依次插入，在链表中找到外接圆中插入点的三角形，并删除有影响的公共边，插入点与三角形顶点连接；再次，优化新的三角形，并将新的三角形放入到链表中；最后，返回到第二步直到所有点都插入为止。

2.3. 稀疏点过滤

第一：计算连接点之间的距离：

$\begin{array}{l}{D}_1:d_1^1\cdots d_{n1}^1\\ D_2:d_1^2\cdots d_{n2}^2\\ \cdots \\ D_m:d_1^m\cdots d_{nm}^m\end{array}$ (2)

其中， $D_i$ 为拓扑空间中的第i个点， $i=1\cdots m$， $m$ 为点的数量， $d_j^i$ 为第i个点中第j个连线的长度，其中 $j=1\cdots n_i$， $n_i$ 为第i个点与之相连点的数量。

第二：每个点与相邻点的均值距离：

${\bar{D}}_i={\displaystyle \underset{j=1}{\overset{n_i}{\sum }}{d}_j^i/n_i}$ (3)

第三：所有点与相邻点均值距离的概率分布密度：

${\displaystyle \underset{i=1}{\overset{m}{\sum }}{p}_i}=1$ (4)

$p_i=k_i/m$ (5)

$k_i=sum\left(\max \left(\bar{D}\right)\ast \left(i-1\right)/m<\bar{D}<\max \left(\bar{D}\right)\ast \left(i+1\right)/m\right)$ (6)

第四：需求点若保留需满足的条件：

${\displaystyle \underset{i=1}{\overset{m_1}{\sum }}{p}_i}\le T_{dot}$ (7)

其中 $T_{dot}$ 为阈值，本文中设定为0.9。

2.4. 基于GNG的拓扑分布感知

GNG (Growing Neural Gas Network)于1995年由Bernd Fritzke等人提出，算法用“Hebb-like”原则 [30] 和有限感知单元学习目标的重要拓扑特征，与其他拓扑学习方法相比主要优势在于算法在不断的学习中不需要参数，能以增量的形式不断的加入学习单元直到达到终止条件为止，这与“生长细胞结构”模型(Fritzke, 1994b) [31] 中使用的方法相同，然而“生长细胞结构”模型具有固定维度(例如，两个或三个)的拓扑。并且相比Growing Cell Structures模型 [31] 只能选用二维和三维的拓扑维度，GNG的维度由输入数据的维度决定，并且输入的数据之间可以是不同维度的形式。算法细节可参考文献 [27]。

3. 对比实验

为验证本文所提方法的有效性，一地区如图4所示，该地区在初始阶段有三个人口聚集区，A、B和C，由于人口聚集区对于资源的需求较大，所以资源需求密度比其他区域稠密。现在开始对该地区进行规划，为了避开人口聚集区，在区域A、B和C的中间区域建立新城区，新城区的建设分为起步期，发展中期以及发展成熟期三个阶段，现模拟不同时期用不同数量的移动资源设施分别用本文方法与Kmeans进行感知。

Figure 4. The initial stage of an area

图4. 某区域初始阶段

根据城市建设发展趋势，新区应以高新技术企业为主，企业需要一定数量的劳动力，所以会建设办公地点和生活社区，可将该区域的发展时期分为三个阶段：初期、中期、成熟期，如图5所示，现在对需求密度进行过滤(Tdot = 0.85)，然后分别基于GNG和Kmeans方法用50和100个感知点对需求密度进行拓扑感知，感知点相当于有限的移动设施，图6~8所示。从中可以看出，无论在任何时期，本文所提方法可有效感知新城区的资源需求，并可有效对该区域部署一定数量的移动设施。观察Kmeans可发现，由于缺乏需密度的过滤，在整个区域都有移动资源的部署，这样会使得人少区域部署部分移动资源造成资源的浪费，在观察发展初期和中期，Kmeans在新区部署的移动设施不明显，但是在成熟时期由于新区的人口数量增加，资源的需求密度也有所增加，基于Kmeans方法在新区移动资源的部署有所显著。所以综上所述，本文所提方法可有效感知资源需求，对可移动资源进行有效部署。

(a) 初期 (b) 中期 (c) 成熟期

Figure 5. Three stages of development

图5. 三个发展阶段

(a) 本文方法(n = 50) (b) 本文方法(n = 100) (c) Kmeans (n = 50) (d) Kmeans (n = 100)

Figure 6. Initial stage of development

图6. 发展起步阶段

(a) 本文方法(n = 50) (b) 本文方法(n = 100) (c) Kmeans (n = 50) (d) Kmeans (n = 100)

Figure 7. Intermediate stage of development

图7. 发展中期阶段

(a) 本文方法(n = 50) (b) 本文方法(n = 100) (c) Kmeans (n = 50) (d) Kmeans (n = 100)

Figure 8. Mature stage

图8. 发展成熟阶段

4. 结论

为解决可移动设施的动态选址问题，本文提出了一种基于需求密度拓扑感知的动态布选址方法，该方法主要由以下三步构成：首先，将需求划分为网状结构，在每个单位区域中统计单位时间中可移动设施的需求次数和使用时间，根据阈值确定单位区域的需求点是否保留，然后根据Delaunay算法将所有需求点与紧邻点进行连接，去除连接密度较低的点；最后根据GNG算法对过滤后的需求点进行几何拓扑感知从而得到可移动设施的布点。对比实验表明本文所提方法可根据可移动设施需求密度分布对有限数量的可移动资源进行有效部署。

基金项目

河北省自然基金项目(F2018207038)；河北省重点研发计划项目(17216108)；河北省教育厅项目(QN 2020186)。