垃圾运输问题建模论文9.docx

1、垃圾运输问题建模论文92012高教社杯全国大学生数学建模承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（

2、包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 江西师范大学 参赛队员 (打印并签名) ：1. 王琨 2. 刘莉 3. 黄安枝 指导教师或指导教师组负责人 (打印并签名)： 日期： 2013 年 8 月 3 日赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：城市垃圾运输问题摘要城市垃圾运输问题是一个寻求最优路

3、径的优化问题。在解决第一问运输车的调度问题时，本文首先确立了一种构思，即缩短运输车的总路程。在此基础上加大空载路程，缩短载重路程，并做到运输车的数量尽可能的少。在第一问中，根据以上几点要求，我们进一步将其深入讨论得出必须使运输车空载至最远点，运用下山法的原理逐步找出下一个最合适的点，此时只需满足横纵坐标都逐渐减小，而所取点垃圾总量不大于6吨，最终通过运算我们得出了10条线路。但是其中有几条线路用时较短，我们对其进行了人工优化，将用时较短的路线进行合并，最终得出只需6辆运输车。在第二问铲车调度的问题中，本文延续并使用了第一问的结果和上述思想。在保持运输车线路不变的情况下，本文估算了一下铲车由第一

4、个工作点开始到最后一个工作点结束的同时再除以4小时，得出最少要三辆铲车。将10条运输线路概括为3个部分，原则是使这3个部分的每个部分内铲车跑的总路程最短，通过人工的运算和时间的对照，我们得出了最终结果。在第三问中，三种型号车的加入增加了解题的灵活性，此时我们的构思依然是缩短运输车的总路程，加大空载路程，而利用8吨车去尽可能的解决远处的垃圾显然可以在不增加总路程的情况下更加缩短空载路程。我们的结果如下：第一问，求得需要运输车6辆，所需总费用为2339.05元，调度方案见正文表5，最优路径见正文图4。第二问，求得需要铲车3辆，所需总费用为142.8元，调度方案见正文表4。第三问，求得需要铲车4辆和

5、运输车5辆，所需总费用为2508.63元，运输车和铲车的调度方案见表6、表7，运输车的最优路径见图8。关键词：最优路径、哈密顿圈、下山法、模拟退火法一、问题的重述为了美化城市环境，环卫部门每天夜里都要对分布在城区各街道的定点垃圾及时进行处理。假设某城区有37个垃圾集中点，环卫车辆每天都要从垃圾处理厂（第38号节点）出发将垃圾运回。现有一种载重量6吨的运输车，每个垃圾点需要用8分钟的时间装车，运输车平均速度为40公里小时（夜里运输，不考虑塞车现象）；每辆车每日平均工作4小时；运输车重载运费为2元/吨公里；运输车和装垃圾用的铲车空载费用均为0.5元/公里；并且假定街道方向均平行于坐标轴。试给出满意

6、的运输调度方案以及试给出满意的运输调度方案以及计算程序。1. 运输车应如何调度（需要投入多少台运输车，每台车的调度方案、运营费用）；2. 铲车应如何调度（需要多少台铲车，每台铲车的行走路线以及运营费用）；3. 如果改用载重为4吨、6吨、8吨的三种运输车，试给出运输车和铲车的调度方案。二、问题的分析2.1问题一的分析问题一是图论中的一个遍历问题。由于运输车的载重与时间的约束，问题一不再是最小树能解决的问题，而是森林，即包含了多个树的图。每一个树用一辆车去把其上面的垃圾运输回来，只要时间足够，同一辆车可能运输不止一棵树的垃圾。问题就变成了在一个森林中，找到这样一些树，使其能用尽可能少的车遍历完所有

7、顶点，且这些树构成哈密顿圈。将垃圾集中点抽象成坐标平面上的点，该点具有两个属性，即位置属性和重量属性：城市抽象成一个3020的一个坐标方格网络。该模型符合以上模型假设。垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，更具具体问题设计出随即下山法，用计算模拟搜索，可以搜寻到令人满意的可行解。通过分析“单独运输”“先远点再近点”“先近点再远点”三种方面和垃圾是否一次清除的情况可得搜索的基本原则。2.2.问题二的分析当加入铲车后,因为铲车的空载费用为0.5元/公里，铲车装入垃圾后为2元/公里小时，我们应该让铲车将就运输车。若改变一条线,则会造成几公里的误差,甚至十几公里的误差

8、,这一项的数目就很大。若是铲车跟随运输车,则即使路线误差大一点,但所需费用也不会变得很大，故我们以第一个方案的路线为准。这时我们只要保证前一条线路的末节点,与后一条线路的首节点的路程差分别相加之和最小即可。根据这一思路，我们利用模拟退火方法，通过排列,遍历每种方案，就求出最优解。再考虑最短路径的情况及考虑和各车在时间地衔接，尽量要在规定的时间内作完，再进行相应的调整得出最优解。2.3问题三的分析对于问题3中4吨、6吨和8吨3种型号的运输车，本文先通过计算机分别运算出只使用一种车时的最优解，然后将三者的运算结果人工优化，从而得出最终解，得出调度方案。三、模型假设1. 运输车匀速行驶且不计一切拐弯

9、损耗时间；2. 车辆在任意两站点中途不停车；3. 只要平行于坐标轴即有街道存在；。4. 无论垃圾量多少，都能在十分钟内装上运输车；5. 每个垃圾站点的垃圾不允许分两次运输，而且也只需要一辆铲车。6. 假设运输车、铲车从A垃圾站到B垃圾站总走最短路线；7. 任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直角边之和；8. 如果车可以跑第二趟，中间无休息时间；9. 假设铲车、运输车载工作途中不发生意外也不遇到意外；10. 所有运输车和铲车均从第38号点出发，且最后均回到38号点；四、符号说明1、子点：本点的下一点； 2、Spend：运费； 3、Time：时间消耗； 4、|A|：A点横

10、纵坐标之和，；5、垃圾集中点在后面用顶点表示6、vi：第i个顶点7、vi.X：第i个顶点的X坐标；vi.Y表示第i个顶点的Y坐标；8、vi.laji：第i个顶点上有的垃圾重量，单位是吨；9、Lij:顶点i到顶点j的距离；10、sumi:顶点i的横纵坐标之和；11、访问一个顶点表示把它的垃圾装上车；12、用到的相关定义 设 G = (V, E) 是连通无向图,(1) 经过 G的每一个顶点正好一次的路,称为 G的一条哈密顿路或 H路;(2) 经过 G的每一个顶点正好一次的圈,称为 G的一条哈密顿圈或 H圈;(3) 含 H圈的图称为哈密顿图或 H图.|A| A点横纵坐标之和|B| B点横纵坐标之和|

11、A-B| 表示A,B两点之间的距离Ta 表示A点所在地的垃圾量cost：运费；time：时间消耗；装的足够多 运输车当前的载重离限载不大于0.55吨(垃圾点的最小垃圾量)序数号 所在点的编号四、模型分析及建立模型4.1 问题分析这是图论中的一个遍历问题。由于运输车的载重与时间的约束，它不再是最小树能解决的问题，而是森林，即包含了多个树的图。每一个树用一辆车去把其上面的垃圾运输回来，只要时间足够，同一辆车可能运输不止一棵树的垃圾。问题就变成了，在一个森林中，找到这样一些树，使其能用尽可能少的车遍历完所有顶点，且这些树构成哈密顿圈。将垃圾集中点抽象成坐标平面上的点，该点具有两个属性，即位置属性和重

12、量属性：城市抽象成一个3020的一个坐标方格网络。该模型符合以上模型假设。垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，更具具体问题设计出随即下山法，用计算模拟搜索，可以搜寻到令人满意的可行解 4.11先注意分析两点的情况，设两点分别为A(x1,y1),b(x2,y2)主要有以下两种情况：1. A,B明显有先后次序-递减状态（如图1）图1不妨设x1x2, y1y2,不难看出A在B的后方,即A比B远。对于前方参考点O,要将A,B对应垃圾点的垃圾全部取回再返回O,一共有三种方式：1) OAO, OBO单独运输。这种情况下，总的路程消费等于空载运行费用(0.4元/公里)与装

13、载时运行费用（1.8元/公里吨）的总和。所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值再加上在A,B两点停留的时间(每个垃圾点上停留了10分钟，1/6小时)，于是有：2） OABO 先远点再近点，即先空载至最远处，装完A点垃圾后再返回至B,再回O点，有：3） OBAO 先近点在远点，即先装B点垃圾，然后载着B点的垃圾奔至A点，再回O点，有： 比较以上三种情况，远近点的遍历顺序，可以看出，“先远后近”绝对比“先近后远”在花费钱的数量上要少的多，省出1.8|A-B|2Tb这部分的钱主要是车载着B点的垃圾奔到A点再返回B点。而又注意到两者的时间花费是相等的。所以在其余同等的情况下选

14、择“先远后近”。考虑到时间上单独运输比其余的两种运输要大的多，多一一倍，而且花费的钱仍不比“先远后近”省，还多了0.4|B|，所以一般情况下，不采用单独运输。4.12 A，B两点没有明显先后顺序。 -并邻状态（如图2）图2还是一共有两种情况： 1）OAO, OBO单独运输。这种情况下，总的路程消费等于空载运行费用（0.4元/公里）与装载时运行费用（1.8元/吨公里）的总和。所需的总时间等于车辆所走过的总路程与速度（35公里/小时）的比值再加上再A,B两点停留的时间（每个垃圾点上停留了10分钟，1/6小时），于是有：2） OABO或OBAO先空载到A或B，即先空载到其中的一个点，装完A（B）点的

15、垃圾再返回B（A），再回到O点，有： -1通过上面两种方式的比较，第1种遍历的费用少，但时间稍多。综合分析，由于时间可调，我们选择费用少的，时间稍多的遍历，即第1种方式。两点选择趋势的讨论。 （如图3）图3由图中看到B,C两点没有明显的先后顺序，属于并邻点。因为当运输车载重行驶时费用会成倍的增长，比其空载时所花费用要大的多，所以排除ABC或ACB这样的一次经过3点的往返路线，仅选择B,C中的某一点与A完成此次运输，将另一点留到下次。那么A点选择B还是C呢？不妨假设|B|C|,即B点离原点的距离比C点的更远，因为A在B,C之后，所以也就是B点离A点更近。这样，此次的运输我们更趋向于选择AB,因为

16、就这三点而论，A无论是选B还是C，三点的垃圾总要运完，所以花费的钱是一样的。但选择AB下次运输车运C点垃圾时就无需跑的更远。4.2 关于垃圾点的垃圾是否一次清除的讨论由假设4知，每天的垃圾必须清除完毕，全部运往37点。这里说的一次清除问题不是指一天，而是指当一辆运输车已经装载了足够多的垃圾，不能完全清理下一个垃圾点的时候，车在下一个站点停还是不停的问题。我们认为前者更好，就是车在装的足够多的情况下应该直接返回原点（37点）。这是因为对于下一垃圾点(假设为A点)内的垃圾而言，无论是一次装完还是分两次装完，将它们运回所花费用是恒定的。整体而言，两者花费的钱是相等的，但分两次装要多花10分钟的装车时

17、间，所以选择前者。综上所述，得出搜索的基本原则：1.在两点递减的情况下，不采用单独运输，选择“先远后近”，2.不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱； 3.车在装的足够多的情况下应该直接返回原点（37点）；4.每条线路的搜索都由未搜点中的最大值开始。五、模型的求解5.1 问题1的求解在不考虑铲车的情况下，运输车的最优路线如下：（见图4）综合两点的分布情况与遍历路线分析，先空载至最远点，即哈密顿距离（横纵坐标和）最远点，如果它没有被访问，则访问它。然后试着返回，途中找它的子点，即没有被访问过的哈密顿距离且车能装下其垃圾的顶点，找到后，访问子点：再以子点为本点，以同样的方式找子

18、点，直到没有子点可找，或车不能装下找到的子点为止。这样就将图分成了多个哈密顿圈。图4对上图中的结果，可以在不改变最佳哈密顿圈且考虑到车载量的约束的基础上改进哈密顿圈，可得下表路线：途经顶点垃圾量（吨）耗时A：28-26-21-25-195.73小时02分B：30-29-275.32小时48分C：36-23-33-325.52小时46分D：34-17-16-252小时07分E：24-18-35-205.22小时22分F：14-31-5-65.851小时46分G：15-13-7-45.62小时04分H：12-8-35.551小时30分I：11-9-141小时30分J：22-103.31小时23分表

19、1运输耗时通过表1与图4，得一下两种车辆分配与路线运输车路线时间总时间1A3小时02分3小时02分2B2小时48分2小时48分3C2小时46分2小时46分4D2小时07分4小时11分G2小时04分5E2小时22分4小时06分F1小时46分6H1小时20分4小时13分I1小时30分J1小时23分表2 运输线路时间安排1运输车路线时间总时间1A3小时02分3小时02分2B2小时48分2小时48分3C2小时46分4小时06分H1小时20分4J1小时23分3小时30分D2小时07分5E2小时22分3小时52分I1小时30分6G2小时04分3小时50分F1小时46分表3 运输车的调度方案经比较分析表2中

20、的路线时间安排更为合理。我们算出所需总费用为2339.05元。5.2 问题2的求解当加入铲车后, 因为铲车的空载费用为0.4元/小时，铲车装入垃圾后为1.8元/公里小时，我们应该让铲车将就运输车。若改变一条线,则会造成几公里的误差,甚至十几公里的误差,这一项的数目就很大。若是铲车跟随运输车,则即使路线误差大一点,但所需费用也不会变得很大，故我们以第一个方案的路线为准。这时我们只要保证前一条线路的末节点,与后一条线路的首节点的路程差分别相加之和最小即可。根据这一思路，我们利用模拟退火方法，设一个结构数组变量,他有11个元素(代表11条元素)。其中每个元素里面有两个结构成员,这样一个元素就代表一条

21、线路，对这11个元素进行排列,这样每一个排列就是一个线路方案，这样便能通过排列,遍历每种方案，就求出最优解。再考虑了最短路径的情况下，由于要考虑和各车在时间地衔接，以及尽量要在规定的时间内作完，我们进行相应的调整。这部分由于考虑到计算复杂性，我们用手工调整，由于前面有最短路径的保证，我们调整的结果接近最优解。 车次发车时间线路线内时间110点A11点06分-0点11.5分E0点22分-1点21.5分D1点50.5分-3点14分210点B11点09分-11点57分G0点06分-1点11.5分F2点11分-3点12分310点C11点03分-0点05.5分J0点14.5分-0点45分H1点26分-2

22、点12.5分I2点33分3点25.5分表4：铲车的调度运输车线路发车时间到达该线起点时间从该线返回时间1A10点11点06分0点11.5分2B10点11点09分11点57分3C10点11点03分0点05.5分H0点45.5分(等待40.5分)2点12.5分4J11点43分0点14.5分0点45分D1点59.5分3点14分5E11点31分0点22分1点21.5分I2点33分3点25.5分6G11点24分0点06分1点11.5分F2点11分3点12分表5运输车的调度5.3 问题3的求解对于问题3 中4吨、6吨和8吨3种型号的运输车，本文先通过计算机分别运算出只使用一种车时的最优解，然后将三者的运算

23、结果人工优化，从而得出最终解。仅使用4吨、6吨和8吨的最优路径如下图4、5、6所示：1）只使用4吨运输车时：图42）只使用6吨运输车时：图53）只使用8吨运输车时：图64）最终优化后的路径：图7对图7进行人工优化得出下表6中运输车的调度方案：车次吨数线路发车时间到该线起点时间从该线返回时间18A10点11点06分0点29分D1点12分2点03分3点21.5分28B10点11点09分0点38分C1点18分2点31分3点52.5分36E1点38分2点21.5分3点36分F2点56分3点39.5分4点54分46G0点17分0点47分1点23.5分H3点42分4点03分4点42.5分54I0点58分1

24、点19分1点48分表6 运输车的调度依据题2中建立的模型和人工的优化可得到铲车的调度方案如下表：车次出发时间线路线内时间回到O点的时间110点A11点06分-0点29分1点50分F0点36.5分-1点11.5分I1点19分-1点38分210点B11点09分-0点38分1点37分G0点47 分-1点23.5分31点18分C2点31分-3点2.5分4点50分H4点03分-4点42.5分41点12分D2点03分-3点21.5分5点03分E3点39.5分-4点54分表7 铲车的调度六、模型的优缺点分析优点：该模型算法简单容易实现，易懂；缺点：我们较多的采用人工方法，导致精度下降，有待改善。七、模型的推

25、广及应用本文主要运用下山法原理，在回收垃圾的过程中，让重量由远到近逐渐增加，从而达到节约成本的目的。如果我们从相反方向来看，似乎可以得到一个上山法的原理，我们可以将其运用到货物的配送中，由近及远逐渐减轻重量，同时，由近及远寻找下一个最优点，从而达到实现最优路径，节省更多的成本。参考文献：1.戴朝寿，孙世良 数学建模简明教程 北京：高等教育出版社2.叶其孝 大学生数学建模竞赛辅导教材 湖南：湖南教育出版社3.赵静，但琦 数学建模与数学实验 北京：高等教育出版社4.刘育兴，钟剑 赣南师范学院学报2006年03期5谭浩强C程序设计 清华大学出版社出版附录（C+）运算程序：#include#inclu

26、de#define M 37#define N M-1int sumM;int sortM;int visitM;int final=0;int LMM;int m,vmin,u;double weight;typedef struct nodedouble laji;int X;int Y;node;node vM;void around(int w) int i,min=1000; for(i=1;i=N;i+) if(Lwimin & vi.X=vw.X & vi.Y=vw.Y & visiti=0) min=Lwi; vmin=i; if(u!=vmin) weight=weight+

27、vvmin.laji; if(weight=6) visitvmin=1; coutvmin-; u=vmin; around(vmin); else cout#; else cout#;void main() int maxindex;v1.laji=1.50;v1.X=3;v1.Y=2;v2.laji=1.50;v2.X=1;v2.Y=5;v3.laji=0.55;v3.X=5;v3.Y=4;v4.laji=1.20;v4.X=4;v4.Y=7;v5.laji=0.85;v5.X=0;v5.Y=8;v6.laji=1.30;v6.X=3;v6.Y=11;v7.laji=1.20;v7.X=

28、7;v7.Y=9;v8.laji=2.30;v8.X=9;v8.Y=6;v9.laji=1.40;v9.X=10;v9.Y=2;v10.laji=1.50;v10.X=14;v10.Y=0;v11.laji=1.10;v1.X=17;v1.Y=3;v12.laji=2.70;v2.X=14;v2.Y=6;v13.laji=1.80;v3.X=12;v3.Y=9;v14.laji=1.80;v4.X=10;v4.Y=12;v15.laji=1.40;v5.X=19;v5.Y=9;v16.laji=1.50;v6.X=2;v6.Y=16;v17.laji=0.80;v7.X=6;v7.Y=18;v18.laji=1.50;v8.X=11;v8.Y=17;v19.laji=0.80;v9.X=15;v9.Y=12;v20.laji=0.60;v10.X=7;v10