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

1、夏明殷鹏远周骏 -敬上深圳市南山区垃圾分类处理与清运方案设计摘要垃圾如何清运与处理成为一个城市持久发展不可忽视的课题。本文就深圳市南山区垃圾清运与处理进行讨论，分析并提出若干模型，编程进行求解。模型一：逐步收缩法，在已知转运站数目与个数、处理中心个数的情况下，可运用此法确定部分转运站的归属情况。文中对38个转运站进行逐步收缩，确定了33个转运站的归属问题。模型二：重心法选址模型，问题一涉及到从38个转运站优化出三个处理中心的整数规划问题，用一般的整数规划方法，会遇到数据难以进行计算机模拟或无法找到最优解的困难，所以要进行简化，多次嵌套重心选址模型对这一问题得到很好的解决。模型三：为了重新设计方

2、案，我们首先参照垃圾收集密度以及当地人口密度，算出每个垃圾中转站的最优收集，求得可以覆盖m座垃圾收集站的最小数目的中转站的具体分布图，我们运用启发式算法进行集合覆盖模型优化来解决可以覆盖m座垃圾收集站的最小数目的中转站选。关键词：整数规划 重心选址法 集合覆盖 逐步收缩法 启发式算法1、问题的重述垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资源回收与再利用的城市绿色工程。在深圳，垃圾分为四类：橱余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾。它们的平均比例为，橱余垃圾：可回收垃圾：有害垃圾：其他不可回收垃圾比例约为4：2：1：3。在垃圾分类收集与处理中，不同类的垃圾

3、有不同的处理方式，简述如下：（1）橱余垃圾可以使用脱水干燥处理装置，处理后的干物质运送饲料加工厂做原料。不同处理规模的设备成本和运行成本（分大型和小型）如下：大型厨余垃圾处理设备，处理能力为200吨/日，投资额约为4500万元，运行成本为150元/吨；小型餐厨垃圾处理机，处理能力为200-300公斤/日，投资额约为28万元，运行成本为200元/吨。橱余垃圾处理后产物价格在1000-1500元/吨。（2）可回收垃圾将收集后分类再利用。（3）有害垃圾将运送到固废处理中心集中处理。（4）其他不可回收垃圾将运送到填埋场或焚烧场处理。所有垃圾将从小区运送到附近的转运站，再运送到少数几个垃圾处理中心。显然

4、，1）和2）两项中，经过处理，回收和利用，产生经济效益，而3）和4）只有消耗处理费用，不产生经济效益。本项研究课题旨在为深圳市的垃圾分类化进程作出贡献。为此请你们运用数学建模方法对深圳市南山区的分类化垃圾的实现做一些研究，具体的研究目标是：问题一：假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计，同时在目前的运输装备条件下给出清运路线的具体方案。以期达到最佳经济效益和环保效果。问题二：假设转运站允许重新设计，请为问题1）的目标重新设计。南山区的垃圾清运设备情况（主要是车辆数目和载重）。拖头（拖车）：只拖十吨的大型厢，只用于从转运站到垃圾中心，每次只拖一个大型“厢”

5、， 平均吨公里耗油25L30L柴油/百公里。收集车辆：只负责从小区的垃圾站到转运站运输。60辆2.5吨汽车，每车耗油20L35L 70#汽油/百公里。司机月薪平均3500元。2、问题分析对于问题一，我们考虑能产生经济效益的厨余垃圾的处理情况，要达到最佳经济效益，需降低成本、损耗，提高回收利润，而单位重量可回收垃圾的回收利润是一定的，所以只需考虑降低成本、损耗，即大小型设备投资总额+运行总成本+耗油量最少，而达到这一目标需要均衡设备类型、数目和运输路线的选择规划。对于大小型设备处理厂的数量，由于不同的设备厂的投资数额、处理能力、运转成本都有差异，利用这些差异粗略分析，可以得出各设备厂的最少数量。

6、根据大小型厨余设备的各种参数，及日垃圾处理量，可确定三个大型处理设备；在合理假设9的基础上，运用逐步收缩法，对部分转运站的归属进行确定；运用重心选址，确定D、E、H的重心坐标，集合内部转运量做叠加；对剩下未定归属阵营的五个点和D、E、H坐标点进行整数规划，最终确定五个点的归属问题；A、B、C内部路线用Dijkstra算法确定。问题二是在问题一上的拓展，使用matlab将汇总后的居民片区在图上描出来，形成一个点集，确定垃圾转运站的位置与数目，再利用问题一的解法，确定处理中心的位置与数目。3 模型假设1、假设同一种运载车辆单位距离运输成本一定（不考虑是否满载）。2、各社区人口数目相对固定，市民每天

7、产生的垃圾量是个定值；3、各社区每天垃圾的产生量和社区的人数成正比；4、垃圾转运站及垃圾处理厂（包括大小设备长）每天仅收一次垃圾（早上或晚上）；5、各垃圾转运站的垃圾将在当天清运完毕，不能积累；6、所有运输车辆不得超载；7、每个转运站与各个小区之间，各个转运站与处理中心（焚烧厂、填埋场、大小设备处理厂）之间均有公路直线相通；8、由于车辆有限，各转运站的垃圾只送往一个处理中心（焚烧厂、填埋场、大小设备处理厂）；9、三个大型处理中心大致呈南、中、北分布；11、所有运输车均从转运站出发前往小区或者处理中心，最后再回到转运站；12、可回收垃圾在垃圾中转站被直接回收，以后不再处理考虑；13、有害垃圾及其

8、他不可回收处理方式为焚烧、填埋都可；14、不考虑居民对垃圾中转站得选址的异议。4、符号说明U：38个转运站的集合。A、B、C、D、E、F、G：各种满足文中指定区域内所有转运站的集合。:第i个点需要转运的橱余垃圾量。：第i个点是否建设处理厂，取值为0或1，取1代表建设处理厂，取0代表不建设处理厂。：取值为0或1，取1代表从第i点运橱余垃圾到第j点，取0则不运。：从第i点到第j点的最短路程。: 转运站变动后的目标函数。: 转运站变动各转运站的纬度矩阵。: 转运站变动各转运站的经度矩阵。: 转运站变动各转运站距第一个大型厨余垃圾处理厂的距离。: 转运站变动各转运站距第二个大型厨余垃圾处理厂的距离。:

9、 转运站变动各转运站距第三个大型厨余垃圾处理厂的距离。: 转运站位置变动后各转运站垃圾容量。: 各小区的人口数量。: 人均垃圾产量。5、模型的建立和求解5.1 问题一5.1.1大小型厨余设备数目的确定由垃圾转运量统计表知：每天转运垃圾804吨；而厨余垃圾：可回收垃圾=2:1,所以每天厨余垃圾约为536吨；大小型设备的数据如下表： 投资额（万）运行成本（元/吨）处理能力（吨/日）大型设备4500150200小型设备282000.20.3显然若建三个大型设备处理中心，处理能力绰绰有余，满足需求；若建二个大型设备中心，经计算，需453个小型处理设备，453个小设备不但投资额远大于一个大设备的投资额，

10、而且运行成本还比大型设备高，所以此种方案不可取；一个大型设备更不可取。初步确定建立三个大型处理中心，每个中心一台设备。5.1.2处理中心位置的确定重心选址得到两次应用，第一次为了简化个数；第二次确定处理中心位置。由于南山区垃圾日产量分布大体均匀，可按地理位置分为三个区域，从南到北编号为A、B、C。1）首先对转运站站点个数进行简化根据垃圾转运量统计表及南山地图知：i）龙井公厕转运站（以此站所在纬度为界，包括此站）以北(记为集合D)垃圾转运总量约为223吨每日（稍小于252）；ii）南山市场公厕转运站（包括此站）以南（记为E）垃圾转运总量为215吨每日（稍小于252）；iii）松坪山（二）公厕转运

11、站（包括此站）以北（记为F）垃圾转运总量为258吨每日(略等于300)；iiii）涌下村转运站（包括此站）以南（记为G）垃圾转运总量为310吨每日（略大于300）。DFHGE 由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的重心列表如下2）整数规划，解决个未定转运站的归属问题。编号为2、9、12、16、18的转运站及D、E、

12、（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目标函数: 约束条件：i处理厂的处理量不超过200 j=1,28ii保证每个点的垃圾只运到一个处理厂 i=1,2,38iii保证只建三个大型处理厂 i=1,2,38通过Floyd算法求出任意点的最短路程，使用Visual C+编程求解，程序：（见附录）3）A、B、C各区路线的确定。在前两步求得的处理站与垃圾运向的基础上，运

13、用Dijkstra算法求出最短线作为清运路线。（程序及清运方案见附录）5.2问题二中转站的选址目标主要以垃圾中转站建设和运行成本最低。它是一个中转站选址是否合理的最重要的衡量标准，参照垃圾收集密度以及当地人口密度，算出每个垃圾中转站的最优收集半径为5米，而后选用集合覆盖模型求出垃圾中转站的待选点，即用尽可能少的垃圾收集中转站去覆盖所有的垃圾收集站。1、 目标函数的建立在考虑厨余垃圾量与路线问题及人口密集程度的前提下，中转站的选址点。我们将在垃圾收集站中选出个做为中转站，则其中的做为厨余垃圾处理厂的中转站的选取是由最优收集半径的大小而定的。根据个厨余垃圾处理厂的选点，建立如下最优化模型: (11

14、)2、 约束条件的确立目标函数为从现有座垃圾中转站的位置中优选出可以覆盖38座中转站的最小数目的中转站选点。（1）对于每一座垃圾中转站，其厨余垃圾均被清运，即： (12)（2）厨余垃圾处理厂能处理垃圾的能力要满足一定的要求： (13)（3）垃圾中转站和厨余垃圾处理厂的垃圾量均非负，即满足不等式： (14)（4）垃圾中转站是否建立在第座厨余垃圾处理厂附近的决策变量：， （5）第座垃圾中转站是否有垃圾收运到第座厨余处理厂的决策变量： ，3、 单目标规划模型的建立目标函数 (15)约束条件： (16) (17) (18) (19) (20)：表示筛选出的第k座垃圾中转站所覆盖的垃圾集合站的集合；：

15、表示第i座垃圾收集站是否被第k座垃圾中转站覆盖；：表示可以覆盖第i座垃圾收集站的中转站的集合；： 表示筛选出的第k座垃圾中转站所覆盖的垃圾收集站的集合。4、 问题二模型的求解利用matlab的绘图功能，我们将这些社区的经度为横坐标，纬度为纵坐标绘制点集，如图三所示。目标函数为从现有的m座垃圾收集站的位置中选出可以覆盖m座垃圾收集站的最小数目的中转站选点，对待这个问题，我们可以运用启发式算法进行集合覆盖模型优化，步骤如下：第一步，确定垃圾收集站的相对位置和距离；第二步，根据垃圾中转站的最优化服务半径，找出每一个可以作为中转站的收集点以提供垃圾收集服务的服务范围内的收集点集合A(k),k=1,2,

16、3,m,即与该收集点距离小于或等于垃圾最优化收集半径的所有收集点的集合；第三步,找到可以给每一个收集点提供服务的可作为中转站的收集点的集合B(i) ,i=1,2,m,一般来说，A(k)和B(i)这两个集合是一致的，但是考虑到其他的一些限制条件，就可能出现差异；第四步，在B(i)中，将其中的子集省去，以简化问题，例如B(1)=(1,2,3,4), B(2)=(1,2,3), B(3)=(1,2,3,4,5),则B(1)和B(2)是B(3)的一个子集，可以省去以简化问题；第五步，确定合适的组合解，在问题被简化后，在有限的候选点上选择一个组合解是可行的。为满足模型目标即以最小数量的设施点覆盖所有的需

17、求点，应尽可能少的确定待选点，从组合解中剔除可以被合并的待选点。按照上述模型计算，结合坐标数据，找出最佳建设位置，具体位置见图二。6、模型评价该模型从整体上解决了深圳市南山区的垃圾处理问题，包括：厨余垃圾处理厂的个数和选址问题，在允许重新设计垃圾转运站的前提下，该模型确定了垃圾转运站重新设计的个数、各个转运站的地址，重新决策的大小型厨余垃圾处理厂个数，各个处理厂的地址，以及重新设计之后的运输方案。但问题一求解中，假设7过于理想，应用于实际时会有偏差；在确定处理中心个数时，方法虽简单合理，但难于推广；处理中心选址采用了逐步收缩法，是在假设9的前提下，求解更一般的问题，假设就不在成立，推广性差；所

18、以在问题二的求解过程中应用了集合覆盖模型，并且还运用了模拟启发式算法来对城市垃圾的分类处理以及清运方案做了设计，这些模型和算法同时可以推广到求解城市公交车网络的行驶的最小路径问题，还有物流选址问题的规划等。这些模型和算法在现实中得到极大的广泛应用和推广。应用这个方案，可达到节省运输垃圾的路程最短还有运费最小的目的，因此此方案存在一定的推广性。7、参考文献1JA邦迪 U.S.R.默蒂，图论及其应用，华盛顿邮报出版社，1982。2姜启源，数学模型第三版M，高等教育出版社，2006。3韩中庚，数学建模方法及其应用M，北京：高等教育出版社，2005年。4 张蓉、彭宏，快速分解模拟退火算法在全局查询优化

19、中的应用、计算机工程与应用，2001年23期，2011-7-27。附录Floyd算法程序：1、 #include2、 using namespace std;3、 float min(float a,float b)4、 5、 if(a=b) return a;6、 else return b;7、 8、 void main()9、 10、 float *d8;11、 for(int i=1;i=8;i+)12、 13、 di= new floati;14、 for(int j=1;jdij;16、 17、 for(int k=1;k=8;k+)18、 19、 for(int i=1;i=8;

20、i+)20、 21、 for(int j=1;j=i) dij=min(dki+dkj,dij);24、 else if(k=j) dij=min(dik+dkj,dij);25、 else dij=min(dik+djk,dij);26、 27、 28、 29、 for(i=1;i=8;i+)30、 31、 for(int j=1;j=i;j+)32、 coutdij ;33、 coutendl;34、 35、 lingo求解程序与结果：程序：model:SETS:point/1.8 / : pro , W ; ! 定义待定点，用pro来区别。W为是否建处理厂。;yunshu(point ,

21、 point): U , D; ! 定义运输集，有U与D两个特征，其中U为是否运i点到k点，D为 i与k点间的距离;endsetsdata : pro= 22 100 23.3 26.7 16.7 84 110 10 60 16.7 40 ; D= 0 2.5 6.7 2.6 3.7 1.9 5.6 3.9 2.5 0 2.6 3.6 1.7 5.4 2.8 4.6 6.7 2.6 0 5.5 4.7 2.3 5.6 2.52.6 3.6 5.5 0 2.1 6.4 3.2 2.83.7 1.7 4.7 2.1 0 1.4 6.4 3.21.9 5.4 2.3 6.4 1.4 0 5.2 3.

22、45.6 2.8 5.6 3.2 6.4 5.2 0 4.13.9 4.6 2 5 2.8 3.2 3.4 4.1 enddata !数据输入;for ( point: bin (W);for ( yunshu: bin (U); !定义U为0,1变量;! 目标函数;min = sum ( yunshu (I, J) : D * U * pro(I )*W(J);!约束条件;for ( point( J ): sum (yunshu (I,J) : U * pro(I) = 200 * W (J) );for ( point(I) : sum (yunshu(I , J) : U ( I ,

23、J) = 1) ;sum ( point (I): W) = 3;end 有效结果：Local optimal solution found. Objective value: 922.100 Extended solver steps: 2452 Total solver iterations: Variable Value Reduced Cost PRO( 1) 22.00000 0. PRO( 2) 100.0000 0. PRO( 3) 23.30000 0. PRO( 4) 26.70000 0. PRO( 5) 16.70000 0. PRO( 6) 84.00000 0. PR

24、O( 7) 110.0000 0. PRO( 8) 10.00000 0. W( 1) 0. 0. W( 2) 1. 323.5997 W( 3) 0. 0. W( 4) 0. 0. W( 5) 0. 0. W( 6) 1. 428.6496 W( 7) 1. 669.8493 W( 8) 0. 0. U( 1, 1) 0. 0. U( 1, 2) 1. 109.9999 U( 1, 3) 0. 0.E-04 U( 1, 4) 0. 0.E-03 U( 1, 5) 0. 0.E-04 U( 1, 6) 0. 340.9997 U( 1, 7) 0. 274.9997 U( 1, 8) 0. 0

25、.E-04 U( 2, 1) 0. 0.E-04 U( 2, 2) 1. 0. U( 2, 3) 0. 0.E-04 U( 2, 4) 0. 0.E-03 U( 2, 5) 0. 0.E-04 U( 2, 6) 0. 1349.999 U( 2, 7) 0. 749.9992 U( 2, 8) 0. 0.E-04 U( 3, 1) 0. 0.E-04 U( 3, 2) 0. 139.7999 U( 3, 3) 0. 0. U( 3, 4) 0. 0.E-03 U( 3, 5) 0. 0.E-04 U( 3, 6) 0. 244.6498 U( 3, 7) 1. 104.8499 U( 3, 8) 0. 0.E-04 U( 4, 1) 0. 0.E-04 U( 4, 2) 1. 213.5998 U( 4, 3) 0. 0.E-04 U( 4, 4) 0. 0. U( 4, 5) 0. 0.E-05 U( 4, 6) 0. 186.8998 U(