姓名：刘鹏
学号：2010142124 学院:理学院
专业：电子信息科学与技术
深圳市南山区垃圾运输问题研究
摘要
随着城市人口的增加，城市建设规模不断扩大，生活垃圾的数量日益增多，分布更广，垃圾问题逐渐成为人们关心的一个严峻的社会问题，急需得到解决。 城市生活垃圾从收集、运输、中转到处理，构成了城市生活垃圾的处理系统[1]。据统计，处理系统费用的75%～85%[2]归因于收集和运输（简称收运），即生活垃圾收运系统。而随着垃圾处理设施的向远离城市的远郊转移，市区面积的扩张，整个垃圾收集运输系统的覆盖面积越来越大，对车辆收运垃圾的路线进行科学合理的规划，就显得尤为重要。
在生活垃圾收运系统中，收集清运工作的科学性、经济性关键就是选择合理的收运路线。选择合理的垃圾收运车辆的路线，可减少行驶距离，节约时间，可高效地调度收运车辆，减少投入车辆数，车辆的维修费用、燃油费也相应减少。同时，人力资源也可发挥更大的效率。因此，通过对垃圾收运车辆行车路线的优化，可以很大程度地节省收运费用,从而产生巨大的经济和社会效益。
就生活中垃圾运输的问题的调度方案予以研究。问题一清运路线中，垃圾清运路线优化垃圾物流具有“产生源高度分散、处置高度集中、产生量和品质随季节变化”的特点
通过对问题的分析和合理的假设，（1）对垃圾从中转站运到处理中心的过程运用图论知识建立动态规划模型，并确定大小型设备的分布。然后获得既环保又经济的运送方案。（2）对于转运站的重设，可采用动态规划模型进行分析。
关键字：运输车调度 非线性规划 最大利益 图论 分布
（一）问题重述：
在垃圾分类收集与处理中，不同类的垃圾有不同的处理方式，简述如下： 1）橱余垃圾可以使用脱水干燥处理装置，处理后的干物质运送饲料加工厂做原料。不同处理规模的设备成本和运行成本（分大型和小型）见附录1说明。 2） 可回收垃圾将收集后分类再利用。
3） 有害垃圾，运送到固废处理中心集中处理。 4）其他不可回收垃圾将运送到填埋场或焚烧场处理。
所有垃圾将从小区运送到附近的转运站，再运送到少数几个垃圾处理中心。显然，1）和2）两项中，经过处理，回收和利用，产生经济效益，而3）和4）只有消耗处理费用，不产生经济效益。-
本项研究课题旨在为深圳市的垃圾分类化进程作出贡献。为此请你们运用数学建模方法对深圳市南山区的分类化垃圾的实现做一些研究，具体的研究目标是：
1） 假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计，同时在目前的运输装备条件下给出清运路线的具体方案。以期达到最佳经济效益和环保效果。
2）假设转运站允许重新设计，请为问题1）的目标重新设计。
仅仅为了查询方便，在题目附录2所指出的网页中，给出了深圳市南山区所有小区的相关资料，同时给出了现有垃圾处理的数据和转运站的位置。
（二）问题分析
对于问题一的清运路线问题、路线运输车调度方案的设计，不能仅仅考虑使运输车的行走路线最短，因为此处还存在着垃圾的累积运输的花费问题，因此，我们的目标函数应该是使得所有运输的花费最少。在建模过程中，我们无需考虑投入的运输车台数，只需对各条路径所花费的时间进行和各运输车载重量约束即可，至于投入的车辆数，在各条路径确定后，最终便可确定投入运输车数量和花费与收益.
对于一中的大小型设备的分布方案，运用图论，从而确定大小型设备的分
布，并获得经济与环保的效益。
一 模型假设
（1）假设南山区人口分为不同部分，每部分人口固定，每天产生垃圾量固定； （2）假设每个小区所有的垃圾都堆在一起；
（3）假设各小区的垃圾和中转站的垃圾都必须在当天清理完毕； （4）不考虑运输车在行驶过程中出现的塞车、抛锚等耽误时间的情况； （5）不允许运输车有超载现象；
（6）每个小区清运站均位于街道旁，保证运输车和铲车行驶顺畅；
（7）所有运输车从中转站出发，最后回到中转站；所有的拖车都从填埋场出发，最后回到填埋场；
（8）一天只从收一次垃圾，只从中转站转运一次垃圾；
（9）拖车将垃圾一起送往大型设备处和小型设备处再前往坟埋场和焚烧场； （10）所有的橱余垃圾处理设备全部分布在中转站。
（11）若中转站的转运垃圾超过60吨（200*3/10）时，建设大型处理设备，其余用小型设备补足或全用小型设备；
（12）拖车只负责将不可回收垃圾运往焚烧场和填埋场；
二 模型的建立及求解
问题1：
模型一
1 符号说明
可将城市生活垃圾收集区域看成一个网络，其中垃圾收集点和街道分别表示网络的顶点和边。如果两个垃圾收集点由一街道相连，则用边把这两点连接起来，表示这两点是相邻的。
在连通图G=(V,A)中，有n+1个顶点（|V|=n+1），表示车库、垃圾收集点和中转站。顶点1表示车库，点n+1表示中转站。其余顶点，即U=V\\{1,n+1},表示垃圾收集点。弧(i,j)（(i,j)∈A）表示在两个收集点之间的街道。单行街道可通过单方向的弧来表示，双行街道则可以用一对方向相反的弧(i,j)和(j.i)来表示。
记：
G=(V,A):网络图，表示收集区域；
2011三峡大学大学生数学建模竞赛学生竞赛大学生
