深圳市南山区垃圾分类处理与清运方案设计z...

夏明殷鹏远周骏--------敬上深圳市南山区垃圾分类处理与清运方案设计摘要垃圾如何清运与处理成为一个城市持久发展不可忽视的课题。本文就深圳市南山区垃圾清运与处理进行讨论，分析并提出若干模型，编程进行求解。模型一：逐步收缩法，在已知转运站数目与个数、处理中心个数的情况下，可运用此法确定部分转运站的归属情况。文中对38个转运站进行逐步收缩，确定了33个转运站的归属问题。模型二：重心法选址模型，问题一涉及到从38个转运站优化出三个处理中心的整数规划问题，用一般的整数规划方法，会遇到数据难以进行计算机模拟或无法找到最优解的困难，所以要进行简化，多次嵌套重心选址模型对这一问题得到很好的解决。模型三：为了重新设计方案，我们首先参照垃圾收集密度以及当地人口密度，算出每个垃圾中转站的最优收集，求得可以覆盖m座垃圾收集站的最小数目的中转站的具体分布图，我们运用启发式算法进行集合覆盖模型优化来解决可以覆盖m座垃圾收集站的最小数目的中转站选。关键词：整数规划重心选址法集合覆盖逐步收缩法启发式算法1、问题的重述垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资源回收与再利用的城市绿色工程。在深圳，垃圾分为四类：橱余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾。它们的平均比例为，橱余垃圾：可回收垃圾：有害垃圾：其他不可回收垃圾比例约为4：2：1：3。在垃圾分类收集与处理中，不同类的垃圾有不同的处理方式，简述如下：（1）橱余垃圾可以使用脱水干燥处理装置，处理后的干物质运送饲料加工厂做原料。不同处理规模的设备成本和运行成本（分大型和小型）如下：大型厨余垃圾处理设备，处理能力为200吨/日，投资额约为4500万元，运行成本为150元/吨；小型餐厨垃圾处理机，处理能力为200-300公斤/日，投资额约为28万元，运行成本为200元/吨。橱余垃圾处理后产物价格在1000-1500元/吨。（2）可回收垃圾将收集后分类再利用。（3）有害垃圾将运送到固废处理中心集中处理。（4）其他不可回收垃圾将运送到填埋场或焚烧场处理。所有垃圾将从小区运送到附近的转运站，再运送到少数几个垃圾处理中心。显然，1）和2）两项中，经过处理，回收和利用，产生经济效益，而3）和4）只有消耗处理费用，不产生经济效益。本项研究课题旨在为深圳市的垃圾分类化进程作出贡献。为此请你们运用数学建模方法对深圳市南山区的分类化垃圾的实现做一些研究，具体的研究目标是：问题一：假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计，同时在目前的运输装备条件下给出清运路线的具体方案。以期达到最佳经济效益和环保效果。问题二：假设转运站允许重新设计，请为问题1）的目标重新设计。南山区的垃圾清运设备情况（主要是车辆数目和载重）。拖头（拖车）：只拖十吨的大型厢，只用于从转运站到垃圾中心，每次只拖一个大型“厢”，平均吨公里耗油25L—30L柴油/百公里。收集车辆：只负责从小区的垃圾站到转运站运输。60辆2.5吨汽车，每车耗油20L—35L70#汽油/百公里。司机月薪平均3500元。2、问题分析对于问题一，我们考虑能产生经济效益的厨余垃圾的处理情况，要达到最佳经济效益，需降低成本、损耗，提高回收利润，而单位重量可回收垃圾的回收利润是一定的，所以只需考虑降低成本、损耗，即大小型设备投资总额+运行总成本+耗油量最少，而达到这一目标需要均衡设备类型、数目和运输路线的选择规划。对于大小型设备处理厂的数量，由于不同的设备厂的投资数额、处理能力、运转成本都有差异，利用这些差异粗略分析，可以得出各设备厂的最少数量。根据大小型厨余设备的各种参数，及日垃圾处理量，可确定三个大型处理设备；在合理假设9的基础上，运用逐步收缩法，对部分转运站的归属进行确定；运用重心选址，确定D、E、H的重心坐标，集合内部转运量做叠加；对剩下未定归属阵营的五个点和D、E、H坐标点进行整数规划，最终确定五个点的归属问题；A、B、C内部路线用Dijkstra算法确定。问题二是在问题一上的拓展，使用matlab将汇总后的居民片区在图上描出来，形成一个点集，确定垃圾转运站的位置与数目，再利用问题一的解法，确定处理中心的位置与数目。3模型假设1、假设同一种运载车辆单位距离运输成本一定（不考虑是否满载）。2、各社区人口数目相对固定，市民每天产生的垃圾量是个定值；3、各社区每天垃圾的产生量和社区的人数成正比；4、垃圾转运站及垃圾处理厂（包括大小设备长）每天仅收一次垃圾（早上或晚上）；5、各垃圾转运站的垃圾将在当天清运完毕，不能积累；6、所有运输车辆不得超载；7、每个转运站与各个小区之间，各个转运站与处理中心（焚烧厂、填埋场、大小设备处理厂）之间均有公路直线相通；8、由于车辆有限，各转运站的垃圾只送往一个处理中心（焚烧厂、填埋场、大小设备处理厂）；9、三个大型处理中心大致呈南、中、北分布；11、所有运输车均从转运站出发前往小区或者处理中心，最后再回到转运站；12、可回收垃圾在垃圾中转站被直接回收，以后不再处理考虑；13、有害垃圾及其他不可回收处理方式为焚烧、填埋都可；14、不考虑居民对垃圾中转站得选址的异议。4、符号说明U：38个转运站的集合。A、B、C、D、E、F、G：各种满足文中指定区域内所有转运站的集合。ripo:第i个点需要转运的橱余垃圾量。iW：第i个点是否建设处理厂，取值为0或1，取1代表建设处理厂，取0代表不建设处理厂。ijU：取值为0或1，取1代表从第i点运橱余垃圾到第j点，取0则不运。ijD：从第i点到第j点的最短路程。iF:转运站变动后的目标函数。ia:转运站变动各转运站的纬度矩阵。ib:转运站变动各转运站的经度矩阵。1il:转运站变动各转运站距第一个大型厨余垃圾处理厂的距离。2il:转运站变动各转运站距第二个大型厨余垃圾处理厂的距离。3il:转运站变动各转运站距第三个大型厨余垃圾处理厂的距离。iC:转运站位置变动后各转运站垃圾容量。iP:各小区的人口数量。:人均垃圾产量。5、模型的建立和求解5.1问题一5.1.1大小型厨余设备数目的确定由垃圾转运量统计表知：每天转运垃圾804吨；而厨余垃圾：可回收垃圾=2:1,所以每天厨余垃圾约为536吨；大小型设备的数据如下表：投资额（万）运行成本（元/吨）处理能力（吨/日）大型设备4500150200小型设备282000.2——0.3显然若建三个大型设备处理中心，处理能力绰绰有余，满足需求；若建二个大型设备中心，经计算，需453个小型处理设备，453个小设备不但投资额远大于一个大设备的投资额，而且运行成本还比大型设备高，所以此种方案不可取；一个大型设备更不可取。初步确定建立三个大型处理中心，每个中心一台设备。5.1.2处理中心位置的确定重心选址得到两次应用，第一次为了简化个数；第二次确定处理中心位置。由于南山区垃圾日产量分布大体均匀，可按地理位置分为三个区域，从南到北编号为A、B、C。1）首先对转运站站点个数进行简化根据垃圾转运量统计表及南山地图知：i）龙井公厕转运站（以此站所在纬度为界，包括此站）以北(记为集合D)垃圾转运总量约为223吨每日（稍小于252）；ii）南山市场公厕转运站（包括此站）以南（记为E）垃圾转运总量为215吨每日（稍小于252）；iii）松坪山（二）公厕转运站（包括此站）以北（记为F）垃圾转运总量为258吨每日(略等于300)；iiii）涌下村转运站（包括此站）以南（记为G）垃圾转运总量为310吨每日（略大于300）。DF由i）和iii）剔除出编号为12、2的转运站；由ii）和iiii）剔除出编号为9、18、16的转运站（编号以垃圾转运量统计表为准）。则C包含D，A包含E，B包含（U-F-G）。编号为2、9、12、16、18的转运站怎样划分，使得损耗最小，就是一般整数规划问题了。原来的38个数据则可简化为8个数据。运用重心法求D、E、H的重心n1in1in1in1iPiPi*YiYcPiPi*XiXc）（）（列表如下2）整数规划，解决５个未定转运站的归属问题。编号为2、9、12、16、18的转运站及D、E、（U-F-G）重新编号为1、2、3、4、5、6、7、8，数据如下：12345678坐标(5.7,6.9)(3.9,5.8)(3.3,6.9)(9.3,5.1)(6.5,5.5)（8.8，12.0）（6.2，6.4）（3.1,3.0）垃圾量2530403015223215216目标函数:81j81ijijiijWUproD***min约束条件：i处理厂的处理量不超过200WUproj81iiji*200**j=1,2…8ii保证每个点的垃圾只运到一个处理厂181jijUi=1,2,3…8iii保证只建三个大型处理厂HGE381jjWi=1,2,3…8通过Floyd算法求出任意点的最短路程，使用VisualC++编程求解，程序：（见附录）3）A、B、C各区路线的确定。在前两步求得的处理站与垃圾运向的基础上，运用Dijkstra算法求出最短线作为清运路线。（程序及清运方案见附录）5.2问题二中转站的选址目标主要以垃圾中转站建设和运行成本最低。它是一个中转站选址是否合理的最重要的衡量标准，参照垃圾收集密度以及当地人口密度，算出每个垃圾中转站的最优收集半径为5米，而后选用集合覆盖模型求出垃圾中转站的待选点，即用尽可能少的垃圾收集中转站去覆盖所有的垃圾收集站。1、目标函数的建立在考虑厨余垃圾量与路线问题及人口密集程度的前提下，中转站的选址点。我们将在垃圾收集站中选出M个做为中转站，则其中的做为厨余垃圾处理厂的中转站的选取是由最优收集半径的大小而定的。根据m个厨余垃圾处理厂的选点，建立如下最优化模型:MkkWFMin1:(11)2、约束条件的确立目标函数为从现有M座垃圾中转站的位置中优选出可以覆盖38座中转站的最小数目的中转站选点。（1）对于每一座垃圾中转站，其厨余垃圾均被清运，即：()1ikkBiU(1,2,,...,)im(12)（2）厨余垃圾处理厂能处理垃圾的能力要满足一定的要求：()iikkkiAkXUCW(1,2,...,;())imkBi(13)（3）垃圾中转站和厨余垃圾处理厂的垃圾量均非负，即满足不等式：,0,ikXC(1,2,...,;())imkBi(14)（4）垃圾中转站是否建立在第k座厨余垃圾处理厂附近的决策变量：0,1kW，10kkWk，建立在第座橱余垃圾场附近，没有建在第座橱余垃圾场附近（5）第i座垃圾中转站是否有垃圾收运到第k座厨余处理厂的决策变量：0,1ikU，1,0ikikUi第座中转站有垃圾运到第座橱余垃圾处理厂，第座中转站没有垃圾运到第k座橱余垃圾处理厂3、单目标规划模型的建立目标函数MkkWFMin1:(15)约束条件：),,2,11)(miUikiBk，（(16)))(;,2,1(,)(iBkmiUWCXkkikAi(17)..ts))(;,2,1(,0,iBkmiCXki(18)1,0Wk(19)1,0Uik(20)()Ak：表示筛选出的第k座垃圾中转站所覆盖的垃圾集合站的集合；Uik：表示第i座垃圾收集站是否被第k座垃圾中转站覆盖；()Bi：表示可以覆盖第i座垃圾收集站的中转站的集合；Ck：表示筛选出的第k座垃圾中转站所覆盖的垃圾收集站的集合。4、问题二模型的求解利用matlab的绘图功能，我们将这些社区的经度为横坐标，纬度为纵坐标绘制点集，如图三所示。目标函数为从现有的m座垃圾收集站的位置中选出可以覆盖m座垃圾收集站的最小数目的中转站选点，对待这个问题，我们可以运用启发式算法进行集合覆盖模型优化，步骤如下：第一步，确定垃圾收集站的相对位置和距离；第二步，根据垃圾中转站的最优化服务半径，找出每一个可以作为中转站的收集点以提供垃圾收集服务的服务范围内的收集点集合A(k),k=1,2,3,…,m,即与该收集点距离小于或等于垃圾最优化收集半径的所有