垃圾分类问题的处理与方案设计全文

1河南理工大学2011年数学建模竞赛论文答卷编号（竞赛组委会填写）：题目编号：（A）论文题目：垃圾分类处理与清运方案参赛队员信息(必填)：姓名年级专业班级联系电话队员1李迎超09信息09-2班15839105400队员2赵亮09信息09-2班15978703650队员3齐卓09结构工程159937380692答卷编号（竞赛组委会填写）：评阅情况（学校评阅专家填写）：评阅1.评阅2.评阅3.3垃圾分类处理与清运方案设计摘要随着大运会的开展，深圳的外观建设和绿化都是展现深圳形象的重要措施，其中垃圾处理尤为重要，因此设计一个良好的垃圾处理与清运方案是很重要的。垃圾转运站设置的一个重要意义在于节省运费。一般用于收集小区垃圾到转运站的车为清运车，在本题中，题目给出了深圳市南山区的垃圾转运站的分布和转运能力的大小，要求设计出大小橱余设备的分布并且给出清运方案的具体设计。在设计大小橱余设备及其分布时，运用了最短路和最少费用作为模型通过程序的编译求出三大部分地区中的线路长短，以十年为期限。第一部分区域如果用大型设备需用1台，选择在动物园垃圾转运站，此时获得纯利润为6678824625元，若用小型设备需用815台，此时获得纯利润52200820元。对于第二部分如果用大型设备需用3台，选择在南山市场垃圾中转站，此时获得纯利润为101023.2元，若用小型设备需用2475台，此时获得纯利润为5230774800元。对于第三部分如果用大型设备需用1台，选择在望海路垃圾转运站，此时获得纯利润为24.3846214243元，若用小型设备需用380台，此时获得纯利润为4380253000元。在设计清运方案时，我们把主干道作为考虑对象并对它进行简化，用图论的相关知识找到每一个区域的可行方案，最终得到了一种可行的具体的清运方案。第二问题依据集合覆盖模型,确定垃圾中转站的待选点;进而运用整数规划构建垃圾收运系统费用最小模型,。由于垃圾转运站被重新设计，因此各个量都是不确定的，在此建立了两个通用的集合覆盖模型与垃圾收运系统费用最小模型。只要带入确定的数据，就能得到垃圾转运站的规模、位置以及最佳经济效益。关键词：网格法；最短路；最短距离矩阵；C语言4一、问题重述垃圾主要分为橱余垃圾，可回收垃圾，有害垃圾和其他不可回收垃圾；为了更好地处理垃圾，引入垃圾收集、分类且尽量对橱余垃圾及可回收垃圾再处理的方法，这样既美化了环境又节约了回收成本，达到取得一定经济效益的目的。由于处理橱余垃圾及可回收垃圾会产生经济效益而后两类垃圾只会消耗费用，并且行驶不同的路线去收集、运送垃圾会使车辆的耗油量不同，同时购买的大小型橱余垃圾处理设备数量不同及安排位置的不同都会使经济效益有所不同，这都涉及了最优化方案问题。第一问是在转运站规模与位置和深圳南山区的实际情况相同时，设计出大小型设备的分布，并且在目前运输装备条件下给出清运路线的具体方案。第二问是转运站被重新设计，此时转运站的规模与位置都是不确定的，再重新求上述问题。二、问题分析本项研究课题能为深圳市的垃圾分类化进程作出贡献，因此具有十分重要的现实意义。第一问中，在垃圾转运站的规模与位置确定条件下，在南山地图上通过用竖直线段与水平线段构成的网格，用网格来具体确定南山地区垃圾转运站的具体位置和各个垃圾转运站之间的路线。对于清运路线的选择，可以把南山区分成若干小块是每一小块只含有一个转运站，从而可以将南山地区的各个垃圾转运站之间的复杂路线进行简化，进一步运用最近线段等效原则，将各段曲线用竖直的直线线段与水平的直线线段来进行等效，再通过对路线等效模型的分析，可以用等效的竖直线段与水平线段的长短和网格的结合来确定各个垃圾转运站之间的距离，从而来确定具体两个垃圾转运站的的最短路线，通过对模型的分析，可以求出南山区各个垃圾转运站之间的最短路线和各个垃圾转运站之间的最短路线的长度，在设备的规划当中，根据南山区的所有垃圾转运站的具体分布，认为南山区北部的垃圾通过拖车运送到南山区南部地区进行处理不符合经济效益，因此，将南山地区的垃圾转运站分为三部分，再通过用最短路线来对设备进行规划与分配。在第二问中由于转运站的规模与位置都是不确定的，增加了模型建立的难度。针对垃圾收运系统的特点，应用了集合覆盖模型，确定垃圾中转站的待选点，然后再引入整数规划构建垃圾收运系统费用的最小模型，从待选点选出垃圾转运站的最优组合，这样对转运站选址分阶段进行了二次优化，避免了直接运用整数规划的复杂运算，为垃圾转运站选址提供一种简单易行的方法。三、模型假设（1）负责从小区到转运站运输的车辆在每天早饭后收集垃圾;（2）清运车辆的耗油量只与所走过的路程有关；（3）清运车尽量走主干道，其次是次干道，最后才走街坊路；（4）拖车走高速路，快速路，主干道和次干道，不走街坊路；（5）垃圾处理中心在转运站里并且所有大小型橱余垃圾处理设备使用年限为十年，使用时不发生任何故障四、符号说明5),(jih拖车从序号为i的转运站到序号为j的转运站转运送垃圾所花费的费用p拖拖车运行时平均吨公里所花费的费用id序号为i的垃圾转运站在所服务区域内每次清运时走的总路线长（在地图上的长度）iz序号为i的转运站M南山地区所有转运站的垃圾总量im序号为i转运站的垃圾总量jid,序号为i的转运站到序号为j的转运站的路线的距离iq序号为i的转运站转运的垃圾总量iQ由序号为i的转运站服务区域产生的，但不能被分类处理的垃圾总量BAd,A,B两点的路线长度1t处理中心设在转运站中，大型设备的个数2t处理中心设在转运站中，小型设备的个数五、模型的建立5.1两点之间路线长度的计算方法由于本模型中的距离是用网格法求解的，因此，对网格法进行如下说明如图一所示，采用坐标点表示网格，若某一点不在网格的边线上（例如：A点,B点）该点所在的网格的左下角点的坐标为),(ji，那么记这个网格的坐标为),(ji。那么A点所在的网格的坐标为)2,4(，B点所在网格坐标为)4,7(；如果点在网格的边线上（例如C点），那么认为包含这条边线的左侧的网格的坐标为它所在的网格的坐标，那么C点所在网格坐标为)3,7(。。6图5.1网格法计算距离举例示意图为了计算方便，参照实际情况，我们可以对距离的求法作出如下简化对于任意两点A，B：（1）如果A,B不在同一网格内并且A,B都不在网格的边线上，对于从A),(AAjiB),(BBji的不同路线，可以把所有路线的长度都看作从A点到),(ABji的直线长度加上从点),(ABji到点B),(BBji的直线长度，即为||BAii+||BAjj。例如图一中A,B两点，认为它们之间的路线长为：3+2=5。（2）如果A,B不在同一网格内或者其中一点在同一网格边线上，对于不在边线上的点认为它在网格的中心处，路线长度的计算与1相同。例如对于图一中的D、E距离为0.55.2最短路线的选取方法如果在两个垃圾堆放点之间有多条路线可以选取，我们结合实际情况，以在保护环境的前提下尽量使车所走路最小为原则作出如下分析：（假设下图曲线就是选取的路线，横竖直线构成网格）首先在地图上绘出水平间距相等和竖直间距相等的直线，构成网格，现假设从A点到B点有如上线路即(网格中的曲线)，将网格中的曲线运用离曲线最近的原则，用标有箭头的连续线段来等效该曲线，要求该线段是网格中的水平线段或图5.2.1图5.2.2ABAB402426681012.A.B.C.D.EFGOP7图5.2.3图5.2.4是网格中的竖直线段，而且绘制出的等效连续直线段的所有端点均匀分布于该曲线的两侧，则上述图中标有箭头的连续线段分别为从A到B点图中曲线段的等效路线设A点指向B点的有向线段作为向量标准，将其分解为沿水平方向与竖直方向上的向量，而且上图中的标有箭头的线段为向量，则有：1在水平方向上从A点到B点之间的所有有向线段中，如果A与B之间存在多条曲线，其中等效有向线段中存在一条或多条水平有向线段与AB有向线段水平方向相反方向的，则那条曲线的距离长度就非AB间线路最短的，例如上图中的1与2。2在竖直方向上从A点到B点之间的所有有向线段中，如果A与B点之间存在多条曲线，选取每个等效有向线段中最大竖直有向线段的模按从大到小顺序排列，则其中竖直有向线段中模最大的即偏离标准AB有向线段越大，则该条曲线的距离长度也非AB间线路最短的，例如上图中的1，3，4。根据上述1和2的分析，则在所有A与B的所有路线中，符合1与2的原则，可以选取从A到B之间的最短线路，用上述等效路线来算出A点到B点的距离，再通过上述网格法来估测A到B的距离，通过比例尺可以算出A到B的距离。如果在某两个垃圾堆放点之间仅有一条路可供选择那么就直接选取那条路作为最短路线。5.3清运方案的设计5.3.1清运车清运方案的设计例如，对于麻勘站所服务的区域我们只考虑主要的路及街道，画出了它们的示意图并对路口，街道口及路和街道的尽头用字母进行编号，并且假设垃圾只存在于编号的地点。ABBA8图5.3在所建立的网格表上找到各点坐标：A267,231,269,231B,269,229C,269,229D,267,227E,34,229F,31z267,229；根据坐标关系确定个点之间的关系进而用5.1所示方法求得各关联点之间的距离：其中CD,在同一格内，那么BAd,=1;CBd,=1;DCd,=0;EDd,=2;FEd,=23;d(F,O)=21。根据求得的距离及示意图寻找清运车的可行方案：垃圾清运方案为3131zFEDCBAFz。最后根据可行方案计算出清运车所走的路程：路线长为：31d=213。经计算得到了其余各站清运车需要走的总路程：1d=6；2d=237；3d=9；4d=14；5d=6；6d=237；7d=24；8d=15；9d=215；10d=233；11d=217；12d=45；13d=225；14d=4；15d=217；16d=239；17z=14；18z=13；19d=215；20d=9；21d=227；22d=221；23d=14；24d=263；25d=6；26d=215；26d=9；27z=17；28z=9；29d35；31d=213；32d=2；33d=9；34d=3；35d=10；36d=44；37d=19；38d=20由于耗油量仅与路程成正比，因此，对于整个南山区的清运车有：V=381275.0iidL（1）OABCDEF9其中id指第i个转运站的清运车每次清运走的总路程，每辆车每公里耗油为0.275L把上述数据代入式1得：V=142.175L现在深圳市汽油价格为8.0元/升，那么每天清运车所需油钱为：142.1758=117.4元。5.3.2拖车及设备的设计由分析可知，居民产生的垃圾全部由收集车辆收集到垃圾转运站，垃圾转运站的转运的垃圾由拖车拖往处理中心进行垃圾处理和回收，其余垃圾直接被拖车拉送到焚烧厂与填埋场处理，由于第一部分分别包括麻勘、阳光、白芒、牛城、大石勘、官龙村、新围村、平山村、动物园、福光、塘朗、长源、西丽路十三个垃圾转运站，垃圾处理中心就设在其中的某个或多个垃圾转运站上。垃圾转运站的地点分布于各个网格中，那么垃圾转运站相对于零点的跨越网格数就是恒定的，序号为i的垃圾转运站在水平方向上跨越的网格数为ix，在竖直方向上跨越的网格数为iy，序号为j的垃圾转运站在水平方向上跨越的网格数jx，在竖直方向上跨越的网格数为jy，由上面分析，转运站之间的线路等效为网格上的竖直与水平线段，那么序号为i的垃圾转运站到序号为j的垃圾转运站所跨越的网格数为jijiyyxx，也就是相当于两不同序号的垃圾转运站之间的路线最短距离为jid.，那么有：jid.=jijiyyxx可知第一部分中各个垃圾转运站点之间的跨越网格数，即垃圾转运站之间的距离可以确定。由于各个站的垃圾是均匀分布的，垃圾转运站的垃圾量与转运站的周围的居