垃圾处理与清运方案设计

1、夏令营数学建模竞赛院系：数学科学学院 班级：09统计班 队员一：刘伟霞 队员二：闫 赛 队员三：李 玲 垃圾分类处理与清运方案设计摘要：对于问题一厨余垃圾处理中心选址问题，为尽量简化模型，首先我们考虑只建大型设备，采用集合覆盖模型，用lingo编程解得所有可以建设大型厨余垃圾处理中心的地址集合（#3 #8 #13 #17 #24 #28 #30 #32 #36 # 38），共10个选址。然后，建大小型设备转换模型，最终得出建设选址：建大型厨余垃圾处理设备的中转站编号分别为3、17、28、30；小型厨余垃圾处理设备的中转站编号分别为8、13、24、32、36、38。对于问题二中转站改建问题，模型

2、一为将原有中转站作为待选点,运用整数规划法建立整个垃圾运系统总费用现值最小模型 ,实现总体优化 ,选出中转站位置的最优组合;模型二首先在excel中利用数据透视表统计各小区的垃圾量，再利用聚类分析思想，简化小区数量，利用重心法确定中转站的最优位置，然后再次采用问题一中分析方法确定厨余垃圾处理中心的位置及清运方案。关键字：集合覆盖 0-1整数规划 重心法 中转站 选址 （一） 问题的重述：垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资源回收与再利用的城市绿色工程，以还居民一个洁净舒适的生活环境，但我们面临中转站的选址和多条线路的选择问题。需要解决的具体问题如下：（1）

3、假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计，同时在目前的运输装备条件下给出清运路线的具体方案.以期达到最佳经济效益和环保效果。（2）假设转运站允许重新设计，请为问题1）的目标重新设计。（二） 问题的分析对于问题一的厨余设备的分布设计问题，为了达到最佳经济效益和环保效果，首先我们主要从厨余垃圾处理设备的投资和运行费用角度进行考虑，来规划厨余垃圾处理中心放置地点问题。另外，为了尽量简化模型，在建模过程中，我们将拖车台数和各条路径所花费的时间作为次要考虑条件，因为投入的车辆数，在各条路径确定后，最终便可确定投入拖车数量和花费与收益。对于问题二中转站的重建问题，垃圾

4、中转站的建设是为了使垃圾收集作业区域和最终处置区域之间的运输更经济、更有效、更合理。中转站一旦建成，由于其前期巨大的投资，就不可能随意的更改地址。所以我们用聚类分析的思想和重心法模型，确定出中转站的合适选址，然后再次运用问题一的方法确定最优的清运路线。（三） 模型的假设（1）南山区人口分为不同部分，假设每部分人口固定，每天产生垃圾量固定；（2）假设各小区清运站的垃圾都必须在当天清理完毕，并且清运站的垃圾不论早晚只被收集一次；（3）不考虑运输车在行驶过程中出现的塞车、抛锚等耽误时间的情况；（4）不允许运输车有超载现象；（5）每个小区清运站均位于街道旁，保证运输车和铲车行驶顺畅；（6）每个厨余垃圾

5、处理中心周围方圆6公里之内转运站的垃圾都运往此中心（个别除外）；（7）所有运输车均从垃圾转运站发车最后回到垃圾转运站；（8）拖车将垃圾一起送往大型设备处或小型设备处再前往填埋场和焚烧场；（四） 模型的建立与求解一、厨余垃圾处理中心选址模型为了减小对环境的影响，我们考虑将厨余垃圾处理中心设置在地理位置适宜的中转站，厨余垃圾处理中心不但要选点布局，而且还要确定其接纳垃圾量的规模，对这两方面的要求如下:(1) 设置频率每个转运站周围方圆6公里之内，应至少设置一台厨余垃圾处理中心。(2) 设置规模大小题中给出大小型厨余设备建设费用有极大的差别，为简化模型，我们考虑首先在合适的地址全部建成大型厨余设备，

6、然后建立大小型厨余垃圾设备转换的模型，使得建设费用降到最低。(3) 垃圾转运量可按下列公式计算：；约束条件：Km式中: 第个中转站到第个中转站的距离； 第个中转站向第个中转站运输的垃圾量；Q 垃圾转运量(t/d);1、集合覆盖模型根据城市环境卫生设施设置标准(CJJ27-2005)和城市转运站设计规范 (CJJ47-91)，参照垃圾收集密度以及当地人口密度，算出每个垃圾处理中心最优收集半径为6km。而后选用集合覆盖模型求出厨余垃圾处理中心的待选点，即用尽可能少的厨余垃圾处理中心去覆盖所有的垃圾中转站。具体过程如下：1.1符号说明M=1，2，m表示有m座垃圾中转站组成的集合;C（k）表示第k座垃

7、圾中转站的中转能力;X表示第座垃圾中转站的垃圾量;A(k)表示筛选出的第k座垃圾厨余垃圾处理中心所覆盖的垃圾中转站的集合;B表示可以覆盖第座垃圾转运站的厨余垃圾处理中心的集合;表示是否启用第座厨余垃圾处理中心;表示第座垃圾转运站是否被第座厨余垃圾处理中心覆盖。W 表示建设厨余垃圾设备的最小数目 1.2模型建立记有m座垃圾中转站，集合覆盖模型为： 约束方程:式中： 目标函数为从现有m座垃圾转运站的位置中优选出可以覆盖m座垃圾转运站的最小数目的厨余垃圾处理中心选点；约束式(1)表示每一座垃圾收集站的垃圾均被清运;约束式(2)是满足厨余垃圾处理中心处理能力的要求;约束式(3)表示转运站和厨余垃圾处理

8、中心处理的垃圾量非负；约束式(4)是垃圾中转站是否位于第k座垃圾厨余垃圾处理中心附近的决策变量;约束式(5)是第i座垃圾中转站是否有垃圾收运到第k座厨余垃圾处理中心的决策变量。1.3模型的求解对厨余垃圾处理中心待选点进行确定，运用启发式算法进行集合覆盖模型优化，利用0-1 整数规划进行求解，步骤如下:第一步，确定垃圾中转站的相对位置和距离;第二步，根据厨余垃圾处理中心服务半径，找出每一个厨余垃圾处理设备中心服务范围内的中转站集合A(k)，k=l，2，m，即距离该厨余垃圾处理中心距离小于或等于垃圾最优收集半径的所有中转站的集合。第三步，找到每一个可以给中转站提供垃圾收集服务的可作为厨余垃圾处理中

9、心的收集点的集合B(i)，i=l，2，m，一般来说，A(k)和B(i)这两个集合是一致的，但是考虑到其他的一些限制条件，就可能出现差异。根据所给图形描绘的垃圾转运站点，我们利用PDF-viwer软件近似测量了各中转站间的相互距离，整理出若将厨余垃圾处理中心建于该中转站时，中转站六千米范围内所覆盖的区域如下表：垃圾转运站名称序号厨余垃圾六千米覆盖的区域九街站129121415171822301玉泉站289151718202612动物园站34192637333平山村站419263734牛城村站532511科技园站616182127306同乐村站78377松坪山（二）站820278大新小学站9215

10、3012914南山村站10101415212230阳光站113132115月亮湾大道站1217112光前站1320293713北头站149223011410涌下村石洲南站162728616前海公园站17121217深圳大学龙村站1926373419松坪山站2027281320南光站21223062110南园站2230114212210望海路站232423花果路站24382324福光站25342538新围村站26372341926大冲站2728616182027沙河市场站2816272835龙井292913南山市场301691415182122

11、3010麻勘站31321131白芒站325113132大石磡站33333长源村站34253438华侨城站353528疏港小区站3636西丽路站3734713192637塘朗站38253834表（一）第四步，在B(i)中，将其中的子集省去，以简化问题。例如:若B(l)=(l，2，3，4)；B(2)=(l，2，3)，B(3)=(1，2，3，4，5)，则B和B(2)是B(3)的一个子集，可以省去以简化问题。第五步，确定合适的组合解。在问题被简化后，在有限的侯选点上选择一个组合解是可行的，为满足模型目标即以最小数量的设施点覆盖所有的需求点，应尽可能少地确定待选点，从组合解中剔除可以被合并的待选点。第六

12、步，通过用lingo软件编程见附录二，得到厨余垃圾处理中心的最优选址组合为#3 #8 #13 #17 #24 #28 #30 #32 #36 # 38，共10个选址。第七步，综合各中转站到与之相邻的厨余垃圾处理中心的距离问题及表（一），在深圳南山地图上画出最优组合，从而各厨余垃圾处理中心所包括的中转站集合分别为3（3 4 19 26 33）、8（7 8 20）、13（13 29 37）、17（1 2 12 17）、24（23 24）、28（16 27 28 35）、30（6 9 10 14 15 18 21 22 30）、32（5 11 31 32）、36（36）、38（25 34 38）1.

13、4、大小型设备转换模型考虑到大小型设备的建设费用的差别，我们根据垃圾处理费用、设备的建设费用，及大小型设备在使用年限的运行成本，建立目标函数再次对模型进行优化，从而确定大小型设备的具体位置。1.41 符号说明W 第i号厨余垃圾中心建设厨余设备的总费用Q 大型厨余垃圾处理设备的建设费用Q 小型厨余垃圾处理设备的建设费用P 大型厨余垃圾处理设备的处理能力（t/d）p 小型厨余垃圾处理设备的处理能力（t/d） 表示大型厨余垃圾使用年限（年） 表示大型厨余垃圾使用年限（年） 厨余垃圾处理中心的厨余垃圾量（吨） n 建设小型设备的数目1.42 模型建立1.4.3模型求解参考有关资料，取=8年，=4年得出

14、结果如下：厨余垃圾处理中心中转站集合处理中心重量厨余垃圾量吨/天吨/天3,4,19,26,33110447,8,20401613,29,3750201,2,12,1710140.423,24602416,27,28,35165666,9,10,14,15,18,21,22,30180725,11,31,323313.236,401625,34,382510总计804321.6表（二）由表（二）中各厨余垃圾处理中心处理的总垃圾量及1.42中的模型得表（三）：厨余垃圾处理中心小型设备数量小型设备成本小型设备造价大型设备造价差额设备选择编号个万元万元万元万47243.811

15、64.6大5415123088.87243.8-4155小6718763832.47243.8-3411.4小135378077227244.8477.2大80224045767243.8-2667.8小2206160125847245.85338.2大2406720137287243.86484.2大4412322516.87246.8-4730小5415123088.87243.8-4155小349521944.87247.8-5303小总计10753010017880.72448-10958表（三）由表（三）易得出建大型厨余垃圾处理设备的中转站编号分别为3（3 4 19 26 33）、1

16、7（1 2 12 17）、28（16 27 28 35）、30（6 9 10 14 15 18 21 22 30）；建小型厨余垃圾处理设备的中转站编号分别为8（7 8 20）、13（13 29 37）、24（23 24）、32（5 11 31 32）、36（36）、38（25 34 38）。综合考虑厨余设备与所负责各中转站的距离与各中转站产厨余垃圾量，在模型假设的前提下，我们得出清运路线的具体方案第个厨余垃圾处理中心清运路线：26193343第个厨余垃圾处理中心清运路线： 第个厨余垃圾处理中心清运路线： 8720 第个厨余垃圾处理中心清运路线：293713第个厨余垃圾处理中心清运路线：2121

17、第个厨余垃圾处理中心清运路线：2023第个厨余垃圾处理中心清运路线：16283527第个厨余垃圾处理中心清运路线：1896153022142110第个厨余垃圾处理中心清运路线：5323115第个厨余垃圾处理中心清运路线：36第个厨余垃圾处理中心清运路线：342538二、中转站重新选址模型垃圾收运系统是一个逆向物流系统，从垃圾的产生地点到垃圾的收集站，然后到中转站，最后才到垃圾处理场所，垃圾中转站的选址是垃圾收运系统的关键，对垃圾中转站的规模、选址、布点等进行合理的规划可以大大减少垃圾收运成本。城市生活垃圾中转站选址问题是考虑建多少中转站，在哪里建立，才能使整个系统的固定投资和运行成本最低。1运

18、输费用最小模型将原有的垃圾中转站作为待选点,运用整数规划法建立整个垃圾运系统总费用现值最小模型 ,实现总体优化 ,并从垃圾中转站待选点中优选出中转站位置的最优组合 ,同时确定最优组合中每座中转站接纳的垃圾量.1. 1模型提出在垃圾收集站和处理场的位置和数量已确定的情况下 ,整个垃圾收运过程中所发生的费用主要取决于规划期内垃圾从收集站到中转站的运输费用、垃圾从中转站到处理场的运输费用、中转站的固定投资费用和中转站的运行费用 ,上述 4种费用彼此相互关联互相制约 ,均与中转站位置、规模密切相关.1. 2符号说明 第 i座收集站运往第 k座中转站单位运输量单位距离的费用,(元 t- 1 km- 1)

19、 ; 第 i座收集站运往第 k 座中转站的日运输垃圾量( td- 1) ; 第 i座收集站运往第 k座中转站运输距离 (km) ; D kj 第 k座中站运往第 j座处理场单位运输量单位距离的费用 (元t- 1 km- 1) ; Y kj 第 k座中转站运往第 j座处理场日运输垃圾量 ( td- 1) ; S kj 第 k座中转站运往第 j座处理场运输距离 (km). F 规划期内待建中转站的固定投资 (元) ; E 中转站的运行成本 (元 t- 1) ; Q 中转站建设的最小控制规模( td- 1) ; Qmax 为中转站建设的最大控制规模 ( td- 1).1. 3垃圾收运系统费用总值最小

20、模型建立目标函数即为规划使用年限内的费用现值最小模型 ,涵盖了垃圾收运系统中收集、中转和运输 3个阶段中所发生的 4部分费用;约束方程 (7)表示中转站固定投资与实际接纳垃圾量间的函数关系;约束方程 ( 8)表示进出中转站垃圾量的物料平衡关系;约束方程 (9)表示 1个收集站的垃圾只运往 1个中转站 ,二者是“多对一 ”的关系;约束方程 (10)表示无垃圾站的垃圾运往中转站时 ,中转站不启用 ,但只要有垃圾站的垃圾运往中转站 ,中转站必须启用;约束方程 ( 11)对中转站规模的进行控制; 约束方程 ( 12 )表示垃圾量非负;约束方程 ( 13 )是中转站是否被选用的决策变量;约束方程 (14

21、)是某一垃圾站的垃圾是否运往某一中转站的决策变量;约束方程 ( 15)是某一中转站的垃圾是否运往某一垃圾处理场的决策变量.1. 4模型的计算与求解 中转站选址费用现值最小模型是一个整数规划模型。整数规划问题的求解算法很多，如模拟退火算法、遗传算法、Tabu搜索算法等。本模型采用取走算算法进行求解。具体步骤如下: 第1步，初始化，令循环参数=p，计算出各中转站合理收集范围，使费用现值最小记为PV; 第2步，在座中转站待选点位置中随机地选取一个，将其状态设“关闭”，而其他中转站待选位置都设为“打开”，搜索出处于“打开”状态的费用现值最小的中转站组合，记为，此组合对应的费用现值记为P; 第3步，在组

22、合下，座中转站中呈“关闭”状态的1座中转站删除，并在增加量最小的目标下，将其垃圾量分配给组合中的中转站; 第4步，令=，在入座中转站待选点位置中随机地选取一个，将其状态设为“关闭”，而其他中转站待选位置都设为“打开”，搜索出处于“打开”状态的费用现值最小的中转站组合，记为，此组合对应的费用现值记为; 第5步，比较与，若，则转向第6步;若，重复2-5步，直至，转向第6步; 第6步，输出以及座垃圾中转站时的，终止程序。计算结果输出的是每个垃圾收集点运往中转站的垃圾量，若计算结果显示某一垃圾中转站的转量为O，则表明在垃圾收运费用现值最小的目标下，不应设置为中转站，应从待选点中剔除;对于输出的计算结果

23、不为O的垃圾中转站，予以保留，从而实现了中转站的选址。由模型计算的出中转站的分布为动物园站（20）、平山村（25）、大新小学站（30）、阳光站（15）、光前站（20）、深圳大学（15）松坪山站（25）南园站（15）、海湾路选址建一个中转站（10）、沙河市场站（80）、龙井站（15）、大石磡（30）、长源村站（5）、华侨城站（80）、西丽路站（15）塘朗站（20）。2重心法模型我们将小区居民数据表进行统计分析，把同一小区的居民数量进行汇总得到79个小区。根据各小区的距离，在一定小的范围内可以根据聚类算法的思想，即同一类对象的相似度较高，而不同类的对象相似度较小的原理将小区进一步分为，将一些小区划

24、分成几个区域，根据聚类分析的结果将南山市划分为不同的区域得到汇总表（四）如下：第一区域：中心区域，特点是人口密度高，并且比较均匀，垃圾产生量较大，收集密度较大，因垃圾收集后运至处理厂的运距远，故设置中转站是必须的。第二区域：次中心区域，特点是人口密度较高且比较离散，垃圾产生量比较多，收集密度次于中心区。第三区域：近郊区，特点是地域广阔，人口分布比较分散，在区域中心地区垃圾分布相对集中。第四区域：远郊区，特点是地广人稀，垃圾产生量较低，收集密度较小，中心地区垃圾分布相对集中。编号小区名字小区人数小区的垃圾量编号小区名字小区人数小区的垃圾量1深航片区20251.2327 41 龙珠X号网格1075

25、26.5454 20X网格629.5038 42 南景苑片区13510.8224 3碧云片区17911.0903 43 南贸综合楼片区10280.6258 4别墅570.0347 44 欧陆经典片区14530.8845 5常兴广场片12890.7847 45 沛鸿宿舍6250.3805 6长兴新村X23991.4604 46 平山X片区4243125.8302 7翠溪路临9号翠溪路旁苗圃80.0049 47 青梧路1号16210.9868 8翠竹园片区17651.0745 48 如意家园片区7700.4687 9大学城X48342.9427 49 桑达苑6950.4231 10动物园小区170

26、01.0349 50 深蓝公寓片区9640.5868 11度假村套房小区8670.5278 51 深旅物业工业园24141.4695 12芳华苑片区16641.0130 52 深南花园4330.2636 13峰景XX区2018312.2866 53 十九冶片区11370.6922 14福光村X片2770.1686 54 苏豪大厦片区4600.2800 15高发公寓片33732.0533 55 塘朗X片区1879211.4398 16工商银行片11530.7019 56 桃源村单身公寓片区10060.6124 17公交公司4710.2867 57 桃源村X片区2632616.0262 18光前村

27、X片120237.3191 58 桃苑小区片区34732.1142 19国兴苑片区4960.3019 59 陶然居片区30131.8342 20海湾X区91995.6000 60 田寮X片区17591.0708 21后海片区13450.8188 61 田厦统建楼片区13170.8017 22花果山X片21291.2960 62 万象X片区36572.2262 23花园城三期片区10830.6593 63 维用综合楼4900.2983 24汇景豪苑14640.8912 64 文华路5号6630.4036 25金海岸A片9650.5875 65 西海湾片区15570.9478 26金粤片区1087

28、0.6617 66 西丽湖小区16000.9740 27康乐片区19781.2041 67 西丽水库980.0597 28科发路11号5510.3354 68 小白楼670.0408 29科丰路X号5010.3050 69 小仓库110.0067 30科技园X区58743.5758 70 杨屋村铁皮房片区90.0055 31科伟路15870.9661 71 怡园片区18331.1159 32科苑西3930.2392 72 邮电局片区700.0426 33科苑学里12690.7725 73 云海片区12550.7640 34丽珠花园25431.5481 74 长源X区56193.4206 35荔

29、园片区19791.2047 75 招北片区15400.9375 36荔苑小区片11810.7189 76 振兴片区17531.0672 37荔枝苑片区24111.4677 77 中旅广场X层片区38952.3711 38龙辉花园x片区49022.9841 78 中新街片区13180.8023 39龙井村X片136188.2901 79 珠光村XXX2556515.5629 40龙尾村片区13890.8456 总计804表（四）21模型的建立 我们在这里只简单的分析两个中转站的选取，然后依据此理论再推广到其他中转站的选取。2.1.1划分区域：首先，在坐标纸上描绘出六个居民点，并用直线把居民点连接

30、起来，以距离为边做出一个完全图，如图所示：图（一）居民区110221.41403321.4104432.231055553.6053.160665.3853.6052.8282.2360表（五）然后，根据它们彼此的距离（如表五所示），先删除距离最大的边，然后再删除余下边中距离最大的，依次进行下去，直到图被分为两个彼此分离的图像，如下图所示：图（二）分为两个区域，根据居民垃圾日产出量和运输量可知，A站与B站的转运量只能m、n。然后分别对A、B站进行求解。21.2.公式（重心法选址）的推导：假设有n个居民点，居民点的坐标为（，），转运站的位置为（X,Y）,则运输成本为：其中，A为单位距离的运输成本

31、，为两点间的距离，为运量。按重心法，将各居民区视为有重量的质点，为各质点的等效重量，重心是到各质点距离最短距离的点，这样，寻求转运站的地址问题，就转化为求重心坐标的问题，所以接下来就是解决求解重心的问题。假设各个质点的等效质量为G，根据重心的特征，可知，等效重量在重心对远点的力矩等于各质点在面上的力矩之和，即：由于X轴与Y轴互相垂直，为不相关变量，所以可以把力矩延着X轴、Y轴分解，即重心对X轴、Y轴的力矩，等于各质点对X轴、Y轴的力矩之和。那么可以得到： 又因为G为等效质量，所以。总上可得： （，）就为所要求解的重心，也就是转运站的最优位置。3 清运路线的设计 由以上的模型基本可以确定优化后中

32、转站的位置，依然按照问题一中集合覆盖模型求解出厨余垃圾厨余垃圾处理中心的适宜选址，然后依然按问题一的方法可以得出清运的最佳方案。现用多车辆清运路线规划模型来找最优调运路线问题。3.1 清运路线的设计模型 多车辆清运路线规划模型就是以中转站确定收集垃圾最佳的行走路径，调派车辆数，完成对离散分布的小区垃圾的一次收集， 满足车载量及垃圾量等约束条件下，使得总的运输成本最小的模型。注：车辆路径规划问题1、模型建立目标函数：约束条件： 其中，V =1, 2,.,n为图所有顶点的集合，为图所有边的集合， 为i到j 的距离，为0-1 整型规划变量， 且， 为i 点垃圾量，q 为车的载重量。2、路径规划算法 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis 准则，粒子在温度T 时趋于平衡的概率为e-E/(kT)，其中E 为温度T 时的内