城市垃圾模型.doc

城市生活垃圾管理问题摘要经过对城市生活垃圾管理问题的研究，并建立了短期城市生活垃圾预测模型和对收集垃圾最短路程的模型，并对此完成了模型评价。对于模型一，选取北京市为例，找到北京市1994至2003年垃圾产量统计数据，根据数据利用spss画出散点图，从图像中，发现2000年北京市垃圾产量突然减少很多，然后在逐年递增，关于2000年产量突然减少的原因有很多种，所以要预测北京市短期内的垃圾产量值，应该以2000年以后的数据为参考标准。再利用spss模拟拟合出2000年以后的垃圾产量图，可以得到拟合的指数模型： ，然后再做残差分析，发现相对误差都在10%以内，所以这个模型对于这个城市的预测还是相对成功的，具体比较结果如图表，所以可以利用该模型预测短期内北京市垃圾年产量，说明北京市的垃圾年产量是成指数增长的，城市管理者应该制定出相应的措施来科学的规范。对于问题二，为了解决如何安排收运路线方能使行车路程最短，可以转化为一个求最段路径的问题，在该题目中，我们选择模拟退火算法来解决该问题。首先对目标函数的提出，通过matlab编程，使用分类的办法给出初始解，将所有的垃圾收集站点归纳成一个大类，使用垃圾收集车的最大载量做为限制因子，划归出一系列的单子独立子分类，选取一组随机组合而又不重合单子独立子分类,在此组单子独立子分类的基础上，再进行模拟退火算法，使其结果更接近全局最优解。因此在这个问题中，对传统的模拟退火算法进行了优良改进，使其模拟退火算法打破了单一性的限制，而又保存了全局最优解的特性，使模型适用性更强，鲁棒性更高。关键词：spss应用 非线性拟合 模拟退火算法 单子独立子分类 问题重述随着人类生产和生活的不断发展，由此而产生的垃圾对生态环境及人类生存带来极大的威胁，成为重要的社会问题。一个地区垃圾的数量影响着该地区的环境，经济等诸多方面。对未来某段时间内垃圾产量的准确预测是相关垃圾管理的部门做出管理规划的前提。准确的预测有利于垃圾管理部门做出正确的管理办法，从而减少对垃圾管理的费用，另外，城市垃圾自其产生到最终被送到处置场处理，需要环卫部门对其进行收集与运输，这一过程称为城市垃圾的收运，合适的垃圾收运方法也有利于减少对城市垃圾管理的费用。收集某城市的垃圾产量，在此基础上建立模型，对该城市未来短期内的垃圾产量做出初步预测，并分析模型的准确性跟实用性。假设某城市有多个行政区，每个区内均有一个车库，假设某一车库拥有最大装载量为 w 的垃圾收集车 k 辆，并且该区的垃圾收集点（待收集垃圾的点）有 n个，该城市共有垃圾中转站 p 座。每天 k 辆垃圾车从车库出发，经过收集点收集垃圾，当垃圾负载达到最大装载量时，垃圾车运往中转站，在中转站卸下所有收运的垃圾，然后再出站收集垃圾，如此反复，直到所有收集点的垃圾都被收集完，垃圾车返回车库。以上收运过程均在各点的工作区间之内完成。（注：必须在收集点的工作区间之内，垃圾车才能在该点收集垃圾。）在要考虑车库和收集点、收集点与中转站、中转站与车库的距离；各收集点每天的垃圾产量；每辆垃圾收运车的最大载荷；垃圾收集点、车库、中转站的工作区间a,b的条件下，如何安排垃圾收运车的收运路线，使在垃圾收运车的行车里程尽可能的少，或者垃圾收运时间尽可能短。建立数学模型来达到上述目的，并设计出有效的算法，针对附录中给出的数据，求解模型。并且对模型的适用性、算法的稳定性和鲁棒性做出分析。问题分析问题一的分析：对未来某段时间内垃圾产量的准确预测是相关垃圾管理的部门做出管理规划的前提。因此选择合适预测模型，作出精确的预测有着重要意义。对于问题一，要预测出该城市短期内的垃圾产量，我们可以根据以前某段时期内垃圾产量，通过非线性拟合的方式求出该城市垃圾产量的数学模型，根据此模型可以粗略计算出该城市短期内的城市垃圾产量。对预测情况进行分析，然后做出改进模型，从而得出更准确的预测数据。问题二的分析：有关垃圾收运路线的最优求解问题，对于规划城区卫生建设和资源的合理调度利用方面具有重要意义。问题二是关于最短路径问题，在安排垃圾运载车的收运路线问题中，有着诸多的限制因子的存在，譬如中转站与运载车最大载量的限制，使问题不再是“求经过这些不重复点的最短路径”的问题，再与多辆垃圾运载车的条件相结合，使问题变得多元化，若不同时考虑多元化的限制，则很容易得到局部最优解，使结果误差增大，而在众多的算法中，现代算法中的模拟退火算法，是从全局的角度来算最优解的。所以我们选择模拟退火算法。模型假设与符号说明符号说明代表年份，（时表示是1994年） 代表某城市的垃圾年产量代 表该区垃圾收集点的数量代表该区垃圾中转站的数量代表该区垃圾收集车的数量代表该区垃圾第个收集点代表该区垃圾第个中转站代表该区垃圾第辆收集车行驶的总路程此为“对应”的的意思（横向对应）此为“对应”的的意思（纵向对应）代表在坐标上的垃圾量为模型假设：1.文中所提的垃圾清运量能代表北京市的城市生活垃圾总量；2.预测时间范围内不会出现严重影响预测结果的事件（自然灾害，战争等）；3.短时间内收集点每天的垃圾量一定；4.垃圾车的车速在行驶过程中始终保持恒定；5.直到所有收集点的垃圾都被收集完，垃圾车才返回车库；6.行驶街道均平行于坐标轴。模型建立与求解建立模型一：假设某城市前年垃圾年产量序列，对原始数据利用spss做出散点图，然后通过非线性拟合得到拟合模型： 从而可得出各个年份的垃圾产量预测值。根据预测值跟实际值的残差分析，通过残差分析，相对残差检验，得出最终适合该城市垃圾产量的预测模型，然后预测出未来的垃圾产量。 模型的求解：根据北京统计信息网可知：表一年份1994199519961997199819992000200120022003北京432.4447.5483460.5495450.1296309321361.4根据表一数据，利用spss画散点图：图一：从图像以及数据中，发现在时（即2000年），北京市垃圾年产量变化很大，这可能跟当时的社会实际情况有关，因为影响垃圾年产量的年产量的因素很多，其中包括人口、经济等各方面。据了解，2000年北京加大了对城市的管理建设，为了在新世纪打出中国的最好的名片以及更有把握的申奥成功，所以在2000年北京市的垃圾年产量减少很多，所以应该以2000年以后的垃圾产量数据为前提来对北京市未来垃圾产量进行预测。根据2000年后北京市垃圾产量利用spss做出拟合图形图形：根据拟合图像得出拟合模型：根据拟合模型得出预测值，再将预测值与实际值进行残差比较，根据残差分心，发现相对残差均在5%内，所以这个模型基本适应于北京市的垃圾产量预测，然后根据此模型得出未来6年内的预测值：模型评价： 该模型建立方便，求解简单，预测北京市垃圾成指数增长，符合该市的实际情况，但是由于所选数据个数有限，所以只能是对短期进行预测，不能达到长期预测目的。建立模型二： 我们假设辆垃圾收集车行驶以下路程表示为：编号为的这一辆垃圾收集车从车库（）出发，依次经过、这两个垃圾站点并收集两站点的垃圾，到这个中转站并全部卸掉垃圾，并接着从出发，再依次经过、这三个垃圾站点并收集三站点的垃圾，到这个中转站并全部卸掉垃圾，再回到车库。而即表示编号为的这一辆垃圾收集车在这一趟工作时行驶的总路程。 目标函数： 在中存在： 表示着编号为的垃圾中转站坐标为，需要垃圾收集车收集0个单位的垃圾量。表示编号为的垃圾站点坐标为，需要垃圾收集车收集个单位的垃圾量。用模拟退火算法求解，描述如下：（1） 分类，选出一组分类，作为初始解将划成几个互不重叠的子分类，使其满足条件为每个子分类的垃圾总量不超过车辆的最大载量，选出其中一组子分类，作为模拟退火算法的初始解，使用其程序（划类程序见附表）例如：摘取原题表1的一段数据：2 -4848260.00 4201545.00 0000 2400 25 6.00 13 -4846395.00 4201227.00 0000 2400 25 4.00 14 -4846328.00 4201235.00 0000 2400 25 4.00 15 -4854754.00 4198649.00 0000 2400 75 24.00 16 -4861521.00 4203864.00 0000 2400 25 8.00 1用划类程序程序运行得：ret_array = 1.0e+005 *0.0000 0 0 0 0 -0.0000 0.2176 1.82760 0.0000 0 0 0 -0.0000 0.2087 1.82380.0000 0.0000 0 0 0 0.0199 0.2087 1.82380 0 0.0000 0 0 -0.0000 0.2089 1.82390.0000 0 0.0000 0 0 0.0196 0.2089 1.8239 0 0.0000 0.0000 0 0 0.0003 0.2087 1.8238 0.0000 0.0000 0.0000 0 0 0.0003 0.2087 1.8238 0 0 0 0.0000 0 -0.0000 0.2239 1.8025 0.0000 0 0 0.0000 0 0.0711 0.2176 1.8025 0 0.0000 0 0.0000 0 0.0884 0.2087 1.8025 0.0000 0.0000 0 0.0000 0 0.0199 0.2087 1.8025 0 0 0.0000 0.0000 0 0.0881 0.2089 1.8025 0.0000 0 0.0000 0.0000 0 0.0196 0.2089 1.8025 0 0.0000 0.0000 0.0000 0 0.0003 0.2087 1.8025 0.0000 0.0000 0.0000 0.0000 0 0.0003 0.2087 1.8025 0 0 0 0 0.0000 -0.0000 0.3074 1.8608 0.0000 0 0 0 0.0000 0.1346 0.2176 1.8276 0 0.0000 0 0 0.0000 0.1545 0.2087 1.8238 0.0000 0.0000 0 0 0.0000 0.0199 0.2087 1.8238 0 0 0.0000 0 0.0000 0.1542 0.2089 1.8239 0.0000 0 0.0000 0 0.0000 0.0196 0.2089 1.8239 0 0.0000 0.0000 0 0.0000 0.0003 0.2087 1.8238 0.0000 0.0000 0.0000 0 0.0000 0.0003 0.2087 1.8238 0 0 0 0.0000 0.0000 0.0854 0.2239 1.8025 0.0000 0 0 0.0000 0.0000 0.0711 0.2176 1.8025 0 0.0000 0 0.0000 0.0000 0.0854 0.2087 1.8025 0.0000 0.0000 0 0.0000 0.0000 0.0199 0.2087 1.8025 0 0 0.0000 0.0000 0.0000 0.0854 0.2089 1.8025 0.0000 0 0.0000 0.0000 0.0000 0.0196 0.2089 1.8025 0 0.0000 0.0000 0.0000 0.0000 0.0003 0.2087 1.8025 0.0000 0.0000 0.0000 0.0000 0.0000 0.0003 0.2087 1.8025选取一组随机组合而又不重合单子独立子分类，以单子独立子分类作为模拟退火的新解。（2） 新解的产生 第一种情况：在两个中转站之间交换，不需要考虑车辆的最大载量 （其中与可交换）第二种情况：跨中转站交换，考虑车辆的最大载量 （其中与可交换）第三种情况：在对中转站的交换，考虑车的最大载量 （其中与可交换）不同一辆车之间的交换，考虑车的最大载量 （3） 求的值设某运输情况为当 时 （4） 接受准则 如果，则接受新的路径。否则，以概率接受新路径，即若大于0到1之间的随机数，则接受。（5） 降温利用选定的降温级数进行降温。即,得到新的温度，这里我们取。（6） 结束条件用选定的终止温度，判断退火过程是否结束。若，算法结束，输出当前结果。自设MALTAB求解模型评价： 对于模型二，此模型使用了现代算法中的模拟退火算法，使结果更趋于最优解，对于垃圾运载车的数量、垃圾站点的数量、垃圾中转站的数量不在有限制，从总体上解决了各种设计运输路线的问题，很具有普遍使用性，在计算次数上，因引入了单子独立分类法，使其计算次数大大缩小，从有限的区域值中找最优解，避免了无效值的计算。参考文献1 北京统计信息网 / ， 2009年8月16日2 蔡健平，刘爱玉，spss应用教程M，北京：北京大学出版社，20053 阮晓青，周义仓，数学建模引论M，北京：高等教育出版社，20064 胡良剑，孙晓君，MATLAB数学实验M，北京：高等教育出版社，20095 梁国业，廖健平，数学建模M，北京：冶金工业出版社，20046 康立山，非数值并行算法-模拟退火算法M，北京：科学出版社，2008附录一，退火算法的MATLAB程序max_value = 15;val_array = 1, 0.1, 0.1; 2, 0.2, 0.2; 3, 0.3, 0.3; 4, 0.4, 0.4; 5, 0.5, 0.5;mid_array = 0, 0; 1, 1;min_array = ;min_mid_array = ;ret_array = ; number = size(val_array, 1);length = pow2(number) - 1;for i = 1 : length val_temp = ; val_buff = i; val_sum = 0; for j = 1 : number m = mod(val_buff, 2); val_buff = (val_buff - m) / 2; val_temp(j) = m; end for k = 1 : number if (val_temp(k) = 1) val_sum = val_sum + val_array(k, 1); end end if (val_sum = max_value) ret_array = ret_array; val_temp; endend for t = 1 : size(ret_array, 1) min_temp = ; min_val = -1; for s = 1 : (number - 1) for r = (s + 1) : number val_dis = -1; if (ret_array(t, s) = 1 & ret_array(t