深圳市南山区垃圾分类与清运方案上海海事参赛论.doc

《深圳市南山区垃圾分类与清运方案上海海事参赛论.doc》由会员分享，可在线阅读，更多相关《深圳市南山区垃圾分类与清运方案上海海事参赛论.doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、深圳市南山区垃圾运输问题研究摘 要就生活中垃圾运输的问题的调度方案予以研究。问题一清运路线中，垃圾清运路线优化垃圾物流具有“产生源高度分散、处置高度集中、产生量和品质随季节变化”的特点通过对问题的分析和合理的假设，建立了单目标（先当作单目标运输费用,环保因素作为次要条件考虑）的非线性规划的数学模型。软件可以得到全局最优解，对此类问题的求解提供了一种较优的方案。由于题中的问题包含着垃圾量和运输费用的累积计算问题，因此，我们以运输车所花费用最少为目标函数，以运输车载重量的大小、当天必须将所有垃圾清理完等为约束条件，以运输车是否从一个小区清运站到达另一个小区清运站为决策变量，建立了使得运输费用最小的

2、单目标的非线性规划模型。需要解决的具体问题如下：1） 假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计，同时在目前的运输装备条件下给出清运路线的具体方案.以期达到最佳经济效益和环保效果。2） 假设转运站允许重新设计，请为问题1）的目标重新设计。关键字：运输车调度 非线性规划 最大利益一问题的分析：近年来，随着经济的快速发展，城市人口的迅猛增加以及人们生活水平的不断提高, 城市生活垃圾问题成为日渐突出的问题，垃圾的产生量大于清运量，无害化处理量更小，垃圾污染事故频出，严重破坏了城市生态环境系统的平衡。城市生活垃圾已成为制约城市社会经济发展的主要因素之一。城市生活垃圾

3、的运输环节是垃圾处理系统中的重要组成部分，在垃圾处理成本中，收集与运输成本占相当大的比例，如W ilson 指出美国每年的垃圾处理费用总额约在200亿美元左右, 其中收集运输费用已超过100亿美元 1 .因而有必要对垃圾车的收运路线进行合理优化, 以降低收运系统成本, 减少环境污染与社会影响.因此, 如何使城市生活垃圾的收运系统快速化、高效化、合理化、经济化是近年来被广泛关注和研究的一个课题。1.1 问题所要考虑的主要因素 在研究垃圾分类处理与清运方案和相关算法时，我们有必要考虑问题的主要因素，在保证垃圾能正常合理的转运清运处理下，尽量的节省能源，即里程最短、费用最少、时间尽量少、车队规模尽量

4、小、车辆利用率高等。1.2 问题的转化与数学描述问题的关键是在一定条件下求出任意两站点之间的投资线路.如果将所有站点看作结点，站点之间用同一趟车转运垃圾（当考虑站点间运送时间时）可以到达看作一条有向边，所花费的时间看作边权，则某一时刻的的公共交通状态便形成了一个网络。因为站点与站点之间可能有多种到达方式，所以该网络是一个多重有向图2.问题就转化为一个图论问题，即在给定的加权网络图中寻找所有其它点(村庄) 到关键点(垃圾站) 的最小路径。1.3 算法选择及其时间复杂度分析在算法的选择上，想到Dijkstra的最短路径算法.因为该算法稳定性好，能适应网络拓扑的变化，同时对系统的内存空间占用少.但在

5、经过试验后，我们发现该算法的数据结构及其实现方法、时间复杂度等方面在本题应用上表现出较大的不足。其一，数据结构复杂。但垃圾站节点线路网络拓扑，很难用现有的数据结构加以完整的表示.如果采用该算法分析，其建立的数据结构模型将非常复杂.其二，算法时间长.我们在试验时还只规定最多两次换乘，在大量数据的情况下，计算速度就慢得让人难以忍受，根本达不到实时查询的需要.该算法的时间复杂度为，其中表示站点结点数，表示所有结点数.其三，垃圾站节点转车的特殊性并不一定要求用Dijkstra算法求出一条最短路径.使用Dijkstra算法计算出来的结果可能是需要转乘多次或上十次车才能到达.这样的计算结果是毫无意义的。于

6、是，我们考虑，如果在搜索过程中能够优先考虑靠近终点方向的顶点，即使用启发式搜索，则可以减少算法搜索空间，并大大提高算法搜索效率。目前在关于路径优化问题最流行的启发式搜索算法是弗洛伊德算法.该算法在选择下一个被检查的节点时，对当前节点距离终点的长度（权值）进行估计，评价其处于最优路径上的可能性量度，这样就可以首先搜索可能性大的节点，达到提高搜索效率的目的.考虑到本题特殊情况，我们在搜索过程中考虑了优先级，对弗洛伊德算法选择具有最小估价函数值的节点改为选择具有最大优先级的节点.这一改进应该能够很好地解决上述其他算法遇到的困难。1.4 考虑转运站重新设计的情况把转运站所管辖的小区做近似处理，以带点的

7、处理方式，根据题目所给的居民数据，利用计算机进行合理分布. 二符号说明和模型假设2.1 符号说明 图的顶点，； 连接顶点和的有向边； 由顶点集、边集和权向量构成的有向多重图； 所查询的始发站至终到站的可行路线方案数； 所查询的始发站至终到站的第个可行路线方案的转乘次数； 从顶点到的路程； 方案总费用.2.2 模型假设H1 为简化问题，只考虑垃圾清运系统正常营运的情况；H2 假设题中所给数据真实可靠；H3 假设居民将垃圾放入垃圾站时，已将垃圾分好类.H4假设任意相邻两个垃圾转运站点之间的距离相同.三数学模型的建立与求解3.1数学模型的建立城市垃圾收运是由产生垃圾的源头运送至处理处置场的全过程操作

8、，包括3 个阶段：收集垃圾从产生源到公共贮存容器的过程；清运指清运车沿一定路线清除贮存容器内垃圾并将其转运到垃圾转运站的过程（在一定情况下，清运车可直接将垃圾运送至处理处置场）；中转指在转运站将垃圾装载至大容量转运车，远途运输至处理处置场.前1 个阶段需要对垃圾产生源分布情况、垃圾产生量及成分等进行调查和预测；后2 个阶段需要运用最优化技术对清运线路和转运站垃圾分配运输进行优化.3.1.1城市生活垃圾产生量预测方法城市生活垃圾收运模式的设计是在对生活垃圾产生量作正确预测的条件下进行的，因为设计的收运模式，不仅应满足当前垃圾产生量的需求，而且应该能够应对未来几年的变化.我们运用灰色系统模型分析法

9、进行预测.灰色系统模型包含模型的变量维数和阶数，记作.在生活垃圾产生量预测中普遍使用模型.通过对原始的时间序列数据进行累加处理后，数据便会出现明显的指数规律，通过进一步分析，可以进行垃圾产生量预测.在实际应用中，灰色系统模型预测法会产生正误差，而线形回归分析方法的预测结果偏小.因此可以结合2 种预测方法的特点，运用2 种预测值的加权平均值作为垃圾产生量的推荐值2。3.1.2垃圾清运路线优化垃圾物流是一种具有“产生源高度分散、处置高度集中、产生量和品质随季节变化”特点的“倒物流”系统，是从分散到集中的过程；而生活物质供应“正物流”是商品从集中到分散的过程.虽然两种物流在表现上有所区别，但也有本质

10、联系.在环卫作业中采用先进的生活垃圾物流管理环境卫生工程，可以有效提高效率，降低成本.因此垃圾清运车辆选择、路线优化可以参照物流配送系统对运输车辆的优化调度.车辆调度问题一般定义为：对一系列发货点、收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时空限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆尽量少等）；比照物流学中车辆调度问题；建立垃圾清运的基本模型。用标志垃圾转运站；设有个清运点，分别用标志完成清运任务需要的车辆数为 ，每个车辆的载质量为；每个清运点的垃圾产生量为；转运站和各清运

11、点中任意两点之间的运距用表示；第 辆车的行车路线称为第条子路径，其包含清运点的数目为表示第 条子路径中个清运点组成的集合，其中的元素 代表第 条子路径中顺序为的清运点；、均表示转运站，即.，；（3）；（4），（5）；（6）经证明：一般车辆优化调度问题属于组合优化领域的NP-hard 问题，通常采用启发式算法进行求解.例如Eugnio de Oliveira Simonetto 等综合运用启发式算法、拍卖算法和动态惩罚法求解了巴西的阿雷格里港24 辆清运车的调度问题.该问题中包含1 个车库，在清运该市60 t 垃圾的同时，满足8 个垃圾分选场的最小需求5.AndrzejJaszkiewicz 等

12、用保距重组算子的遗传局部搜索算法解决了1 个固体废物管理公司清运30 000 个垃圾容器的车辆运输问题.该问题包含1 个车库，2个垃圾填埋场6.该优化问题不仅要总路线最短，而且要实现经济、环境与社会三方共赢.宋薇等提出可将环境与社会因素的信息加至优化模型中，即对实际路线长度进行加权改造.得到综合路线长度公式为7：.（7）式中： 为综合路线长度，； 为实际路线长度，； 为噪声影响权重； 为大气影响权重； 为交通状况权重.3.1.3转运站设置设置垃圾转运站可以更有效地利用人力和物力，充分发挥垃圾清运车的效益，保证载质量较大的垃圾转运车经济而有效地进行长距离运输，从而降低垃圾收运总费用.所以，一般来

13、说，当转运距离超过一定临界值时，需要设置转运站.目前，多目标评价模型8、整数规划模型9被广泛应用于转运站的选择决策中.3.1.4转运优化城市垃圾转运的优化属于运输问题，主要是根据不同处置方式的处置量，以及各转运站至不同处置场所的运输路线及距离来确定各转运站向不同处置场所分配和运输垃圾的量.如设有 个转运站 分别产生的垃圾量为.另有垃圾处理处置点 个，分别为可接收的处置量分别为.从 到的运输距离（体现运能的经济性） 为，在产生量与处置量平衡的条件下，求最经济（运输距离最小） 的调运方案10.数学模型：设从 到的发运量为，则.（8）， .（9）5 结束语在决策中引入定量模型，可以提高决策的质量和水

14、平，但应该注意城市生活垃圾收运系统的规划设计牵涉到许多相互关联、相互制约的因素，涵盖经济、环境、社会多个方面.因此，在建立模型时应该综合考虑各种因素，经过反复比较和权衡，最后获得最佳的生活垃圾清运与处理方案.3.2数学模型的求解垃圾转运站数据模型3以垃圾转运路线段为基本单元.转运线路是一系列垃圾转运线路段的有序排列，为转运车辆行驶的一个物理路径，不同的运输线路是由居民生活垃圾站连接的.在垃圾转运过程中，我们关心的是垃圾转运的路径最短、耗时最少等问题，而对转运过程经过的街道并不感兴趣.于是将垃圾站点和转运站点合并，得到适合垃圾转运线路查询的数据模型如图1所示.转运路线ID包含存在于包含 存在于包

15、含 存在于居民垃圾站点ID线路线段ID包含存在于居民垃圾站点ID包含存在于垃圾处理点ID图1 垃圾转运数据模型3.2.1问题转化与数学刻画垃圾转运与处理站点的布局关键是在一定条件下求出任意两站点A与B之间的运行线路上的权重.如果将所有站点看作结点，站点之间投入大型或小型运输车辆（看作一条有向边）运输垃圾所开销的成本看作边权，则某一时刻的运输交通状态便形成了一个网络.因为站点与站点之间可能有多种到达方式，所以该网络是一个多重有向图2.问题就转化为一个图论问题，即在给定的加权网络图中寻找任意两点与之间满足一定条件（本题表示为运输成本最少、投资路程最短、费用最少等）的一条通路.根据题目要求以及前面关

16、于投入最少获利最大的分析，由最优化原理4，问题可以依次描述为下面优化问题： （4.1） （4.2） （4.3） （4.4）其中，表示与匹配的大，小型运输车辆， 表示第个下一个节点匹配的相邻站点行驶路径.3.1.2 算法描述与求解在考虑大，小型运输车辆如何投入时，我们知道相距较远且不在相邻区域的垃圾处理点是不可能进行垃圾集中处理的.所以，根据：1）深圳市南山区垃圾转运站垃圾转运量等情况统计表（南山），2）南山区居民数据，3）中转站位置图.采用佛洛依德算法来求解上述优化问题.弗洛伊德算法5在选择下一个被检查的节点时，比Dijkstra算法快速，从而提高效率.考虑到本题特殊情况，在搜索过程中应该考虑

17、到垃圾处理站点的区域性，对佛洛依德算法选择具有最小开销成本的节点，我们按照“设最大值-做标记”的优先顺序进行估计.下面是佛洛依德算法步骤，其中INFINITY和enum BOOL False,True是引入的两个标记位，INFINITY为超出区域的两垃圾处理站以及没有可行边的两节点的标记位，enum BOOL False,True为存在可行边的且处于同一个最近区域的两节点的标记位.第一步，生成垃圾站点模拟图CreateGraph(Graph &)，建立垃圾站点模拟图的邻接矩阵arcsMAX_NUMMAX_NUM，初始其权值为INFINITY.依次读入邻接矩阵的值.令INFINITY表示无穷大，

18、不于考虑.第二步，依次循环探视其他节点（若开始节点为由V到W），若存在U节点使得Dvu+Duw Dvw存在，则置enum BOOL False,True的标志位为True，并将其作为最佳节点BEST.否则，置False，继续探视下个相邻的节点.直止探视完非INFINITY为止.第三步，根据第二步探视的BOOL值，修改邻接矩阵arcsMAX_NUMMAX_NUM的值.第四步，输出节点之间的最小权值，并显示运行路线.3.1.3 复杂度比较分析为了说明我们所采用算法的优越性，下面把之前我们尝试过的Dijkstra算法和动态规划算法与之进行形势上的比较.鉴于动态规划算法在试验过程中执行太慢，已经超过了

19、人们的心理承受能力，在此没有必要拿来比较.虽然Dijkstra算法与弗洛伊德算法的时间复杂度也是，但形式上简单些.弗洛伊德算法仍从图的带权邻接矩阵arcsMAX_NUMMAX_NUM出发，其基本思想是：假设求从顶点Vi到Vj的最短路径.如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为arcsij的路径，该路径不一定是最短的，尚需进行n次的探试.首先考虑路径（Vi,V0,Vj）是否存在（即判别弧（Vi,V0）( V0 ,Vj)是否存在）.如果存在，则比较（Vi,Vj）和（Vi,V0,Vj）的路径长度取较短者为从Vi到Vj的中间顶点的序列不大于0的最短路径.假如在路径上再加入一个顶点V1，也就是

20、说，如果（Vi，V1）和（Vi，Vj）分别是当前找到的中间顶点的序列号不大于0的最短路径，那么（Vi，V1，Vj）就有可能是从Vi到Vj的中间顶点的序列号不大于1的最短路径.将它和已经得到的从Vi到Vj中间顶点序列号不大于0的最短路径相比较，从中选出中间顶点的序列号不大于1的最短路径之后，再增加一的顶点V2继续进行探试.依次类推.在一般情况下，若（Vi，Vk）和（Vk，Vj）分别是从Vi到Vk和Vk到Vj的中间序列号不大于k-1的最短路径，则将（Vi，Vk，Vj）和已经得到Vi到Vj且中间顶点序列号不大于K-1的最短路径比较，其长度较短者便是Vi到Vj的中间序列号不大于k的最短路径.这样，经过

21、n次的比较后，最后必然求得Vi到Vj的最短路径.按照此法，可以同时求得各对顶点的最短距离.3.1.4 模型评价本模型首先从宏观上给出了一个垃圾站节点数据模型，这对进一步理解整个系统的运行和算法的实现都大有帮助.我们在算法中考虑了优先级搜索，对目前在关于路径优化问题方面最流行的启发式搜索算法弗洛伊德算法进行了相关改进，使得搜索效率大大提高，基本能够满足实时查询需要.这体现在与其他算法的比较数据中.当同时考虑最短路径和大小型车辆的投入时，我们对问题进行了合理的转化，把大小型车辆的投入看成“特殊的权”，只需在程序中加上几个简单的约束和说明，就很快得到了相应问题的解.但是本模型所采用的改进弗洛伊德算法

22、只是我们目前找到的一种可行算法而已，有无比其更加适合的算法需要进一步分析寻找.题中基本假设H3只是为简化问题而设，与实际情况可能存在一些出入，但这并不影响改进弗洛伊德算法本身的执行.此外，基于投资者满意度最优的优化模型虽然充分考虑了运输的满意度，但是寻找合适的算法就变得更加复杂，这也是一个不容忽视的问题.四进一步的问题4.1 关于算法的思考我们采用改进的弗洛伊德算法虽然获得了比较满意的结果，但如果对垃圾站节点网络中的节点和边赋予空间信息，那么由几何学原理，两点之间直线最短，若两节点间存在一条边，则该边为两节点间的最短路径；若不存在边相连，则连接两点间的直线段代表了一个路线趋势，顺着连线的方向的某条边是最短路径的可能性较大.从而可在计算最短路径时采用效用优先的路径搜索.所以，如果再加上一张标有路径距离的地图，我们的算法还可以改进，搜索效率还可以提高。4.2 关于“和谐垃圾站节点7”的构想“和谐社会”， “关注民生”，“以人为本”.这已经逐步成为我国社会主义社会的鲜明特征.那么，作为与城市居民息息相关的垃圾站节点系统，理应逐步实现“和谐垃圾站节点”，做到“以人为本”.具体到垃圾站节点查询系统的开发上，城市居民的满意度应该成为首要实现的任务.交互界面的友好性，目标选择的多样性和可扩展性就成为软件开发必须考虑的因素。