深圳南山区橱余垃圾处理方案设计

2011年华南师范大学数学建模竞赛深圳南山区橱余垃圾处理方案设计摘要本文所讨论的问题可以归结为图论与整数规划问题。首先，根据给出的“南山区垃圾转运站分布图”，将图形简化，把38个垃圾转运站归结为11个分布点，并在地图上选取主要干道的13交叉点与11个分布点一起作为橱余处理厂的建设候选点。由此将问题转化为图论问题。其次，根据图论中的“Floyd算法”，算出24个候选点两两之间的最短路程。由此将问题转化为“多设施选址问题”。再次，根据[2]中已证结论：当粮仓可以建在村庄里或道路上时，则粮仓建在村庄里可使总运费达到最小。我们确定将橱余处理厂建在所选的候选点上能使总运费最小。然后根据设备处理量、设备建设成本、待处理垃圾总量等条件与总成本最小这一目标构建整数规划模型。在实际建模中合理假设建设3个大型处理厂成本最小，然后利用lingo软件求解，得出处理厂的分布方案。具体如下：建设3个大型处理厂，分别在2v（新围公厕垃圾站附近）、6v（前海公园公厕垃圾站附近）、7v（大冲公厕垃圾站附近）进而规划清运路线。再者，利用图论中的Dijkstra算法，求出最短的清运路线。具体如下：12vv、4132vvv、5166vvv、917166vvvv、1019186vvvv、37vv、8217vvv、1124208217vvvvvv最后，在问题2中把居民区合理简化为分布点，同样把所选的主要干道交叉点一齐作为中转站的候选点，参考问题一的步骤，修改了问题一的模型求出新的垃圾中转站方案，再根据这个方案利用问题一的方法与步骤求出新的橱余处理厂方案与橱余垃圾清运方案。本文给出的模型可以求解出处理厂的建设数量、规模、位置以及中转站垃圾的运输去向，同时模型的应用性强，可以用来解决本题中的1、2小题，并对模型进行了适当修改使之能够适用于其他地区的相关设施建设问题，适用性强。关键词：图论、最短路、Floyd算法、整数线性规划、Dijkstra算法问题重述垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资源回收与再利用的城市绿色工程。在深圳，垃圾分为四类：橱余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾。它们的平均比例为，橱余垃圾：可回收垃圾：有害垃圾：其他不可回收垃圾比例约为4：2：1：3。在垃圾分类收集与处理中，不同类的垃圾有不同的处理方式，简述如下：（1）橱余垃圾可以使用脱水干燥处理装置，处理后的干物质运送饲料加工厂做原料。不同处理规模的设备成本和运行成本（分大型和小型）如下：大型厨余垃圾处理设备，处理能力为200吨/日，投资额约为4500万元，运行成本为150元/吨；小型餐厨垃圾处理机，处理能力为200-300公斤/日，投资额约为28万元，运行成本为200元/吨。橱余垃圾处理后产物价格在1000-1500元/吨。（2）可回收垃圾将收集后分类再利用。（3）有害垃圾将运送到固废处理中心集中处理。（4）其他不可回收垃圾将运送到填埋场或焚烧场处理。所有垃圾将从小区运送到附近的转运站，再运送到少数几个垃圾处理中心。显然，1）和2）两项中，经过处理，回收和利用，产生经济效益，而3）和4）只有消耗处理费用，不产生经济效益。本项研究课题旨在为深圳市的垃圾分类化进程作出贡献。为此请你们运用数学建模方法对深圳市南山区的分类化垃圾的实现做一些研究，具体的研究目标是：假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计，同时在目前的运输装备条件下给出清运路线的具体方案。以期达到最佳经济效益和环保效果。假设转运站允许重新设计，请为问题1）的目标重新设计。南山区的垃圾清运设备情况（主要是车辆数目和载重）。拖头（拖车）：只拖十吨的大型厢，只用于从转运站到垃圾中心，每次只拖一个大型“厢”，平均吨公里耗油25L—30L柴油/百公里。收集车辆：只负责从小区的垃圾站到转运站运输。60辆2.5吨汽车，每车耗油20L—35L70#汽油/百公里。司机月薪平均3500元。问题分析我们认为最符合经济效益应该为：总成本最小，其中总成本=处理厂建设成本+垃圾处理费用+垃圾运输成本；最符合环保效益应该为：把所有能够利用回收的垃圾都回收。根据所给出的垃圾中转站处理垃圾数据以及垃圾的比例，我们认为有害垃圾和其他不可回收不通过中转站直接运到处理点处理，经中转站的那部分总量为804吨的垃圾，都为橱余与可回收垃圾，其中按照橱余垃圾：可回收垃圾=4：2来算出橱余垃圾量为536吨。由于实际生活中可回收垃圾有相关回收公司上门回收，所以本题仅考虑橱余处理厂的建设问题以及这部分橱余垃圾的运输问题。本题的运输路线是南山区的实际道路，已经建成，出于成本考虑，我们不可能在一个没有道路的地方建设处理厂，所以选取实际道路，把问题变成图论问题。本题是研究怎么建橱余处理厂使得总成本最小，是个整数规划问题。模型假设假设1：把实际地图简化成图论中的图。由于南山区的道路网络十分复杂，为简化问题的求解，我们只适当选取主要的道路作为解决问题考虑的边；另一方面，由于实际的垃圾转运站数目较多，一部分的地理位置分布又比较接近，我们将38个转站归结为中11个点来考虑（简化原则是：如果数个中转站地理位置相近或必须经过同一条道路，就把它们归为同一点）。这样，选出的点加上选出的道路的交点还有选出的主要道路，就得到一张图论中的图。假设2：假设建设三个大型处理设备处理所有橱余垃圾。因为，虽然题目中有两种橱余处理设备，但是都建大型处理机需要三个，成本13500万，建两个大型的，其他建小型的处理机，处理完536吨橱余垃圾需要建设454个小型处理机，总成本达21712万，另一方面，南山区中任意两点的最远距离为15公里，最大运输成本为15/100*536*7.34*30=17704.08元，远小于上面建设成本差8212万元。假设3：建设橱余处理厂不考虑当地建设成本差异，所有的候选点都能够建处理厂。假设4：假设所选的路线交通畅通，无事故发生，不考虑运输车辆（拖车）空车的运行成本。假设5：对于第二个问题，为简化问题，我们类似地把众多的居民区归为数量合理的点，并和上面的主要道路一起构成另一张图。假设6：问题二中所建设的中转站最大转运量为Z。模型建立问题1：第一步：求处理厂位置与中转点垃圾运向问题。目标函数：运费最小242411minijiijjjiKDproUW约束条件：1、处理厂的处理量不超过200241200iijjiproUWj=1,2…242、保证每个点的垃圾只运到一个处理厂2411ijjUi=1,2,3…243、保证只建三个大型处理厂2413jjWi=1,2,3…24符号说明：ripo:第i个点需要转运的橱余垃圾量。前11个为具体数值，后13个为0。iW：第i个点是否建设处理厂，取值为0或1，取1代表建设处理厂，取0代表不建设处理厂。ijU：取值为0或1，取1代表从第i点运橱余垃圾到第j点，取0则不运。ijD：从第i点到第j点的最短路程。K：单位运输成本。（拖头）第二步：清运路线在第一步求得的处理站与垃圾运向的基础上，运用Dijkstra算法求出最短线作为清运路线。问题2：第一步：中转站的个数与位置及小区垃圾去向目标函数：运费与建设成本和最小111minnnnijiijjjjijKDproUWCW约束条件：1、中转站的中转量不超过Z241iijjiproUZWj=1,2…n2、保证每个点的垃圾只运到一个中转站11nijjUi=1,2,3…n符号说明：ripo:第i个点需要转运的垃圾量。前m个为具体数值，后n-m个为0。iW：第i个点是否建设中转站，取值为0或1，取1代表建设中转站，取0代表不建设中转站。ijU：取值为0或1，取1代表从第i点运垃圾到第j点，取0则不运。ijD：从i点到j点的最短路程。K：单位运输成本。（收集车辆）第二步：求橱余处理厂位置与中转点垃圾运向问题。由第一步，把问题二转化为问题一。接下求解同问题一。模型求解问题一：第一步：画简化图，求邻接矩阵。简化深圳市南山区垃圾转运站分布图得到加权图：G（V,L）。其中,vi为简化后的第i个点,i=1,2,3…24,前11个为中转站点,用标出。由图边权可求得邻接矩阵：0(),,,,,ijijijlijijvvijvv边权(邻接),(不邻接)：（取1000，由于数据量大，这里不具体写出）下面是G(V,L)：V3V1V2V4V5V2V6V7V8V9V10V13V14V15V16V17V12V11V18V19V20V21V22V23V245V25V23.5V25V24V24V22V21V24V22V22V22V22.5V22.5V21V22.52.5V25V22.5V24.5V21.5V21.5V21.5V21.51.5V24.5V23.5V24.5V23V23V23V23每1.5单位代表1km垃圾中转站清运路线1.5V22V21.5V22V2第二步：求ijD由邻接矩阵ijl，通过Floyd算法求出任意点的最短路程，使用VisualC++编程求解，程序：（见附录）第三步：求解线性规划模型：使用Lingo软件编程求解。程序和结果：（见附录）第四步：求中转站到已定的处理厂的最短路线。根据第三步求解得到的处理厂位置和垃圾转运去向，使用Dijkstra算法，求出最短路线，从而得到垃圾的清运路线方案。问题二：由于数据不足，居民区的资料处理花费太多精力和时间而我们的时间和人手不足，加上华师校园网在建模期间网速太慢，难以查找需要的资料，我们不具体求解第二题。结果表示ijD的值如下：Lingo求出的规划模型结果为：2v、6v、7v处建立大型垃圾处理厂。1v、2v、4v三处的中转站的橱余垃圾运向2v处理。5v、6v、9v、10v四处的中转站的橱余垃圾运向6v处理。3v、7v、8v、11v四处的中转站的橱余垃圾运向7v处理。由Dijkstra算法得到的清运路线如下：12vv、4132vvv5166vvv、917166vvvv、1019186vvvv37vv、8217vvv、1124208217vvvvvv结果分析模型与求解都依据简化了的图论图，我们的简化过程尽量依据实际给出的南山区垃圾转运站分布图，并对中转站点作出了合理的简化。在此基础上，根据Floyd算法运用VC++编程求出的两点间最短距离ijD比较精准，再根据规划模型利用lingo编程求出结果，软件运行300多万次，显示结果为局部最优，基本可信。最后利用Dijkstra算法求出的清运路线方案基本可信。但是由于图形是简化的，与实际上确实存在不可忽略的误差，而且直接考虑建设3个大型橱余处理设备虽然符合实际情况，但也有可能出现错误，并不一定就是最优解。模型评价本文给出的模型实用性强，可以很好的符合本题目的条件，在进行了合理的假设后，计算比较简单，求解出的结果具有实际参考价值。但是因为一开始假定了建设3个大型处理厂，并不一定十分合理，可能与最优解存在误差，并且推广性不强。模型修正这次建模的模型由于在假设的时候将橱余设备的选择限制为大型设备，结果必定与最优解有一定的误差，而且难推广，我们经过对原有模型的理解和思考，得到下面的修正模型：通过加入三个变量，分别表示使用大型设备，小型设备和大小并用三个情况。符号解释：jX：取值0或1，只使用大型设备则取1，否则0；jY：取值0或1，只使用小型设备则取1，否则0；jZ：取值0或1，同时使用大型和小型设备则取1，否则0；A：大型处理设备的处理能力；a：大型处理设备的建设费用；a：大型处理设备的运行成本；B：小型处理设备的处理能力；b：小型处理设备的建设费用；b：小型处理设备的运行成本。其他符号同原模型。目标函数：运费最小242411241min/1/1///1//ijiijjjijjjjjjjjjjjjjjKDproUWMAaMaXMBbMbYMAaMMAABbMAAaZMMAAb