答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：论文题目： 组 别：本科生参赛队员信息(必填)： 姓 名专业班级及学号联系 参赛队员1参赛队员2参赛队员3 参赛学校：黑龙江八一农垦大学答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：评阅情况（学校评阅专家填写）：学校评阅1.学校评阅2.学校评阅3. 评阅情况（联赛评阅专家填写）：联赛评阅1.联赛评阅2.联赛评阅3.垃圾分类处理与清运方案设计摘要随着环境保护日益被人们重视，垃圾分类化受到越来越多国家的重视随着国民经济发展与城市化进程加快，我国大城市的垃圾分类化也已经提到日程上来但是垃圾的运送处理成为了一个很难解决的问题，因此如何达到最佳经济效益和环保效果，是我们此次研究的主要问题问题一：厨余垃圾处理设备的分布设计本问题我们首先采用最短距离聚类模型以及k-Means 聚类模型来确定大型厨余垃圾处理设备的数量通过对两种模型的分析比较，我们发现采用k-Means 聚类模型所得结果更为符合我们所要达到的效果，而且通过比较建设厨余垃圾处理设备的花费，发现使用3个大型厨余垃圾处理设备时能达到最佳经济效益和环保效果。
因此我们运用k-Means聚类模型进行距离聚类，将38个垃圾转运站分成3块然后我们利用优化模型，使用Matlab进行编程，求解厨余垃圾处理设备的位置分布将三个大型厨余垃圾处理设备分别置于新围公厕垃圾站，大冲公厕垃圾站及涌下村通过计算建立设备的总花费为13500万元问题二：清运路线具体方案设计我们通过建TSP模型来解决对于焚烧垃圾和填埋垃圾清运路线的确定，我们首先运用k-Means聚类方法，将38个垃圾转运站划分为16块，然后采用下山逐点搜索法，确定路线运输路线而对于厨余垃圾的运输，我们在第一问题中所分得的3块基础上，再次利用k-Means聚类方法将每个块分为5～6个块，最后采用下山逐点搜索法确定出处于厨余垃圾的运输路线,通过计算得出每天总的费用为5001元（不包括可回收垃圾、有害垃圾以及每个小区收集垃圾的运输费用）问题三：垃圾运转站的重新分布设计和大、小型厨余垃圾处理设备的分布设计对于此问题我们建立了k-Means聚类模型，中位点选址模型以及集合覆盖模型对于此模型，我们首先利用excel将深圳所有小区的数据按片区名称分类汇总，并得出每个小区的总人数然后筛选出人数超过2800人的小区及人数不足2800人但房间数超过80间的小区作作为分析研究的对象。
再运用谷歌地球软件测出筛选出来的小区的坐标通过Matlab软件中的pdist函数和squareform函数将其化为距离方阵，并通过k-Means方法将小区聚为38类然后以每一类中的居民人数和距离作为选取转运站位置的主要依据，用选址问题中的中位点选址方法确定垃圾运转站的位置，最后根据所给的垃圾运转站的转运量进行局部调整而得出垃圾站点的位置分布问题四：垃圾运转站位置重新设计后清运路线具体方案设计此问题的解决方案与解决问题二的方案相同关键词：中位点选址方法 Matlab 下山搜索法 集合覆盖算法 k-Means聚类法一、问题重述垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资源回收与再利用的城市绿色工程我国大城市如北京、上海、重庆和深圳的垃圾分类化已经提到日程上来，并且都都取得了一定成果，但是许多问题仍然是垃圾分类化进程中需要深入研究的在深圳，垃圾分为四类：橱余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾在垃圾分类收集与处理中，不同类的垃圾有不同的处理方式，所有垃圾将从小区运送到附近的转运站，再运送到少数几个垃圾处理中心其中，厨余垃圾和可回收垃圾经过处理，回收和利用，能产生经济效益。
而有害垃圾和不可回收垃圾只有消耗处理费用，不产生经济效益我们此次研究主要是解决以下几个问题：问题（一）：假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计问题（二）：在目前的运输装备条件下给出清运路线的具体方案以期达到最佳经济效益和环保效果问题（三）：假设转运站允许重新设计，重新给出大、小型设备的分布设计问题（四）：求出重新设计垃圾运转站位置后清运路线的具体方案二、问题分析2.1 厨余垃圾处理设备的分布设计根据题意我们首先要解决的问题是厨余垃圾处理设备的分布设计，对于此问题我们要考虑所用大、小型处于垃圾处理设备的数量，以及所选用的厨余垃圾处理设备的放置地点的选择我们首先计算大型设备和小型设备所需的台数由于大、小型设备的处理垃圾能力不同，而且大型设备的的处理能力远远大于小型设备，所以我们先考虑大型厨余垃圾处理设备的安置通过计算，我们得出厨余垃圾总量大约460吨，而大型厨余设备处理能力为200吨，小型厨余垃圾处理能力在0.2-0.3吨相对来说小型厨余垃圾处理设备比大型厨余垃圾处理设备成本高出许多，所以决定采用3台大型厨余垃圾处理设备我们考虑将38个垃圾站点分成三类，并分别建设大型厨余垃圾处理设备。
为此，先运用模糊数学中的聚类分析方法，构造距离相似矩阵，将转运站分为三类，每一类转运站中布置一台大型厨余设备然后，确定设备的具体位置，这时可以考虑在每一个大型设备分区内，以运行成本最少为目标来确定位置为此，我们用百度地图搜索到了转运站之间的最短距离，结合各转运站的厨余垃圾量，以及距离和各转运站的厨余垃圾量乘积之和为运行成本，求最小成本值求出每一个大型设备分区内大型厨余垃圾处理设备的具体位置具体算法可以采用退火算法、中位点算法等，因为数据少、计算精确我们选择中位点算法求得具体位置2.2 清运路线具体方案的设计对于此问题我们建立了TSP模型解决首先根据题意，针对焚烧和填埋垃圾的运输，我们运用k-Means聚类方法，将38个垃圾转运站划分为16个块，然后运用TSP模型，确定路线运输路线而对于厨余垃圾的运输，我们在第一问题中所分得的3块的基础上，再次利用k-Means聚类方法将每个块分为5～6个块并运用TSP模型确定出厨余垃圾的运输路线2.3 垃圾运转站的重新分布设计和大、小型厨余垃圾处理设备的分布设计对于此问题我们建立了三个数学模型：k-Means聚类模型，中心位置选址模型和集合覆盖模型通过对问题的分析，我们首先要解决的是居民小区的数据。
我们首先利用excel将深圳所有小区的数据按片区名称分类汇总，并得出每个小区的总人数，然后通过人数和房间数对小区进行筛选作为分析研究的对象再运用谷歌地球软件测出筛选出来的小区的坐标，通过Matlab软件中的pdist函数和squareform函数将其化为距离方阵，并通过k-Means聚类法将小区聚类然后以每一类中的居民人数和距离作为选取转运站位置的主要依据，用选址问题中的中位点选址方法确定垃圾运转站的位置，最后根据所给的垃圾运转站的转运量进行局部调整而得出垃圾站点的位置分布此问题与问题二方法相同三、模型假设1．假设题目所给的数据真实可靠；2．假设百度地图中测量的两点间距离真实可靠；3．考虑到环保，假设厨余垃圾处理设备建在垃圾转运站处；4．各垃圾点的垃圾必须当天及时清除完，不允许滞留；5．晚上22：00后不堵车；6．垃圾只在晚上运输，每天各垃圾点的垃圾量基本相同，并且基本保证运完后，当天不会再有新的垃圾产生；7．每个垃圾点无论其中垃圾是否清理完全都需要10分钟装车时间；8．假设小区人数小于等于2800人在数据处理时忽略（虽然平均每个小区的人数在1400人左右，但人数分布比较集中，所以利用人数较集中的小区作为研究对象，将小区人数的下界定为2800人。
9．测小区坐标时不考虑海拔高度对距离的影响；10．假设小区间距离用其坐标之间的直线距离表示；11．假设垃圾的产生量与人数呈正比关系；12．不考虑小区人数的变动；13．厨余设备所安放的转运点出厨余垃圾不需要运输；14．假设2.5吨小车运送垃圾时，在每个站点运送时所走路程相等；四、定义与符号说明：距离矩阵，元素（i,j ＝1，2，…，9）为垃圾转运点至垃圾转运点的最短路径长度调整后的距离矩阵（t=1，2，…，3）各垃圾转运点的载荷矩阵（以厨余垃圾的转运量为载荷）每一个垃圾转运点至其它各个垃圾转的最短路径长度的加权和垃圾转运站点第一区中第i个垃圾转运站的厨余垃圾量（i=1，2，…，13）第二区中第i个垃圾转运站的厨余垃圾量（i=1，2，…，12）第三区中第i个垃圾转运站的厨余垃圾量（i=1，2，…，13）第一区中第i个垃圾转运站到涌下村垃圾处理中心的距离（i=1，2，…，13）第二区中第i个垃圾转运站到大冲公厕垃圾站垃圾处理中心的距离（i=1，2，…，12）第三区中第i个垃圾转运站到新围公厕垃圾站的距离（i=1，2，…，13）表示各个垃圾转运站焚烧垃圾量（i=1，2，…，37）表示第i个垃圾转运站到南山垃圾厂的距离（i=1，2，…，37）。
表示各个垃圾转运站填埋垃圾的量（i=1，2，…，37）表示各个垃圾转运站到下坪固体废物填埋场的距离（i=1，2，…，37）表示有m座垃圾收集站组成的集合；：表示筛选出的第k座垃圾中转站的中转能力；：表示第i座垃圾收集站的垃圾量；：表示筛选出的第k座垃圾中转站所覆盖的垃圾收集站的集合；：表示可以覆盖第f座垃圾收集站的中转站的集合；：表示是否启用第k座垃圾中转站；：表示第f座垃圾中转站是否被第七座垃圾中转站覆盖第二问中第i个垃圾转运站所需2.5吨汽车的数量；：垃圾转运站重新分配后第i个垃圾站点所需要转运的垃圾总量五、模型的建立与求解5.1 厨余垃圾处理设备的分布设计5.1.1 模型一：聚类分析模型——确定大型设备的台数根据以上分析，我们建立了最短距离聚类模型和k-Means聚类模型1. 最短距离聚类模型（1）每一个转运站看成一类，依次记为，构造38个转运站间的距离矩阵以距离矩阵为基础，利用最短距离方法聚类2）算法流程Step1：在距离矩阵的非对角元素中找出距离最短的两个类和，并为一新类Step2：然后按计算公式计算原来各类与新类之间的距离，得到一个新的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.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）7同乐村站（333.31，758.42）26新围村站(509.69,862.21)8松坪山（二）站(414.05,705.39)27大冲站4)9大新小学站(294.92,585.53)28沙河市场站(591.91,629.27)10南山村站(251.38,456.19)29龙井(630.57,731.07)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.92,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，我们得出：一区建立92台小型设备；二区建立2台大型设备和8台小型设备；三区建立138台小型设备在不考虑运费的情况下，我们计算出总费用为：15440万元2. k-Means 聚类模型：（1）k-Means [5] 聚类基本思路：接受聚类参数k，然后将事先输入的n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的2）算法流程Step1：从数据集中任意选取3赋给初始的聚类中心，，Step2：对数据集中的每个样本点，计算其与各个聚类中心的欧式距离并获取其类别标号：。
Step3：按下式重新计算3聚类中心Step4：重复Stept2和Stept3，直到达到最大迭代次数为止3）k-Means聚类模型求解我们利用第一部分测出38个垃圾转运站的坐标值然后利用Matlab中的pdist函数和squareform函数将坐标转化为距离矩阵，并利用k-Means函数进行最短距离聚类，得到如下三部分结果：表3. 垃圾转运站分类结果类别垃圾转运站一类玉泉站 平山村站 同乐村站 松坪山（二）站 光前站 白石洲南站 松坪山站 大冲站 沙河市场站 龙井 华侨城站 深圳大学站 科技园站二类动物园站 牛城村站 阳光(白芒关外)站 福光站 麻勘站 白芒站 大石磡站 长源村站 塘朗站 官龙村站 新围村站 西丽路站三类九街站 大新小学站 南山村站 月亮湾大道站 北头站 涌下村站 前海公园站 南光站 南园站 望海路站 花果路站 南山市场 疏港小区站通过对表3结果的计算和分析，我们得出：一区建立一个大型设备；二区建立以个大型设备；三区建立一个大型设备和14个小型设备在不考虑运费的情况下，我们计算出总费用为：13867万元3 两种模型的比较及最终聚类结果通过对两种方案总费用的比较，我们得出k-means聚类算法为最优方案。
5.1.2 模型二：优化模型——确定厨余垃圾处理中心位置根据表4的垃圾转运站最终聚类结果，以及对于厨余垃圾处理设备的分布设计，我们首先用百度地图测出每一个垃圾转运站至其它各个站点的最短路径长度（i，j ＝ 1，2，…），求出三类内部的距离矩阵下面建立模型确定每一类内部厨余垃圾处理中心的位置以距离和各转运站的厨余垃圾量乘积之和为运行成本，以成本值为目标函数确定垃圾处理设备的具体位置考虑目标函数其中，为每类内各站点的载荷矩阵（厨余垃圾量）以每一类内部为约束条件，以各垃圾转运站点的载荷加权，用Matlab中的矩阵运算求得每一个站点至其它各个站点的最短路径长度的加权和，最后得出将3个大型厨余垃圾处理设备位置分别如下表表4. 垃圾转运站最终聚类结果类别大型厨余垃圾处理设备位置一类新围公厕垃圾站二类大冲公厕垃圾站三类涌下村5.2 清运路线具体方案的设计5.2.1 模型一：加权载荷模型——车辆的分配由于车辆有限，我们先将16辆车分给三类垃圾的运输，为此建立加权载荷模型1） 模型：观测值；：观测值的对应权数；：权算术平均数（即预测值）2）模型求解运输厨余垃圾的拖车所占比率：运输焚烧垃圾的拖车所占比率：运输填埋垃圾的拖车所占比率：（2）求解车辆的分配用加权载荷法确定每类具体方法如下：表5. 垃圾转运站最终聚类结果车辆类别所占比率车辆数量运输厨余垃圾的车辆5运输焚烧垃圾的车辆4运输填埋垃圾的车辆75.2.2 模型二：TSP模型——清运路线的设计（1）焚烧垃圾的清运路线通过对同中所给数据的分析，以及相关资量的查阅，我们决定采用TSP模型对问题进行求解。
TSP模型[6]路运输问题的最为典型的一个模型，它的全称是TravelingSalesman Problem(TSP)，中文叫做旅行商问题TSP模型可以如下描述：在给出的一个雄顶点网络(有向或无向)，要求找出一个包含所有甩个顶点的具有最小耗费的环路任何一个包含网络中所有n个顶点的环路被称作一个回路(Tour)在旅行商问题中，要设法找到一条最小耗费的回路既然回路是包含所有顶点的一个循环，故可以把任意一个点作为起点(因此也是终点)，这也是TSP模型的一个特点 TSP模型数学表达式如下：连通图H，其顶点集合A，定点间距离为目标函数：约束条件：决策变量：，从i到j无通路；，从i到j有通路我们首先利用k-Means聚类方法将38个垃圾转运站点分成16块，记为P集合，具体数据如下表所示：表6. P集合及该集合的垃圾量块序号垃圾站点序号垃圾量到焚烧厂的距离116,27,2822,7，8,20734,19,2641,9,12，17523,2465,32725,34,38814,15,21,22,306.8,8911,3121.5,221010116,812.3,14.9,1213,29,3717.6,16.7,1513361431535163323然后我们采用TSP模型对集合的垃圾运转路径进行搜索得出焚烧垃圾运输路线如下图。
图1. 焚烧垃圾运输路线图注： :垃圾量超过8.5吨，且一次就能运完的垃圾站点 :表示需要运输两次或两次以上的垃圾站点 :表示垃圾处理中心费用的计算公式：（:表示转运站点之间的距离；:表示末点到处理中心的距离）时间的计算公式：(:表示总路程;a:表示装车的次数;b:表示卸车的次数)（2）填埋垃圾的清运路线此问题的求解过程与焚烧垃圾清运路线的求解过程一样，并且结果基本相同通过计算，每天运输填埋垃圾的总费用为2349元，每辆车需工作4.8个小时3）厨余垃圾的清运路线我们将三类内部的垃圾站点分别采用k-Means聚类方法分成5块，并记为、、集合，具体数据如下表所示：表7. 、、集合中的垃圾量以及到处理中心的距离区块块序号集合垃圾量到涌下村的距离一区123，2417.13，17.13，236321，22，10，14，3049，1，17512二区1722，18，638，20413，27516，28，3517.1，17.1，40三区131，11，5，32234319，4，3425，38，37533然后采用和处理P集合同样的处理方法对 、、进行处理，得出厨余垃圾的运输路线，结果如下图所示：图2. 一区的厨余垃圾运输路线图3. 二区的厨余垃圾运输路线图4. 三区的厨余垃圾运输路线注： :运走n*10吨后,还有剩余的站点(n是次数，n=1,2,…) :垃圾量超过8.5吨，且一次就能运完的垃圾站点 :表示运走n*（8.5～10）吨后无剩余的站点（n是次数，n=2,3，…） :表示需要运输两次或两次以上的垃圾站点 :表示垃圾处理中心小结： 1. 每天厨余垃圾的的产量为460吨，我们通过查找资料得出厨余垃圾经处理设备处理后的产物的产率为0.2，然后计算出厨余垃圾经处理设备处理后的产物量为92吨，其收益为23000～69000元。
2. 我们首先利用题目所给的四类垃圾（厨余垃圾、可回收垃圾、有害垃圾、其他不可回收垃圾）的比例（4:2:1:3）计算出每天产生的可回收垃圾量为230吨，然后，利用可回收垃圾中四类垃圾（纸类、塑料、玻璃、金属）的平均比例计算出相应垃圾的产量，具体结果如下表表8. 可回收垃圾收益表类别产量（吨）收益（元）纸类127019塑料201201玻璃6898金属22994合计438358112 3. 总收益为381112～427112元5.3 垃圾运转站的重新分布设计和大、小型厨余垃圾处理设备的分布设计对于本问题我们采用了k-means模型、集合覆盖模型以及中心位点选址模型进行求解5.3.1 模型一：k-Means模型——垃圾转运站点的初步确定（1）k-Means 聚类基本思路：接受聚类参数k，然后将事先输入的n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的2）算法流程Step1：从数据集中任意选取3赋给初始的聚类中心，，Step2：对数据集中的每个样本点，计算其与各个聚类中心的欧式距离并获取其类别标号：。
Step3：按下式重新计算3聚类中心Step4：重复Stept2和Stept3，直到达到最大迭代次数为止 （3）k-Means模型的求解：我们首先利用excel[3] 深圳所有小区的数据按片区名称分类汇总，并得出每个小区的总人数然后筛选出人数超过2800人的小区以及剩余中房间数超过80间的小区作为分析研究的对象再运用谷歌地球软件测出筛选出来的小区的坐标参照当地人口密度以及垃圾收集密度，算出该城区垃圾收集最优半径为 750m；再结合实际勘探情况以及城市总体规划共布置大型垃圾收集站149座然后通过Matlab软件中的pdist函数和squareform函数将其化为距离方阵，并通过k-Means方法将小区聚为38类然后以每一类中的居民人数和距离作为选取转运站位置的主要依据，用选址问题中的中位点选址方法确定垃圾运转站的位置，5.3.2 模型二：集合覆盖模型——垃圾转运站点的调整集合覆盖模型目标是在满足覆盖所有垃圾运转战的情况下，确定建立大型厨余垃圾处理设备的个数或建设费用最小，并配置这些服务设施使所有的转运站都能被覆盖住到具体表达式如下所示目标函数为从现有m座垃圾运转站的位置中优选出可以覆盖m座垃圾收集站的最小数目的中转站选点；约束式l表示每一座垃圾运转站的垃圾均被清运；约束式2是满足垃圾运转站中转能力的要求；约束式3表示垃圾站和中转站的垃圾量非负；约束式4是垃圾收集站是否位于第k座垃圾中转站附近的决策变量；约束式5是第j座垃圾收集站是否有垃圾收运到第k座中转站的决策变量。
从而得出垃圾转运站点的位置分布，如下表所示：表9. 垃圾运转站新站点分布编号片区名称地址总人数垃圾转运量1平山村站南山区平山村内28943233207网格片区 汇总南山华泰小区7941307网格片区 汇总后海小学4001401网格片区 汇总登良路与南商路交叉口处333305南山村站东滨路与前海路交汇处411356沙河市场站南山区沙河市场旁798037大冲站深南大道大冲村旁199978前海公园站南山区前海公园内191119龙井龙珠五路龙井村旁3202810大新小学站南头街大新小学旁581291103网格片区 汇总大磡村综合市场173461201网格片区 汇总公园路与招商路163331322网格片区 汇总新围村1473414华侨城站侨城东路西侧214551505网格片区 汇总白芒村南2251216北头站前海路与桂庙路交叉口1041917动物园站深圳野生动物园120401816网格片区 汇总留仙洞村1306219南园站南山区南园村内4060920白石洲站白石洲与石洲中路交叉口289392107网格片区 汇总西丽路22612221网格 汇总珠光村152132304网格片区 汇总北环大道与京港澳高速公路交叉口1368324玉泉站玉泉路宝龙路口2373425九街站深南大道南头中学旁120482610网格片区 汇总官龙村1706627深圳科技工业园大厦深圳科技工业园大厦168252803网格片区 汇总东角头-地铁站202952907网格片区 汇总玉泉路142513011网格片区 汇总兴海大道蛇口站126593102网格片区 汇总南山区福光村内5080773432松坪山（二）站高新北区朗山一路绿地内2047133深圳大学站校园内810634平山P片区 汇总创业路与南光路交叉口1748635科技园站科苑南路与滨海路大道交汇处西侧863336松坪山站南山区松坪山第五工业区30543703网格片区 汇总桃李花园32813803网格片区 汇总学府路与南山大道交叉口9649图5. 新设计的垃圾转运站分布图5.3.3 模型三：优化模型——厨余垃圾处理中心的确定 1. 聚类分析模型——将38个站点分为三类根据表9的垃圾转运站最终聚类结果，以及对于厨余垃圾处理设备的分布设计，我们首先用百度地图测出每一个垃圾转运站至其它各个站点的最短路径长度（i，j ＝ 1，2，…），求出三类内部的距离矩阵下面建立模型确定每一类内部厨余垃圾处理中心的位置。
以距离和各转运站的厨余垃圾量乘积之和为运行成本，以成本值为目标函数确定垃圾处理设备的具体位置考虑目标函数其中，为每类内各站点的载荷矩阵（厨余垃圾量）我们首先采用与解决问题一同样的方法确定38个垃圾站点的坐标，结果如下表：编号坐标编号坐标1（547.1,869.34）20（577.27,550.11）2（345.24,733.22）21（494.08,783.75）3（392.92,386.71）22（554.73,769.06）4（362.46,429.27）23（655.83,680.95）5（252.6,454.16）24（391.07,644.08）6（586.87,625）25（312.61,613.73）7（514.02,607.82）26（485.09,882.88）8（264.94,635.45）27（460.24,622.45）9（638.63,730.19）28（374.03,290.08）10（303.64,585.1）29（339.18,643.76）11（623.8,1066.86）30（205.16,262.11）12（340.02,311.26）31（731.16,914.41）13（511.47,859.4）32（425.96,704.59）14（730,599.32）33（431.65,569.51）15（433.04,1108.14）34（344.07,468.1）16（287.36,506.84）35（455.62,498.45）17（556.8,910.94）36（478.67,696.43）18（381.51,866.35）37（294.47,558.23）19（308.44,486.35）38（342.25,532.26）然后利用k-Means聚类法将38个站点分为三个区，结果如下表11. 新垃圾转运站最终聚类结果分块转运站编号11，9，11，13，14，15，17，18，21，22，23，26，3122，6，7，8，10，20，24，25，27，29，32，33，35，3633，4，5，12，16，19，28，30，34，37，38 2. k-Means 聚类模型——厨余垃圾处理中心的确定：我们采用与相同的处理方法在三类中选出最优的厨余垃圾处理设备的安放位置，其结果如下表表12. 垃圾转运站最终聚类结果类别大型厨余垃圾处理设备位置一类1二类4三类275.4 垃圾运转站位置重新设计后清运路线具体方案设计5.4.1 模型三：加权载荷模型——车辆的分配1. 拖车的分配：此问题的解决方法与问题2的处理方法相同，由于车辆有限，我们先将16辆车分给三类垃圾的运输，为此建立加权载荷模型。
1） 模型：观测值；：观测值的对应权数；：权算术平均数（即预测值）2）模型求解所得结果如下表13. 垃圾转运站最终聚类结果车辆类别所占比率车辆数量运输厨余垃圾的车辆5运输焚烧垃圾的车辆4运输填埋垃圾的车辆72. 汽车的分配：我们采用按垃圾量分配的解决方法，利用公式得出每个垃圾站点所需2.5吨汽车的数量编号汽车数量编号汽车数量编号汽车数量111432722115228331161292421713035118131262191321712023318421134191221351102232362112241371122251382131261对于2.5吨汽车收集垃圾的路线一般采用TVR模型算法，我们通过上网查询发现深圳市现在并不存在70#汽油，我们采用深圳市价格最低为7元/升的90#汽油计算，得到2.5吨汽车每天使用油费为3225.6元5.4.2 模型三：TSP模型——清运路线的设计（1）焚烧垃圾和填埋垃圾的清运路线的方案设计：我们首先利用k-Means聚类方法将38个垃圾转运站点分成16块，记为P集合，具体数据如下表所示：表15. P集合及该集合的垃圾量块序号垃圾站点序号垃圾量到焚烧厂的距离115,11231317,26,1,13418521,2269,2317,1971482,32,361.3,2.2,5.5,97,6,201024,271129,8,25,101233,351338,37,16,19,24143,4,51512,281630然后采用TSP模型确定清运路线，结果如下：图6. 新焚烧垃圾运输路线图注： :垃圾量超过8.5吨，且一次就能运完的垃圾站点 :表示需要运输两次或两次以上的垃圾站点 :表示垃圾处理中心每天的总费用1236元：,每辆车须工作5个小时 填埋垃圾的清运路线与焚烧垃圾的清运路线基本相同，每天总费用为2132元，每辆车需工作4.9个小时。
2）厨余垃圾清运路线的设计我们将三类内部的垃圾站点分别采用k-Means聚类方法分成5块，并记为、、集合，具体数据如下表所示：表16. 、、 集合及其垃圾量块区块序号垃圾站点序号垃圾量到焚烧厂的距离一区115,11218331417,26,13,21,2259,23614二区12,32229,24336,748,25,10,37,3856,20633,35三区116,19,34,59.8,9.8,11.6,12.6,2310312,28430结果如下图所示图7. 新一区的厨余垃圾运输路线图8. 新二区的厨余垃圾运输路线图9. 新三区的厨余垃圾运输路线注： :运走n*10吨后,还有剩余的站点(n是次数，n=1,2,…) :垃圾量超过8.5吨，且一次就能运完的垃圾站点 :表示运走n*（8.5～10）吨后无剩余的站点（n是次数，n=2,3，…） :表示需要运输两次或两次以上的垃圾站点 :表示垃圾处理中心小结：1. 每天厨余垃圾的的产量为512吨，我们通过查找资料得出厨余垃圾经处理设备处理后的产物的产率为0.2，然后计算出厨余垃圾经处理设备处理后的产物量为102.4吨，其收益为25600～76800元。
2. 我们首先利用题目所给的四类垃圾（厨余垃圾、可回收垃圾、有害垃圾、其他不可回收垃圾）的比例（4:2:1:3）计算出每天产生的可回收垃圾量为230吨，然后，利用可回收垃圾中四类垃圾（纸类、塑料、玻璃、金属）的平均比例计算出相应垃圾的产量，具体结果如下表表17. 可回收垃圾收益表类别产量（吨）收益（元）纸类140800塑料224000玻璃7680金属25600合计2563980803. 总收益为423680～474880元六、模型评价与推广6.1 模型的评价1. 对于厨余垃圾处理设备的分配问题，我们建立了两种数学模型，即最短距离聚类模型和k-Means聚类模型，并通过对两者的比较得出最优解决方案避免了只采用一种方案而产生的结果不准确2. 对于厨余设备的分配我们把复杂因素简单化，抓住两个重要因素即厨余垃圾的转运量和转运站到处理中心的距离进行分析建立模型较好的解决了厨余设备的选址为题，避免了问题的复杂化3. 我们把几何覆盖模型运用到垃圾转运站点的选址问题上，有效的解决了近距离垃圾转运站的重叠，从而有效的减少了资金投入1.第二问中对于垃圾转运站选址问题，我们所考虑的因素较少，没有考虑到交通因素、占地费用因素以及每个地方垃圾量的不确定性等，因此的出的结果不够准确。
2.对于2.5吨汽车的分配问题，由于题中所给的数据有限和未考虑汽车运输时的排队问题，造成汽车分配不够恰当6.2 模型的改进1. 在解决垃圾站点重新设计问题的数据处理时，由于时间有限，我们将2800人以下的小区忽略了，这将导致垃圾站点的分布存在偏差如果时间充裕，将所有小区的人数纳入考虑范围内，那么，垃圾站点的分布将更精确2. 对重新设计后每个站点的垃圾量的计算，我们还可以考虑多重因素（如人口数量，房间数量，地域因素）并参照原垃圾转运站收集垃圾的区域以及垃圾量进行差值拟合，用Matlab进行编程，得到每一片小的区域产生的垃圾数量再以各垃圾转运站运输费用最少为目标，划定各垃圾转运站点的收集范围最后把各个小区域的垃圾量加和，得出每个垃圾转运站收集的垃圾量 6.3 模型的推广本文在对城市生活垃圾收运系统各个环节进行深入分析的基础上，结合现代物流理论，以经济最优化为目标，提出了城市垃圾收运系统的优化方法和数学模型，在解决深圳市南山区垃圾处理问题上准确性较高具有通用性，可以推广到全国各大城市的垃圾处理方案设计中以及特定情况下的货物运输问题中七、参考文献[1] 赵静, 但琦. 数学建模与数学实验[M]. 北京: 高等教育出版社, 2004, 8.[2] 纪震，廖惠连，吴青华. 粒子群算法及应用[M]. 北京: 科学出版社, 2009, 1.[3] 袁新生等. LINGO和Excel在数学建模中的应用[M]. 北京: 科学出版社, 2007.[4] 黄雍检, 赖明勇. MATLAB语言在运筹学中的应用[M]. 湖南: 湖南大学出版社, 2005, 5.[5] 王祝文, 刘菁华, 任莉. 基于K均值动态聚类分析的地球物理测井岩性分类方法[J]. 东华理工大学学报, 2009, 2.[6] 吴翊, 吴孟达, 成礼智. 数学建模的理论与实践[M]. 长沙: 国防科技大学, 1999, 8.附 录附录1：最短距离聚类谱系图的绘制：X=[0 8 7.4 11.3 9.8 11.9 21.1 22.2 18.6; 8 0 11.3 8.7 9.9 10.7 17.4 18.7 28; 7.4 11.3 0 2.2 1.2 3.7 13 3.7 10.4; 11.3 8.7 2.2 0 3.6 4.3 11.3 12 22.5; 9.8 9.9 1.2 3.6 0 2.2 7.7 8.6 7.8; 11.9 10.7 3.7 4.3 2.2 0 3.7 3.6 3.6; 21.1 17.4 13 11.3 7.7 3.7 0 6.25 21; 22.2 18.7 3.7 12 8.6 3.6 1.25 0 3.8; 18.6 28 10.4 22.5 7.8 3.6 21 3.8 0];BX=zscore(X); Y=pdist(X) D=squareform(Y) Z = linkage(Y) T = cluster(Z,3) [H,T]=dendrogram(Z) 附录2：38个转运站用k-Means聚类的编程a = [310.88,614.74;387.25,643.88;557.51,912.21;550.19,869.55;364.03,1035.02;456.6,501.66;333.31,758.42;414.05,705.39;294.92,585.53;251.38,456.19; 423.74,1128.34;262.01,643.21;566.28,740.23;289.49,502.03;303.78,552.77;576.85,551.37;267.75,635.54;432.21,569.66;481.69,883.28;472.67,708.31; 346.3,485.51;305.11,490.7;377.43,272.8;373.79,297.45;731.16,918.44;509.69,862.21;512.03,609.54;591.91,629.27;630.57,731.07;315.83,525.02; 507.74,1158.73;440.77,1087.5;621.53,1054.34;810.19,928.92;728.92,597.51;186.92,286.51;489.97,788.75;738.11,904.59];b = pdist(a),data=squareform(b),[Idx,C,sumD,D]=Kmeans(data,3,'dist','sqEuclidean','rep',100)附录3：一区大型厨余垃圾处理设备分布位置：D1=[0 0.76 4.9 6.3 6.7 6.1 7.2 7.1 8.3 8.9 8.9 9.8 12.9; 0.76 0 5.5 6 6.4 5.8 6.9 6.8 8 8.6 8.6 9.5 12.6; 0.49 5.5 0 6.6 6.2 4.5 5.4 6.1 7.1 7 8.9 7.5 14; 6.3 6 6.6 0 0.69 2.4 2.1 1.2 2.3 2.9 2.9 4.4 7.8; 6.7 6.4 6.2 6.9 0 2.0 2.0 0.86 2.0 2.8 3.4 4.2 8.4; 6.1 5.8 4.5 2.4 2.0 0 1.1 1.7 2.8 2.8 4.7 4.1 10.7; 7.2 6.9 5.4 2.1 2.0 1.1 0 0.76 1.9 2.6 3.4 4.1 8.3; 7.1 6.8 6.1 1.2 0.86 1.7 0.76 0 1.2 1.7 2.9 3.2 8.8; 8.3 8.0 7.1 2.3 2.0 2.8 1.9 1.2 0 0.54 2.0 2.6 3.8; 8.9 8.6 7.0 2.9 2.8 2.8 2.6 1.7 0.54 0 1.3 1.9 3.1; 8.9 8.6 8.9 2.9 3.5 4.7 3.4 2.9 2.0 1.3 0 2.3 3.1; 9.8 9.5 7.5 4.4 4.2 4.1 4.1 3.2 2.6 1.9 2.3 0 1.1; 12.9 12.6 14 7.8 8.4 10.7 8.3 8.8 3.8 3.1 3.1 1.1 0],B=[17.13 22.84 17.13 8.565 8.565 14.275 8.565 14.275 11.42 17.13 11.42 9.136 22.84],S=D1*B'min(S)附录4：二区大型厨余垃圾处理设备分布位置：D1=[0 4.0 6.6 11.7 4.0 8.5 5.5 5.8 8.8 6.9 6.9 10.8; 4.0 0 0.99 6.5 1.7 7.2 5.4 3.4 8.2 10.4 6.4 10.2; 6.6 0.99 0 5.1 3.2 3.7 4.5 3.9 5.1 7.3 5.5 7.1; 11.7 6.5 5.1 0 8.5 5.2 8.3 5.4 6.0 8.3 2.3 8.1; 4.0 1.7 3.2 8.5 0 3.6 1.9 4.9 4.9 7.2 11.1 7.0; 8.5 7.2 3.7 5.2 3.6 0 3.6 1.1 1.4 3.6 7.7 3.4; 5.5 5.4 4.5 8.3 1.9 3.6 0 2.8 4.2 6.4 8.9 6.2; 5.8 3.4 3.9 5.4 4.9 1.1 2.8 0 3.6 5.5 11.1 5.4; 8.8 8.2 5.1 6.0 4.9 1.4 4.2 3.6 0 2.2 6.8 2.0; 6.9 10.4 7.3 8.3 7.2 3.6 6.4 5.6 2.2 0 8.8 2.1; 6.6 6.4 5.5 2.3 11.1 7.7 8.9 11.1 6.8 8.8 0 6.1; 10.8 10.2 7.1 8.1 7.0 3.4 6.2 5.4 2.0 2.1 6.1 0],A=[2.855 5.71 14.275 11.42 14.275 19.985 8.565 11.42 17.13 17.13 8.565 39.97],S=D1*A'min(S)附录5：三区大型厨余垃圾处理设备分布位置：D3=[0 2.8 5.3 11 2.4 7 7.1 8.6 8.1 9.6 10.1 10 3.8; 2.8 0 4.1 12.7 0.7 4.9 6.0 7.6 7.6 10.5 10.4 10.4 3.9; 5.3 4.1 0 11.4 3.2 3.6 4.7 6.6 6.2 8.8 8.6 9.1 9.4; 11 12.7 11.4 0 11.8 8.3 7.6 7.5 9.1 6.7 6.3 9.1 12.3; 2.4 0.7 3.2 11.8 0 4.4 5.2 7.1 。