基于Voronoi理论的维修站点选址算法研究

Research on Maintenance Site Location Algorithm Based on Voronoi Theory

摘要: 选址问题涉及各行各业，在智能维修管理过程中，企业花费在产品售后维修的成本比例越来越高。对于大型的企业，需要在某城市建立维修站来更有效地进行售后维修。维修站点的科学选址有助于企业减少维修成本。Voronoi理论经常被应用于覆盖问题的研究。本文针对维修站点的地址选择问题，将Voronoi理论引入到站点选址问题研究中，提出一种基于Voronoi图的维修站点选址算法，以建立最少的维修站来获得预定的服务质量，从而在服务质量的约束下最小化维修站点个数，减少了维修成本。仿真证明了算法的有效性。

Abstract: The site selection problem is important in many areas. In intelligent maintenance management, the cost for after-sales maintenance increases gradually. For large enterprises, it is necessary to establish some maintenance stations in a city to carry out after-sale maintenance more effectively. Scientifically choosing the address of a maintenance site helps businesses reduce maintenance costs. Voronoi theory is often applied to the study of covering problems. In order to solve the selection problem for the maintenance site, this paper presents a site selection algorithm based on Voronoi diagram. The algorithm can obtain the predetermined service quality with minimum maintenance stations. It minimizes the number of maintenance sites under the constraint of service quality and it reduces the maintenance cost. Simulation results show that the algorithm is effective.

1. 引言

随着设备复杂程度的增加，现代化企业越来越重视智能维修管理在企业运营中的作用 [1] 。智能维修管理包含：维修成本模型定义与管理、维修任务的确定、维修策略评估、备件库存管理、售后服务模型建立与管理等 [1] 。现代化企业也越来越认识到高额的维修费用是影响企业效益增长的主要问题之一 [2] ，从而需要智能化的维修管理策略来最小化维修消耗。智能维修策略已经在许多领域中得到深远地发展，如医疗 [3] [4] [5] 、工业 [6] [7] [8] 、民航 [9] 、农业、交通等等。

选址问题研究涉及各行各业，为了最小化成本，取得最大的效益，科学的选址策略是必不可少的。设施选址问题，即合理地布置设施，一方面建立尽可能少的设施以节约成本，另一方面充分利用设施实现期望的目标，提高任务完成效率。选址问题的研究涉及各个行业，如针对设施选址问题的研究：钟慧玲等 [10] 对危险品道路运输过程中，应急设施选址问题进行了研究。利用场景方法，提出一个目标分层的 $\sigma$ ——鲁棒的弧段覆盖模型，该算法需进行场景假设，具有不确定性。李彤等 [11] 以模拟植物生长算法为工具，提出了一种解决设施选址问题的智能优化算法。针对不确定环境下的城市配送中心选址问题的研究：赵娜等 [12] 采用AHP法和模糊算法相结合提出了一种配送中心选址算法，文中将层次分析法的定量性和客观性的优点与模糊综合评价法的包容性有机融合。郭文昌等在文中 [13] 提出了一种改进的蚁群算法，首先通过遗传算法求得问题的较优解，然后再将此较优解转换为改进蚁群算法的初始信息进行优化求值而得到最优解。网络基站选址优化问题研究中，马宝罗等 [14] 和李道国等 [15] 提出了基于免疫算法的基站选址算法研究；韩江洪等 [16] 则提出一种动态规划方法进行基站选址问题的研究。针对风电场选址问题研究中：仲炜等 [17] 针对由于地形对风速影响而造成的常用风电场选址设计软件评估结果的不准确性,提出一种基于GIS空间分析的风电场选址算法。许昌等在专利 [18] 公开了一种基于CFD和改进PSO的复杂地形风电场微观选址方法。

以上各种选址问题的研究，多使用遗传算法、蚁群算法和模拟退火算法等智能优化算法，将Voronoi算法用于维修站点选址问题的研究，是售后智能管理的一次探索和尝试。

Voronoi图是计算几何的重要研究对象之一 [19] 。它按照对象集合中元素的邻近属性将空间划分成许多互不重叠单元区域，即Voronoi区域 [20] ，根据对象的Voronoi区域是否邻接，可以清晰地识别对象间的邻接关系。Voronoi图包含全部的空间邻近信息。广泛被应用在定性空间推理研究 [21] 、机械工程、虚拟现实、机器人、图形图像处理 [22] [23] 、CAD等领域，也是解决距离计算、碰撞检测、路径规划、无线传感器网络覆盖与定位研究 [24] 、产品供应链、配电网供电分析 [25] 等的重要方法之一。

在产品售后服务管理中，维修站点的选址会直接影响到维修人员的服务效率和维修费用。产品售出后，企业需负责产品的售后维修，当售出产品数量较多时，需要选择合适的位置来建立维修站，多年来，维修站点的选址是人工进行，站点选址不科学，从而造成成本的浪费。针对这种问题，本文提出一种基于Voronoi图的维修站点选址算法，在算法中，根据售出产品的密集程度，采用Voronoi图方法，选择最优的位置建立维修站点，使得建立最少的站点获取最大的产品覆盖率。

2. 定义与定理证明

2.1. 定义

在500 × 500的正方形区域中部署了边界点和初始点，其相应的Voronoi图如图1，图中各元素的定义 [26] 如下：

• 维修人员服务区域

假设维修人员需要上门维修，但是由于时间和交通的限制，维修人员的服务范围限制在某个圆形区域内。

• 点的Voronoi区域

图1中A、B、C、D、E、F、G是已有的维修站点，深色区域中的任意点到节点A的距离小于到邻近节点的距离，深色区域称作A节点的Voronoi区域。

• Voronoi边

两个相邻节点的Voronoi区域相交于一个线段，该线段称之为Voronoi边。节点A和F之间的Voronoi边被称作 $AF$ 的Voronoi边。

• 邻近节点

两个节点的Voronoi区域相邻，且区域之间存在一条公共voronoi边，这两个点称为邻近节点，如图1中节点B、C、D、E、F是节点A的邻近节点，从而A节点的Voronoi区域有5个边。

• Voronoi图交点

Voronoi图中邻近节点的voronoi边相交的点称为Voronoi交点，一个Voronoi交点连接至少两个Voronoi边。

2.2. 定理与证明

图2中，A和F是两个邻近节点，线段 $MN$ 是的Voronoi边，节点M和N是线段 $MN$ 的两个端点，被标记为菱形的 $X$ 点是线段 $MN$ 上的任意一点。

• 定理1：

Voronoi边上的任意一点到相邻两个节 $A$ 和 $F$ 的距离相等 [27] 。

• 定理2：

线段 $MN$ 与节点 $A$ 和 $F$ 的连线 $AF$ 相垂直，且垂直平分线段 $AF$ 。

Figure 1. Voronoi map

图1. Voronoi图

Figure 2. Theorem proof

图2. 定理证明

由定理1，可知：

$MA=MF$ (1)

$OA=OF$ (2)

所以可推出：

$\Delta MAO\cong \Delta MFO$ (3)

从而得到

$\angle MOA=\angle MOF={90}^{\circ }$ (4)

• 定理3：

在线段 $MN$ 上，到节点 $A$ 或 $F$ 的距离最近的点是 $O$ 点；最远的点是线段 $MN$ 的两个端点，即 $M$ 点或 $N$ 点。

已知相同的两个圆的中心点越远，两个圆重叠的面积越小。又知图2中 $M$ 点分别是线段 $MN$ 、、 $MD$ 的端点。从而由定理3可推出：在 $M$ 点建立新的圆(即维修站点)，与邻近的圆(站点)的覆盖重叠面积最小，也就是增加的覆盖面积最大。

3. 选址算法

假设 $500\text{m}\times 500\text{m}$ 区域为目标区域。某产品在该区域进行销售，由于销售产品数量的增加，需要建立维修站点来对用户所买产品进行上门维修。

• 初始点的确定

首先为了避免voronoi图的发散，给出一些边界点进行预先部署。接下来在目标区域中进行随机地循环搜索，选出与已有节点没有覆盖重叠的位置，分别计算这些位置对已售出的产品增加的覆盖率，选择出增加覆盖率最大的位置作为新的维修站点。循环 $n$ 次，完成初始点的部署。

• 初始点voronoi图的构造

初始点被确定后，构造基于初始点和边界点的voronoi图。记录voronoi图各种信息。

• 新站点的确定

将图中的各voronoi边的端点提取出来存放到待选集合中，分别计算包含销售产品的个数(产品地址到该节点的距离)，计算该节点增加产品覆盖个数，选择增加个数最多的点作为新的站点地址。

• 重复增加节点

重复上一个步骤，直到产品覆盖率达到预定目标。从而达到了建立最少的维修站点获取了预定覆盖率目标。

4. 仿真

假设产品数量为100，产品用户覆盖率目标为85%，维修人员服务区域半径为60 m，进行算法的仿真，仿真结果如图3~图13。

图3显示了售出产品的地址，算法目标则是建立最少的维修站点达到对产品的覆盖率目标为85%。

由于初始选址中，只要依次选则最大覆盖率、且没有覆盖重叠的节点就能获得以最少的节点达到最大的产品覆盖率的目标，如图4显示。图4中是最初的完全没有覆盖重叠的初始点的选址情况，并建立了相应的Voronoi图。

如图4显示，由定理2、3证明可知，在图中某个Voronoi交点处部署新站点和其他邻近站点的覆盖重叠最小，依照算法，从所有Voronoi交点中选择能最大增加覆盖率的Voronoi交点最为新的站点，也就是所有Voronoi交点中能覆盖新的产品节点个数最多的交点作为新站点。如图5。

依次重复上述选址方法，图6~图13依次显示了算法执行步骤2至步骤9地址选择情况：

经过9步，产品覆盖率就达到了产品用户覆盖率目标85%。算法执行简单，效率高，达到了建立最少站点获得要求覆盖率的目标。

Figure 3. User random distribution

图3. 产品用户随机分布

Figure 4. Initial deployment, coverage is 52%

图4. 初始点部署，产品覆盖率为52%

Figure 5. The 1th step, the coverage is 60%

图5. 第1步，产品覆盖率为60%

Figure 6. The 2th step, the coverage is 65%

图6. 第2步，产品覆盖率为65%

Figure 7. The 3th step, the coverage is 69%

图7. 第3步，产品覆盖率69%

Figure 8. The 4th step, the coverage is 73%

图8. 第4步，产品覆盖率73%

Figure 9. The 5th step, the coverage is 76%

图9. 第5步，产品覆盖率76%

Figure 10. The 6th step, the coverage is 79%

图10. 第6步，产品覆盖率为79%

Figure 11. The 7th step, the coverage is 82%

图11. 第7步，产品覆盖率为82%

Figure 12. The 8th step, the coverage is 84%

图12. 第8步，产品覆盖率为84%

Figure 13. The 9th step, the coverage is 86%

图13. 第9步，产品覆盖率为86%

5. 结束语

在文中，作者提出一种基于Voronoi图的维修站点选址算法，算法中循环找出最大覆盖率增长点来确定新维修站点，以达到建立最少的维修点获得最大的产品覆盖率的目的。

基金项目

校博士后启动基金(20142023)；国家自然科学基金(61701122)；中国广东自然科学基金(2016A030313734)；广州市科技项目(201804010238)；广东省应用重点工程(201604020016)。

参考文献

NOTES

*通讯作者