深圳市南山区垃圾分类处理与清运模型.doc

深圳市南山区垃圾分类处理与清运模型一摘要本文研究了深圳市南山区垃圾分类处理清运方案设计问题,运用最优化方法理论,将双目标问题简化为两个单目标问题去解决,从而使问题得到很好的解答。在求解过程中我们首先运用了模拟退火启发式算法、模拟退火算法，求解了转运垃圾站位置固定、橱余垃圾处理中心地理位置未知和转运站位置不定、橱余垃圾处理中心位置不定两种条件下的最优清运路径。结果得出了三个大型橱余垃圾处理厂的位置（坐标），它们的坐标分别为：A(22.5587,113.9507),B(22.5303,113.9263),C(22.6195,113.9691)。对于问题一我们将不同橱余垃圾处理中心的分布及数量这双目标规划，分开转化为求厨余垃圾处理中心的数量和橱余垃圾处理中心的位置分布这两个单目标的优化问题。对后一规划的求解我们采用了能解决多变量问题的模拟退火启发式算法，较好的解决了问题一。针对问题二，我们在问题一的基础上，假设每两个中转站之间的距离为5米，而后选用集合覆盖模型求出垃圾中转站的待选点，即用尽可能少的垃圾收集中转站去覆盖所有的垃圾收集站。因此，我们建立了以从现有的m座垃圾收集站的位置中选出可以覆盖m座垃圾收集站的最小数目的中转站选点为目标函数，并给出了约束条件，为了重新设计方案，我们首先参照垃圾收集密度以及当地人口密度，算出每个垃圾中转站的最优收集，求得可以覆盖m座垃圾收集站的最小数目的中转站的具体分布图，我们运用启发式算法进行集合覆盖模型优化来解决可以覆盖m座垃圾收集站的最小数目的中转站选。最后我们按照上述模型，结合坐标数据，找出了建设中转站的最佳位置（具体的位置见正文）。【关键词】最优路线 模拟退火算法 集合覆盖模型 启发式算法 垃圾分类一问题重述垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资源回收与再利用的城市绿色工程。在深圳，垃圾可分为四类：橱余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾，这种分类顾名思义不难理解。 在垃圾分类收集与处理中，不同类的垃圾有不同的处理方式，简述如下：橱余垃圾,可以使用脱水干燥处理装置，处理后的干物质运送饲料加工厂做原料。 可回收垃圾,将收集后分类再利用。 有害垃圾，运送到固废处理中心集中处理。 其他不可回收垃圾,将运送到填埋场或焚烧场处理。所有垃圾将从小区运送到附近的转运站，再运送到少数几个垃圾处理中心。显然，1）和2）两项中，经过处理，回收和利用，产生经济效益，而3）和4）只有消耗处理费用，不产生经济效益。（相关数据看表一、表二和表三）表一：大、小型厨余垃圾设备的相关数据设备类型处理能力投资额运行成本大型厨余设备200吨/日4500万元150元/吨小型厨余设备200-300公斤/日28万元200元/吨橱余垃圾处理后产物价格在1000-1500元/吨。表二：四类垃圾的平均比例橱余垃圾可回收垃圾有害垃圾不可回收垃圾4213表三：可回收垃圾的分类及相关数据可回收垃圾类别所占比例废品回收价格纸类55%1.5元/公斤塑料35%2.5元/公斤玻璃6%0.5元/公斤金属4%2.5元/公斤南山区的垃圾清运设备情况（主要是车辆数目和载重）。拖头（拖车）：只拖十吨的大型厢，只用于从转运站到垃圾中心，每次只拖一个大型“厢”， 平均吨公里耗油25L30L柴油/百公里。收集车辆： 只负责从小区的垃圾站到转运站运输。100辆2.5吨汽车，每车耗油20L35L 70#汽油/百公里。 司机月薪平均3500元。 本项研究课题旨在为深圳市的垃圾分类化进程作出贡献。为此请你们运用数学建模方法对深圳市南山区的分类化垃圾的实现做一些研究，具体的研究目标是：1） 假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计，同时在目前的运输装备条件下给出清运路线的具体方案。以期达到最佳经济效益和环保效果。2） 假设转运站允许重新设计，请为问题1）的目标重新设计。二问题分析(一)问题一的分析：对于问题一，我们首先考虑的是不可回收垃圾和有害垃圾的处理，由题目所给的条件可知，有害垃圾是直接运往固废处理中心处理的，其他不可回收垃圾则直接运往填埋场或焚烧场处理。由于焚烧场及填埋场和转运站的位置都是固定的，因此我们可以知道处理有害垃圾和其他不可回收垃圾的运输成本是相对固定的。要将运输成本降低到最小，我们可以以焚烧场和填埋场的中垂线为界，界线以西的转运站垃圾运往焚烧场，界线以东的转运站垃圾运往填埋场。而可回收垃圾虽然经过转运站，但是不需要设备来进行分类，且根据实际生活中可回收垃圾由相关回收公司上门收购。其次，我们考虑能产生经济效益的厨余垃圾的处理情况。对于大小型设备处理厂的数量，由于不同的设备厂的投资数额、处理能力、运转成本都有差异，利用这些差异粗略分析，可以得出各设备厂的最少数量。我们将目标函数设定为各垃圾转运站运往大、小厨余垃圾处理中心的运费最低，而忽略其运输的趟数或是出动的车辆。然后对其分布我们采用模拟退火启发式算法进行模拟分析，进行多变量下的最优化运输路线求解，给出一个最优分布方案，最后将求解结果还原为车辆运输方案。所以对于问题一，我们主要考虑的是厨余垃圾的处理情况。(二)问题二的分析：对于问题二，我们借鉴了问题一模型的部分结论进行推广，在转运站的分布可变条件下我们根据各社区（街道、村庄）位置的固定性来搜索最佳的转运站位置，由于垃圾转运站数量和选址的不确定性，使得整个问题的复杂度上升。为此，我们在处理整个问题之前，先将垃圾转运站的数量和位置确定下来。我们使用matlab将汇总后的居民片区在图上描出来，形成一个点集，再在点集上套以横纵距离相等的方格，用方格将这些点大致分为了九个大的片区。然后将每一个大片区的情况汇总，主要是每个片区的总人数，根据总人数决定在此片区内部设定的垃圾转运站数目。在每一个大的片区内，根据片区人数决定建立的转运站的数量。出于环保要求，离散的那些居民片区也必须解决垃圾处理的问题，查得平均每人每日产生垃圾1，也就是说规模超过10000人的片区每日会产生接近10吨的垃圾，因此在规模超过10000的居民片区单独建立一个垃圾转运站。剩余的离散居民片区，由于人数不多，不适合建立新的垃圾转运站，那么处理垃圾的办法就是就近选择已经选好的转运站，将产生的垃圾运往转运站处理。转运站确定以后，接下来该决策厨余垃圾处理厂的建立与选址。同第一问一样，因为小型的厨余垃圾处理厂的垃圾处理量过小，没有实际应用价值，因此也不考虑。一个大型厨余垃圾处理中心能处理200吨的垃圾，且建立成本高，因此同样选择建立三个大型厨余垃圾处理中心。三模型假设(1) 各社区人口数目相对固定，市民每天产生的垃圾量是个定值；(2) 各社区每天垃圾的产生量和社区的人数成正比；(3) 垃圾转运站及垃圾处理厂（包括大小设备厂）每天仅收一次垃圾（早上或晚上）；(4) 各垃圾转运站的垃圾将在当天清运完毕，不能积累；(5) 各垃圾转运站的垃圾转运量以70吨为限，不得超出此最大界限；(6) 所有运输车辆不得超载；(7) 每个转运站与各个小区之间，各个转运站与处理中心（焚烧厂、填埋场、大小设备处理厂）之间均有公路直线相通；(8) 由于车辆有限，各转运站的垃圾只送往一个处理中心（焚烧厂、填埋场、大小设备处理厂）；(9) 所有运输车均从转运站出发前往小区或者处理中心，最后再回到转运站；(10)可回收垃圾在垃圾中转站被直接回收，以后不再处理考虑；(11)有害垃圾及其他不可回收垃圾处理方式为焚烧、填埋都可；(12)题目所给数据及所指示网站数据真实可靠；(13)不考虑居民对垃圾中转站的选址的异议。四符号说明: 目标函数（是投资成本最小）。: 大型厨余垃圾处理设备数。: 小型厨余垃圾处理设备数。: 目标函数（是转运站到处理场的总运费最小）。: =1、2、3 第一/二/三个大型厨余垃圾处理厂的纬度值。: =1、2、3 第一/二/三个大型厨余垃圾处理厂的经度值。: 0,1变量设定为由各转运站运往第一个大型厨余垃圾处理厂,其中1表示运往第一个大型厨余垃圾处理厂，0表示不运往。: 各转运站到第一个大型厨余垃圾处理厂的距离。: 各转运站到第二个大型厨余垃圾处理厂的距离。: 各转运站到第三个大型厨余垃圾处理厂的距离。: 各个转运站厨余垃圾运往处理中心单位距离（）的运输费用。: 37个中转站的纬度。: 37个中转站的经度。: 转运站变动后的目标函数。: 转运站变动各转运站的纬度矩阵。: 转运站变动各转运站的经度矩阵。: 转运站变动各转运站距第一个大型厨余垃圾处理厂的距离。: 转运站变动各转运站距第二个大型厨余垃圾处理厂的距离。: 转运站变动各转运站距第三个大型厨余垃圾处理厂的距离。: 转运站位置变动后各转运站垃圾容量。: 各小区的人口数量。: 人均垃圾产量。五模型的建立和求解5.1.1 问题一模型的建立 其他垃圾清运方案研究由问题一的分析我们可以得到首先处理的是各个转运站的需填埋或者焚烧的垃圾，由于运费和转运站与填埋场或者焚烧厂的距离直接相关，我们可以以焚烧厂和填埋场的中垂线为界，界线以西的转运站垃圾运往焚烧厂，以东垃圾运往填埋场。通过查阅Google地图我们得到了各个转运站和南山垃圾焚烧厂和罗湖区清水河垃圾填埋场的经纬度，统计后汇总到表四（具体的数据见附录二）。表四：各个转运站和南山垃圾焚烧厂和罗湖区清水河垃圾填埋场的经纬度表序号转运站站名或填埋场焚烧厂纬度经度1九街站22.5399113.93782玉泉站22.5494113.92723动物园站22.5587113.96124平山村站22.5889113.95655牛城村站22.6163113.921734长源村站22.5990114.004235华侨城战22.5423113.990636疏港小区站22.4891113.890437西丽路站22.5750113.944138塘朗站22.5948113.9914运用matlab将各个垃圾转运站的坐标、焚烧厂和填埋场连线及其中垂线绘制成图，如图一（见下图）。图一：垃圾转运站的坐标、焚烧厂和填埋场连线及其中垂线图 厨余垃圾的清运方案探讨 下面讨论大小厨余垃圾处理厂数量和分布问题：1)大、小厨余垃圾处理厂数量的探讨由于大小厨余垃圾处理厂的投资成本、处理能力各不相同，我们对各处理设备的数量进行假设，将投资金额作为目标函数，显然我们希望目标函数尽可能的小，于是有方程约束条件：a)所建处理厂能够处理所有的厨余垃圾：b)厨余垃圾处理厂的数量非负：c) 处理厂数量必为整数：d)小型厨余设备的处理能力在200公斤/日-300公斤/日：以上几个方程构成了整数规划问题 (1) (2) (3) (4) (5)求解可得到最佳分配是；。我们将这三个大型厨余垃圾处理厂分别叫做第一厨余垃圾处理厂，第二厨余垃圾处理厂和第三厨余垃圾处理厂。2)大、小厨余垃圾处理厂分布方案厨余垃圾处理厂的分布关系到各转运站运输厨余垃圾的费用，而费用又与各转运站和厨余垃圾处理厂的距离直接相关，因此我们可以建立以下目标函数： (6)约束条件：a)是一个0-1变量，表示了是否从转运站运垃圾到大型厨余垃圾处理厂，1表示运往，0则不运送：=0或1 (7)b)各个转运站到厨余垃圾处理中心的距离 (8) (9) (10)5.1.2 问题一模型的求解需运往垃圾填埋场和焚烧厂的清运方案从图一我们可以看出，中垂线（red line）上方的垃圾转运站（共计六个），这六个点对应的垃圾转运站是：长源公厕垃圾站、华侨城公厕垃圾站、福光公厕垃圾站、塘郎公测垃圾站、麻磡公厕垃圾站、大石勘公厕垃圾站。 大、小型厨余垃圾处理厂数量的确定由于所确立的整数规划比较简单，我们作如下几次运算便能得出优解：1.=0, =1787 =50036；2.=1, =1120 =35860；3.=2, =454 =21712；4.=3, =0 =13500；5.=4, =0 =18000；6. 由上面的运算可以得出以下结论：当时，函数是减函数，所以所建的处理中心的厨余垃圾设备的投资额是逐渐减少的；当时，函数是增函数，所以所建的处理中心的厨余垃圾设备的投资额是逐渐增加的。因此我们得出最优解为：=3, =0。 大、小型厨余垃圾处理厂数量的分布由目标函数可以看出，这是个无约束多目标非线性0-1变量优化，据此我们运用了模拟退火启发式算法进行模型来求解，求解过程用流程图表示如图二（见下图）。开始初始可行解（x1，y1），（x2，y2），（x3，y3）输出（xfinal1，yfinal1），（xfinal2，yfinal2)，（xfinal3，yfinal3）,kiF减少（x1，y1）沿向量（0，y1），（x2，y2）沿向量(0，y2)，（x3，y3）沿向量（0，y3）移动（x1，y1）沿向量（0，y1），（x2，y2）沿向量(0，y2)，（x3，y3）沿向量（0，y3）移动F减少图二：模拟退火启发式算法流程图根据上图流程我们编写matlab程序，对目标函数进行求解。输入1：（22.5413, 113.9172），（22.5372，113.9272），（22.619,113.9169）输出1：x1min =22.5613,y1min =113.9472 ; x2min =22.5177,y2min =113.9464;X3min =22.5194,y3min =113.9254 Ki 1i38 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1fymin =42.4696输入2：（22.5436, 113.9353），（22.5329, 113.9356）,(22.6329,113.9320)输出2：x1min =22.5636,y1min =113.9453;x2min =22.5129,y2min =113.9456;x1min =22.5263,y1min =113.9402 Ki 1i38 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 20 0 0 0 1fymin =42.7462输入3：（22.5587, 113.9507），（22.5303, 113.9263）,(22.6237,113.9360)输出3：x1min =22.5687,y1min =113.9507;x2min =22.5203,y2min =113.9263;x1min =22.5142,y1min =113.9081Ki 1i381 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1fymin =31.0534由输出结果我们可以得出最优解收敛于三点：A(22.5587,113.9507),B(22.5303, 113.9263),C(22.6195,113.9691)；这三点可以分别看作是第一、二和三厨余垃圾处理厂的经纬度地址。输出0-1矩阵K，则是各转运站拖车车辆清运情况，结合的结果再根据拖车的运送规格，最后我们得到运送方案如表五所示。表五：在转运站地理位置固定的情况下垃圾分类处理清运的最佳方案转运站名称是否运往第一厨余垃圾站运输量是否运往第二橱余垃圾站运输量是否运往第三橱余垃圾站运输量大石勘公厕垃圾站1120018福光公厕垃圾站140000塘郎公测垃圾站140000长源公厕垃圾站120000动物园公厕垃圾站1800116/3平山村公厕垃圾站11000120/3新围公厕垃圾站1800116/3官龙村公厕垃圾站160014牛城村公厕垃圾站120000白芒公厕垃圾站13.20000阳光公厕垃圾站140018/3麻磡公厕垃圾站140018/3西丽路公厕垃圾站160014光前公厕垃圾站1800122/3龙井公厕垃圾站001614同乐村垃圾站120000松坪山（二）公厕垃圾站180000松坪山公厕垃圾站11000120/3前海公园公厕垃圾站0016.400月亮湾大道00116132/3九街公厕垃圾站0018116/3大新小学垃圾站00112110玉泉公厕垃圾站0010150/3沙河市场垃圾站1120018华侨城公厕垃圾站1280000深圳大学垃圾站001614白石洲南公厕垃圾站1120018涌下村001800南山市场公测垃圾站0011000北头公厕垃圾站001614南园公厕垃圾站001614南山村公厕垃圾站00110120/3南光公厕垃圾站001614科技园公厕垃圾站001800花果路公厕垃圾站0011218望海路垃圾站0011218疏港小区垃圾站00116132/3大冲站11400005.2.1 问题二模型的建立中转站的选址目标主要以垃圾中转站建设和运行成本最低。它是一个中转站选址是否合理的最重要的衡量标准，参照垃圾收集密度以及当地人口密度，算出每个垃圾中转站的最优收集半径为5米，而后选用集合覆盖模型求出垃圾中转站的待选点，即用尽可能少的垃圾收集中转站去覆盖所有的垃圾收集站。 目标函数的建立在考虑厨余垃圾量与路线问题及人口密集程度的前提下，厨余处理厂的选址点。我们将在38个垃圾中转站中选出个垃圾中转站做为厨余垃圾处理场，则其中的做为厨余垃圾处理厂的中转站的选取是由最优收集半径的大小而定的。根据个厨余垃圾处理厂的选点，建立如下最优化模型: (11) 约束条件的确立目标函数为从现有座垃圾中转站的位置中优选出可以覆盖38座中转站的最小数目的中转站选点。（1）对于每一座垃圾中转站，其厨余垃圾均被清运，即： (12)（2）厨余垃圾处理厂能处理垃圾的能力要满足一定的要求： (13)（3）垃圾中转站和厨余垃圾处理厂的垃圾量均非负，即满足不等式： (14)（4）垃圾中转站是否建立在第座厨余垃圾处理厂附近的决策变量：， （5）第座垃圾中转站是否有垃圾收运到第座厨余处理厂的决策变量： ， 单目标规划模型的建立目标函数 (15)约束条件： (16) (17) (18) (19) (20)：表示筛选出的第k座垃圾中转站所覆盖的垃圾集合站的集合；： 表示第i座垃圾收集站是否被第k座垃圾中转站覆盖；：表示可以覆盖第i座垃圾收集站的中转站的集合；： 表示筛选出的第k座垃圾中转站所覆盖的垃圾收集站的集合。5.2.2 问题二模型的求解利用matlab的绘图功能，我们将这些社区的经度为横坐标，纬度为纵坐标绘制点集，如图三所示。目标函数为从现有的m座垃圾收集站的位置中选出可以覆盖m座垃圾收集站的最小数目的中转站选点，对待这个问题，我们可以运用启发式算法进行集合覆盖模型优化，步骤如下：第一步，确定垃圾收集站的相对位置和距离；第二步，根据垃圾中转站的最优化服务半径，找出每一个可以作为中转站的收集点以提供垃圾收集服务的服务范围内的收集点集合A(k),k=1,2,3,m,即与该收集点距离小于或等于垃圾最优化收集半径的所有收集点的集合；第三步,找到可以给每一个收集点提供服务的可作为中转站的收集点的集合B(i) ,i=1,2,m,一般来说，A(k)和B(i)这两个集合是一致的，但是考虑到其他的一些限制条件，就可能出现差异；第四步，在B(i)中，将其中的子集省去，以简化问题，例如B(1)=(1,2,3,4), B(2)=(1,2,3), B(3)=(1,2,3,4,5),则B(1)和B(2)是B(3)的一个子集，可以省去以简化问题；第五步，确定合适的组合解，在问题被简化后，在有限的候选点上选择一个组合解是可行的。为满足模型目标即以最小数量的设施点覆盖所有的需求点，应尽可能少的确定待选点，从组合解中剔除可以被合并的待选点。按照上述模型计算，结合坐标数据，找出最佳建设位置，具体位置见图四。图四：深圳市南山区垃圾转运站分布图注：红点为重置后的转运站的位置六、模型的评价与改进优点：该模型从整体上解决了深圳市南山区的垃圾处理问题，包括：各个转运站是运往填埋场还是焚烧厂的选择，厨余垃圾处理厂的个数和选址问题，每个转运站运往第一个厨余垃圾处理场和第二厨余垃圾处理场还是第三厨余垃圾处理场，模型在选择厨余垃圾处理厂的位置，根据模拟退火算法的思想，自行设计了求解三个变量对目标函数影响的算法，在全局寻找使得目标函数最小的可行解，具有创意，是本文的一大亮点。在对模型的处理当中,合理地假设了一些其他次要因素,使模型变得更加清晰明了。缺点：为了减少运算量，使算法简单化，在三个变量改变过程中，采取了固定步长的方法，并且变化方向相同或相反。这样可能会使目标函数落入局部最优解，需要代入多个初始可行解来比较判断是否是全局最优。在将来的发展中，可以寻找一个能够减小三个变量之间的变化的相关性的步长，或者是两个变量的步长分别取值，以扩大在全局搜索最优的范围。我们在处理模型时是把该模型每两个垃圾转运站之间的距离当成单纯的直线来计算的，但是实际上两个垃圾转运站之间的距离可能是折线或者曲线。建立模型时，我们没有考虑每个站点之间垃圾的变化情况，认为垃圾量是不变的，但是实际上垃圾量可能会因为人为的因素而增加或者减少。该模型的处理方法忽视了人口随机分布的现实特征，弱化了人口流动的内在特点，降低了模型求解的准确性。模型的推广与应用本文给出的模型实用性强，可以很好地符合本题目要求，在进行了合理的假设后，计算比较简单，求解出的结果具有实际参考价值。因此此模型不仅仅可以用于深圳市南山区的垃圾处理与回收，而且还是用于其他地方，如省、市、区得垃圾清运处理与回收。另外，在本题中应用了集合覆盖模型，并且还运用了模拟启发式算法来对城市垃圾的分类处理以及清运方案做了设计，这些模型和算法同时可以推广到求解城市公交车网络的行驶的最小路径问题，还有物流选址问题的规划等。这些模型和算法在现实中得到极大的广泛应用和推广。应用这个方案，可达到节省运输垃圾的路程最短还有运费最小的目的，因此此方案存在一定的可行性。参考文献1深圳市南山区垃圾分类处理清运方案探讨,陈潮、后磊、胡泽辉，/view/0652cc1b227916888486d78b.html，2011-7-27。2全国大学生数学建模夏令营/student.php,2011-7-26。3数学建模垃圾分类处理与清运方案设计，/view/d440550d7cd184254b35355f.html，2011-7-27。4新型垃圾转运站垃圾转运量等情况统计表/view/23a48f3410661ed9ad51f388.html，2011-7-26。5董臻圃，数学建模方法与实践M，北京：国防工业出版社，2006年。6韩中