数学建模

2011年三峡大学大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：垃圾分类处理与清运方案设计摘要垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资回收与再利用的城市绿色工程。深圳市对垃圾分类处理的问题就很重视，本文即针对深圳市山区的分类化垃圾的实现做一些研究。一个好的垃圾分类处理与清运路线应包括以下内容：垃圾如何很好分类；资源的循环利用；出动几辆垃圾运输车，分别在哪些路线上，各运输多少次（因为随机因素影响，我们只求出各条路线上的运输车安排）；一个合格的计划应尽可能考虑城市的环保要求，而一个好的计划还应考虑以下两条原则：①总运量（吨百公里）最小，同时出动最小的垃圾运输车，从而使运输成本最小；②合理布局橱余垃圾处理场，使一个城市的经济效益和环保效益达到最优;针对问题一,在垃圾转运站规模与位置不变条件下，对于运输车调度方案的设计，不能仅仅考虑使运输车的行走路线最短，因为此处还存在着垃圾的累积运输的花费问题，因此，我们的目标函数应该是使得所有运输的花费最少。在建模过程中，我们首先将地图转化为jpg格式，将图片导入到matlab中，并利用matlab功能，实现对垃圾转运站坐标的确定，并求出相邻两垃圾站的距离.并且得到了垃圾中转站的分布图以及坐标。其次，我们用已有的Dijkstra算法以及c++语言编程得到运输车的最优路线，根据运输车路线图，我们可以得到运输车的总运营费用为2496.3元，总共花费的时间23小时08分钟，同时用LINGO编程求得使用大型橱余设备的总数为1，使用小型橱余设备的总数为82，最大收益为14500。具体的每个运输车的费用和时间见正文。针对问题二，我们在问题一的基础上，允许中转站允许重径为5米，而后选用集合覆盖模型求出垃圾中转站的待选点，即用尽可能少的圾收中转站去覆盖所有的垃圾收集站。因此，我们建立了以从现有的m座垃圾收集站的位置中选出可以覆盖m座垃圾收集站的最小数目的中转站选点为目标函数，并给出了约束条件，为了新设计，则应该首先参照垃圾收集密度以及当地人口密度，算出每个垃圾中转站的最优收集半求得可以覆盖m座垃圾收集站的最小数目的中转站的具体分布图，我们运用启发式算法进行集合覆盖模型优化来解决可以覆盖m座垃圾收集站的最小数目的中转站选。最后我们按照上述模型，结合坐标数据，找出了建设中转站的最佳位置（具体的位置见正文）。关键词：最优路线Dijkstra算法集合覆盖模型启发式算法垃圾分类一、问题重述垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资源回收与再利用的城市绿色工程。在发达国家普遍实现了垃圾分类化，随着国民经济发展与城市化进程加快，我国大城市的垃圾分类化已经提到日程上来。2010年5月国家发改委、住房和城乡建设部、环境保护部、农业部联合印发了《关于组织开展城市餐厨废弃物资源化利用和无害化处理试点工作的通知》，并且在北京、上海、重庆和深圳都取得一定成果，但是许多问题仍然是垃圾分类化进程中需要深入研究的。在深圳，垃圾分为四类：橱余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾，这种分类顾名思义不难理解。其中对于居民垃圾，基本的分类处理流程如下：在垃圾分类收集与处理中，不同类的垃圾有不同的处理方式，简述如下：1）橱余垃圾可以使用脱水干燥处理装置，处理后的干物质运送饲料加工厂做原料。不同处理规模的设备成本和运行成本（分大型和小型）见附录1说明。2）可回收垃圾将收集后分类再利用。3）有害垃圾，运送到固废处理中心集中处理。4）其他不可回收垃圾将运送到填埋场或焚烧场处理。所有垃圾将从小区运送到附近的转运站，再运送到少数几个垃圾处理中心。显然，1）和2）两项中，经过处理，回收和利用，产生经济效益，而3）和4）只有消耗处理费用，不产生经济效益。本项研究课题旨在为深圳市的垃圾分类化进程作出贡献。为此请你们运用数学建模方法对深圳市南山区的分类化垃圾的实现做一些研究，具体的研究目标是：1）假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计，同时在目前的运输装备条件下给出清运路线的具体方案。以期达到最佳经济效益和环保效果。2）假设转运站允许重新设计，请为问题1）的目标重新设计。仅仅为了查询方便，在题目附录2所指出的网页中，给出了深圳市南山区所有小区的相关资料，同时给出了现有垃圾处理的数据和转运站的位置。其他所需数据资料自行解决。附录11）大型厨余垃圾处理设备（如南山餐厨垃圾综合利用项目，处理能力为200吨/日，投资额约为4500万元，运行成本为150元/吨。小型餐厨垃圾处理机，处理能力为200-300公斤/日，投资额约为28万元，运行成本为200元/吨。橱余垃圾处理后产物价格在1000-1500元/吨。2）四类垃圾的平均比例橱余垃圾：可回收垃圾：有害垃圾：其他不可回收垃圾比例约为4：2：1：3。可回收垃圾划分为纸类、塑料、玻璃、金属四大类，大概比例分别是：55%、35%、6%、4%。纸类、塑料、玻璃、金属四类的废品回收价格是每公斤：1元、2.5元、0.5元、2.5元。3）南山区的垃圾清运设备情况（主要是车辆数目和载重）。拖头（拖车）：只拖十吨的大型厢，只用于从转运站到垃圾中心，每次只拖一个大型“厢”，平均吨公里耗油25L—30L柴油/百公里。收集车辆：只负责从小区的垃圾站到转运站运输。100辆2.5吨汽车，每车耗油20L—35L70#汽油/百公里。司机月薪平均3500元。附录2.：1）垃圾转运站垃圾转运量等情况统计表（南山），2）南山区居民数据，3）中转站位置图。见附录数据（或上网站，在数学建模基础数据页之垃圾问题基础数据下载）二、问题分析这是一个垃圾分类处理与清运方案的设计的便利问题，此问题的困难之处在于确定橱余垃圾处理厂的布局问题，并使垃圾运输车工作时尽量花费最小，才能使垃圾分类处理与清运满足题目的要求——环保与经济。为此，应该使橱余垃圾处理厂布局合理，也就是说，合理的橱余垃圾处理厂能够运输车工作时花费最小。针对问题一，在垃圾转运站规模与位置不变条件下，对于运输车调度方案的设计，不能仅仅考虑使运输车的行走路线最短，因为此处还存在着垃圾的累积运输的花费问题，因此，我们的目标函数应该是使得所有运输的花费最少。在建模过程中，我们无需考虑投入的运输车台数，只需对各运输车载重量约束即可，至于投入的车辆数，在各条路径确定后，车辆数也就唯一确定了。针对问题二，在问题一的基础上，允许转运站允许重新设计，对于橱余垃圾处理场布局方案的设计，橱余垃圾处理场的选址应服从城市总体规划，绝不能因选址不当破坏了城市的生态环境，阻碍城市的经济发展。因此，我们的目标函数应该是综合考虑橱余垃圾处理场的启用问题。在建模过程中，我们既要考虑城市的生态环境又要考虑运输花费问题。一个合理的橱余垃圾处理场有利于其经济效益的改善，功能的发挥，并且使橱余垃圾处理场对周围环境影响最小，从而使经济效益与社会效益达到最优。三、模型的假设（1）假设深圳市南山区垃圾转运站之间转运路程近似为两地之间的直线距离。（2）不考虑运输车在行驶过程中出现的塞车、抛锚等耽误时间的情况。（3）假设各站点的垃圾都必须在当天清理完毕，当天没有剩余。（4）根据大量资料显示，假设大、小型设备的使用寿命为10年。（5）在较长的一段时间内，汽油和柴油的价格都保持稳定，价格分别为7.7元/升和7.5元/升。（6）在运输过程当中，不考率运输车空载的费用以及其他额外的费用。四、符号的约定与说明(1,2,3......)Mm:表示有m座垃圾收集站组成的集合;Ck:表示筛选出的第k座垃圾中转站所覆盖的垃圾收集站的集合;()Ak:表示筛选出的第k座垃圾中转站所覆盖的垃圾集合站的集合;()Bi:表示可以覆盖第i座垃圾收集站的中转站的集合;Wk:表示是否启示用第k座垃圾中转站;Uik:表示第i座垃圾收集站是否被第k座垃圾中转站覆盖；Ai大型设备台数Bi小型设备台数ijQ表示第i辆车在其子回路对应的第j个垃圾收集点的垃圾量2z购买一台小型设备所投资的钱1z购买一台大型设备所投资的钱3h厨余垃圾处理后的价格2h每台小型厨余垃圾处理设备日运行成本1h每台大型厨余垃圾处理设备日运行成本2e每台小型厨余垃圾处理设备日处理能力1e每台大型厨余垃圾处理设备日处理能力xS所有大车从转运站到焚烧垃圾场之间的总距离yS所有小车从转运站到焚烧垃圾场之间的总距离ixU从第i个转运站到垃圾场得距离iyU从第i个转运站到填埋场得距离dv大车的速度1w处理后的收益2w车行驶的总费用五、问题一的解答5.1模型一的建立5.1.1模型的准备首先，根据题目中的要求，即假设在现有垃圾装运站规模与位置不变的条件下，根据深圳市南山区垃圾转运站分布图，并结合《新型垃圾转运站垃圾转运量等情况统计表》，由附录1中给出的垃圾处理设备相关数据，建立整数线性规划模型，计算出需要的大、小型设备的台数N。其次，根据第一步求出的设备台数N，并结合深圳市南山区垃圾转运站分布图，将南山区分为N个区域，并建立最短路模型，对每个区进行分析，利用matlab编程计算最短路径及中位点的选址。我们先将地图转化为jpg格式，将图片导入到matlab中，并利用matlab功能，实现对垃圾转运站坐标的确定，并求出相邻两垃圾站的距离。（程序见附录一）得到的垃圾中转站分布图及坐标位置如下图所示：垃圾中转站的分布图序号垃圾转运站名称垃圾量T坐标(km)序号垃圾转运站名称垃圾量T坐标(km)橱余垃圾可回收垃圾有害垃圾不可回收垃圾橱余垃圾可回收垃圾有害垃圾不可回收垃圾xyxy1疏港小区站16841246.520光前站842612182花果路站1263986.521松坪山站1052.57.51017.53望海路站126398622松坪山2站42138.5174南山村站1052.57.5511.523同乐村站210.51.5718.55南光站631.54.5711.524西丽路站631.54.510196南园站631.54.56.511.25新围村842611.215站57北头站631.54.56.51226平山村站1052.57.511.521.58南山市场1052.57.56.512.527官龙村站631.54.51021.59科技园站84269.51228动物园站84261222.510白石洲南站12639121329牛城村站210.51.57.525.511深圳大学站631．54.5913.530塘朗站4213162212大冲站1473.510.51114.531福光站421315.522.513沙河市场站1263912.51532长源村站210.51.51722.514玉泉站1052.57.5815.533大石勘站1263913.52615大新小学站1263961434白芒站3．21.60.82.492716九街站84266.51535阳光站421392817前海公园站6.43.21.64.85.515.536麻勘站421311.52818华侨城站281472115.51437涌下村站84266.513.519龙井站631.54.513.517.538月光湾大道站1684125165.12模型一的建立5.1收益函数的建立（1）由总处理量大于或等于总需要处理量可得：0.41211nneAeBHiiii1110.2(55%1.2352.56%0.540.5)21nnijiiiiwQBzAz1222111(0.4)nnnijiiiiihQBeeBh-310.4nijiQh由于每辆大车最大运载量为10000kg,而除去厨余垃圾和可回收垃圾剩余垃圾量为10.4nijiQ，故有10.410000nijixixQSU10.410000nijiyiyQ