城市垃圾运输问题.doc

《城市垃圾运输问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、魅力数模美丽师大浙江师范大学“同梦杯”第八届数学建模竞赛自信创新合作快乐AB论文题目城市垃圾运输问题编号56组评分监制：浙江师范大学数学建模研究会（2009年5月7日）（说明：评分一栏为评阅人填写，请参赛者不要填写）垃圾运输问题摘要：该题我们的主要解题思路分三阶段：第一阶段，我们先根据题设条件和基本假设画出该题的图。第二阶段，我们根据图和点的位置关系结合题设，归纳出一些最基本的确定路线的原则：在仔细分析该题后，我们认为该题为一个TSP与VRT相结合的问题。我们先抛开空载费用，若要把所有的垃圾运回垃圾

2、处理站，这部分有效工的费用为∑2.0＊

3、Xi

4、＊Yi(

5、Xi

6、为垃圾点Xi到原点的距离,Yi为垃圾点的垃圾量)，是恒定不变的。只要我们能保证空载路线最小，则所花的时间和费用都最小。因此解题的关键在于找出一个调度方案，使空载行驶的线路最小。第三阶段则是编制程序阶段，我们结合下山法逐点搜索，并引入随机生成器。在出现后继点权值相等难以判断以哪点继续搜索时，由随机生成器确定。为了让算法更接近人的思维，我们让更靠近父点的子点有更高的几率被作为下一个将去的垃圾点，这也与我们的算法原则对应。采用计算机模拟搜索的计

7、算方法，搜索出运输车投入辆数以及运输车最佳调配方案，使得在不考虑铲车的情况下运营费用最低。总运营费用为运输车空载费与实际运输费之和。问题的解答如下：第一问，求得所需总费用为2496.3元，所需总时间为23小时08分，路线分配图见正文；第二问，求得需4辆铲车，铲车费用为199.0元，分配图及运输车调度表见正文；第三问，运营总费用为：2460.6，其中8吨、6吨、4吨载重量的运输车各需5、2、3辆，路线分配图见正文。关键词：单目标优化计算机搜索TSP一、问题的重述某城区有38个垃圾集中点，每天都要从垃圾

8、处理厂（第38号节点）出发将垃圾运回。现有一种载重6吨的运输车。每个垃圾点需要用10分钟的时间装车，运输车平均速度为40公里／小时（夜里运输，不考虑塞车现象）；每台车每日平均工作4小时。运输车重载运费2.0元/吨公里；运输车和装垃圾用的铲车空载费用0.5元/公里；并且假定街道方向均平行于坐标轴。请你给出满意的运输调度方案以及计算程序。问题：1.运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）2.铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用）3.如果有载重量为4吨、

9、6吨、8吨三种运输车，又如何调度？（垃圾点地理坐标数据表见附录一）二、模型的假设1.运输车匀速行驶且不计一切拐弯损耗时间；2.车辆在任意两站点中途不停车；3.只要平行于坐标轴即有街道存在；。4.无论垃圾量多少，都能在十分钟内装上运输车；5.每个垃圾站点的垃圾不允许分两次运输，而且也只需要一辆铲车。6.假设运输车、铲车从A垃圾站到B垃圾站总走最短路线；7.任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直角边之和；8.如果车可以跑第二趟，中间无休息时间；9.假设铲车、运输车载工作途中不发

10、生意外也不遇到意外；10.所有运输车和铲车均从第38号点出发，且最后均回到38号点；三、主要变量的说明1、子点：本点的下一点；2、Spend：运费；3、Time：时间消耗；4、

11、A

12、：A点横纵坐标之和，；5、垃圾集中点在后面用顶点表示6、v[i]：第i个顶点7、v[i].X：第i个顶点的X坐标；v[i].Y表示第i个顶点的Y坐标；8、v[i].laji：第i个顶点上有的垃圾重量，单位是吨；9、L[i][j]:顶点i到顶点j的距离；10、sum[i]:顶点i的横纵坐标之和；11、访问一个顶点表示把它的

13、垃圾装上车；12、用到的相关定义　设G=(V,E)是连通无向图,(1)经过G的每一个顶点正好一次的路,称为G的一条哈密顿路或H路;(2)经过G的每一个顶点正好一次的圈,称为G的一条哈密顿圈或H圈;(3)含H圈的图称为哈密顿图或H图.

14、A

15、A点横纵坐标之和

16、B

17、B点横纵坐标之和

18、A-B

19、表示A,B两点之间的距离Ta表示A点所在地的垃圾量cost：运费；time：时间消耗；装的足够多运输车当前的载重离限载不大于0.55吨(垃圾点的最小垃圾量)序数号所在点的编号一、问题的分析与模型的建立这是一个遍历问题。

20、由于运输车的载重与时间的约束，它不在是最小树能解决的问题，而是森林，包含了多个树。每一个树用一辆车去把其上面的垃圾运输回来，只要时间足够，同一辆车可能运输不止一颗树的垃圾。问题就变成了，在一个森林中，找到这样一些树，使其能用尽可能少的车遍历完所有顶点的，且这些树够成哈密顿圈。将垃圾集中点抽象成坐标平面上的点，该点具有两个属性，即位置属性和重量属性；城市抽象成一个30*20的一个坐标方格网络。该模型假设如第二项中所述。垃圾运输问题最终可以归结为最优路径搜索问题，但注意到