基于K-Means算法的小区垃圾分类站选址问题研究

潘冯超 刘勤明 史展维 刘靖杰

摘 要：为促进垃圾分类政策实施，科学、合理地在居民生活小区设置垃圾分类站，建立选址模型和成本模型对垃圾分类站建设运营成本及居民满意度负效应成本进行求解，并对K-means聚类算法与模糊C-means聚类算法进行比较。通过对某小区每栋居民楼到垃圾分类站的平均距离分析得出，K-means聚类算法计算得出的平均距离相比模糊C-means聚类算法缩短了约17%，在成本模型中建设运营成本降低了1万元，居民满意度负效应成本降低了0.68万元，验证了模型的可行性及K-means聚类算法的优越性。在未来的研究中可对算法进行改进，以进一步优化成本，确定全局最优。

关键词：垃圾分类;选址优化;K-means聚类;居民满意度负效应

DOI：10. 11907/rjdk. 201315

中图分类号：TP319文献标识码：A 文章编号：1672-7800（2020）010-0102-04

Abstract：In order to promote the implementation of the garbage classification policy， scientifically set up the number of garbage classification stations in the residential quarters， we establish the location model and cost model for the construction and transportation of garbage classification stations. By comparing K-means clustering algorithm with fuzzy C-means clustering algorithm， we find that K-means clustering algorithm is 17% lower than that of fuzzy c-means clustering algorithm. In the cost model， the construction and operation cost is reduced by 10 000 yuan， and the cost of satisfaction negative effect is reduced by 6 800 yuan， which verifies the feasibility of the model and the superiority of the algorithm. It can further improve the algorithm to continue to optimize the cost and determine the global optimization.

Key Words： garbage classification; site selection optimization; K-means clustering; negative effect of residents satisfaction

0 引言

从2019年7月1日起，上海市开始正式施行《上海市生活垃圾管理条例》[1]。根据条例规定，个人和单位必须严格进行垃圾分类投放。居民将按照干垃圾、湿垃圾、可回收垃圾、有害垃圾将垃圾在规定时间段内投放至小区设置的垃圾分类站，垃圾分类站需安排工作人员进行管理，以确保垃圾分类的顺利进行。因此，垃圾分类站数量及选址策略很大程度上会影响居民投放垃圾的便捷性和物业投入的人力及物力成本[2]。在小区内适当位置设定一定数量的垃圾分类站，既可以使居民方便、快捷地投放垃圾，又能大大降低物业管理成本。

垃圾分类站选址对于绿色社区建设具有重要意义。一般而言，选址问题可分为离散型选址问题和连续型选址问题，垃圾分类站选址问题属于离散型选址问题，因此通常采用层次分析法[3]、双层规划分析法[4]和聚类算法[5]等。K-means聚类算法是无监督学习的一种智能算法，多应用于文档聚类[6-7]、设施选址规划[8-9]、机器学习[10-11]等领域。很多学者也对相关问题进行了研究，如栗娜等[12]分析并建立垃圾站选址对居民影响最小化及建设成本最小化双目标优化数学模型，对模型求解得出影响最小且成本最低的解决方案;汤云峰[13]在解决高校快递柜选址问题时，利用重心法结合层次分析法为高校快递柜选址提供参考，但其研究未考虑大规模网点情况;倪训友等[14]研究中国大中型城市停车场选址问题，其建立城市公共停车场双层规划选址模型，但未考虑停车场运维管理对选址的反馈作用;管玉洁等[15]研究应急物流中心选址问题，并对所建立的数学模型运用K-means聚类算法进行求解，但其研究范围过大，导致精度很低;吴红波等[16]研究城镇污水厂选址问题，其建立多目标优化模型，对选址问题进行指标评价分析，但未考虑无法用指标量化的因素;肖玉徽等[17]在解决自取货的物流末端节点选址問题时考虑了客户满意度因素，并运用均值聚类算法对模型进行求解，但未考虑节点建设运营成本因素。

本文基于K-means聚类算法[18]，创新性地引入居民满意度负效应评价指标，构建以垃圾分类站建设运营成本最低与居民满意度负效应最小为目标的选址规划模型，运用相关算法对样本数据进行聚类分析以解决垃圾分类站选址问题，从而为社区物业规划及相关部门制定垃圾分类政策提供参考。

1 问题介绍

垃圾分类问题是城市治理中的一个重要问题[19-20]，实施垃圾分类有利于资源的循环利用以及社会的可持续发展，但目前对于垃圾分类的推广仍存在较大困难。在生活小区内设置垃圾分类站可提高环保部门的垃圾处理效率，但各小区原有垃圾投放点因面积太小，无法在原地建立垃圾分类站，所以需要在更大的场地建立新的垃圾分类站。每个垃圾分类站建设成本由分类站建设初始成本及后期维护成本组成。由于居民垃圾分类意识尚未成熟，难免出现少数居民不愿意进行垃圾分类的情况，需要安排相关工作人员进行监督指导，因此需要花费较高人力成本。科学地在小区适当位置建立垃圾分类站以及合理设置垃圾分类站数量对于垃圾分类政策的顺利实施具有重大意义，同时也是物业相关部门急需解决的问题。

2 垃圾分类站选址模型

2.1 数学模型

在备选的地址集合里，如何选择m个地址，使得每个垃圾分类站的服务范围都能辐射周围住户，并且要求每个住户到该地址的加权平均距离最小是需要重点研究的问题。设模型样本集{X}中有n个样本（即每个住户）和k个分类，以每个样本到聚类中心的加权平均间距最小为目标，其目标函数为：

根据实际情况，每个住户只会去一个垃圾分类站投放垃圾，相当于每个分类住户只会被分配到一个聚类中心，可用数学公式表示为：

2.2 K-Means聚类算法

K-Means聚类算法是一种最常用的基于划分的聚类算法，又称为K-均值聚类算法[21-22]，主要以距离作为相似性评价指标。两个对象距离越近，表示其相似度越大，可将相似度一致的所有对象归并为一个分类。K-Means聚类算法流程如图1所示。

求解步骤如下：

（1）给定大小为n的样本集，选择任意k个聚类中心ck（k=1，2，…，ck）。

（2）将各个样本按照最小距离分配给k个聚类中心的某一个ck，计算每个样本与聚类中心的距离d。

（3）重新计算聚类中心[cj'=1NjX（1，2，…，k）]，[ Nj]表示第j个聚类中心包含的样本个数。

（4）若[c'j≠cj]，则转至步骤（2），否则输出结果。

3 垃圾分类站选址成本模型

3.1 模型架构

（1）总成本最小模型。在小区垃圾分类站建设中，应重点分析建立垃圾分类站的固定投资成本及后期维护成本，这两个成本是垃圾分类站建设的主要成本。

（2）居民满意度负效应最小模型。由于垃圾分类站可能导致蚊虫增多、异味增加，对居民生活造成一定负面影响，导致居民对小区物业管理满意度下降。所以物业部门在建设垃圾分类站时需要考虑地址及垃圾分类站容量等因素，实现居民满意度的负效应最小。

3.2 参数定义

相关参数定义如下：

i：表示第i个住户（i=1，2，…，n）。

m：表示第m个垃圾分类站（m=1，2，…，M）。

[Cmq]：表示建立第m个垃圾分类站的固定成本，垃圾分类站容量为q。

[qi]：表示住户i平均每天投放的垃圾量。

[qm]：表示第m个垃圾分类站每天接收的垃圾总量。

[Cβ]：表示单位垃圾的人工维护成本。

[Dim]：表示住户i到垃圾分类站m的距离。

[Qm]：表示第m个垃圾分类站的设计容量。

[Yim]：0～1变量，当[Yim=1]表示住户i投放垃圾至垃圾分类站m处。

[Xmq]：0～1变量，当[Xmq=1]表示在m点建立容量为q的垃圾分类站。

[θ ω φ]：居民满意度负效应影响系数。

3.3 目标函数

总成本最小目标函数为：

居民满意度负面效应最小目标函数为：

每个住户的垃圾只会投放到一个最近的固定垃圾分类站：

一个地址只能建立一个容量为q的垃圾分类站：

因每个住户投放垃圾的总和不能超过垃圾分类站容量，垃圾分类站容量约束为：

决策变量约束为：

4 案例分析

4.1 选址模型案例分析

根据建立的小区垃圾分类站选址模型，以上海某小区为例对模型进行验证。根据物业管理处给出的历史数据计算出该小区需要设置6个垃圾分类站，经过数据处理后，将小区平面图放在一个二维直角坐标系中，如图2所示。该小区共有33栋楼，将小区内每栋楼的坐标导入计算机，经过1 000次迭代计算后得到6个聚类中心，粗略将这6个坐标设为垃圾分类站坐标。

为验证算法的稳定性，本文选取模糊C-means聚类算法与K-means聚类算法进行比较，得到两个聚类结果如表1所示。

根据表1的比较结果可得出结论，通过K-means聚类算法得出的6个垃圾分类站距各所属楼栋平均距离相比模糊C-means聚类算法计算出的平均距离缩短约17%左右，约为41m。各楼栋到垃圾分类站平均距离越小，说明居民投放垃圾越方便，居民满意度将越高，由此可得出K-means聚类算法的优越性。

4.2 成本模型案例分析

根据建立的垃圾分类站选址模型，小区内共建立6个垃圾分类站，假设小区每栋楼每天产生的垃圾量固定为0.5m3，建造费用及维护费用为1.5万元/m3，单位垃圾的人工维护成本为0.5万元/m3，居民满意度负效应影响系数[θ、 ω、φ]分别取0.2、0.3、0.5。采用K-means与C-mean两种算法，其中通过K-means聚类算法得出的垃圾分类站相關数据如表2所示，通过模糊C-means聚类算法得出的垃圾分类站相关数据如表3所示。

确定每栋楼平均每天产生的垃圾量以及6个垃圾分类站容量，结合选址模型中的数据，根据相关公式计算垃圾分类站花费总成本及居民满意度负效应成本如下：

根据以上结果对比可知，通过K-means聚类算法求出的最小总成本为38万元，比模糊C-means聚类算法求出的最小成本低1万元，居民满意度负效应成本为4.82万元，比模糊C-means聚类算法低0.68万元，由此证明了模型的可行性以及K-means聚类算法的优越性。

5 结语

实行垃圾分类对于推动资源循环利用以及社会可持续发展具有十分重要的意义。本文研究小区垃圾分类站选址问题，在构建模型时考虑了居民投放垃圾的便捷性与垃圾分类站的建造及维护成本，以及居民满意度负效应成本。最后通过实际案例分析，验证了模型的可行性及K-means聚类算法的优越性，可为社区物业规划及相关部门制定垃圾分类政策提供参考。在未来研究中，可对算法进行改进，以进一步优化成本，确定全局最优。另外，垃圾分类站动态选址问题可作为下一步研究重点。

参考文献：

[1] 王霁. 生活垃圾管理条例7月1日起施行[J].  上海人大月刊， 342（2）：23-24.

[2] 罗楠.  上海生活垃圾分类治理模式探索[J]. 城乡建设， 2019， 563（8）：18-21.

[3] 周振钊. 应用层次分析法对某垃圾填埋场规划选址进行分析[J].  西部资源， 2019， 88（1）：163-164.

[4] 张晨，刘勤明，叶春明，等. 双层规划下考虑环境侵害的垃圾分拣中心选址研究[J/OL]. 计算机应用研究：1-6[2020-05-29]. https：//doi.org/10.19734/j.issn.1001-3695.2019.09.0525.

[5] TANG J L，WANG D，ZHANG Z G，et al. Weed identification based on K-means feature learning combined with convolutional neural network[J]. Computers & Electronics in Agriculture，2017，135：63-70.

[6] HABIB S T，ZAHID A. An analysis of MapReduce efficiency in document clustering using parallel K-means algorithm[J].  Future Computing & Informatics Journal， 2018，3（2）：200-209

[7] LI W，FENG Y，LI D，et al. Micro-blog topic detection method based on BTM topic model and K-means clustering algorithm[J].  Automatic Control & Computer Sciences，2016， 50（4）：271-277.

[8] 劉伟，张弈鹏，罗凤鸣. 基于改进K-means算法的多场景分布式电源规划[J]. 吉林大学学报（信息科学版）， 2018， 36（5）：43-48.

[9] 鲁玲岚， 秦江涛.  基于改进的K-means聚类的多区域物流中心选址算法[J]. 计算机系统应用，2019，28（8）：251-255.

[10] TANG J L，WANG D，ZHANG Z G，et al. Weed identification based on K-means feature learning combined with convolutional neural network[J].  Computers & Electronics in Agriculture，2017，135：63-70.

[11] TANG J L，ZHANG Z G，WANG D，et al. Research on weeds identification based on K-means feature learning[J].  Soft Computing， 2018（22）：7649-7658.

[12] 栗娜，李珍萍. 垃圾站选址问题的数学模型及应用[J].  物流技术，2011，30（12）：135-137.

[13] 汤云峰. 基于重心法和层次分析法的高校快递智能柜选址布局问题研究[J]. 山东科学，2019，32（3）：65-72.

[14] 倪训友， 孙健.  城市公共停车场选址双层规划模型[J]. 城市交通， 2019， 17（2）：114-118.

[15] 管玉洁，徐迅，黄雅娟，等. 基于K-Means聚类算法的应急物流中心选址[J]. 理论数学，2019，9（7）：809-812.

[16] 吴红波， 杨肖肖， 王国田.  基于多目标优化模型的城镇污水处理厂选址分析[J]. 地理空间信息，2019，17（12）：42-46.

[17] 肖玉徽， 楼振凯.  考虑客户满意度的物流末端节点选址模型及算法[J].  工业工程， 2019（3）：126-131.

[18] 杨俊闯，赵超. K-Means聚类算法研究综述[J]. 计算机工程与应用，2019，55（23）：7-14，63.

[19] 汪中求.  垃圾分类背后的真相[J]. 企业管理，2019（8）：25-27.

[20] 赵丁仪. 建筑垃圾处理厂的选址决策研究[D].  南宁：广西大学， 2017.

[21] PHAM D T，DIMOV S S，NGUYEN C D. Selection of K in K-means clustering[J].  Proceedings of the Institution of Mechanical Engineers Part C Journal of Mechanical Engineering Science， 2005， 219（1）：103-119.

[22] HARTIGAN J A， WONG M A. A K-means clustering algorithm[J].  Applied Statistics， 2013， 28（1）：100-108.

（责任编辑：黄 健）