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

1、河南理工大学2011年数学建模竞赛论文答卷编号（竞赛组委会填写）：题目编号：（ A）论文题目： 垃圾分类处理与清运方案 参赛队员信息(必填)： 姓 名年级专业班级联系电话队员1李迎超09信息09-2班队员2赵亮09信息09-2班队员3齐卓09结构工程 答卷编号（竞赛组委会填写）：评阅情况（学校评阅专家填写）：评阅1.评阅2.评阅3. 垃圾分类处理与清运方案设计 摘要随着大运会的开展，深圳的外观建设和绿化都是展现深圳形象的重要措施，其中垃圾处理尤为重要，因此设计一个良好的垃圾处理与清运方案是很重要的。垃圾转运站设置的一个重要意义在于节省运费。一般用于收集小区垃圾到转运站的车为清运车，在本题中，题

2、目给出了深圳市南山区的垃圾转运站的分布和转运能力的大小，要求设计出大小橱余设备的分布并且给出清运方案的具体设计。在设计大小橱余设备及其分布时，运用了最短路和最少费用作为模型通过程序的编译求出三大部分地区中的线路长短，以十年为期限。第一部分区域如果用大型设备需用1台，选择在动物园垃圾转运站，此时获得纯利润为元，若用小型设备需用815台，此时获得纯利润元。对于第二部分如果用大型设备需用3台，选择在南山市场垃圾中转站，此时获得纯利润为元，若用小型设备需用2475台，此时获得纯利润为元。对于第三部分如果用大型设备需用1台，选择在望海路垃圾转运站，此时获得纯利润为元，若用小型设备需用380台，此时获得纯

3、利润为元。在设计清运方案时，我们把主干道作为考虑对象并对它进行简化，用图论的相关知识找到每一个区域的可行方案，最终得到了一种可行的具体的清运方案。第二问题依据集合覆盖模型,确定垃圾中转站的待选点;进而运用整数规划构建垃圾收运系统费用最小模型,。由于垃圾转运站被重新设计，因此各个量都是不确定的，在此建立了两个通用的集合覆盖模型与垃圾收运系统费用最小模型。只要带入确定的数据，就能得到垃圾转运站的规模、位置以及最佳经济效益。关键词： 网格法；最短路；最短距离矩阵；C语言一、问题重述垃圾主要分为橱余垃圾，可回收垃圾，有害垃圾和其他不可回收垃圾；为了更好地处理垃圾，引入垃圾收集、分类且尽量对橱余垃圾及可

4、回收垃圾再处理的方法，这样既美化了环境又节约了回收成本，达到取得一定经济效益的目的。由于处理橱余垃圾及可回收垃圾会产生经济效益而后两类垃圾只会消耗费用，并且行驶不同的路线去收集、运送垃圾会使车辆的耗油量不同，同时购买的大小型橱余垃圾处理设备数量不同及安排位置的不同都会使经济效益有所不同，这都涉及了最优化方案问题。第一问是在转运站规模与位置和深圳南山区的实际情况相同时，设计出大小型设备的分布，并且在目前运输装备条件下给出清运路线的具体方案。第二问是转运站被重新设计，此时转运站的规模与位置都是不确定的，再重新求上述问题。二、问题分析本项研究课题能为深圳市的垃圾分类化进程作出贡献，因此具有十分重要的

5、现实意义。第一问中，在垃圾转运站的规模与位置确定条件下，在南山地图上通过用竖直线段与水平线段构成的网格，用网格来具体确定南山地区垃圾转运站的具体位置和各个垃圾转运站之间的路线。对于清运路线的选择，可以把南山区分成若干小块是每一小块只含有一个转运站，从而可以将南山地区的各个垃圾转运站之间的复杂路线进行简化，进一步运用最近线段等效原则，将各段曲线用竖直的直线线段与水平的直线线段来进行等效，再通过对路线等效模型的分析，可以用等效的竖直线段与水平线段的长短和网格的结合来确定各个垃圾转运站之间的距离，从而来确定具体两个垃圾转运站的的最短路线，通过对模型的分析，可以求出南山区各个垃圾转运站之间的最短路线和

6、各个垃圾转运站之间的最短路线的长度，在设备的规划当中，根据南山区的所有垃圾转运站的具体分布，认为南山区北部的垃圾通过拖车运送到南山区南部地区进行处理不符合经济效益，因此，将南山地区的垃圾转运站分为三部分，再通过用最短路线来对设备进行规划与分配。在第二问中由于转运站的规模与位置都是不确定的，增加了模型建立的难度。针对垃圾收运系统的特点，应用了集合覆盖模型，确定垃圾中转站的待选点，然后再引入整数规划构建垃圾收运系统费用的最小模型，从待选点选出垃圾转运站的最优组合，这样对转运站选址分阶段进行了二次优化，避免了直接运用整数规划的复杂运算，为垃圾转运站选址提供一种简单易行的方法。三、模型假设（1）负责从

7、小区到转运站运输的车辆在每天早饭后收集垃圾;（2）清运车辆的耗油量只与所走过的路程有关；（3）清运车尽量走主干道，其次是次干道，最后才走街坊路；（4）拖车走高速路，快速路，主干道和次干道，不走街坊路；（5）垃圾处理中心在转运站里并且所有大小型橱余垃圾处理设备使用年限为十年，使用时不发生任何故障四、符号说明拖车从序号为的转运站到序号为的转运站转运送垃圾所花费的费用拖车运行时平均吨公里所花费的费用序号为的垃圾转运站在所服务区域内每次清运时走的总路线长（在地图上的长度）序号为的转运站M南山地区所有转运站的垃圾总量序号为转运站的垃圾总量序号为的转运站到序号为的转运站的路线的距离序号为的转运站转运的垃圾

8、总量由序号为的转运站服务区域产生的，但不能被分类处理的垃圾总量A,B两点的路线长度处理中心设在转运站中，大型设备的个数处理中心设在转运站中，小型设备的个数五、模型的建立5.1两点之间路线长度的计算方法 由于本模型中的距离是用网格法求解的，因此，对网格法进行如下说明 如图一所示，采用坐标点表示网格，若某一点不在网格的边线上（例如：A点,B点）该点所在的网格的左下角点的坐标为，那么记这个网格的坐标为。那么A点所在的网格的坐标为，B点所在网格坐标为；如果点在网格的边线上（例如C点），那么认为包含这条边线的左侧的网格的坐标为它所在的网格的坐标，那么C点所在网格坐标为。6F. DG. E . B. C4

9、O. AP20121086 4 2图5.1 网格法计算距离举例示意图为了计算方便，参照实际情况，我们可以对距离的求法作出如下简化对于任意两点A，B：（1）如果A,B不在同一网格内并且A,B都不在网格的边线上，对于从AB的不同路线，可以把所有路线的长度都看作从A点到的直线长度加上从点到点B的直线长度，即为+。例如图一中A,B两点，认为它们之间的路线长为：3+2=5。（2）如果A,B不在同一网格内或者其中一点在同一网格边线上，对于不在边线上的点认为它在网格的中心处，路线长度的计算与相同。例如对于图一中的D、E距离为0.55.2最短路线的选取方法如果在两个垃圾堆放点之间有多条路线可以选取，我们结合实

10、际情况，以在保护环境的前提下尽量使车所走路最小为原则作出如下分析：（假设下图曲线就是选取的路线，横竖直线构成网格） 首先在地图上绘出水平间距相等和竖直间距相等的直线，构成网格，现假设从A点到B点有如上线路即(网格中的曲线)，将网格中的曲线运用离曲线最近的原则，用标有箭头的连续线段来等效该曲线，要求该线段是网格中的水平线段或AABB 图5.2.1 图5.2.2AABB 图5.2.3 图5.2.4是网格中的竖直线段，而且绘制出的等效连续直线段的所有端点均匀分布于该曲线的两侧，则上述图中标有箭头的连续线段分别为从A到B点图中曲线段的等效路线设A点指向B点的有向线段作为向量标准，将其分解为沿水平方向与

11、竖直方向上的向量，而且上图中的标有箭头的线段为向量，则有：在水平方向上从A点到B点之间的所有有向线段中，如果A与B之间存在多条曲线，其中等效有向线段中存在一条或多条水平有向线段与AB有向线段水平方向相反方向的，则那条曲线的距离长度就非AB间线路最短的，例如上图中的与。在竖直方向上从A点到B点之间的所有有向线段中，如果A与B点之间存在多条曲线，选取每个等效有向线段中最大竖直有向线段的模按从大到小顺序排列，则其中竖直有向线段中模最大的即偏离标准AB有向线段越大，则该条曲线的距离长度也非AB间线路最短的，例如上图中的，。根据上述和的分析，则在所有A与B的所有路线中，符合与的原则，可以选取从A到B之间

12、的最短线路，用上述等效路线来算出A点到B点的距离，再通过上述网格法来估测A到B的距离，通过比例尺可以算出A到B的距离。如果在某两个垃圾堆放点之间仅有一条路可供选择那么就直接选取那条路作为最短路线。5.3清运方案的设计5.3.1清运车清运方案的设计例如，对于麻勘站所服务的区域我们只考虑主要的路及街道，画出了它们的示意图并对路口，街道口及路和街道的尽头用字母进行编号，并且假设垃圾只存在于编号的地点。O 图5.3在所建立的网格表上找到各点坐标：,；根据坐标关系确定个点之间的关系进而用5.1所示方法求得各关联点之间的距离：其中在同一格内，那么=1;=1;=0;=2;=;d(F,O)=。根据求得的距离及

13、示意图寻找清运车的可行方案：垃圾清运方案为。最后根据可行方案计算出清运车所走的路程：路线长为：=。经计算得到了其余各站清运车需要走的总路程：=6；=；=9；=14；=6；=；=24；=15；=；=；= ；=45；=；=4；=；=；=14；=13；=；=9；=；=；=14；=；=6；=；=9；=17；=9；35；=；=2；=9；=3；=10；=44；=19；=20由于耗油量仅与路程成正比，因此，对于整个南山区的清运车有： = （1）其中指第个转运站的清运车每次清运走的总路程，每辆车每公里耗油为0.275把上述数据代入式得：=142.175现在深圳市汽油价格为8.0元/升，那么每天清运车所需油钱为

14、：142.1758=117.4元。5.3.2拖车及设备的设计由分析可知，居民产生的垃圾全部由收集车辆收集到垃圾转运站，垃圾转运站的转运的垃圾由拖车拖往处理中心进行垃圾处理和回收，其余垃圾直接被拖车拉送到焚烧厂与填埋场处理，由于第一部分分别包括麻勘、阳光、白芒、牛城、大石勘、官龙村、新围村、平山村、动物园、福光、塘朗、长源、西丽路十三个垃圾转运站，垃圾处理中心就设在其中的某个或多个垃圾转运站上。垃圾转运站的地点分布于各个网格中，那么垃圾转运站相对于零点的跨越网格数就是恒定的，序号为的垃圾转运站在水平方向上跨越的网格数为，在竖直方向上跨越的网格数为，序号为的垃圾转运站在水平方向上跨越的网格数，在竖

15、直方向上跨越的网格数为，由上面分析，转运站之间的线路等效为网格上的竖直与水平线段，那么序号为的垃圾转运站到序号为的垃圾转运站所跨越的网格数为，也就是相当于两不同序号的垃圾转运站之间的路线最短距离为，那么有：=可知第一部分中各个垃圾转运站点之间的跨越网格数，即垃圾转运站之间的距离可以确定。 由于各个站的垃圾是均匀分布的，垃圾转运站的垃圾量与转运站的周围的居民分布密度有直接关系，人口密度越大，则垃圾转运站的垃圾总量越多，垃圾转运站的规模越大，转运量就也就越大，那么各个垃圾转运站的垃圾总量，则： 其中 垃圾从序号为转运站运送到序号为转运站产生的费用，有： 在第一部分任意选取序号为的垃圾转运站作为分析

16、:若选取序号为的垃圾转运站作为垃圾处理中心，即大，小型设备设在该垃圾转运站，其他有（）个垃圾转运站运送到该垃圾处理中心处理。十年中一大型厨余垃圾处理设备所挣取的利润与可回收垃圾的利润和为:十年中一小型设备垃圾处理设备所挣取的利润与可回收垃圾的利润和为：通过上述分析，在第一部分地区的使其余垃圾转运站运送垃圾到达垃圾转运站时，在同样的地区使用设备十年，使用大型设备产生的经济效益大于使用小型设备产生的经济效益可以得到在第一部分中把动物园的垃圾转运站中设立为垃圾处理中心。在第二部分中存在二十二个垃圾转运站，垃圾处理中心就设在其中的某个或多个垃圾转运站上。同理，用划网格的方法将第二部分中各个垃圾转运站的

17、之间的最短线路求出来：有 =第二部分中各个垃圾转运站点之间的跨越网格数，即垃圾转运站之间的距离可以确定，由上述的网格方法可得出垃圾转运站之间各点最短距离矩阵得：垃圾从序号为转运站运送到序号为转运站产生的费用： 若选取序号为的垃圾转运站作为垃圾处理中心，即大，小型设备设在该垃圾转运站，其他有（）个垃圾转运站运送到该垃圾处理中心处理；其他（）个垃圾转运站运送到该垃圾处理中心的拖车运送总费用为;十年中一个大型厨余垃圾处理设备所挣取的利润与可回收垃圾的利润和为:十年中一个小型设备垃圾处理设备所挣取的利润与可回收垃圾的利润和为：求出第一部分中使其余垃圾转运站运送垃圾到达各个垃圾转运站时，拖车运送总费达到

18、最小： 即 将拖车运送总费用按照从小到大顺序排列，依次选出其中垃圾转运站，选取其中从小到大的依次考虑得：若垃圾转运站的垃圾总的转用来的垃圾总量成倍数关系，那么就在该处理中心建造几个大型设备若垃圾转运站的垃圾总的转用来的垃圾总量不成倍数，根据具体情况来分配大型垃圾处理设备若垃圾转用来的垃圾总量/0.25的倍数，那么就在该处理中心设几台设备若垃圾转用来的垃圾总量/0.25不是成倍数关系，那么处理中心就应该在第二部分中：由程序得： 由于，可以得到在第一部分中序号为30即南山市场的垃圾转运站中设立垃圾处理中心，其大型设备的个数即等于3 246那么 .6可以得到：在十年内在第二部分中，在南山市场垃圾转运

19、站中用大型设备处理垃圾，可以带来的纯利润为：若如果将大型设备换作小型设备来处理，大概能产生的经济效益为：由程序计算得： 由于，可以得到在第二部分中序号为30即南山市场的垃圾转运站中设立垃圾处理中心，其小型设备的个数即等于2475来处理同等的垃圾: 246 通过上述分析，在第二部分地区的使其余垃圾转运站运送垃圾到达垃圾转运站时，在同样的地区使用设备十年，使用大型设备产生的经济效益远大于使用小型设备来产生的经济效益。同理，在第三部分，即东滨路以南地区中有花果路公厕、望海路垃圾站两个垃圾转运站，在在第三部分中：由程序计算得： 那么 1026可以得到：在十年内在第三部分中，在花果路公厕市场垃圾转运站中

20、用大型设备处理垃圾，可以带来的纯利润为：如果将大型设备换作小型设备来处理，大概能产生的经济效益为：由程序运行得： 可以得到：在十年内在第三部分中，在南山市场垃圾转运站中用大型设备处理垃圾，可以带来的纯利润为：通过上述分析，在第三部分地区的使其余垃圾转运站运送垃圾到达垃圾转运站时，在同样的地区使用设备十年，使用大型设备产生的经济效益小于使用小型设备来产生的经济效益，因此，在此区域应该选用小型设备来处理垃圾。5.4垃圾转运站规模与位置不定垃圾收运过程是垃圾从分散到集中的过程是一个产生源高度分散、处置相对集中、产生量随季节变化的“倒物流”系统。借鉴物流系统理论来垃圾收运“倒物流”系统的规划是可行的。

21、在各种垃圾回收物流系统的运作方式中，转运站起垃圾收集和运输分开的作用。因此，垃圾转运站的优化选址是垃圾收运系统优化研究的关键环节，必须研究两个问题：其一是必须达到的运输距离，即所谓临界转运距离；其二是垃圾转运站设置的合理位置。本文针对垃圾收运系统的特点，首先应用集合覆盖模型，确定垃圾中转站的待选点，然后再引入整数规划构建垃圾收运系统费用的最小模型，从待选点选出垃圾中转站的最优组合，这样对转运站选址分阶段的二次优化，避免了直接运用整数规划的复杂运算，为垃圾转运站选址提供一种简单易行的方法。5.4.1垃圾中转站待选点的确定5.4.1.1垃圾收运系统物流系统通常应用交叉中值模型、精确重心法、覆盖模型

22、和中值模型。对于城市垃圾收运系统，在综合考虑城市总体规划、当地经济、市政设施、交通状况、公众的接受认可度等影响因素，并进行现场勘探的基础上，利用集合覆盖模型初步确定垃圾转运站的待选址。考虑到垃圾站越多，环境影响点越多，因此，在不影响垃圾正常收集的前提下，参照垃圾收集密度以及当地人口密度，适当增加每座垃圾站的服务范围，计算出每一垃圾转运站的规模，即转运能力，而后用最少垃圾转运站去覆盖所有小区。具体步骤如下：设有座小区，集合覆盖模型为： （1）对上述（1）模型求解，可以应用分支定界的求解方法进行精确计算，但计算过程复杂且运算量较大。因此，本研究选用启发式算法进行求解，所得结果可能不是最优解，但必定

23、是可行解，据此初步确定垃圾转运站的待选点，为二次优化做准备。5.2.2垃圾转运站选址优化模型的建立在确定了垃圾转运站的待选点后，运用整数规划法建立整个垃圾收运系统总费用最小模型，实现总体优化。5.2.2.1模型提出整个垃圾收运过程中所发生的费用主要取决于规划期内垃圾从小区到转运站的运输费用，垃圾从转运站到垃圾处理中心、南山垃圾焚烧厂、下坪固体废弃物填埋厂的运输费用，大小型厨余垃圾处理设备的投资费用与运行成本，最后还有司机的工资。这些费用彼此相互关联相互制约，均与转运站位置、规模密切相关。5.2.2.2垃圾收运系统费用最小模型 （2）式中，为规划使用年限，为第座小区运往第座转运站单位运输量单位距

24、离的费用，为第i座小区 运往第k 座转运站的日运输垃圾量， 为第i座小区运往第k座转运站运输距离 ，为第k座转运站运往第j座垃圾处理中心单位运输量单位距离的费用， 为第k座转运站运往第j座处理场日运输垃圾量， 为第k座转运站运往第j座处理场运输距离， 为规划期内待购买的大小型设备的固定投资， E为大小型设备的运行成本， Qmin为中转站建设的最小控制规模， Qmax为中转站建设的最大控制规模。六、模型评价（1）针对垃圾收运系统的特点，利用网格法确定两点的位置与距离，,引入逆向物流理论,应用集合覆盖模型,确定垃圾中转站的待选点;进而运用整数规划构建垃圾收运系统费用现值最小模型,从待选点中选出垃圾

25、中转站的最优组合。（2）通过对中转站选址分阶段的两次优化，避免了整数规划复杂的运算，实际应用性好为城市垃圾转运站选址提供了一种简单易行的方法.(3)本模型采用网格法测定两点的距离，再加上使用粗糙的比例尺会使某些点间的距离不太准确，影响结论数据的准确度。七、参考文献1 姜启源，谢金星，叶俊.数学模型（第三版）.北京：高等教育出版社，20032王宏志，韩志明.C语言程序设计（第二版）.中国铁道出版社，20093蔡临宁.物流系统规划建模及实例分析M.北京：机械工业出版社，3043附录：附录1：对转运站的编号编号垃圾转运站名称编号垃圾转运站名称编号垃圾转运站名称1九街站14北头站27大冲站2玉泉站15涌下村站28