垃圾分类处理与清运方案设计(东北三省数学建模)1

1、答卷编号（参赛学校填写） ：答卷编号（竞赛组委会填写） ：论文题目：A.垃圾分类处理与清运方案设计组别：本科生参赛队员信息 (必填 )：姓名专业班级及学号联系电话参赛队员 1参赛队员 2参赛队员 3参赛学校：黑龙江八一农垦大学答卷编号（参赛学校填写） ：答卷编号（竞赛组委会填写） ：评阅情况（学校评阅专家填写）：学校评阅 1.学校评阅 2.学校评阅 3.评阅情况（联赛评阅专家填写）：联赛评阅 1.联赛评阅 2.联赛评阅 3.垃圾分类处理与清运方案设计摘要随着环境保护日益被人们重视，垃圾分类化受到越来越多国家的重视。随着国民经济发展与城市化进程加快，我国大城市的垃圾分类化也已经提到日程上来。但是

2、垃圾的运送处理成为了一个很难解决的问题，因此如何达到最佳经济效益和环保效果，是我们此次研究的主要问题。问题一：厨余垃圾处理设备的分布设计。本问题我们首先采用最短距离聚类模型以及 k-Means 聚类模型来确定大型厨余垃圾处理设备的数量。通过对两种模型的分析比较，我们发现采用 k-Means 聚类模型所得结果更为符合我们所要达到的效果， 而且通过比较建设厨余垃圾处理设备的花费，发现使用 3 个大型厨余垃圾处理设备时能达到最佳经济效益和环保效果。因此我们运用k-Means 聚类模型进行距离聚类，将38 个垃圾转运站分成 3 块。然后我们利用优化模型，使用Matlab 进行编程，求解厨余垃圾处理设备

3、的位置分布。将三个大型厨余垃圾处理设备分别置于新围公厕垃圾站，大冲公厕垃圾站及涌下村。通过计算建立设备的总花费为13500 万元。问题二：清运路线具体方案设计。 我们通过建 TSP 模型来解决。 对于焚烧垃圾和填埋垃圾清运路线的确定，我们首先运用k-Means 聚类方法，将 38 个垃圾转运站划分为16 块，然后采用下山逐点搜索法，确定路线运输路线。而对于厨余垃圾的运输，我们在第一问题中所分得的 3 块基础上，再次利用 k-Means 聚类方法将每个块分为 56 个块，最后采用下山逐点搜索法确定出处于厨余垃圾的运输路线,通过计算得出每天总的费用为 5001 元（不包括可回收垃圾、有害垃圾以及每

4、个小区收集垃圾的运输费用） 。问题三：垃圾运转站的重新分布设计和大、小型厨余垃圾处理设备的分布设计。对于此问题我们建立了 k-Means 聚类模型，中位点选址模型以及集合覆盖模型。对于此模型，我们首先利用 excel 将深圳所有小区的数据按片区名称分类汇总，并得出每个小区的总人数。然后筛选出人数超过 2800 人的小区及人数不足 2800 人但房间数超过 80 间的小区作作为分析研究的对象。再运用谷歌地球软件测出筛选出来的小区的坐标。通过 Matlab 软件中的 pdist 函数和 squareform 函数将其化为距离方阵，并通过 k-Means 方法将小区聚为 38 类。然后以每一类中的居

5、民人数和距离作为选取转运站位置的主要依据，用选址问题中的中位点选址方法确定垃圾运转站的位置， 最后根据所给的垃圾运转站的转运量进行局部调整而得出垃圾站点的位置分布。问题四：垃圾运转站位置重新设计后清运路线具体方案设计。此问题的解决方案与解决问题二的方案相同。关键词： 中位点选址方法Matlab 下山搜索法集合覆盖算法k-Means 聚类法1一、问题重述垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资源回收与再利用的城市绿色工程。我国大城市如北京、上海、重庆和深圳的垃圾分类化已经提到日程上来，并且都都取得了一定成果，但是许多问题仍然是垃圾分类化进程中需要深入研究的。在深

6、圳，垃圾分为四类：橱余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾。在垃圾分类收集与处理中，不同类的垃圾有不同的处理方式，所有垃圾将从小区运送到附近的转运站，再运送到少数几个垃圾处理中心。其中，厨余垃圾和可回收垃圾经过处理，回收和利用，能产生经济效益。而有害垃圾和不可回收垃圾只有消耗处理费用，不产生经济效益。我们此次研究主要是解决以下几个问题：问题（一）：假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计问题（二）：在目前的运输装备条件下给出清运路线的具体方案。以期达到最佳经济效益和环保效果。问题（三）：假设转运站允许重新设计，重新给出大、小型设备的分布设计。问题（

7、四）：求出重新设计垃圾运转站位置后清运路线的具体方案二、问题分析2.1 厨余垃圾处理设备的分布设计根据题意我们首先要解决的问题是厨余垃圾处理设备的分布设计， 对于此问题我们要考虑所用大、小型处于垃圾处理设备的数量，以及所选用的厨余垃圾处理设备的放置地点的选择。我们首先计算大型设备和小型设备所需的台数。由于大、小型设备的处理垃圾能力不同，而且大型设备的的处理能力远远大于小型设备，所以我们先考虑大型厨余垃圾处理设备的安置。通过计算，我们得出厨余垃圾总量大约460 吨，而大型厨余设备处理能力为 200 吨，小型厨余垃圾处理能力在0.2-0.3 吨。相对来说小型厨余垃圾处理设备比大型厨余垃圾处理设备成

8、本高出许多，所以决定采用3 台大型厨余垃圾处理设备。我们考虑将 38 个垃圾站点分成三类，并分别建设大型厨余垃圾处理设备。为此，先运用模糊数学中的聚类分析方法，构造距离相似矩阵，将转运站分为三类，每一类转运站中布置一台大型厨余设备。然后，确定设备的具体位置，这时可以考虑在每一个大型设备分区内，以运行成本最少为目标来确定位置。为此，我们用百度地图搜索到了转运站之间的最短距离，结合各转运站的厨余垃圾量，以及距离和各转运站的厨余垃圾量乘积之和为运行成本，求最小成本值。求出每一个大型设备分区内大型厨余垃圾处理设备的具体位置。具体算法可以采用退火算法、中位点算法等，因为数据少、计算精确我们选择中位点算法

9、求得具体位置。12.2 清运路线具体方案的设计对于此问题我们建立了TSP 模型解决。首先根据题意，针对焚烧和填埋垃圾的运输，我们运用 k-Means 聚类方法，将 38 个垃圾转运站划分为 16 个块，然后运用 TSP 模型，确定路线运输路线。而对于厨余垃圾的运输，我们在第一问题中所分得的 3 块的基础上，再次利用 k-Means 聚类方法将每个块分为 5 6 个块并运用 TSP 模型确定出厨余垃圾的运输路线。2.3 垃圾运转站的重新分布设计和大、小型厨余垃圾处理设备的分布设计对于此问题我们建立了三个数学模型： k-Means 聚类模型，中心位置选址模型和集合覆盖模型。通过对问题的分析，我们首

10、先要解决的是居民小区的数据。我们首先利用 excel 将深圳所有小区的数据按片区名称分类汇总，并得出每个小区的总人数，然后通过人数和房间数对小区进行筛选作为分析研究的对象。 再运用谷歌地球软件测出筛选出来的小区的坐标，通过 Matlab 软件中的 pdist 函数和 squareform函数将其化为距离方阵，并通过 k-Means 聚类法将小区聚类。然后以每一类中的居民人数和距离作为选取转运站位置的主要依据，用选址问题中的中位点选址方法确定垃圾运转站的位置，最后根据所给的垃圾运转站的转运量进行局部调整而得出垃圾站点的位置分布。2.4 垃圾运转站位置重新设计后清运路线的具体方案设计此问题与问题二

11、方法相同。三、模型假设1假设题目所给的数据真实可靠；2假设百度地图中测量的两点间距离真实可靠；3考虑到环保，假设厨余垃圾处理设备建在垃圾转运站处；4各垃圾点的垃圾必须当天及时清除完，不允许滞留；5晚上 22：00 后不堵车；6垃圾只在晚上运输，每天各垃圾点的垃圾量基本相同，并且基本保证运完后，当天不会再有新的垃圾产生；7每个垃圾点无论其中垃圾是否清理完全都需要10 分钟装车时间；8假设小区人数小于等于2800 人在数据处理时忽略（虽然平均每个小区的人数在1400 人左右，但人数分布比较集中， 所以利用人数较集中的小区作为研究对象， 将小区人数的下界定为 2800 人。）9测小区坐标时不考虑海拔

12、高度对距离的影响；10假设小区间距离用其坐标之间的直线距离表示；11假设垃圾的产生量与人数呈正比关系；12不考虑小区人数的变动；13厨余设备所安放的转运点出厨余垃圾不需要运输；14假设 2.5 吨小车运送垃圾时，在每个站点运送时所走路程相等；。四、定义与符号说明2D ：距离矩阵，元素 dij （i,j 1，2， ，9）为垃圾转运点 vi 至垃圾转运点 v j 的最短路径长度。Dt ：调整后的距离矩阵（t=1， 2， ，3）。A ：各垃圾转运点的载荷矩阵（以厨余垃圾的转运量为载荷）。S ：每一个垃圾转运点至其它各个垃圾转的最短路径长度的加权和。v i 、 vj ：垃圾转运站点。x1i ：第一区中

13、第i 个垃圾转运站的厨余垃圾量（i=1，2， ，13）。x2i：第二区中第 i 个垃圾转运站的厨余垃圾量（i=1， 2， ，12）。x3i ：第三区中第 i 个垃圾转运站的厨余垃圾量（i=1，2， ，13）。D1i：第一区中第 i 个垃圾转运站到涌下村垃圾处理中心的距离（ i=1，2，13）。D2i：第二区中第 i 个垃圾转运站到大冲公厕垃圾站垃圾处理中心的距离（ i=1，2，12）。D3i ：第三区中第 i 个垃圾转运站到新围公厕垃圾站的距离（i=1，2， ，13）。Yi ：表示各个垃圾转运站焚烧垃圾量（i=1，2， 37）。DYi ：表示第 i 个垃圾转运站到南山垃圾厂的距离（i=1，2，

14、 37）。Zi ：表示各个垃圾转运站填埋垃圾的量（i=1 ， 2， ，37）。D Zi ：表示各个垃圾转运站到下坪固体废物填埋场的距离（i=1 ，2， ，37）。M 1,2, , m ：表示有 m 座垃圾收集站组成的集合；Ck ：表示筛选出的第k 座垃圾中转站的中转能力；X i ：表示第 i 座垃圾收集站的垃圾量；A(k ) ：表示筛选出的第k 座垃圾中转站所覆盖的垃圾收集站的集合；B(i ) ：表示可以覆盖第f 座垃圾收集站的中转站的集合；Wk ：表示是否启用第k 座垃圾中转站；U ik ：表示第 f 座垃圾中转站是否被第七座垃圾中转站覆盖。3Ni ：第二问中第i 个垃圾转运站所需2.5 吨

15、汽车的数量；ni ：垃圾转运站重新分配后第i 个垃圾站点所需要转运的垃圾总量。五、模型的建立与求解5.1 厨余垃圾处理设备的分布设计模型一：聚类分析模型 确定大型设备的台数根据以上分析，我们建立了最短距离聚类模型和k-Means 聚类模型。1. 最短距离聚类模型（1）每一个转运站看成一类，依次记为G1, G2 , G38 ，构造 38 个转运站间的距离矩阵d11d12d1,38d21d22d2,38Dd38,1d38,2d38,38以距离矩阵 D 为基础，利用最短距离方法聚类。（2）算法流程Step1：在距离矩阵 D 的非对角元素中找出距离最短的两个类Gp 和 Gq ，并为一新类Gr 。Ste

16、p2：然后按计算公式drk min d pk , dqk (k p, q)计算原来各类与新类之间的距离，得到一个新的37 阶的距离矩阵。Step3：转到 Step1，这样一直下去，直至各分类对象被归为一类为止。（3）最短距离聚类模型求解测出 38个垃圾转运站以题中所给地图的左边缘和下边缘为坐标轴建立直角坐标系，的相对坐标，结果如下表。表 1.垃圾转运站点坐标序站点坐标序站点坐标号号1九街站(310.88,614.74)20松坪山站(472.67,708.31)2玉泉站(387.25,643.88)21南光站(346.3,485.51)3动物园站(557.51,912.21)22南园站(305.

17、11,490.7)4平山村站(550.19,869.55)23望海路站(377.43,272.8)5牛城村站(364.03,1035.02)24花果路站(373.79,297.45)6科技园站(456.6,501.66)25福光站（ 731.16， 918.44）47同乐村站（ 333.31， 758.42）26新围村站(509.69,862.21)8松坪山（二）站(414.05,705.39)27大冲站(512.03,609.54)9大新小学站(294.92,585.53)28沙河市场站(591.91,629.27)10南山村站(251.38,456.19)29龙井(630.57,731.0

18、7)11阳光 (白芒关外 )站(423.74,1128.34)30南山市场(315.83,525.02)12月亮湾大道站(262.01,643.21)31麻勘站(507.74,1158.73)13光前站(566.28,740.23)32白芒站(440.77,1087.5)14北头站(289.49,502.03)33大石磡站(621.53,1054.34)15涌下村站(303.78,552.77)34长源村站（ 810.19， 928.92）16白石洲南站(576.85,551.37)35华侨城站(728.92,597.51)17前海公园站(267.75,635.54)36疏港小区站(186.9

19、2,286.51)18深圳大学站(432.21,569.66)37西丽路站（ 489.97， 788.75）19官龙村站(481.69,883.28)38塘朗站（ 738.11， 904.59）通过对本问题的以上分析和算法流程，把38 个垃圾转运站点聚为 3 类，具体做法是利用 Matlab 中的 pdist 函数和 squareform 函数将坐标转化为距离矩阵，并利用linkage和 cluster 函数进行最短距离聚类，得到如下三类结果如下表。表 2.垃圾转运站分类结果类别垃圾转运站一类疏港小区站二类九街站玉泉站动物园站平山村站牛城村站科技园站同乐村站松坪山（二）站 大新小学站南山村站阳

20、光 (白芒关外 )站 月亮湾大道站光前站北头站涌下村站白石洲南站前海公园站深圳大学站官龙村站松坪山站南光站 南园站福光站新围村站大冲站沙河市场站龙井南山市场麻勘站白芒站大石磡站长源村站华侨城站西丽路塘朗站三类望海路站花果路站根据表 2，我们得出：一区建立 92 台小型设备； 二区建立 2 台大型设备和 8 台小型设备；三区建立 138 台小型设备。在不考虑运费的情况下， 我们计算出总费用为： 15440 万元2. k-Means 聚类模型：（1）k-Means 5 聚类基本思路： 接受聚类参数 k，然后将事先输入的n 个数据对象划分为k 个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较

21、高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象 ”（引力中心）来进行计算的。（2）算法流程Step1：从数据集 xn 38n1 中任意选取 3 赋给初始的聚类中心c1 ， c2 ， c3 。Step2：对数据集中的每个样本点xi ，计算其与各个聚类中心c j 的欧式距离并获取其类别标号：label (i )arg min | xicj |2 , i1,2,.,38, j1,2,3 。j5Step3：按下式重新计算3 聚类中心xscjs:label ( s)j, j 1,2,3。N jStep4：重复 Stept2 和 Stept3，直到达到最大迭代次数

22、为止。（3）k-Means 聚类模型求解我们利用第一部分测出 38个垃圾转运站的坐标值。然后利用 Matlab中的 pdist函数和squareform函数将坐标转化为距离矩阵， 并利用 k-Means函数进行最短距离聚类， 得到如下三部分结果：表 3. 垃圾转运站分类结果类别垃圾转运站一类玉泉站 平山村站 同乐村站 松坪山（二）站光前站白石洲南站松坪山站大冲站 沙河市场站 龙井 华侨城站深圳大学站 科技园站二类动物园站 牛城村站阳光 (白芒关外 )站 福光站麻勘站白芒站大石磡站长源村站 塘朗站 官龙村站新围村站西丽路站三类九街站 大新小学站南山村站月亮湾大道站北头站涌下村站前海公园站南光站

23、南园站 望海路站花果路站南山市场 疏港小区站通过对表 3 结果的计算和分析，我们得出：一区建立一个大型设备；二区建立以个大型设备；三区建立一个大型设备和 14 个小型设备。在不考虑运费的情况下，我们计算出总费用为： 13867 万元。3 两种模型的比较及最终聚类结果通过对两种方案总费用的比较，我们得出 k-means 聚类算法为最优方案。模型二：优化模型 确定厨余垃圾处理中心位置根据表 4的垃圾转运站最终聚类结果，以及对于厨余垃圾处理设备的分布设计，我们首先用百度地图测出每一个垃圾转运站vi 至其它各个站点 v j 的最短路径长度 dij （ i，j 1，2，），求出三类内部的距离矩阵d11d

24、1nDt, t1,2,3.dm1dmn下面建立模型确定每一类内部厨余垃圾处理中心的位置。以距离和各转运站的厨余垃圾量乘积之和为运行成本， 以成本值为目标函数确定垃圾处理设备的具体位置。考虑目标函数min St (vi ) S(v1 ), S(v2 ), S( vn ) Dt * Ati其中， At a(v1 ), a(v2 )a(vn ) 为每类内各站点的载荷矩阵（厨余垃圾量） 。以每一类内部为约束条件，以各垃圾转运站点的载荷加权，用Matlab中的矩阵运算求得每一个站点至其它各个站点的最短路径长度的加权和，最后得出将3个大型厨余垃6圾处理设备位置分别如下表。表 4. 垃圾转运站最终聚类结果类

25、别大型厨余垃圾处理设备位置一类新围公厕垃圾站二类大冲公厕垃圾站三类涌下村5.2 清运路线具体方案的设计模型一：加权载荷模型 车辆的分配由于车辆有限，我们先将 16 辆车分给三类垃圾的运输，为此建立加权载荷模型。（1）模型ixij Dij(i 1,2,3; j1,2,3, 13, s 1,2,3, ,38)xs Dsxij ：观测值； Dij ：观测值的对应权数；i ：权算术平均数（即预测值） 。（2）模型求解运输厨余垃圾的拖车所占比率：1312135 ( x1 i D1ix2 iD2 ix3iD3i )1i 1i 1i 11312135 ( x1i D1ix2i D2 ix3iD3 i ) Y

26、iDYiZi DZii 1i 1i1运输焚烧垃圾的拖车所占比率：2YiDYi1312135 ( x1i D1ix2 i D2 ix3 i D3i )Yi DYi Zi DZii 1i 1i 1运输填埋垃圾的拖车所占比率：3ZiDZi1312135 ( x1i D1ix2i D2 ix3 i D3i )Yi DYi Zi DZii 1i 1i 1（2）求解车辆的分配用加权载荷法确定每类具体方法如下：表 5.垃圾转运站最终聚类结果车辆类别所占比率车辆数量运输厨余垃圾的车辆0.325运输焚烧垃圾的车辆0.254运输填埋垃圾的车辆0.4277模型二： TSP 模型 清运路线的设计（1）焚烧垃圾的清运路

27、线通过对同中所给数据的分析， 以及相关资量的查阅， 我们决定采用 TSP 模型对问题进行求解。TSP 模型 6 路运输问题的最为典型的一个模型，它的全称是TravelingSalesman Problem(TSP)，中文叫做旅行商问题。 TSP 模型可以如下描述：在给出的一个雄顶点网络 (有向或无向 )，要求找出一个包含所有甩个顶点的具有最小耗费的环路。任何一个包含网络中所有 n 个顶点的环路被称作一个回路 (Tour)。在旅行商问题中，要设法找到一条最小耗费的回路。既然回路是包含所有顶点的一个循环，故可以把任意一个点作为起点 (因此也是终点 )，这也是 TSP 模型的一个特点。TSP 模型数

28、学表达式如下：连通图 H，其顶点集合 A ，定点间距离为 Ccij i, jN ,1i , jn目标函数：mnmincij xiji 1j1约束条件：nxij1,i1,2,nj 1nxij1,i1,2,mi 1xij 0,1,i 1,2, , n, j1,2, , m决策变量：xij0 ，从 i 到 j 无通路； xij 1 ，从 i到 j 有通路。我们首先利用 k-Means 聚类方法将 38 个垃圾转运站点分成 16 块，记为 P 集合，具体数据如下表所示：表 6. P 集合及该集合的垃圾量块序号垃圾站点序号垃圾量到焚烧厂的距离116,27,285.9,3.9,8.914.8，13.5,1

29、6.822,7， 8,207.4,1.5,2.9,7.410.8，12.9,14.9,13.834,19,267.4,4.5,5.918.8,17.1,16.941,9,12， 175.9,8.9,11.9,4.710.1,8.1,10.2,8.8523,248.9,8.911.7,11.265,321.5,2.419.4,20.1725,34,382.9， 1.5,2.921.9,24.1,21.2814,15,21,22,304.5,5.9,4.5,4.5,7.46.8,8.5,8.2,7.6,7.5911,312.9， 2.921.5,2210107.45.98116,85.9， 2.9

30、12.3,14.9,1213,29,375.9， 4.5，4.517.6,16.7,15133611.94.81435.919.8153520.817.216338.923然后我们采用 TSP 模型对 P 集合的垃圾运转路径进行搜索得出焚烧垃圾运输路线如下图。图 1. 焚烧垃圾运输路线图注：:垃圾量超过 8.5 吨，且一次就能运完的垃圾站点:表示垃圾量不足8.5 吨的垃圾站点9:表示需要运输两次或两次以上的垃圾站点:表示垃圾处理中心费用的计算公式： F费0.32.07L2.07(lL' )（ l :表示转运站点之间的距离； L ':表示末点到处理中心的距离）时间的计算公式：TS

31、总 /4010a5b ( S总 : 表示总路程 ;a:表示装车的次数 ;b:表示卸车的次数 )每天运输焚烧垃圾的总费用1428 元： ,每辆车需工作 5.2 个小时（2）填埋垃圾的清运路线此问题的求解过程与焚烧垃圾清运路线的求解过程一样，并且结果基本相同。通过计算，每天运输填埋垃圾的总费用为 2349 元，每辆车需工作 4.8 个小时。（3）厨余垃圾的清运路线我们将三类内部的垃圾站点分别采用k-Means 聚类方法分成 5 块，并记为 P1 、 P2 、P3 集合，具体数据如下表所示：表 7. P1 、 P2 、 P3 集合中的垃圾量以及到处理中心的距离区块块序号1 集合垃圾量到涌下村的距离P

32、一区123， 2417.13， 17.13，8.3， 8.023622.847.1321， 22， 10， 14， 308.57，8.57，14.28，8.57，14.282.3，2.0，2.8，1.949， 1， 1717.13， 11.42， 9.141.2， 0.54， 2.051222.843.8二区172.88.522， 18， 614.3，8.6， 11.44.0， 3.6， 1.138， 205.7， 14.37.2， 3.7413， 2711.4， 8.65.2， 7.7516， 28， 3517.1，17.1， 401.4， 3.6， 3.4三区131， 11， 5， 325

33、.7， 5.7， 2.9，4.67.1，6.0，4.7，5.22342.97.6319， 4， 38.6， 14.3， 11.40.85，2.3， 2.4425， 38， 375.7， 5.7， 8.65.1， 4.6， 5.653317.15.6然后采用和处理 P 集合同样的处理方法对P1 、 P2 、 P3 进行处理，得出厨余垃圾的运输路线，结果如下图所示：10图 2. 一区的厨余垃圾运输路线图 3. 二区的厨余垃圾运输路线11图 4. 三区的厨余垃圾运输路线注：:运走 n*10 吨后 ,还有剩余 的站点 (n是次数， n=1,2, ):垃圾量超过 8.5吨，且一次就能运完的垃圾站点:表示

34、运走 n* （8.510）吨后无剩余的站点（n是次数， n=2,3，）:表示垃圾量不足 8.5吨的垃圾站点:表示需要运输两次或两次以上的垃圾站点:表示垃圾处理中心运输厨余垃圾每天的总费用为 1224元，每辆车需工作 4.7个小时小结：1. 每天厨余垃圾的的产量为 460吨，我们通过查找资料得出厨余垃圾经处理设备处理后的产物的产率为 0.2，然后计算出厨余垃圾经处理设备处理后的产物量为 92吨，其收益为 2300069000元。2. 我们首先利用题目所给的四类垃圾（厨余垃圾、可回收垃圾、有害垃圾、其他不可回收垃圾）的比例（ 4:2:1:3）计算出每天产生的可回收垃圾量为 230吨，然后，利用可回

35、收垃圾中四类垃圾（纸类、塑料、玻璃、金属）的平均比例计算出相应垃圾的产量，具体结果如下表表 8. 可回收垃圾收益表类别产量（吨）收益（元）纸类127.019127019塑料80.8304201201玻璃13.85666898金属9.237822994合计230.94383581123. 总收益为 381112 427112元5.3 垃圾运转站的重新分布设计和大、小型厨余垃圾处理设备的分布设计对于本问题我们采用了k-means 模型、集合覆盖模型以及中心位点选址模型进行求解。模型一： k-Means 模型 垃圾转运站点的初步确定（1）k-Means 聚类基本思路： 接受聚类参数 k，然后将事先输

36、入的n 个数据对象划分为 k 个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象 ”（引力中心）来进行计算的。（2）算法流程Step1：从数据集 xn 38n1 中任意选取 3 赋给初始的聚类中心c1 ， c2 ， c3 。Step2：对数据集中的每个样本点xi ，计算其与各个聚类中心c j 的欧式距离并获取其类别标号：label (i )arg min | xicj |2 , i1,2,.,38, j1,2,3 。j12Step3：按下式重新计算3 聚类中心xscjs:label ( s)j, j

37、1,2,3 。N jStep4：重复 Stept2 和 Stept3，直到达到最大迭代次数为止。（3）k-Means 模型的求解：我们首先利用 excel3 深圳所有小区的数据按片区名称分类汇总，并得出每个小区的总人数。然后筛选出人数超过 2800 人的小区以及剩余中房间数超过80 间的小区作为分析研究的对象。再运用谷歌地球软件测出筛选出来的小区的坐标。参照当地人口密度以及垃圾收集密度，算出该城区垃圾收集最优半径为750m；再结合实际勘探情况以及城市总体规划共布置大型垃圾收集站149 座。然后通过 Matlab软件中的 pdist 函数和 squareform 函数将其化为距离方阵，并通过 k

38、-Means 方法将小区聚为 38 类。然后以每一类中的居民人数和距离作为选取转运站位置的主要依据，用选址问题中的中位点选址方法确定垃圾运转站的位置，模型二：集合覆盖模型 垃圾转运站点的调整集合覆盖模型目标是在满足覆盖所有垃圾运转战的情况下， 确定建立大型厨余垃圾处理设备的个数或建设费用最小，并配置这些服务设施使所有的转运站都能被覆盖住到。具体表达式如下所示。minWkkMU ik1(i1,2,m)(1)k B (i )X iU ikCk Wk (i 1,2, m; kB(i )(2)i A (k )Xi , Ci0,( i1,2, m; kB(i)(3)Wk0,1(4)U ik0,1(5)目

39、标函数为从现有 m 座垃圾运转站的位置中优选出可以覆盖m 座垃圾收集站的最小数目的中转站选点；约束式l 表示每一座垃圾运转站的垃圾均被清运；约束式2 是满足垃圾运转站中转能力的要求；约束式3 表示垃圾站和中转站的垃圾量非负；约束式 4是垃圾收集站是否位于第k 座垃圾中转站附近的决策变量；约束式5 是第 j 座垃圾收集站是否有垃圾收运到第k 座中转站的决策变量。从而得出垃圾转运站点的位置分布，如下表所示：表 9. 垃圾运转站新站点分布编片区名称地址总人数垃圾转运量号1平山村站南山区平山村内2894324.5323313207网格片区汇总南山华泰小区79415.843525307网格片区汇总后海小

40、学400117.44932401网格片区汇总登良路与南商路交叉口处3333036.789725南山村站东滨路与前海路交汇处4113522.166556沙河市场站南山区沙河市场旁7980331.861247大冲站深南大道大冲村旁1999714.715158前海公园站南山区前海公园内1911153.19449龙井龙珠五路龙井村旁3202817.6762810大新小学站南头街大新小学旁5812932.081441103网格片区汇总大磡村综合市场1734629.147331201网格片区汇总公园路与招商路1633330.979121322网格片区汇总新围村1473419.516114华侨城站侨城东路西

41、侧2145542.627721505网格片区汇总白芒村南2251227.3336616北头站前海路与桂庙路交叉口1041917.2507717动物园站深圳野生动物园1204016.300411816网格片区汇总留仙洞村130625.76714319南园站南山区南园村内4060917.2401120白石洲站白石洲与石洲中路交叉口2893931.942922107网格片区汇总西丽路2261217.82287221网格汇总珠光村1521320.150562304网格片区汇总北环大道与京港澳高速公1368327.18597路交叉口24玉泉站玉泉路宝龙路口237349.52912825九街站深南大道南头

42、中学旁1204813.29862610网格片区汇总官龙村1706615.697927深圳科技工业园大厦深圳科技工业园大厦1682529.566342803网格片区汇总东角头 -地铁站2029539.241252907网格片区汇总玉泉路1425131.460563011网格片区汇总兴海大道蛇口站1265941.919093102网格片区汇总南山区福光村内5080731.9473432松坪山（二）站高新北区朗山一路绿地内2047110.0595633深圳大学站校园内81068.73254734平山 P片区 汇总创业路与南光路交叉口1748620.403535科技园站科苑南路与滨海路大道交86331

43、7.02847汇处西侧36松坪山站南山区松坪山第五工业区305425.651883703网格片区汇总桃李花园328118.107873803网格片区汇总学府路与南山大道交叉口964923.8228214图 5. 新设计的垃圾转运站分布图模型三：优化模型 厨余垃圾处理中心的确定1. 聚类分析模型 将 38 个站点分为三类根据表 9的垃圾转运站最终聚类结果，以及对于厨余垃圾处理设备的分布设计，我们首先用百度地图测出每一个垃圾转运站vi 至其它各个站点 v j 的最短路径长度 dij （ i，j 1，2，），求出三类内部的距离矩阵d11d1nDt, t 1,2,3.dm1dmn下面建立模型确定每一类内部厨余垃圾处理中心的位置。以距离和各转运站的厨余垃圾量乘积之和为运行成本， 以成本值为目标函数确定垃圾处理设备的具体位置。考虑目标函数min St (vi ) S(v1 ), S(v2 ),S( vn )Dt * Ati15其中， At a(v1 ), a(v2 ) a(vn ) 为每类内各站点的载荷矩阵（厨余垃圾量） 。我们首先采用与解决问题一同样的方法确定38 个垃圾站