基于K-Means聚类算法的应急物流中心选址

Location of Emergency Logistics Center Based on K-Means Clustering Algorithm

摘要: 应急物流中心的选址结果决定了救援运输效率的上限。本文主要讨论的是药品储备集装箱的选址问题。在美国波多黎各飓风袭击的背景下，选取了一系列约束条件，建立对应的数学模型，并通过K-means聚类算法求解，最后比较其与模糊C聚类算法的结果。

Abstract: The location of emergency logistics center determines the upper limit of rescue and transportation efficiency. The paper mainly discusses the location of the medicine storage container. Under the background of hurricane attacking Puerto Rico, a series of constraints are selected, and the corre-sponding mathematical models are established, which are solved by K-means clustering algorithm. Finally, the results of the algorithm are compared with those of fuzzy C clustering algorithm.

1. 引言

自然灾害具有“突发性”这一特点，灾害应急救援的关键在于灾害发生后能快速做出高效反应。由此，及时快捷的灾情相关信息对于及时制定相应的救援策略、提高救援的效率和质量都起着至关重要的作用。无人机航空遥感系统相较卫星遥感以及载人航空遥感而言，具有实时性强、机动灵活、影像分辨率高、成本低等多个特点，且能够在高危地区进行作业 [1]。同时在无人机救援过程中，医疗集装箱的选址优化能够极大提高救援效率。

2. 问题介绍

2017年，美国的波多黎各(Puerto Rico)遭遇最严重飓风袭击。飓风使该岛遭受严重破坏，造成2900多人死亡。狂风暴雨击倒了波多黎各80％的电线杆和所有输电线路，导致基本上所有岛屿都失去了电力。此外，风暴还破坏或摧毁了岛上大部分的蜂窝通信网络。岛上大部分地区的电力和电池服务中断持续数月，而在某些地区则更长。广泛的洪水阻塞并破坏了岛上的许多高速公路和道路，使得紧急服务地面车辆几乎不可能规划和导航他们的路线。波多黎各的数十个地区被孤立，没有通信。

非政府组织(Non-governmental organizations, NGO)经常面临在自然灾害期间或之后提供充分和及时响应的挑战，例如2017年袭击美国波多黎各领土的飓风。一个非政府组织HELPInc计划在波多黎各启动“DroneGo”项目——一个灾难响应系统。“DroneGo”项目计划在该地区放置三个货物集装箱，每个集装箱内包括一定数量的无人机和装有医疗箱的货舱。灾害发生时，无人机从集装箱放置点起飞，搭载货舱将药品送往医院，避险中心等药品需求点或者飞往各个路口搜集道路受损情况，使救援中心第一时间掌握道路信息。

3. 模型建立以及求解流程 [2]

3.1. 建立选址问题的数学模型

已知模型的样本集 $\left\{X\right\}$ 中有n个样本和k个模式分类 $\left\{s_j,j=1,2,\cdots ,K\right\}$ ，以每个样本到聚类中心的距

离之和达到最小为目标，建立聚类问题数学模型如下 [3] ：

$\min {\displaystyle \underset{j=1}{\overset{k}{\sum }}{\displaystyle \underset{x\in s_j}{\sum }{y}_{ij}}}\Vert X-m_j\Vert$ (1)

s.t.

${\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}_{ij}}=1\left(i=1,2,\cdots ,n\right)$ (2)

$m_j=\frac{1}{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}_{ij}}}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}_{ij}}{X}_i\left(j=1,2,\cdots ,K\right)$ (3)

$y_{ij}=\{\begin{array}{l}1\\ 0\end{array}$ (4)

其中

式(1)为目标函数，表示每个样本到聚类中心的距离之和达到最小；

式(2)表示每一模式样本能且只能分配到一个聚类中心上；

式(3)表示求解样本的均值向量公式；

式(4)中y_ij为0~1变量，y_ij取1时，表示样本i分配在j聚类中心上，否则y_ij取0。

3.2. K-Means聚类算法求解流程

K-means算法的求解步骤如下 [4] ：

STEP1：任意选择k个初始的聚类中心为 $c_1,c_2,\cdots ,c_k$ ；

STEP2：逐一将样本集 $\left\{X\right\}$ 中的各个样本按照最小距离的原则分配给k个聚类中心的其中一个 $c_j$ ；

STEP3：由上计算新的聚类中心 ${c^{\prime }}_j=\frac{1}{N_j}{\displaystyle \sum X}\left(j=1,2,\cdots ,k\right)$ ，其中 $N_j$ 表示第j个聚类中心包含的样本个数；

STEP4：如果满足 ${c^{\prime }}_j\ne c_j$ ，转至STEP2；否则即为算法收敛，结束。

4. 实验计算

球面的距离计算公式：设地球上A地在 ${\theta }_1{}^{\circ }$ ，B地在 ${\theta }_2{}^{\circ }$ ，它们的经度之差为 $\alpha$ ， $\alpha \in \left[0,\text{π}\right]$ ，则AB两地的球面距离为：

$d=2R\arccos \left(\cos {\theta }_1\cos {\theta }_2\cos \alpha +\sin {\theta }_1\sin {\theta }_2\right)$

由于地球表面某一点的位置是由经度与纬度来确定的，则只要知道球面上两点的经纬度，就能相应求出该两点间的球面距离。

经过数据处理后，导入各个主要道路和医院的地理经纬度，通过计算机1000次迭代，算法结果收敛，得到三个聚类中心，粗略将其设为医疗集装箱的位置，之后我们将根据救援效率，公平性，居民点，海拔高度，障碍物等多个因素进行深入讨论。

5. 结果分析

以三个聚类点为中心，我们将B型飞机的最大运输距离作为侦察半径。由于集装箱内可能不设充电装置，结合集装箱最大容量所能装载的飞机数目和医疗包数目，我们飞机数目是足够多的(下面在分配医疗配置和无人机机队时会进行详细描述)，因此我们考虑单程情况下，B型飞机的最大运输距离作为可达侦察半径，可以得出下图(见图1)结果。

Figure 1. Results of K-means clustering algorithm

图1. K-means聚类算法的求解结果

为了验证模型的稳定性，我们运用聚类算法初步确定了医疗集装箱的地理位置，采取将K-means聚类和FC聚类方法所得的两个聚类求解结果进行比较(见表1)，可以发现：聚类中心接近，从而判断模型较为稳定。

Table 1. Comparison of clustering methods for geographic coordinates of container location

表1. 集装箱位置地理坐标的聚类方法比较

最终，在K-means聚类下得出三个集装箱选址的地理位置。