关于深圳南山垃圾清运方案最终论文.doc

深圳南山垃圾分类处理与清运方案设计组员：教技1092 方启梅 数学1092 陈惠玲 电子1192 黎学清目 录摘要3一、问题重述4二、问题假设4三、符号说明5四、模型的建立与求解54.1问题一54.1.1确定大、小型橱余垃圾处理设备数量54.1.2确定橱余设备的位置64.1.3橱余垃圾的清运路线10五、模型优缺点分析13六、参考文献13附录13垃圾分类处理与清运方案设计摘要 随着城市经济的发展及城市化进程的加快，如何对垃圾进行合理地分类收集与处理，对垃圾清运系统进行合理地规划优化设计，已经成为城市规划的重要课题，垃圾转运系统的转运效率和投资效益在城市建设中起着越来越重要的作用。垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资源回收与再利用的城市绿色工程。本文就深圳市南山区垃圾分类处理与清运方案设计的问题进行研究，分析并建立数学模型，利用编程进行求解。 针对问题一：我们主要是要解决两个问题，首先是要确定大小型厨余设备放置的位置，然后在给定的条件下，确定具体的清运路线。我们是运用整数规划的模型，用Winqsb软件求出所需厨余设备的数量，即需要两台大型设备，不用小型设备；接下来我们先用matlab软件找出38个中转站的坐标，根据这些坐标在几何画板上绘出站点，由此我们在原有的转运站上，南北各放一个设备，两转运站之间实际距离为权重，画出无向赋权图，转化为图论问题，再根据Floyd算法，运用Winqsb软件确定任意两转运站之间的最短路矩阵和路径矩阵，从而确定设备的位置和清运路线。 对模型的优缺点分析：因为我们重考虑处理中心位置和清运路线，对经济效益和环境保护讨论的较少，考虑那些问题需要设置更多的条件，模型需要再改进。 关键词：整数规划 kmeans算法 清运路线一、 问题重述垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资源回收与再利用的城市绿色工程。在深圳，垃圾分为四类：橱余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾，四类垃圾的比例图如下： 在纸类、塑料、玻璃、金属四类的废品回收价格是每公斤： 1元、2.5元、0.5元、2.5元。在垃圾分类收集与处理中，不同类的垃圾有不同的处理方式，简述如下：1）橱余垃圾可以使用脱水干燥处理装置，处理后的干物质运送饲料加工厂做原料；2）可回收垃圾将收集后分类再利用；3）有害垃圾，运送到固废处理中心集中处理；4）其他不可回收垃圾将运送到填埋场或焚烧场处理。所有垃圾将从小区运送到附近的转运站，再运送到少数几个垃圾处理中心。运用数学建模方法对深圳市南山区的分类化垃圾的实现做一些研究，具体的研究目标是：1）假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计，同时在目前的运输装备条件下给出清运路线的具体方案，以期达到最佳经济效益和环保效果。2）假设转运站允许重新设计，请为问题1）的目标重新设计。二、 问题假设1. 每个站不能同时往处理中心运垃圾；2. 各社区人口数目相对固定，市民每天产生的垃圾量为定值；3. 垃圾转运站及垃圾处理厂每天都处理一次垃圾；4. 各垃圾转运站的垃圾将在当天清运完毕，不能积累；5. 选择转运站和处理中心时，不考虑它们所处地理位置的地产价格；6. 所有运输车辆不得超载，不考虑交通所带来的影响（如：堵车等）；7. 所有运输车和拖车均从转运站出发前往小区或者处理中心，最后再回到转运站，拖车到一个中转站运完垃圾之后便返回处理中心；8. 拖车每次所耗油量与载重量无关。 三、 符号说明f 目标函数（即投资成本最小）x 大型橱余垃圾处理设备数y 小型橱余垃圾处理设备数四、 模型的建立与求解4.1问题一4.1.1确定大、小型橱余垃圾处理设备数量 确定数量，要考虑大、小型橱余垃圾处理设备的投资成本、处理能力、运行成本各不相同，同时要使设备的投资金额尽量小。假设大型橱余垃圾处理设备数为x，小型橱余垃圾处理设备数y，目标函数为投资金额Z，取小型处理设备每天处理0.25顿，于是有方程其中约束条件为：所建处理厂能够处理所有的橱余垃圾：1)所建处理厂能够处理所有的橱余垃圾：2)橱余垃圾处理厂的数量非负：3)处理厂数量必为整数：以上几个方程构成了整数规划问题，要求目标函数尽量小，即在满足使投资金额最小：用Winqsb求解可得到最佳结果为：即两台大型设备就可以满足要求。 综上所述，大型设备的投资额虽然比较高，但是运行成本低，运行效率高；小型橱余垃圾处理设备的处理能力远小于大型设备，且运行成本较高，性价比低，不适宜于大规模应用，因此选两台大型设备来处理橱余垃圾是合理的。4.1.2确定橱余设备的位置 1、模型的建立由上一步求出，恰好只需要2台大型的橱余垃圾处理设备，因此可以考虑将南山分成两个区域，每个区域在合适的位置安放一台处理设备，使得区域内各转运站到该设备所在的处理中心的距离之和最小，再确定各转运站到橱余垃圾处理中心的最优路线。为方便定位及分区，用matlab把南山区的地图导入，确定每个转运站的位置的坐标。表一 各个转运站坐标表序号垃圾转运站名称XY1九街站2.22582.85062玉泉站2.75023.04993动物园站3.93294.89424平山村站3.88064.6025牛城村站2.59255.7516科技园站3.2292.06847同乐村站2.37883.84328松坪山（二）站2.93193.47749大新小学站2.11672.655810南山村站2.2612.233911阳光(白芒关外)站2.99686.386512月亮湾大道站1.89483.051313光前站3.9973.70914北头站2.08032.078115涌下村站2.17932.430716白石洲南站4.06622.405517前海公园站1.93083.004118深圳大学站3.05512.54219官龙村站3.39514.702620松坪山站3.33233.500121南光站2.46911.963322南园站2.18711.996223望海路站2.68260.502724花果路站2.65640.672125福光站5.14844.934526新围村站3.59644.552527大冲站3.61122.805228沙河市场站4.16942.936529龙井4.44043.634630南山市场2.26392.235431麻勘站3.58496.544632白芒站3.11626.10833大石磡站4.38235.870634长源村站5.7015.007335华侨城站5.13922.706336疏港小区站1.37920.598437西丽路站3.45214.049838塘朗站5.19624.8458 2、关于算法 应用kmeans算法，我们将38个垃圾站分出区域。 以下是对Kmeans算法的描述： 给定一个包含n个数据的数据集和生成聚-类的个数k，算法将n个数据划分成k个子集，每个子集代表一个聚类，同一聚类中的数据间距离较近，而不同聚类的数据间距离较远。每个聚类由其中心值来表示，通过计算聚类中所有数据的平均值可以得到它的中心值。算法：输入：生成聚类的数目和包含个对象的数据集。输出：个聚类中心，及个聚类数据对象集合，使得质心点不再发生变化。算法描述：Beginm = 1；initialize k prototypes , j 1 ,K ；Repeatfor i = 1 to n doBeginfor j = 1 to k docompute D(,) =| - |；if D(,) = min D( , ) then ；end ； / / 数据对象归类if m = 1 then ；m=m+1；for j = 1 to k do； / / 重新计算聚类中心;；Until | | = 0End.其中，用于簇和簇之间的距离度量标准是：1)最小距离：，其中和2)最大距离：，其中和3)中间距离：，其中和是和的质心4)平均距离：，其中和，且和是类和间的样本数。5)误差平方和准则：，其中，是的质心，即所有样本的平方误差和。 3、结果 1）用matlab编程可得：并求出两个中心值： 则说明，38个垃圾站被分为南北两区，北区有16个，南区有22个。2）用matlab 分别将两个处理中心绘入图中，并将相应的垃圾站点的序号标入，得到下图：4.1.3橱余垃圾的清运路线1、上下两个区域的赋权图通过查找资料，通过googel地图，判断任意两个转运站之间是否连通，如何连通，在每个区域中，以垃圾转运站作为无向赋权图的节点，用matlab求出任意两点间的距离，将其做为无向边的权值，用图论工具得到上下两个区域的无向赋权图（如图一、图二）。图一 南山区分区后的北区区域的无向赋权图图二 南山区分区后的南区区域的无向赋权图2、由Floyd算法得到最短路矩阵和路径矩阵算法描述设G是赋权图，权为实属，。：i到j的距离。：i到j之间的插入点输入：带权邻接矩阵（1）赋初值：对所有；（2）更新：对所有I,j，若，则；（3）若，停止，否则，转（2）。3、确定厨余垃圾清运路线 在图论软件上易得各点到橱余垃圾处理中心的最短路径表二 北区路线图转运站编号路线每趟垃圾量/吨55193z116111132z17.21313z1826263z1162929z163131z143333z112343425z16353513z13637374z1163838z14表三 南区路线图转运站编号路线每趟垃圾量/吨88202z2249915z220121272z22816166z22017171z214.420202z220222221z21223232421z23028282718z25036361430z232五、 模型优缺点分析 针对南山区垃圾垃圾分类处理与清运方案设计，我们采用了整数规划模型和适用于图论问题的Floyd算法。整数规划模型考虑到现有的约束条件下，给出了合理精确的解。Floyd算法能在已知权矩阵的情况下，给出最短路矩阵和路径矩阵，在确定合适位置的同时，能给出其余各点到该点的最短路径。但是我们考虑的模型约束条件不够多，重考虑处理中心位置和清运路线，对经济效益和环境保护讨论的较少，结果可能会出现一下偏差，所以需要到时候再改进。六、 参考文献1MATLAB在数学建模中的应用，北京航空航天大学出版社，2011.42数学建模案例精选，科学出版社，2003.31数学建模，中国科学技术大学出版社，2008.8附录1. 分南北两区的matlab编程： x=2.2258 2.8506; 2.75023.0499; 3.9329 4.894; 3.8806 4.602; 2.5925 5.751; 3.229 2.0684; 2.3788 3.8432; 2.93193.4774; 2.1167 2.6558; 2.261 2.2339; 2.9968 6.3865; 1.8948 3.0513; 3.997 3.709; 2.0803 2.0781; 2.17932.4307; 4.0662 2.4055; 1.93083.0041; 3.0551 2.542; 3.3951 4.7026; 3.3323 3.5001; 2.4691 1.9633; 2.1871 1.9962; 2.68260.5027; 2.6564 0.6721; 5.14844.9345; 3.5964 4.5525; 3.61122.8052; 4.1694 2.9365; 4.44043.6346; 2.2639 2.2354; 3.58496.5446; 3.1162 6.108; 4.3823 5.8706; 5.701 5.0073; 5.1392 2.7063; 1.37920.5984; 3.4521 4.0498; 5.19624.8458;k=2n,d=size(x);bn=round(n/k*rand);%第一个随机数在前1/k的范围内nc=x(bn,:);x(2*bn,:);%初始类聚中心cid,nr,centers=kmeans(x,k,nc)for i=1:38 if cid(i)=1; plot(x(i,1),x(i,2),b.) else cid(i)=2 plot(x(i,1),x(i,2),g.) hold on endendstrt=蓝色*为第一类;绿色*为第三类;text(-4,-3.6,strt); %BasicKMeans.m主类 function cid,nr,centers = kmeans(x,k,nc)n,d = size(x);% 设置cid为分类结果显示矩阵cid = zeros(1,n); % Make this different to get the loop started.oldcid = ones(1,n);% The number in each cluster.nr = zeros(1,k); % Set up maximum number of iterations.maxgn= 100;iter = 1;while iter maxgn%计算每个数据到聚类中心的距离 for i=1:n dist = sum(repmat(x(i,:),k,1)-nc).2,2); m,ind = min(dist); % 将当前聚类结果存入cid中 cid(i) = ind; end for i = 1:k%找到每一类的所有数据，计算他们的平均值，作为下次计算的聚类中心? ind = find(cid=i); nc(i,:) = mean(x(ind,:);% 统计每一类的数据个数 nr(i) = length(ind); end iter = iter + 1;end% Now check each observation to see if the error can be minimized some more.% Loop through all points.maxiter = 2;iter = 1;move = 1while iter maxiter & move = 0 move = 0;% 对所有的数据进行再次判断，寻求最佳聚类结果 for i = 1:n dist = sum(repmat(x(i,:),k,1)-nc).2,2); r = cid(i);% 将当前数据属于的类给r dadj = nr./(nr+1).*dist; % 计算调整后的距离 m,ind = min(dadj); % 早到该数据距哪个聚类中心最 if ind = r% 如果不等则聚类中心移动 cid(i) = ind;%将新的聚类结果送给cid ic = find(cid = ind);%重新计算调整当前类别的聚类中心 nc(ind,:) = mean(x(ic,:); move = 1; end end iter = iter+1;end centers = nc; if move = 0 disp(No points were moved after the initial clustering procedure.) else disp(Some points were moved after the initial clustering procedure.) end2. 找出处理中心的matlab编程： x=2.2258 2.8506; 2.7502 3.0499; 3.9329 4.894; 3.8806 4.602; 2.5925 5.751; 3.229 2.0684; 2.3788 3.8432; 2.93193.4774; 2.1167 2.6558; 2.261 2.2339; 2.9968 6.3865; 1.8948 3.0513; 3.997 3.709; 2.0803 2.0781; 2.17932.4307; 4.0662 2.4055; 1.9308 3.0041; 3.0551 2.542; 3.3951 4.7026; 3.3323 3.5001; 2.4691 1.9633; 2.1871 1.9962; 2.68260.5027; 2.6564 0.6721; 5.14844.9345; 3.5964 4.5525; 3.61122.8052; 4.1694 2.9365; 4.44043.6346; 2.2639 2.2354; 3.58496.5446; 3.1162 6.108; 4.3823 5.8706; 5.701 5.0073; 5.1392 2.7063; 1.37920.5984; 3.4521 4.0498; 5.19624.8458;%x=2.2258 2.7502;3.9329 3.8806;2.5925 3.229;2.3788 2.9319;2.1167 2.261;2.9968 1.8948;3.997 2.0803;2.1793 4.0662;1.9308 3.0551;3.3951 3.3323;2.4691 2.1871;2.6826 2.6564;5.1484 3.5964;3.6112 4.1694;4.4404 2.2639;3.5849 3.1162;4.3823 5.701;5.1392 1.3792;3.4521 5.1962;5.1494 4.9501;3.1058 3.398;2.249 5.9316;4.1568 4.5226;5.3442 5.7661;1.6135 4.9487;4.291 5.9219;5.5693 5.5945;4.9959 5.458;3.2974 4.4999;6.0367 6.0038;7.4973 7.3279;3.0655 3.4475;5.1948 5.0635;4.3654 5.7646;1.4554 1.892;2.1294 2.9927;5.2937 7.4016;3.9502 3.1542k=2;n,d=size(x);bn=round(n/k*rand);%第一个随机数在前1/k的范围内nc=x(bn,:);x(2*bn,:);%初始类聚中心cid,nr,centers=kmeans(x,k,nc)for i=1:38 if cid(i)=1; plot(x(i,1),x(i,2),b.) else cid(i)=2 plot(x(i,1),x(i,2),g.) hold on endendtext(x(1,1),x(1,2),1);text(x(2,1),x(2,2),2);text(x(3,1),x(3,2),3);text(x(4,1),x(4,2),4);text(x(5,1),x(5,2),5);text(x(6,1),x(6,2),6);text(x(7,1),x(7,2),7);text(x(8,1),x(8,2),8);text(x(9,1),x(9,2),9);text(x(10,1),x(10,2),10);text(x(11,1),x(11,2),11);text(x(12,1),x(12,2),12);text(x(13,1),x(13,2),13);text(x(14,1),x(14,2),14);text(x(15,1),x(15,2),15);text(x(16,1),x(16,2),16);text(x(17,1),x(17,2),17);text(x(18,1),x(18,2),18);text(x(19,1),x(19,2),19);text(x(20,1),x(20,2),20);text(x(21,1),x(21,2),21);text(x(22,1),x(22,2),22);text(x(23,1),x(23,2),23);text(x(24,1),x(24,2),24);text(x(25,1),x(25,2),25);text(x(26,1),x(26,2),26);text(x(27,1),x(27,2),27);text(x(28,1),x(28,2),28);text(x(29,1),x(29,2),29);text(x(30,1),x(30,2),30);text(x(31,1),x(31,2),31);text(x(32,1),x(32,2),32);text(x(33,1),x(33,2),33);text(x(34,1),x(34,2),34);text(x(35,1),x(35,2),35);text(x(36,1),x(36,2),36);text(x(37,1),x(37,2),37);text(x(38,1),x(38,2),38);plot(4.0345,4.8937,r.);plot(2.6296,2.4046,r.);text(4.0345,4.8937,z1);text(2.6296,2.4046,z2);%BasicKMeans.m主类 function cid,nr,centers = kmeans(x,k,nc)n,d = size(x);% 设置cid为分类结果显示矩阵cid = zeros(1,n); % Make this different to get the loop started.oldcid = ones(1,n);% The number in each cluster.nr = zeros(1,k); % Set up maximum number of iterations.maxgn= 100;iter = 1;while iter maxgn%计算每个数据到聚类中心的距离 for i=1:n dist = sum(repmat(x(i,:),k,1)-nc).2,2); m,ind = min(dist); % 将当前聚类结果存入cid中 cid(i) = ind; end for i = 1:k%找到每一类的所有数据，计算他们的平均值，作为下次计算的聚类中心? ind = find(cid=i); nc(i,:) = mean(x(ind,:);% 统计每一类的数据个数 nr(i) = length(ind); end iter = iter + 1;end% Now check each observation to see if the error can be minimized some more.% Loop through all points.maxiter = 2;iter = 1;move = 1while iter maxiter & move = 0 move = 0;% 对所有的数据进行再次判断，寻求最佳聚类结果 for i = 1:n dist = sum(repmat(x(i,:),k,1)-nc).2,2); r = cid(i);% 将当前数据属