基于K-Means算法的小區(qū)垃圾分類站選址問題研究

潘馮超 劉勤明 史展維 劉靖杰

摘 要：為促進垃圾分類政策實施，科學、合理地在居民生活小區(qū)設置垃圾分類站，建立選址模型和成本模型對垃圾分類站建設運營成本及居民滿意度負效應成本進行求解，并對K-means聚類算法與模糊C-means聚類算法進行比較。通過對某小區(qū)每棟居民樓到垃圾分類站的平均距離分析得出，K-means聚類算法計算得出的平均距離相比模糊C-means聚類算法縮短了約17%，在成本模型中建設運營成本降低了1萬元，居民滿意度負效應成本降低了0.68萬元，驗證了模型的可行性及K-means聚類算法的優(yōu)越性。在未來的研究中可對算法進行改進，以進一步優(yōu)化成本，確定全局最優(yōu)。

關鍵詞：垃圾分類;選址優(yōu)化;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]。根據(jù)條例規(guī)定，個人和單位必須嚴格進行垃圾分類投放。居民將按照干垃圾、濕垃圾、可回收垃圾、有害垃圾將垃圾在規(guī)定時間段內投放至小區(qū)設置的垃圾分類站，垃圾分類站需安排工作人員進行管理，以確保垃圾分類的順利進行。因此，垃圾分類站數(shù)量及選址策略很大程度上會影響居民投放垃圾的便捷性和物業(yè)投入的人力及物力成本[2]。在小區(qū)內適當位置設定一定數(shù)量的垃圾分類站，既可以使居民方便、快捷地投放垃圾，又能大大降低物業(yè)管理成本。

垃圾分類站選址對于綠色社區(qū)建設具有重要意義。一般而言，選址問題可分為離散型選址問題和連續(xù)型選址問題，垃圾分類站選址問題屬于離散型選址問題，因此通常采用層次分析法[3]、雙層規(guī)劃分析法[4]和聚類算法[5]等。K-means聚類算法是無監(jiān)督學習的一種智能算法，多應用于文檔聚類[6-7]、設施選址規(guī)劃[8-9]、機器學習[10-11]等領域。很多學者也對相關問題進行了研究，如栗娜等[12]分析并建立垃圾站選址對居民影響最小化及建設成本最小化雙目標優(yōu)化數(shù)學模型，對模型求解得出影響最小且成本最低的解決方案;湯云峰[13]在解決高?？爝f柜選址問題時，利用重心法結合層次分析法為高?？爝f柜選址提供參考，但其研究未考慮大規(guī)模網(wǎng)點情況;倪訓友等[14]研究中國大中型城市停車場選址問題，其建立城市公共停車場雙層規(guī)劃選址模型，但未考慮停車場運維管理對選址的反饋作用;管玉潔等[15]研究應急物流中心選址問題，并對所建立的數(shù)學模型運用K-means聚類算法進行求解，但其研究范圍過大，導致精度很低;吳紅波等[16]研究城鎮(zhèn)污水廠選址問題，其建立多目標優(yōu)化模型，對選址問題進行指標評價分析，但未考慮無法用指標量化的因素;肖玉徽等[17]在解決自取貨的物流末端節(jié)點選址問題時考慮了客戶滿意度因素，并運用均值聚類算法對模型進行求解，但未考慮節(jié)點建設運營成本因素。

本文基于K-means聚類算法[18]，創(chuàng)新性地引入居民滿意度負效應評價指標，構建以垃圾分類站建設運營成本最低與居民滿意度負效應最小為目標的選址規(guī)劃模型，運用相關算法對樣本數(shù)據(jù)進行聚類分析以解決垃圾分類站選址問題，從而為社區(qū)物業(yè)規(guī)劃及相關部門制定垃圾分類政策提供參考。

1 問題介紹

垃圾分類問題是城市治理中的一個重要問題[19-20]，實施垃圾分類有利于資源的循環(huán)利用以及社會的可持續(xù)發(fā)展，但目前對于垃圾分類的推廣仍存在較大困難。在生活小區(qū)內設置垃圾分類站可提高環(huán)保部門的垃圾處理效率，但各小區(qū)原有垃圾投放點因面積太小，無法在原地建立垃圾分類站，所以需要在更大的場地建立新的垃圾分類站。每個垃圾分類站建設成本由分類站建設初始成本及后期維護成本組成。由于居民垃圾分類意識尚未成熟，難免出現(xiàn)少數(shù)居民不愿意進行垃圾分類的情況，需要安排相關工作人員進行監(jiān)督指導，因此需要花費較高人力成本?？茖W地在小區(qū)適當位置建立垃圾分類站以及合理設置垃圾分類站數(shù)量對于垃圾分類政策的順利實施具有重大意義，同時也是物業(yè)相關部門急需解決的問題。

2 垃圾分類站選址模型

2.1 數(shù)學模型

在備選的地址集合里，如何選擇m個地址，使得每個垃圾分類站的服務范圍都能輻射周圍住戶，并且要求每個住戶到該地址的加權平均距離最小是需要重點研究的問題。設模型樣本集{X}中有n個樣本（即每個住戶）和k個分類，以每個樣本到聚類中心的加權平均間距最小為目標，其目標函數(shù)為：

根據(jù)實際情況，每個住戶只會去一個垃圾分類站投放垃圾，相當于每個分類住戶只會被分配到一個聚類中心，可用數(shù)學公式表示為：

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個聚類中心包含的樣本個數(shù)。

（4）若[c'j≠cj]，則轉至步驟（2），否則輸出結果。

3 垃圾分類站選址成本模型

3.1 模型架構

（1）總成本最小模型。在小區(qū)垃圾分類站建設中，應重點分析建立垃圾分類站的固定投資成本及后期維護成本，這兩個成本是垃圾分類站建設的主要成本。

（2）居民滿意度負效應最小模型。由于垃圾分類站可能導致蚊蟲增多、異味增加，對居民生活造成一定負面影響，導致居民對小區(qū)物業(yè)管理滿意度下降。所以物業(yè)部門在建設垃圾分類站時需要考慮地址及垃圾分類站容量等因素，實現(xiàn)居民滿意度的負效應最小。

3.2 參數(shù)定義

相關參數(shù)定義如下：

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的垃圾分類站。

[θ ω φ]：居民滿意度負效應影響系數(shù)。

3.3 目標函數(shù)

總成本最小目標函數(shù)為：

居民滿意度負面效應最小目標函數(shù)為：

每個住戶的垃圾只會投放到一個最近的固定垃圾分類站：

一個地址只能建立一個容量為q的垃圾分類站：

因每個住戶投放垃圾的總和不能超過垃圾分類站容量，垃圾分類站容量約束為：

決策變量約束為：

4 案例分析

4.1 選址模型案例分析

根據(jù)建立的小區(qū)垃圾分類站選址模型，以上海某小區(qū)為例對模型進行驗證。根據(jù)物業(yè)管理處給出的歷史數(shù)據(jù)計算出該小區(qū)需要設置6個垃圾分類站，經過數(shù)據(jù)處理后，將小區(qū)平面圖放在一個二維直角坐標系中，如圖2所示。該小區(qū)共有33棟樓，將小區(qū)內每棟樓的坐標導入計算機，經過1 000次迭代計算后得到6個聚類中心，粗略將這6個坐標設為垃圾分類站坐標。

為驗證算法的穩(wěn)定性，本文選取模糊C-means聚類算法與K-means聚類算法進行比較，得到兩個聚類結果如表1所示。

根據(jù)表1的比較結果可得出結論，通過K-means聚類算法得出的6個垃圾分類站距各所屬樓棟平均距離相比模糊C-means聚類算法計算出的平均距離縮短約17%左右，約為41m。各樓棟到垃圾分類站平均距離越小，說明居民投放垃圾越方便，居民滿意度將越高，由此可得出K-means聚類算法的優(yōu)越性。

4.2 成本模型案例分析

根據(jù)建立的垃圾分類站選址模型，小區(qū)內共建立6個垃圾分類站，假設小區(qū)每棟樓每天產生的垃圾量固定為0.5m3，建造費用及維護費用為1.5萬元/m3，單位垃圾的人工維護成本為0.5萬元/m3，居民滿意度負效應影響系數(shù)[θ、 ω、φ]分別取0.2、0.3、0.5。采用K-means與C-mean兩種算法，其中通過K-means聚類算法得出的垃圾分類站相關數(shù)據(jù)如表2所示，通過模糊C-means聚類算法得出的垃圾分類站相關數(shù)據(jù)如表3所示。

確定每棟樓平均每天產生的垃圾量以及6個垃圾分類站容量，結合選址模型中的數(shù)據(jù)，根據(jù)相關公式計算垃圾分類站花費總成本及居民滿意度負效應成本如下：

根據(jù)以上結果對比可知，通過K-means聚類算法求出的最小總成本為38萬元，比模糊C-means聚類算法求出的最小成本低1萬元，居民滿意度負效應成本為4.82萬元，比模糊C-means聚類算法低0.68萬元，由此證明了模型的可行性以及K-means聚類算法的優(yōu)越性。

5 結語

實行垃圾分類對于推動資源循環(huán)利用以及社會可持續(xù)發(fā)展具有十分重要的意義。本文研究小區(qū)垃圾分類站選址問題，在構建模型時考慮了居民投放垃圾的便捷性與垃圾分類站的建造及維護成本，以及居民滿意度負效應成本。最后通過實際案例分析，驗證了模型的可行性及K-means聚類算法的優(yōu)越性，可為社區(qū)物業(yè)規(guī)劃及相關部門制定垃圾分類政策提供參考。在未來研究中，可對算法進行改進，以進一步優(yōu)化成本，確定全局最優(yōu)。另外，垃圾分類站動態(tài)選址問題可作為下一步研究重點。

參考文獻：

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

[2] 羅楠.? 上海生活垃圾分類治理模式探索[J]. 城鄉(xiāng)建設， 2019， 563（8）：18-21.

[3] 周振釗. 應用層次分析法對某垃圾填埋場規(guī)劃選址進行分析[J].? 西部資源， 2019， 88（1）：163-164.

[4] 張晨，劉勤明，葉春明，等. 雙層規(guī)劃下考慮環(huán)境侵害的垃圾分揀中心選址研究[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，F(xiàn)ENG 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算法的多場景分布式電源規(guī)劃[J]. 吉林大學學報（信息科學版）， 2018， 36（5）：43-48.

[9] 魯玲嵐， 秦江濤.? 基于改進的K-means聚類的多區(qū)域物流中心選址算法[J]. 計算機系統(tǒng)應用，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] 栗娜，李珍萍. 垃圾站選址問題的數(shù)學模型及應用[J].? 物流技術，2011，30（12）：135-137.

[13] 湯云峰. 基于重心法和層次分析法的高校快遞智能柜選址布局問題研究[J]. 山東科學，2019，32（3）：65-72.

[14] 倪訓友， 孫健.? 城市公共停車場選址雙層規(guī)劃模型[J]. 城市交通， 2019， 17（2）：114-118.

[15] 管玉潔，徐迅，黃雅娟，等. 基于K-Means聚類算法的應急物流中心選址[J]. 理論數(shù)學，2019，9（7）：809-812.

[16] 吳紅波， 楊肖肖， 王國田.? 基于多目標優(yōu)化模型的城鎮(zhèn)污水處理廠選址分析[J]. 地理空間信息，2019，17（12）：42-46.

[17] 肖玉徽， 樓振凱.? 考慮客戶滿意度的物流末端節(jié)點選址模型及算法[J].? 工業(yè)工程， 2019（3）：126-131.

[18] 楊俊闖，趙超. K-Means聚類算法研究綜述[J]. 計算機工程與應用，2019，55（23）：7-14，63.

[19] 汪中求.? 垃圾分類背后的真相[J]. 企業(yè)管理，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.

（責任編輯：黃 ?。?/p>