文档介绍：2012高教社杯全国大学生数学建模
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。
我们知道,抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。如有违反竞赛规则的行为,我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公开展示(包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等)。
我们参赛选择的题号是(从A/B/C/D中选择一项填写):
我们的参赛报名号为(如果赛区设置报名号的话):
所属学校(请填写完整的全名): 江西师范大学
参赛队员(打印并签名) :1. 王琨
2. 刘莉
3. 黄安枝
指导教师或指导教师组负责人(打印并签名):
日期: 2013 年 8 月 3 日
赛区评阅编号(由赛区组委会评阅前进行编号):
赛区评阅记录(可供赛区评阅时使用):
评
阅
人
评
分
备
注
全国统一编号(由赛区组委会送交全国前编号):
全国评阅编号(由全国组委会评阅前进行编号):
城市垃圾运输问题
摘要
城市垃圾运输问题是一个寻求最优路径的优化问题。在解决第一问运输车的调度问题时,本文首先确立了一种构思,即缩短运输车的总路程。在此基础上加大空载路程,缩短载重路程,并做到运输车的数量尽可能的少。
在第一问中,根据以上几点要求,我们进一步将其深入讨论得出必须使运输车空载至最远点,运用下山法的原理逐步找出下一个最合适的点,此时只需满足横纵坐标都逐渐减小,而所取点垃圾总量不大于6吨,最终通过运算我们得出了10条线路。但是其中有几条线路用时较短,我们对其进行了人工优化,将用时较短的路线进行合并,最终得出只需6辆运输车。
在第二问铲车调度的问题中,本文延续并使用了第一问的结果和上述思想。在保持运输车线路不变的情况下,本文估算了一下铲车由第一个工作点开始到最后一个工作点结束的同时再除以4小时,得出最少要三辆铲车。将10条运输线路概括为3个部分,原则是使这3个部分的每个部分内铲车跑的总路程最短,通过人工的运算和时间的对照,我们得出了最终结果。
在第三问中,三种型号车的加入增加了解题的灵活性,此时我们的构思依然是缩短运输车的总路程,加大空载路程,而利用8吨车去尽可能的解决远处的垃圾显然可以在不增加总路程的情况下更加缩短空载路程。
我们的结果如下:
第一问,求得需要运输车6辆,,调度方案见正文表5,最优路径见正文图4。
第二问,求得需要铲车3辆,,调度方案见正文表4。
第三问,求得需要铲车4辆和运输车5辆,,运输车和铲车的调度方案见表6、表7,运输车的最优路径见图8。
关键词:最优路径、哈密顿圈、下山法、模拟退火法
一、问题的重述
为了美化城市环境,环卫部门每天夜里都要对分布在城区各街道的定点垃圾及时进行处理。假设某城区有37个垃圾集中点,环卫车辆每天都要从垃圾处理厂(第38号节点)出发将垃圾运回。现有一种载重量6吨的运输车,每个垃圾点需要用8分钟的时间装车,运输车平均速度为40公里/小时(夜里运输,不考虑塞车现象);每辆车每日平均工作4小时;运输车重载运费为2元/吨公里;;并且假定街道方向均平行于坐标轴。试给出满意的运输调度方案以及试给出满意的运输调度方案以及计算程序。
运输车应如何调度(需要投入多少台运输车,每台车的调度方案、运营费用);
铲车应如何调度(需要多少台铲车,每台铲车的行走路线以及运营费用);
如果改用载重为4吨、6吨、8吨的三种运输车,试给出运输车和铲车的调度方案。
二、问题的分析

问题一是图论中的一个遍历问题。由于运输车的载重与时间的约束,问题一不再是最小树能解决的问题,而是森林,即包含了多个树的图。每一个树用一辆车去把其上面的垃圾运输回来,只要时间足够,同一辆车可能运输不止一棵树的垃圾。问题就变成了在一个森林中,找到这样一些树,使其能用尽可能少的车遍历完所有顶点,且这些树构成哈密顿圈。
将垃圾集中点抽象成坐标平面上的点,该点具有两个属性,即位置属性和重量属性:城市抽象成一个3020的一个坐标方格网络。该模型符合以上模型假设。垃圾运输问题最终可以归结为最优路径搜索问题,但注意到此图为森林而不是树,更具具体问题设计出随即下