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

深圳市南山区摘要本题主要研究深圳南山区垃圾分类化过程中对橱余垃圾的处理设备的分布设计，由于涉及了南山区的地形区域分块等实际问题，我们首先将南山区分成六个板块分别解决. 利用图论的基本概念，在每个板块之中，我们都得到一个图作为简化模型，该图以每一个垃圾转运站为顶点、所有顶点的集合为其顶点集；以垃圾站之间互相连接的最短路线的集合为其边集. 为简化模型，我们假设橱余垃圾处理设备置放在顶点即垃圾转运站处，于是将题目第一步转化为：在每一个板块内的图中，求出一个垃圾转运站点，使所有其它垃圾站运送垃圾到此站的总运送量（t×km）最小. 我们用矩阵表示图，通过矩阵运算，使用matlab软件编程，利用Floyd算法，求出图内任意两点的最短路程及路线，分别用距离矩阵和路径矩阵表示结果. 然后再结合垃圾转运站的转运垃圾吨数，将问题转化为最短路程问题中的重心问题. 最终利用Excel表格求解得到总运量最小的垃圾处理中心的具体位置. 其次，通过对大小型设备的收益回收成本速度的函数比较，决定板块内的垃圾处理设备类型选择. 对于第二题，我们直接给出这样的方案：在保持原来垃圾转运站位置不变的条件下，通过改变原来的垃圾转运站转运规模，将板块内使最优运输方案下的站点设置与最短路线下的站点设置一致. 然后使用与第一题一样的算法和程序进行求解和检验. 下面是我们给出的题目的答案：第一题：板块A的设备分布点是大石磡站，设立的设备是100台小型橱余垃圾处理设备；板块B的设备分布点是官龙村站，设立的设备是一台大型橱余垃圾处理设备；板块c的设备分布点是大新小学站，设立的设备是一台大型橱余垃圾处理设备板块D的设备分布点是沙河市场站，设立的设备是一台大型橱余垃圾处理设备板块E的设备分布点是疏港小区站，设立的设备是64台小型橱余垃圾处理设备板块F的设备分布点是花果路站或者望海路站，设立的设备是96台小型橱余垃圾处理设备. 具体的运输路线参照各板块求出的路径矩阵R. 第二题：板块A的设备分布点是白芒站，设立的设备是100台小型橱余垃圾处理设备；板块B的设备分布点是官龙村站，设立的设备是一台大型橱余垃圾处理设备；板块C的设备分布点是北河湾站，设立的设备是一台大型橱余垃圾处理设备板块D的设备分布点是沙河市场站，设立的设备是一台大型橱余垃圾处理设备板块E的设备分布点是疏港小区站，设立的设备是64台小型橱余垃圾处理设备板块F的设备分布点是花果路站或者望海路站，设立的设备是96台小型橱余垃圾处理设备. 具体的运输路线参照各板块求出的路径矩阵R.最后，我们通过对成本回收时间及经济效益计算，对模型进行检验，得出结论：该模型对橱余垃圾的处理能够在满足环保效果的前提实现最佳经济效益. 【关键字】图论    图的矩阵表示    Floyd算法    最短路问题  重心问题目录1. 问题的重述31.1 基本情况31,2 问题由来31.3 问题提出32. 问题分析33. 模型的假设与约定44. 符号说明及名词定义45. 模型建立55.1 应用算法55.2 选择使用大型设备和小型设备的依据55.3 深圳市南山区的所有垃圾中转站分布图分块情况65.4 A块模型计算 65.5 B块模型计算 85.6 C块模型计算 115.7 D块模型计算 145.8 E块模型计算 165.9 F块模型计算 166. 模型的检验 177. 模型的优缺点 178. 参考文献 17附录171. 问题重述1.1 基本情况垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资源回收与再利用的城市绿色工程。在深圳市，垃圾分为四类：橱余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾，其中橱余垃圾和可回收垃圾经过处理，回收和利用，产生经济效益。但是许多问题仍然是垃圾分类化进程中需要深入研究的。1.2 问题由来深圳市南山区，共有38个垃圾中转站，所有垃圾需要从小区运送到附近的转运站，再运送到少数几个垃圾处理中心，经过处理，回收和利用，产生经济效益。而处理橱余垃圾的设备分为大小两种，不同处理规模的设备成本和运行成本也不一样，这就需要考虑如何达到最佳的问题。1.3 问题提出根据深圳市南山区的实际情况，现要求解决下列问题：问题一：在现有垃圾转运站规模与位置不变条件下，给出大小型分布位置以及台数，同时给出此运输装备条件下清运的具体方案（包括：清运路线、各路线清运的垃圾吨数和运输时间）。问题二：在垃圾转运站位置不变的条件下，重设垃圾转运站规模，给出大小型分布位置以及台数，同时给出此运输装备条件下清运的具体方案（包括：清运路线、各路线清运的垃圾吨数和运输时间）。问题三：分别求出上述两种方案的经济效益，并对方案进行评价。2. 问题分析第一阶段：简化模型：1 先将深圳市南山区的所有垃圾中转站分布图分成6个大部分。2 在每个部分中简化模型，将垃圾转运站设为顶点，连接顶点做出无向图。3 再针对每个部分分别进行模型的处理，给垃圾处理站顶点确定设备，再找出使运输距离总和最小的垃圾中转站。4 问题求解过程中，我们只针对橱余垃圾进行求解，包括定出转运站的最优分布位置和垃圾处理设备的使用台数及垃圾处理效益。第二阶段：垃圾处理站点的设置：1 利用比例尺，运用图论模型编程求解，求出所有任意两点间的距离。2 用距离乘以每个中转站的垃圾量，得出其最小值点。将垃圾处理站设在该点。第三阶段：求出所有垃圾转运站到垃圾处理站的路程最小值：1 保持垃圾中转站的位置不变。2 根据垃圾处理数量，为了获得最大效益，将垃圾处理站定在转运量承载最大的转运站点。3 为了达到运输过程车辆分配的最优化和最大效益，将其他中转站的转运量平均分配。4 求出所有垃圾转运站到垃圾处理站的路程最小值，根据路程最小值给定运输路线方案。3. 模型假设与约定1. 运输车行走拐弯的时间，路上的意外事故的耽搁时间忽略。2. 假定每个模块只设一个垃圾处理站3. 设小型餐厨垃圾处理机，处理能力为250公斤/日橱余垃圾处理后产物价格在1250元/吨。4. 各垃圾点的垃圾必须当天及时清除完，不允许滞留5. 晚上9：00后不堵车6. 每天各垃圾点的垃圾量基本相同7. 每个垃圾点无论其中垃圾是否清理完全都需要10分钟装车时间8. 每个垃圾点都在路口，便于垃圾的集中、运输9. 垃圾只在晚上运输，基本保证运完后，当天不会再有新的垃圾产生10. 假定人均垃圾产生垃圾量一定4. 符号说明及名词定义G（V，E） 表示一个图，其中V为顶点集合，E为边集合. W  表示图的带权邻接矩阵，W=，其中：1D  表示图的距离矩阵，D=，其中表示到的最短距离. 1R  表示路径矩阵，R=,的含义是从到的最短路要经过点号为的点每求得一个D(k)时，按下列方式产生相应的新的R(k)1即当被插入任何两点间的最短路径时，被记录在R(k)中，依次求D(v)时求得R(v)，可由R(v)来查找任何点对之间最短路的路径1分别表示38个垃圾转运站，具体对应表见附录. 5. 模型建立5.1 应用算法Floyd算法：求任意两点间的最短路D(i,j)：i到j的距离R(i,j)：i到j之间的插入点输入: 带权邻接矩阵w(i,j)（1）赋初值：对所有i,j, d(i,j) w(i,j), r(i,j) j, k1（2）更新d(i,j), r(i,j)对所有i,j，若d(i,k)+d(k,j)<d(i,j)，则d(i,j) d(i,k)+d(k,j), r(i,j) k（3）若k=，停止否则kk+1，转（2）5.2 选择使用大型设备和小型设备的依据由于分块之后，每一块的日处理橱余垃圾吨数都大于250公斤而小于200t，因此我们需要确定在何种情况要设立一个大型设备，何种情况设立多个小型设备.  设每天需要处理n吨橱余垃圾（），投资大型、小型橱余垃圾处理设备后的收益(除去设备运行成本，不计运输成本)，收回投资成本分别需要的天数为、天. 对大型设备，有：（）对小型设备，有：（）利用matlab画出这两个函数图像，通过求解及观察可看出，当时，投资小型设备能更快收回成本；当时，投资大型设备能更快收回成本. 5.3 深圳市南山区的所有垃圾中转站分布图分块情况如图所示，先将深圳市南山区的所有垃圾中转站分布图分成6个大部分。5.4 A块模型计算图A1                                  图A2根据图论，将左图的实际站点位置和路线简化为右图的图的模型，记为图GA。 有：两点之间的权为其直接到达的路线长度的公里数. 利用Photoshop及谷歌地图求出所给地图比例尺，可测出图上任意两点距离. 因此， 图的带权邻接矩阵可表示为：用matlab编程，利用Floyd算法求出任意两点的最短路. 具体程序见附录程序%Floyd及%板块A. 运行程序可求得图的距离矩阵为：该矩阵为对称矩阵路径矩阵为：. 把以上距离矩阵输入到Excel表格中，然后利用Excel表格的函数功能，把矩阵的每一行乘以该行对应垃圾中转站的垃圾转运量，接着把每一列所得的乘积结果累加，得到的累加结果即为将橱余垃圾处理中心设在该列所对应的垃圾中转站时，所需的垃圾转运总量，得到的累加行结果如下表所示：表1 A块垃圾转运量统计表格（全部数据见附表A）转运站牛陈村阳光白芒麻勘大石磡总运量（吨·公里）412197.8226.5328.4163      我们对以上表格中的总运量进行比较，找出总运量最少的列所对应的转运站大石磡站。由于此行表示将橱余垃圾处理中心设在该列所对应的垃圾中转站时，所需的垃圾转运总量，因此，我们认为把A块的橱余垃圾处理中心设在大石磡站，在现在运输装备情况下，总运量将会是最少的。根据题目所给的“垃圾转运站垃圾转运量等情况统计表（南山）”可以求出，A片区中，5个垃圾中转站每天需要转运的垃圾总量为63吨，根据题目附录1中所给数据可知，橱余垃圾占垃圾总量的40%，因此，A片区总需要处理的橱余垃圾数量为25.2吨，根据前面所作出的大小型垃圾处理设备的投资成本回收所需天数与垃圾量的关系函数，对于A片区，我们决定在大石磡站处设100台小型处理设备。第二题：我们根据第一题求出的距离矩阵DA，转化成Excel表格，分别把每一列累加，得到的累加结果即为该列对应的垃圾中转站设为橱余垃圾处理中心时，从垃圾中转站到处理中心的运输路程总和，得到表4  A块垃圾运输距离统计表（全部数据见附录A）转运站牛陈村阳光白芒麻勘大石磡运输距离（公里）23.913.513.421.321.9      比较上表中的数据，找出使运输距离总和最小的垃圾中转站白芒站。由于此行表示把每列对应的垃圾中转站设为橱余垃圾处理中心时，从垃圾中转站到处理中心的运输路程总和，因此，我们认为把A块的橱余垃圾处理中心设在大石磡站，在现在运输装备情况下，总运量将会是最少的。将本区域的所有垃圾平均分配到本区域的所有垃圾中转站。5.5 B块模型计算 图B1                                  图B2根据图论，将右图的实际站点位置和路线简化为左图的图的模型，记为图GB。 有：两点之间的权为其直接到达的路线长度的公里数. 利用Photoshop及谷歌地图求出所给地图比例尺，可测出图上任意两点距离. 因此， 图的带权邻接矩阵可表示为：该矩阵为对称矩阵. 用matlab编程，利用Floyd算法求出任意两点的最短路. 具体程序见附录程序%Floyd及%板块B. 运行程序可求得图的距离矩阵为:该矩阵为对称矩阵. 路径矩阵为：把以上距离矩阵输入到Excel表格中，然后利用Excel表格的函数功能，把矩阵的每一行乘以对应垃圾中转站的垃圾转运量，接着把每一列所得的乘积结果累加，得到的累加结果即为将橱余垃圾处理中心设在该列所对应的垃圾中转站时，所需的垃圾转运总量，得到的累加行结果如下表所示：表3 B块垃圾转运量统计表格（全部数据见附表B）转运站动物园站平山村站新围村站官龙村站西丽路站总运量（吨·公里）493.915557.025515.88463.8586.68转运站龙井光前站塘朗站福光站长源村站总运量（吨·公里）912.78789.74751.955747.32976.795      我们对以上表格中的总运量进行比较，找出总运量最少的列所对应的转运站官龙村站。由于此行表示将橱余垃圾处理中心设在该列所对应的垃圾中转站时，所需的垃圾转运总量，因此，把B块的橱余垃圾处理中心设在官龙村站，在现在运输装备情况下，总运量将会是最少的。根据题目所给的“垃圾转运站垃圾转运量等情况统计表（南山）”可以求出，B片区中，10个垃圾中转站每天需要转运的垃圾总量为155吨，根据题目附录1中所给数据可知，橱余垃圾占垃圾总量的40%，因此，B片区总需要处理的橱余垃圾数量为62吨，根据前面所作出的大小型垃圾处理设备的投资成本回收所需天数与垃圾量的关系函数，对于B片区，我们决定在官龙村站处设1台大型处理设备。第二题：在问题假设中，我们将本区域的所有垃圾平均分配到本区域的所有垃圾中转站。我们根据第一题求出的距离矩阵DB，转化成Excel表格，分别把每一列累加，得到的累加结果即为该列对应的垃圾中转站设为橱余垃圾处理中心时，从垃圾中转站到处理中心的运输路程总和，得到累加行如下：表4  B块垃圾运输距离统计表（全部数据见附录B）中转站动物园站平山村站新围村站官龙村站西丽路站运输距离（公里）37.08143.51441.78436.57644.768中转站龙井光前站塘朗站福光站长源村站运输距离（公里）59.24355.77944.79244.98357.64      比较上表中的数据，找出使运输距离总和最小的垃圾中转站官龙村站。由于此行表示把每列对应的垃圾中转站设为橱余垃圾处理中心时，从垃圾中转站到处理中心的运输路程总和，因此，我们认为把B块的橱余垃圾处理中心设在官龙村站，在现在运输装备情况下，运输距离将会是最少的。由于第二题和第一题以同样的划分处理，垃圾总量不变，因此，垃圾处理设备的分布情况和第一题一样。5.6 C块模型计算图C1                              图C2根据图论，将右图的实际站点位置和路线简化为左图的图的模型，记为图GC。 有：利用Photoshop及谷歌地图求出所给地图比例尺，可测出图上任意两点距离. 因此， 图的带权邻接矩阵可表示为：该矩阵为对称矩阵. 用matlab编程，利用Floyd算法求出任意两点的最短路. 具体程序见附录程序%Floyd及%板块C. 运行程两点之间的权为其直接到达的路线长度的公里数.序可求得图的距离矩阵为:该矩阵为对称矩阵. 路径矩阵为：把以上距离矩阵输入到Excel表格中，然后利用Excel表格的函数功能，把矩阵的每一行乘以对应垃圾中转站的垃圾转运量，接着把每一列所得的乘积结果累加，得到的累加结果即为将橱余垃圾处理中心设在该列所对应的垃圾中转站时，所需的垃圾转运总量，得到的累加行结果如下表所示：表5 C块垃圾转运量统计表格（全部数据见附表C）转运站同乐村松坪山松坪山（二）月亮湾前海公园九街总运量（吨·公里）1756.771556.891894.011176.071135.1907.29转运站玉泉大新小学涌下村南山市场北头南山村总运量（吨·公里）1155.29875.7893.551117.48916.941228.59转运站南园南光科技园深圳大学总运量（吨·公里）1240.451135.341561.191671.63       我们对以上表格中的总运量进行比较，找出总运量最少的列所对应的转运站大新小学站。由于此行表示将橱余垃圾处理中心设在该列所对应的垃圾中转站时，所需的垃圾转运总量，因此，把C块的橱余垃圾处理中心设在白芒站，在现在运输装备情况下，总运量将会是最少的。根据题目所给的“垃圾转运站垃圾转运量等情况统计表（南山）”可以求出，C片区中，16个垃圾中转站每天需要转运的垃圾总量为321吨，根据题目附录1中所给数据可知，橱余垃圾占垃圾总量的40%，因此，C片区总需要处理的橱余垃圾数量为128.4吨，根据前面所作出的大小型垃圾处理设备的投资成本回收所需天数与垃圾量的关系函数，  对于C片区，我们决定在白芒站处设1台大型处理设备。第二题：在问题假设中，我们将本区域的所有垃圾平均分配到本区域的所有垃圾中转站。我们根据第一题求出的距离矩阵DC，转化成Excel表格，分别把每一列累加，得到的累加结果即为该列对应的垃圾中转站设为橱余垃圾处理中心时，从垃圾中转站到处理中心的运输路程总和，得到累加行如下：表6  C块垃圾运输距离统计表（全部数据见附录C）中转站同乐村松坪山松坪山二月亮湾前海公园九街运输距离（公里）85.3973.4788.0360.7758.56 46.57 垃圾站玉泉大新小学涌下村南山市场北头南山村运输距离（公里）55.87 44.14 43.29 52.22 42.60 57.55 垃圾站南园南光科技园深圳大学  运输距离（公里）56.47 50.66 69.97 74.39          比较上表中的数据，找出使运输距离总和最小的垃圾中转站北头站。由于此行表示把每列对应的垃圾中转站设为橱余垃圾处理中心时，从垃圾中转站到处理中心的运输路程总和，因此，我们认为把C块的橱余垃圾处理中心设在北头站，在现在运输装备情况下，运输距离将会是最少的。由于第二题和第一题以同样的划分处理，垃圾总量不变，因此，垃圾处理设备的分布情况和第一题一样。5.7 D块模型计算图D1                            图D2根据图论，将右图的实际站点位置和路线简化为左图的图的模型，记为图GD。 有：两点之间的权为其直接到达的路线长度的公里数. 利用Photoshop及谷歌地图求出所给地图比例尺，可测出图上任意两点距离. 因此， 图的带权邻接矩阵可表示为：该矩阵为对称矩阵. 由于该图为连通图，故其带权邻接矩阵即为其距离矩阵：该矩阵为对称矩阵. 路径矩阵为：把以上距离矩阵输入到Excel表格中，然后利用Excel表格的函数功能，把矩阵的每一行乘以对应垃圾中转站的垃圾转运量，接着把每一列所得的乘积结果累加，得到的累加结果即为将橱余垃圾处理中心设在该列所对应的垃圾中转站时，所需的垃圾转运总量，得到的累加行结果如下表所示：表7 D块垃圾转运量统计表格（全部数据见附表D）转运站大冲沙河市场白石洲南华侨城总运量（吨·公里）463.5434.4477.45440.1     我们对以上表格中的总运量进行比较，找出总运量最少的列所对应的转运站沙河市场站。由于此行表示将橱余垃圾处理中心设在该列所对应的垃圾中转站时，所需的垃圾转运总量，因此，把D块的橱余垃圾处理中心设在白芒站，在现在运输装备情况下，总运量将会是最少的。根据题目所给的“垃圾转运站垃圾转运量等情况统计表（南山）”可以求出，D片区中，4个垃圾中转站每天需要转运的垃圾总量为165吨，根据题目附录1中所给数据可知，橱余垃圾占垃圾总量的40%，因此，D片区总需要处理的橱余垃圾数量为66吨，根据前面所作出的大小型垃圾处理设备的投资成本回收所需天数与垃圾量的关系函数，对于D片区，我们决定在白芒站处设1台大型处理设备。第二题：在问题假设中，我们将本区域的所有垃圾平均分配到本区域的所有垃圾中转站。我们根据第一题求出的距离矩阵DD，转化成Excel表格，分别把每一列累加，得到的累加结果即为该列对应的垃圾中转站设为橱余垃圾处理中心时，从垃圾中转站到处理中心的运输路程总和，得到累加行如下：