垃圾运输问题建模论文.docVIP

垃圾运输问题 摘要 垃圾运输问题是一个寻求最优路径的优化问题。在解决第一问运输车的调度问题时，本文首先确立了一种构思，即缩短运输车的总路程。在此基础上加大空载路程，缩短载重路程，并做到运输车的数量尽可能的少。 在第一问中，根据以上几点要求，我们进一步将其深入讨论得出必须使运输车空载至最远点，运用下山法的原理逐步找出下一个最合适的点，此时只需满足横纵坐标都逐渐减小，而所取点垃圾总量不大于6吨，最终通过运算我们得出了10条线路。但是其中有几条线路用时较短，我们对其进行了人工优化，将用时较短的路线进行合并，最终得出只需6辆运输车。 在第二问铲车调度的问题中，本文延续并使用了第一问的结果和上述思想。在保持运输车线路不变的情况下，本文估算了一下铲车由第一个工作点开始到最后一个工作点结束的同时再除以4小时，得出最少要三辆铲车。将10条运输线路概括为3个部分，原则是使这3个部分的每个部分内铲车跑的总路程最短，通过人工的运算和时间的对照，我们得出了最终结果。 在第三问中，三种型号车的加入增加了解题的灵活性，此时我们的构思依然是缩短运输车的总路程，加大空载路程，而利用8吨车去尽可能的解决远处的垃圾显然可以在不增加总路程的情况下更加缩短空载路程。 我们的结果如下： 第一问，求得需要运输车6辆，所需总费用为2339.05元，调度方案见正文表5，最优路径见正文图4。 第二问，求得需要铲车3辆，所需总费用为142.8元，调度方案见正文表4。 第三问，求得需要铲车4辆和运输车5辆，所需总费用为2508.63元，运输车和铲车的调度方案见表6、表7，运输车的最优路径见图8。 关键词：最优路径、哈密顿圈、下山法、模拟退火法 一、阐述题目 为了美化城市环境，环卫部门每天夜里都要对分布在城区各街道的定点垃圾及时进行处理。假设某城区有３６个垃圾集中点，每天都要从垃圾处理厂（第３７号节点）出发将垃圾运回。现有一种载重 6吨的运输车每个垃圾点需要用１０分钟的时间装车，运输车平均速度为40公里／小时（夜里运输，不考虑塞车现象）；每车每平均工作 4小时运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴。运输车行走拐弯的时间，路上的意外事故耽搁的时间忽略；夜里运输，不考虑塞车现象；垃圾只在晚上运输，基本保证运完后，当天不会再有新的垃圾产生； 每个垃圾点的垃圾必须每天清除完，不允许滞留；5. 每个垃圾点都在路口了，便于垃圾的集中运输；6. 假定街道方向均平行于坐标轴，只要和坐标轴平行就有路存在；7. 每个垃圾点无论是否处理完全都需要10分钟装车时间；8. 假设卸垃圾及倒车均在分钟内完成；9. 车在装的足够多的情况下应该直接返回原点；）20的一个坐标方格网络。该模型符合以上模型假设。垃圾运输问题最终可以归结为最优路径有哪些信誉好的足球投注网站问题，但注意到此图为森林而不是树，更具具体问题设计出随即下山法，用计算模拟有哪些信誉好的足球投注网站，可以搜寻到令人满意的可行解 4.11先注意分析两点的情况，设两点分别为A(x1,y1),b(x2,y2) 主要有以下两种情况： 1. A,B明显有先后次序--递减状态（如图1） 图1 不妨设x1x2, y1y2,不难看出A在B的后方,即A比B远。对于前方参考点O,要将A,B对应垃圾点的垃圾全部取回再返回O,一共有三种方式： OAO, OBO 单独运输。这种情况下，总的路程消费等于空载运行费用(0.4元/公里)与装载时运行费用（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点。而又注意到两者的时间花费是相等的。所以在其余同等的情况下选择“先远后近”。考虑到时间上单独运输比其余的两种运输要大的多，多一一倍，而且花费的钱仍不比“先远后近”省，还多了0.4|B|，所以一般情况下，不采用单独运输。 4.12 A，B两点没有明显先后顺序。 --并邻状态（如图2） 图2 还是一共有两种情况： 1）OAO, OBO 单独运输。这种情况下，总的路程消费等于空载运行费用（0.4元/公里）与装载时运行费用（1.8元/吨公里）的总和。所需的总时间等于车辆所走过的总路程与速度（35公里/小时）的比值再加上再A,B两点停留的时间（每个垃圾点上