垃圾处理场分布及转运的数学建模

《垃圾处理场分布及转运的数学建模》由会员分享，可在线阅读，更多相关《垃圾处理场分布及转运的数学建模（16页珍藏版）》请在装配图网上搜索。

1、菏泽学院数学建模参赛作品作品名称：深圳市南山区垃圾运输问题研究参赛时间：2011年5月指导老师：李忠广所选题目：A题参赛队员：崔玉良 09自动化 于娜娜 09自动化赵田 09自动化目录一、 问题的提出4（1） 问题起源4（2） 问题设计4二、 问题分析4（1） 方案分析4（2） 目标函数5（3） 优化目标5三、 模型假设5(1) 人口假设5(2) 运输车假设5(3) 环境假设6四、 符号说明6（1） 模型一的符号说明6（2）模型二的符号说明7五、模型的建立及求解7(1)模型一的建立及求解8（3） 模型二的建立及求解11六、建议与改进21(1)建议21(2)改进21七、参考文献22摘要：本文通过

2、类比系统的研究方法，运用定量的数学计算，可从理论上得出垃圾转运站的最佳选址方案。考虑到转运站垃圾收集与转运的功能，需要建立不同的理想模型来研究。文章以深圳市南山区垃圾转运站选址为实例，初步讨论了理论选址坐标。通过对问题的分析和合理的假设，我们建立了以运输费用等作为多目标，以运输车载重量的大小、当天必须将所有垃圾清理完等为约束条件，以运输车是否从一个小区清运站到达另一个小区清运站为决策变量，建立了使得运输费用最小等的多目标的规划模型。借助于MTLAB、软件与EXCEL的数据交换、以及物流选址的方法得到全局最优解，进而得出垃圾转运站的理论地址。关键字：非线性规划 最短路径 最大利益 物流选址Abs

3、tract：In this article we use the analogy system research methods and quantitative calculation, we can obtain the best location scheme of refuse transfer station in theoretically. Considering the transfer function of garbage collection and transport, we should set up different ideal model to research

4、 necessarily. In this article we take the refusing transfer station location of nanshan district in Shenzhen as an example and discuss the theoretical location coordinates preliminary.By analyzing the problems and making reasonable assumptions, we established the multi-objective programming model: t

5、aking the transportation cost as a target, using the load capacity of the truck and all the rubbish must be cleaned up as constraint conditions, whether the trucks go from the district transporting station to another as decision variable ,we established the multi-objective programming model which ma

6、de the minimum transport costs. By the help of MATLAB, LINGO software and EXCEL data exchanges, and logistics location methods we get the global optimal solution, and get the theory address of refuse transfer station.Key words: nonlinear programming shortest path maximum benefits logistics location一

7、、问题提出（1）问题起源随着我国城市生活质量提高及垃圾处理事业的发展，垃圾转运系统的转运效率和投资效益在城市环卫建设中起着越来越重要的作用。因此，转运系统的合理规划及优化设计，也随之成为城市环卫规划中的一个重要课题。(2)问题设计在转运系统的一个层次内进行布局规划，最基本的要求是节省运输费用，即应以城市总体规划和环境卫生专业规划为基础，进行优化设计。垃圾的分类处理与回收再利用是现今社会比较热门的话题，所以本文以垃圾处理设备的分布以及最大效益为目标进行设计。二、问题分析 （1）方案分析对于垃圾处理设备的分布，应根据垃圾量的分布情况、人口密度及垃圾处理厂处理能力的合理确定。（2）目标函数我们以多目

8、标函数作为方案设计，利用非线性回归的函数计算方法，求解出最佳方案。（3）优化目标转运系统优化目标为：垃圾收运总体费用最低，运输车行程最短、将当天的垃圾全部清扫完毕、地址设置科学、运输车载重合理、垃圾处理厂尽量远离居民区、交通便利，易安排运线路、有可靠的电力供应、供水水源及污水放系统、转运站内作业方式与设备选择合理。三、模型假设（1）基础假设1. 假设南山区人口在此期间，人口固定不变，没有大的人口流动情况，每个人每天产生垃圾量固定；2.转运站周围方圆5公里之内的小区清运站的垃圾都运往此转运站；3. 一天清运站从小区只收一次垃圾（晚上或下午）；4. 拖车将垃圾一起送往大型设备处和小型设备处再前往坟

9、埋场和焚烧场；（2）运输车假设1 假设运输车在每次清运垃圾时，运输车全被装满。2. 运输车在行驶过程中出现的堵车、抛锚等耽误的时间忽略不计；3. 不允许运输车有超载现象；4. 假设运输车在运输过程中保持匀速。5. 假设运输车到达垃圾处理站后，停车，卸车与离开启动时之间的时间忽略不计。（3）环境假设1.假设各小区转运站每天的垃圾产生量是固定不变的； 2.每个小区清运站位置合理，保证运输车行驶顺畅；四、符号说明（1）模型一的符号假设-第个小区清运站向第个小区清运站运输的垃圾量；-运输车是否从第个小区清运站向第个小区清运站运输的0-1变量；-第个小区清运站和第个小区清运站之间的距离； -垃圾运输车的

10、单位量货物每公里的运输费用；-垃圾运输车每公里的空载费用；-每天每个清运点的垃圾产生量；Gi(x,y) -垃圾收集点直角坐标位置；pi-收集点的垃圾收集量；fi -各收集点的单位量垃圾的收集运输成本费；C(X,Y) -垃圾处理设备点待选的的位置。0、n+1-均标志垃圾转运站；（2）模型二的符号假设n -小区清运站需求数目N -小区清运站限制数目m -垃圾转运站数目 -第i个小区清运站可回收垃圾量 -小区清运站可装载垃圾车辆上限 -转运站可卸载垃圾车辆上限U -汽车的载重量（单位：吨）K -运输车的总趟数 -第i个小区清运站到第j个转运站的距离（单位：公里）-小区清运到 转运站的路程向量 -第个

11、小区清运站向到个转运站的流量（单位：车）-小区清运站到转运站的流量向量i(x),i(y) -垃圾站点 i 的横纵坐标-两垃圾集中点之间的路程，本题中为网格距离 -0-1 变量，取1 表示第趟从站点i直接到达站点 k j，取 0 表示其他情况五、模型建立及求解（1）模型一的建立及求解垃圾转运系统其实是一个大型的物流系统。普通物流系统，货物流通方向是从集中到分散，而垃圾转运系统则是一个倒向的物流系统。垃圾收集转运站终端处理图1 垃圾转运系统流程简图 图2 垃圾处理系统框图垃圾处理中心小区1垃圾转运站站小区2小区n现代物流网络中的物流节点特别是物流中心对优化整个物流网络起着重要作用，是整个物流网络的

12、灵魂所在，这一点也同样类似于垃圾转运系统中的中转站。目前国内研究垃圾转运系统方法极少，但研究物流系统的方法却很多，而且很成熟，因此物流系统的研究方法非常值得借鉴。物流中心选址方法很多，大致可分为定性和定量两种。本文重点讨论定量方法。建立直角坐标系，图中黑色圆圈Gi(xi,yi)( i=1,2 ,3 ,4 ,5 38)表示38个垃圾收集点直角坐标位置，pi（i=1,2,3,4,538)表示这38个收集点的垃圾收集量，fi表示各收集点的单位量垃圾的收集运输成本费，红色圆圈C(X,Y)表示垃圾处理设备点待选的的位置。垃圾处理设备的选址问题可以转化为数学建模求解多组坐标值Xc和Yc，运用数学中的重心法

13、：； 求解xc和yc，可得；一般地，在同一转运服务区内，单位量垃圾的收集运输成本视为相等的。因此上式可化简为：； 另外，当收集点较多时，宜需用偏导法求解。根据最小二乘法数学理论，可建立如下数学模型公式: 其中c表示总收集费用，Mi 表示各收集点垃圾收集量。在比例系数都为1的情况下，运用微积分中求解二元函数极值的解法求解:联立此两个方程，得到和。如果考虑垃圾从中转站运输到垃圾处理场的费用，对此问题重新建模，得 式中第一部分为从小区向转运站的垃圾收集费用，第二部分为转运站到垃圾处理设备的运输费用。K1表示单位量垃圾的收集成本；K2表示单位量垃圾的运输成本；理论上这种方法能精确地求出多组X,Y值，但

14、存在一些问题，当n很大时，根本无法求解。但联系实际，在解决垃圾处理设备规划布局问题中，在求解上式时，只需考虑相对各收集点的最佳转运站选址即可。表1 收运系统坐标图收集点(Gi)G1G2G3G4G38坐标(xi,yi)1,12,18,29，336，31垃圾量(Pi)2025202510对以上38个收集点，计算出垃圾处理设备最佳选址坐标可为：；因此，垃圾处理设备的理论坐标为C（Xc，Yc）。（2）模型二的建立及求解分析：由小区到垃圾转运站目标期望总运量最小，同时出动最少的汽车，从而使运输成本最小，由此很容易想到建立一个双目标规划模型。具体过程如下：总运量即垃圾运输量乘以运输距离，要使得总运量最小，

15、则最小，亦即最小，这就是双目标规划的第一个目标函数： -（1）要使得汽车数量最少，则第二个目标函数为： -（2）对于目标一应用线性规划模型，在满足一定约束的条件下以总运量最小来优化各条线路上的流量分配，对于目标二按照定线定车的原则安排车辆，运用动态分配的方法及时作出微调，通过计算机模拟给出合理的车辆安排。线性规划阶段目标函数及约束条件：其中，由以下不等式描述：以上的条件a）是各转运站的垃圾量要求；b）和c）是各转运站的品位限制；d）和e）是各小区垃圾总量限制；f）和g）是各小区及转运站工作量的上限约束。对于线性规划结果的分析：1、 小区垃圾清运点的选择模型中假设初始状态为各小区都可设立清运点。

16、线性规划得到的结果是总运量值及各清运点与转运站间的流量。易知，小区清运点对于整体目标实现的权重是随着该小区垃圾产量的增大而增大的。选择标准：小区垃圾出产量选择方法：如果垃圾出产量不为零的小区清运站需求数n少于等于限制数量N，我们就选择设立n个小区清运站；如果垃圾出产量不为零的小区清运站需求数n大于限制数量N，我们就选择垃圾出产量最大的N个清运站。2、 总运量的求解根据线性规划得出的目标函数的最优值是最小总运量即：。汽车调度阶段该阶段要解决的问题是：在已知垃圾出产量的前提下，优化汽车的分配，调用最少的汽车完成任务。解决途径如下：i 确定汽车下限和理论估计值 下限的确定设汽车数量的下限是，所有汽车

17、的平均满载时间为t。我们假设汽车的利用率达到最高即除去装卸时间，汽车均处于运输状态，这时对于运输事件整体，汽车的满载时间和空载时间相等，于是有方程：总运量就是在所有的汽车在满载时间内行驶通过的路程，于是有方程：由方程（1）和（2）联立，可得到的值。 汽车数量理论估计值的确定对于小区清运站i到转运站j的线路，我们可求出该线路上汽车的单循环时间，进而可求出一个班次内一辆汽车可以完成的循环次数，依据每条线路的流量，从而可求出一个班次内该线路上需要汽车的理论估计值。于是有一个班次内某线路上需要汽车的理论估计值为：总汽车数的理论估计值：综上，我们不难发现汽车的数量与总运量存在一定的正相关性，在此通过汽车

18、下限和理论估计值确定汽车数量。ii安排车辆表1：各小区间及小区与其垃圾送往转运站间的距离、小区垃圾产生量Distence/km01234nk01234 nkRubbish/t 表2：各运输路径所包含的小区清运站、运输量及所需时间路径包含的站点运输垃圾总量每条线路所走路程 123456789利用LINGO10编程，对运输车调度方案的模型进行求解,求得各小区清运站的清运方案如表所示，此时，求得将所有垃圾运回到垃圾转运站运输车所需费用为 元。2.垃圾转运站与处理中心模型 为了让问题更加清晰，不妨设所有运输车总共运送 K 趟垃圾，即把所有垃圾站点的垃圾运送完。 对本问题，最优的情况应该是，每趟运输的第

19、一个垃圾站点为离处理中心最远的垃圾站点，否则，必有运输完某站点的垃圾后再带着垃圾去运送离处理中心最远的垃圾站的垃圾，由于载重费用大于空载费用则必然导致总费用的增加。 在运送完离处理中心最远的垃圾站的垃圾后，如果能在垃圾运输车返回处理中心途中“顺带”把某些垃圾站点的垃圾运走，那必定是最优的运输线路。而那些“顺道”被清理的垃圾站的横、纵坐标一定要小于离处理中心最远的垃圾站的垃圾的横、纵坐标。 然而，有些点的横坐标和纵坐标的坐标值可能并不都比最远的站点的横坐标和纵坐标的坐标值要小。现分析在此种情况下垃圾运输车如何调度，设此两垃圾站点分别为 a 和 b（a 点离处理中心的距离比 b 点离处理中心的距离

20、大），坐标值分别表示为(a(x),a(y)和(b(x),b(y)，垃圾量分别为和，我们考虑两种情况：1) a 站点的垃圾和 b 站点的垃圾分开运输回处理中心，其总费用为 2) 先去 a 站点再去 b 站点运垃圾，然后返回处理中心，其总费用为比较得到：当的方案较优； 当的方案较优； 当的方案与情况 2）的方案所需费用一样。事实上，当的值很小时，我们便只需要考虑与 0 的比较，由于0ab构成一个三角形，则显然，于是在绝大数情况下 a站点的垃圾和 b 站点的垃圾分开运回处理中心是最优的方案。 由于在垃圾运输车调度的过程中符合以下三个原则： 1、总的最优化方案中的三个子方案必定达到最优； 2、无后向性

21、：前一个阶段的状态无法直接影响后一阶段未来的决策； 3、每个子问题具有重叠性。 故根据动态规划理论在垃圾运输车调度过程中达到全局最优解时，必定每个子问题，即每个局部都达到最优解。因此，可以用递归回溯算法或动态规划思路来解决此问题。由以上分析所得结论，可以对原一般模型增加如下约束： 1、每条运输线路必定是首先到达该线路中距原点最远的点： 约束条件为：即，如果第 条线路首先到达 点，则 点的横、纵坐标一定比这条线路中经过的其它节点的横、纵坐标大。 2、每条线路先到达的节点一定比后到达的节点的横、纵坐标大。 约束条件为：即，如果第条线路由节点直接到节点，那么，节点的横、纵坐标一定大于节点k i ij

22、的横、纵坐标。 因此在上述一般模型的基础上加上如下条件，问题得到简化：ii 模型的求解 根据以上的分析，知道动态规划算法或递归回溯算法都能对以上问题进行求解，但考虑到动态规划要划分阶段、状态和状态转移方程，过程比较复杂，现运用递归回溯算法搜索出最优解。其搜索的路径即为若干个包含原点的原图的哈密顿子图，且这些子图的顶点包含原图所有的顶点。 递归回溯算法搜索的原则如下： 1）当点b的x和y轴的坐标值都小于或等于a点的x和y轴的坐标值时， 先搜索a再搜索b； 2）当点b的x和y轴的坐标不都小于或等于a点的x和y轴的坐标值时， 如果很小，则把 a 和 b 分别在不同的哈密顿子图中，如果不可忽略时，根据

23、来考虑；3）每一次搜索从离原点最远的点开始 4）当一辆垃圾运输车达到最大载重时，返回原点。递归回溯算法流程：初始化，每个站点i配一个运输车，Di=xi+yi所有线路，站点处于未处理状态选择Dm=max Di,给Di选择合适的路过站点Dj (xjxm,yjym)， 并在Dj中选择离原点最远的点 Dm=max Dj是否还有Dm经过的点，则执行；否则结束得到每条保留路线进过的站点。六、建议与改进（1）建议本文以深圳市南山区垃圾处理布局为背景，结合计算机辅助工具对垃圾处理设备的布局以及清运路线最优化设计，这种模型对于现实的布局具有极高的参考价值。在本文合理的计算过程中，通过优化垃圾处理设备的合理布局，

24、既可以获得最大的经济效益，又可以得到最大的环境保护，对于城市的发展有极高的促进性。（2）改进 虽然本文对于垃圾处理设备的布局以及清运路线最优化，但是仍有很多不足的地方，比如在LINGO于EXCEL数据交换的时候，数据量庞大，不能有很好的软件支持；在数据计算过程中，数据不够精确；利用MATLAB进行线性拟合时，拟合程度不高。七、参考文献1薛定宇 陈阳泉，高等应用数学问题的MATLAB求解，北京，清华大学出版社，北京，2008，10，第二版。2孙利娟 王良俊等，改进的蚁群算法及其在TSP问题中的应用研究，通信学报，第25卷，第10期。3刘育兴 钟剑，垃圾运输问题的模型及其求解，赣南师范学院学报，2006年，第三期。 4 陈学武. 可持续发展的城市交通系统模式研究. 南京: 东南大学交通学院,2002.5 梁小民. 西方经济学导论. 北京: 北京大学出版社, 19936郭耀煌等编著. 运筹学与工程系统分析M . 北京: 中国建筑工业出版社, 1986.7 肖位枢主编. 图论及其算法M . 北京: 航空工业出版社, 1993.8 张琦. 动态OD 估计的交通检测器优化布置研究C . 硕士毕业论文,吉林大学,2005.9 盛骤, 谢式千, 潘承毅编. 概率论与数理统计M . 北京: 高等教育出版社, 2002.