新版数学建模—垃圾运输问题的求解及源代码

垃圾运输问题*信息工程学院计算机应用专业*摘要：通过分析垃圾站点之间的分布位置，建立了垃圾运输问题的解决模型。首先，在给定的数据中制作xy散布图，根据问题设定提出自己的假设条件。其次，结合现有模型，研究和证明垃圾点之间的位置分布关系，决定最基本的行驶路线原则。然后，制作c语言程序，利用计算机进行算法模拟，(1)不考虑叉车而使运费最小，(2)考虑叉车在某个模型中的最佳解，(3)合理地分配不同运费量的运输车，安排成总费用最小根据我们决定的解题思路，最终我们得到了如下一系列的可行解。第一题，所有运输费用为2340.97元，总时间为21.95小时第二题：要求需要三辆叉车第三题：求总运费为2323.77元。 其中8吨的车有4辆，6吨的车有3辆，4吨的车有3辆。具体路线图，车辆调度图见正文部分。本文讨论的解题方法模型简单，结果只是接近最优解的可行解，因此我们可以采用更智能的算法等，有很大的改善空间。关键词：计算机算法仿真优化1 .问题的重新陈述某镇有37个垃圾堆积处，每天从垃圾处理场(第38号节点)送回垃圾。 目前有载重6吨的运输车。 每个垃圾场需要10分钟装车，运输车平均速度为40公里/小时(不考虑夜间运输、堵车现象)。 一辆台车每天平均工作四小时。 运输车的重负荷运费为2元/吨公里的运输车和垃圾用叉车的无负荷费用为0.5元/公里，另外，假设街道方向与坐标轴平行。 请提出令人满意的运输调度方案和计算程序。问题：1 .运输车应如何安排(需要投入多少辆运输车，每辆车的安排方案，运营费用)。2 .应如何安排叉车(需要多少台叉车、每台叉车的行驶路线、运营费用)。如果有载重4吨、6吨、8吨的运输车，怎么安排？2 .模型的基本前提和符号说明(1)基本假设1 .忽略车辆转弯时的时间损失。2 .车辆在任意两个站点的中途不停车，保持稳定的速度。3 .如果与坐标轴平行，就有街道。4 .与垃圾量无关，10分钟内可装载运输车。每个垃圾站点的垃圾只能搬运一辆搬运车。6 .假定运输车、叉车从a垃圾站到b垃圾站走最短路线。7 .任何两个垃圾站之间的最短路线是两个垃圾站的连接在斜边上的直角三角形的两个直角边之和。8 .建设在运输垃圾的过程中没有新的垃圾。9 .假设叉车、运输车工作途中发生事故不会遇到事故10 .各垃圾站每天的垃圾量比较稳定。(2)符号的说明|A|表示从a点到原点的距离，为恒正|B|表示从b点到原点的距离，常数为正|A-B|表示a、b两点间的距离、恒正Ta表示a点所在地的垃圾量成本：运费time :消耗时间足以装载的运输车的当前装载距离在0.55吨以下(垃圾点的最小垃圾量)具有序号的点的编号3 .建立模型垃圾运输问题最终可归结为最优路径搜索问题，但发现该图为森林而不是树木，无法直接应用Krusal、Prim等现有算法，因此根据具体问题设计随机下山法，通过计算仿真进行搜索，找到令人满意的可行解首先注意到两点的情况下，将两点分别设为A(x1，y1 )、B(x2，y2 )。主要有两种情况：1.a、b显然有优先权。 -减少状态(图1 )如果设为x1x2、y1y2，则a比b的后方，也就是说a比b远。 对于前方的基准点o，要回收与a、b的垃圾点对应的所有垃圾并返回o，有以下3种方法1.O-A-O，O-B-O单独运输。 在这种情况下，总行程消耗等于空载运行费用(0.4元/公斤)和装载运行费用(1.8元/公斤)之和。 所需的总时间是车辆行走的总路程和速度(40公里/小时)之比，再加上停留在a、b两点的时间(在垃圾点停留10分钟、1/6小时)，如下所示cost=0.4*|a|1.8 *|a|* ta0.4*|b|1.8 *|b|* TBTime=(2*|A| 2*|B|)/40 1/6*22. O-A-B-O先从远点到近点，即最远无负荷，放入a点的垃圾后返回b点，返回o点，有以下情况cost=0.4 *|a|1.8 *|a-b|* ta 1.8 *|b|* (TATB )=0.4*|A| 1.8*|A|*Ta 1.8*|B|*TbTime=2*|A|/40 1/6*23. O-B-A-O首先，放入近点为远点，即b点的垃圾，放上b点的垃圾跑到a点，返回o点，如下所示cost=0.4 *|b|1.8 *|a-b|* TB 1.8 *|a|* (TATB )=0.4 *|b|1.8 *|a|* ta 1.8 *|b|* TB 1.8 *|a-b|*2* TBTime=2*|A|/40 1/6*2比较以上3种情况可知，远近点的扫描顺序中，“远远后近”比“近远后远”的费用少，节省了1.8*|A-B|*2*Tb的费用的主要是车载的b点的垃圾向a点行进而返回b点。 还注意到两者的时间是一样的。 因此，如果馀数相等，请选择“先远后近”。 时间上的单独运输比剩下的两种运输要大得多，多一倍，而且费用比“接近先前”的省多0.4*|B|，所以一般不采用单独运输。二. a、b两点没有明显的优先次序。 -邻接状态(图2 )有三个案例1.O-A-O，O-B-O单独运输。 在这种情况下，与a、b两点具有优先顺序情况完全相同，即cost=0.4*|a|1.8 *|a|* ta0.4*|b|1.8 *|b|* TBtime=(2*|A| 2*|B|)/40 1/6*22.O-A-B-Ocost=0.4 *|a|1.8 *|a-b|* ta 1.8 *|b|* (TATB )-1Time=(|A| |A-B| |B|)/40 1/6*23.O-B-A-Ocost=0.4 *|b|1.8 *|a-b|* TB 1.8 *|a|* (TATB )-2Time=(|A| |A-B| |B|)/40 1/6*2相比之下，由于相邻状态下的单独运输费用最少，因此对于不需要时间的相邻两点，采用单独运输最节约了费用。 将1式和2式的减法除以1.8，得到如下的判定式| a-b|* (ta-TB ) (TATB ) * (|b|-|a|-3 )上式0时，选择0-A-B-O上式0时，选择O-B-A-O上式=0时，可任意选择上述两条路线。3.2点选择倾向的探讨。 (图3 )从图中b、c这2点没有明显的优先顺序，属于邻接点。 运输车装载行驶的话费用会倍增，比无负荷时要多，因此排除A-B-C和A-C-B这样一次通过3点的往返路线，只选择b、c中的某点和a完成这次运输，另一点留在下面。 a分是b还是c？|B|C|，也就是说，假设b点离原点比c点远。 因为a在b、c之后，所以b点接近a点。 这样，这次运输有选择A-B的倾向。 关于这三点，a是b还是c，三点的垃圾一定会被运送，所以费用是一样的。 但是，选择A-B后，下一辆搬运车搬运c点的垃圾时，没有必要再跑了。4 .垃圾点垃圾是否一次性被除去的研究(6吨车例)从假设2可以看出，每天的垃圾一定要清除，一共运到37点。 在这里所说的一次清扫问题，不是一天，而是在搬运车上积满足够的垃圾，无法完全清扫下一个垃圾场所的时候，车在下一个网站上“停不停”的问题。 例如，一辆运输车选择了30-26-18-35-20的路线(即，将空车转向30，整理30点的垃圾，然后转向26、18、35、20 )，从20返回时车已经装载了5.8吨的垃圾，还有0.2吨(小于垃圾点垃圾量的最小值0.5 ) 二十点钟以下还有很多地方，一定装不下地方的垃圾。 这辆车是直接37点回来，还是一直开到车满为止？前者的判断比较好的是，如果汽车装得够多的话，就应该直接回到原点(37点)。 这是因为对于下一个垃圾点(假设为a点)内的垃圾，无论一次装载还是两次装载，送回它们的费用都是一定的，等于1.8*Ta*|A|。 总的来说，两者花的钱是一样的，但是分两次安装需要10分钟以上，请选择前者。综上所述，获得检索的基本原则1 .减少两点时，不采用单独运输2 .其馀韵同等时选择“先接近远”3 .在不要求时间情况下，对于相邻的2点，通过单独输送方式最节约的一般通过式3 )进行判断4 .车辆装载充足时，应直接返回原点(37点)5 .每次布局和线路搜索可以从剩馀未搜索点中的最大值开始。4 .模型求解问题1 .不考虑叉车的。首先，根据问题给出的数据制作散布图总运营费用2345.4元，总时间22.5小时，求解程序如附录2所示，运输车最佳路线如下图所示表：线路的费用和所需时间站点编号空费需要时间1号线0-30-29-27-3-018.42.3 2/3二号线0-28-26-32-25-5-017.62.2 5/6东京地铁3号线0-36-23-33-21-016.82.1 2/3四号线0-24-18-35-15-013.61.7 2/35号线0-34-17-16-2-0121.45 2/3六号线0-20-11-10-011.21.4 1/2七号线0-19-13-8-010.81.35 1/2八号线0-14-7-4-1-08.81.1 1/2九号线0-22-08.41.05 1/610号线0-12-9-081/311号线0-31-6-06.80.85 1/3问题2 .叉车加入后的讨论加入叉车后，我们应该把叉车放在运输车上。 叉车空载费用为0.4元/小时。 叉车装垃圾后1.8元/公里时间。 改变线的话会产生几公里的误差，甚至是十几公里的误差。 这个数量很多。 叉车坐在运输车上，线的误差很大，但是所需的费用也不大。 因此，我们以第一方案的路由为基准，将前一路由的最后的节点与下一路由的最初的节点的距离差分别合计为最小即可。 根据该想法，设定结构阵列变量，他具有11个要素(代表11个要素)。 其中，各要素中有两个结构成员。 这个要素代表一条路线。 如排列这十一个要素，一个个排列成一条线路。 这样，通过排列，可以横穿所有的方案。 求最优解。 在考虑最短路径的情况下，与各车在时间上联系，尽量在规定的时间内完成，考虑到这一点进行调整。由于该部分考虑到计算的复杂性而手工调整，因此先有最短路径的保证，调整结果接近最佳解。程序代码附录3【源代码】程序的执行结果请参照附录3【结果】表：行驶路线和所需时间铁路时间0-30-29-27-3-02.3 4/60-28-26-32-25-5-02.2 5/60-36-23-33-21-02.1 4/60-24-18-35-15-01.7 4/60-34-17-16-2-01.45 2/30-19-13-8-01.35 1/20-20-12-9-01.0 1/20-11-10-00.7 1/30-31-6-00.7 1/30-14-7-4-1-00.55 4/613.5小时根据总时间和路线的时间，平均6小时的工作条件下需要3量的叉车，3台叉车的起点分别是36、31、28由于搬运车时速为40km/h，因此叉车的速度不需要为40km/h以上.如果速度不足40km/h，至少买一台叉车是重复的，所以最好多花钱买一台大功率的叉车。 为了保证晚上能做到我们可以同时做多条路，但是考虑到新的叉车费用，我们只要同时工作3台叉车，就能在规定的时间内完成。 总费用为81.6元。问题3 :有4吨、6吨、8吨三种运输车的时间表如果有4吨、6吨、8吨三种，应该尽量掌握8吨的汽车、远处的垃圾、远处的垃圾越多，之后的汽车的无负荷路线就越少，不考虑无负荷费用，只要把垃圾运到垃圾处理厂，其费用就不会变化的原则。同时，考虑到8吨、6吨、4吨的运输车费用问题，8吨的车不要太多。 在分析过程中，发现主要难以处理第