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

1、*垃圾运输问题信息工程学院计算机应用专业*天天快乐摘要： 本文通过对垃圾站点之间分布位置的分析，构造出解决垃圾运输问题的模型。首先，我们对所给数据绘制其xy 散点图，根据题设提出自己假设的条件，。其次， 结合已有的模型，对垃圾点之间的位置分布关系进行讨论及证明，从而确定最基本的行车路线原则。然后， 编写 c 语言程序，利用计算机进行算法的模拟，从而搜索出各运输车辆的数量以及最佳的分配方案，使得 （1） 在不考虑铲车的情况下运输费用最少、（2） 考虑在有铲车的模型中的最佳解、（3） 对不同运输量的运输车进行合理分配调度，使得总费用最少。根据我们确定的解题思路，最终我们得到了一组可行解，如下：第一

2、问，求得全部的运输费用是2340.97 元，花费的总时间是21.95 小时；第二问：求得需要3 辆铲车；第三问：求得总的运输费用是2323.77 元。其中8 吨的车 4 辆， 6 吨的车 3辆， 4 吨的车 3 辆。具体的路线分配图，车辆调度图见正文部分。本文讨论的解题方法模型简单，得出的结果只是一个近似最优解的可行解，所以还有很大的改进空间，比如我们可以采用更加智能的算法等。关键词：计算机算法模拟优化1 问题的重述某城区有37 个垃圾集中点，每天都要从垃圾处理厂（第 38 号节点） 出发将垃圾运回。现有一种载重6 吨的运输车。每个垃圾点需要用10 分钟的时间装车，运输车平均速度为40 公里小

3、时（夜里运输，不考虑塞车现象）；每台车每日平均工作4 小时。运输车重载运费 2 元 / 吨公里；运输车和装垃圾用的铲车空载费用0.5 元 / 公里； 并且假定街道方向均平行于坐标轴。请你给出满意的运输调度方案以及计算程序。问题：1. 运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）2. 铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用）3. 如果有载重量为4 吨、 6 吨、 8 吨三种运输车，又如何调度？2 模型的基本假设与符号说明（一）基本假设1车辆在拐弯时的时间损耗忽略。2车辆在任意两站点中途不停车，保持稳定的速率。3只要平行于坐标轴即有街道存在。4无论垃圾

4、量多少，都能在十分钟内装上运输车。5. 每个垃圾站点的垃圾只能由一辆运输车运载。6. 假设运输车、铲车从 A垃圾站到B垃圾站总走最短路线。7. 任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直角边之和。8. 建设在运输垃圾过程中没有新垃圾入站。9. 假设铲车、运输车载工作途中不发生意外也不遇到意外；10. 各垃圾站每天的垃圾量相对稳定。（二）符号说明|A| 表示A点到原点的距离，恒正|B| 表示B点到原点的距离，恒正|A-B|表小A,B两点之间的距离，恒正Ta 表示A点所在地的垃圾量cost :运费；time ：时间消耗；装的足够多运输车当前的载重离限载不大于0.55吨（垃圾点

5、的最小垃圾量）序数号所在点的编号3 .模型的建立垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，不能直接套用Krusal , Prim等现成算法，于是根据具体问题设计出随机下山法，用计算模拟搜 索，可以搜寻到令人满意的可行解。先注意到两点的情况，设两点分别为A（x1,y1）,B（x2,y2）。主要有以下两种情况：一. A,B明显有先后次序。-递减状态（如图1）不妨设x1x2, y1y2,不难看出A在B的后方，即A比B远。对于前方参考点 O,要将A,B 对应垃圾点的垃圾全部取回再返回。，一共有三种方式：1. O-A-O, O-B-O单独运输。这种情况下，总的路程消费等于空

6、载运行费用（0.4元/公里）与装载时运行费用（1.8元/公里吨）的总和。所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值再加上在 A,B两点停留的时间（每个垃圾点上停留了 10分钟，1/6小时），于 是有：Cost = 0.4*|A| + 1.8*|A|*Ta + 0.4*|B| + 1.8*|B|*TbTime = （2*|A| + 2*|B|）/40 + 1/6*22. O-A-B-O先远点再近点，即先空载至最远处，装完A点垃圾后再返回至B,再回。点，有：Cost = 0.4*|A| + 1.8*|A-B|*Ta +1.8*|B|*（Ta+Tb）=0.4*|A| + 1.8

7、*|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|*（Ta+Tb）=0.4*|B| + 1.8*|A|*Ta + 1.8*|B|*Tb + 1.8*|A-B|*2*Tb Time = 2*|A|/40 + 1/6*2比较以上三种情况，远近点的遍历顺序，可以看出，“先远后近”绝对比“先近后远”在花费钱的数量上要少的多，省出 1.8*|A-B|*2*Tb这部分的钱主要是车载着B点的垃圾奔到A点再

8、返回B点。而又注意到两者的时间花费是相等的。所以在其余同等的情况下选择“先远后近”。考虑到时间上单独运输比其余的两种运输要大的多，多一一倍，而且花费的钱仍 不比“先远后近”省，还多了 0.4*|B| ,所以一般情况下，不采用单独运输。A, B两点没有明显先后顺序。-并邻状态（如图2）1. O-A-O, O-B-O单独运输。这种情况下，跟 A,B两点有先后顺序中的情况完全相同，即有：Cost = 0.4*|A| + 1.8*|A|*Ta + 0.4*|B| + 1.8*|B|*Tbtime = (2*|A| + 2*|B|)/40 + 1/6*22. O-A-B-OCost = 0.4*|A|

9、+ 1.8*|A-B|*Ta + 1.8*|B|*(Ta+Tb)- 1 Time = (|A| + |A-B| + |B|)/40 + 1/6*23.O-B-A-OCost = 0.4*|B| + 1.8*|A-B|*Tb + 1.8*|A|*(Ta+Tb)- 2 Time = (|A| + |A-B| + |B|)/40 +1/6*2相比之下，清晰可见并邻状态下的单独运输所花的费用最少，所以在不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱。用式与2状相减除以1.8,得到如下判断式：|A-B|*(Ta-Tb) + (Ta+Tb)*(|B|-|A|)-上式 A-B-O;上式 0 时，

10、选 O-B-A-O;3. =0时，任意选上述两路线。两点选择趋势的讨论。（如图3）a图三由图中看到B,C两点没有明显的先后顺序, 会成倍的增长，比其空载时所花费用要大的多， 过3点的往返路线，仅选择 B,C中的某一点与 点选择B还是C呢？不妨假设|B|C|,即B点离原点的距离比属于并邻点。因为当运输车载重行驶时费用所以排除A-B-C或A-C-B这样的一次经A完成此次运输，将另一点留到下次。那么 AC点的更远，因为A在B,C之后，所以也就是B点离A点更近。这样，此次的运输我们更趋向于选择 A-B,因为就这三点而论， A无论是 选B还是C,三点的垃圾总要运完，所以花费的钱是一样的。但选择 A-B后

11、，下次运输车 运C点垃圾时就无需跑的更远。四.关于垃圾点的垃圾是否一次清除的讨论（以 6吨车例）由假设2知，每天的垃圾必须清除完毕，全部运往37点。这里说的一次清除问题不是指一天，而是指当一辆运输车已经装载了足够多的垃圾，不能完全清理下一个垃圾点的时候，车在下一个站点“停还是不停”的问题。例如，一辆运输车选择了30-26-18-35-20 的路线（即先将空车开往 30,清理装载30点的垃圾，然后依次到 26, 18, 35, 20）,它从20 返回时车已经装载了 5.8吨垃圾，仍可以装 0.2吨（小于垃圾点垃圾量的最小值0.5,称这种情况为“装的足够多”）。在20点下方仍有不少的点，但肯定不能

12、将下面的任意点的垃圾 装完，那么此车是直接返回37点呢，还是继续装直至车装满为止呢？我们判断前者更好，就是车在装的足够多的情况下应该直接返回原点（37点）。这是因为对于下一垃圾点（假设为A点）内的垃圾而言，无论是一次装完还是分两次装完，将它们运回所花费用是恒定的，等于1.8叮a*冏。整体而言，两者花费的钱是相等的，但分两次装要多花10分钟的装车时间，所以选择前者。综上所述，得出搜索的基本原则：1 .在两点递减的情况下，不采用单独运输；2 .在其余同等的情况下选择“先远后近” ；3 .不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱；一般情况下用式h全w 金 ia mma a a a

13、u s &i a &s&aAaa&a & q* IIp, j. _ _ =_ = _ M110+ :1 *_i H _ _ _Lh+ :|i./?.正:4pPj-r -a*ii1h| 上 ；. !L. .111Il1h* : :-.L . . . uL. 1!T ii.I111iii *i14111一151Q15202530图四求得总运营费用为 2345.4元，总时间为22.5小时，求解程序如附录二，运输车的最优 路线如下图所示：图五表一：线路的费用和所用时间站点序号空载费用所花时间T线0-30-29-27-3-018.42.3+2/3二号线0-28-26-32-25-5-017.62.2+5

14、/6三号线0-36-23-33-21-016.82.1+2/3四号线0-24-18-35-15-013.61.7+2/3五号线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/6H/线0-12-9-081+1/3H线0-31-6-06.80.85+1/3问题二.铲车加入后的讨论当加入铲车后，我们应该让铲车将就运输车 ，因为铲车的空载费用为 0.4元/小时.铲车 加入垃圾后为 1.8元/公里小时.若改变一条线

15、，则会造成几公里的误差，甚至十几公里的误 差,这一项的数目就很大.若是铲车将就运输车，则即使路线误差大一点，但所需费用也不会 变得很大.故我们以第一个方案的路线为准.这时我们只要保证前一条线路的末节点，与后一条线路的首节点的路程差分别相加之和最小即可.根据这一思路.我们设一个结构数组变量，他有11个元素（代表11条元素）.其中每个元素里面有两个结构成员，这样一个元素就代表一条线路.对这11个元素进行排列，这样每一个排列就是一个线路方案.这样便能通过排列，遍历每种方案.就求出最优解.再考虑了最短路径的情况下，由于要考虑和各车在时间地衔接， 以及尽量要在规定的时间内作完，我们进行相应的调整。这部分

16、由于考虑到计算复杂性，我们用手工调整，由于前面有最短路径的保证，我们调整的结果接近最优解。程序代码如附录三【源码】程序运行结果见附录三【结果】表二：行走线路和所用时间线路时间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小时根据总时间和个线

17、路的耗时，依平均工作6小时为条件得出需要三量铲车，三辆铲车的 起始点分别为36 , 31 ,28;因为运输车时速为 40km/h,则铲车速度无须大于 40km/h.若速度小于40km/h,则至少要多买一辆铲车，这样造成重复，故最好多花点钱买大功率 的铲车.为了保证能在晚上干完，我们可以多条路同时干，但考虑到新加铲车费用，我们只让三辆铲车同时工作，就能在 规定时间干完。总费用为81.6元。问题三：存在4吨，6吨，8吨三种运输车时的调度若存在4吨,6吨,8吨三种，我们应把握的原则是：尽量让8吨的车，拉远处白垃圾，远处 垃圾拉得越多，以后车的空载路程就越少，而不考虑空载费用，只把垃圾运回垃圾处理厂

18、，它 的这部分费用不变.同时，我们考虑到 8吨,6吨,4吨的运输车费用问题，故8吨的车不宜太多.我们在分析 过程中，发现主要是第15点比较难处理，因此8吨的车应将这一点在 30那条线上一并处理.而象第2点，用6吨车单独拉一次太浪费，应用4吨车还有11,22这两条线也可改用 4吨车.51015202530国七运营总费用为：2325.8 其中运输费用是 2213.4 空载费用为112.4 求解程序如附录四：表三：线路所用时间和承载垃圾量线路时间垃圾量30-29-27-20-11-02.3+5/67.828-26-32-25-14-7-02.2+17.936-23-33-21-22-02.1+5/6

19、724-18-35-15-31-5-01.7+17.9534-17-16-2-01.45+2/3519-13-8-3-1-01.35+5/66.9512-9-01.0+1/34.110-00.7+1/61.56-00.7+1/61.34-00.55+1/61.2表四:运输车数量8吨56吨24吨3铲车路线:铲车跟随运输厂车行驶， 先行驶到远点、伴随运输车网回路行驶， 铲完一趟后就寻找该离铲车最近的另外一条运输线的起始点（运输车远端），然后再跟着运输车行驶。5 .模型优缺点分析然而，该问题在站点众多，运输半径较大的前提下，缺点就会显得尤为突出。首先是运输车载重的不足，当运输车的载重不能满足其中任一

20、点的垃圾量时， 模型就可能不能适用了， 该模型优点是算法简单容易实现，精度特别是后两个模型的精度不是很高 .前两问只要进行 穷举就能得出最优解.第三问的处理原则不算很精确 ，有待改进6 .模型的推广和应用该模型可以应用在很多方面，比如说货物运输、车辆分配等。7 .参考文献全国大学生数学建模竞赛 优秀论文汇编。中国物价出版社，2002宋兆基，徐流美等。MATLAB6.5科学计算中的应用。A#华大学出版社，20058 .附录附录一：垃圾点地理坐标数据表序号站点编号垃圾量T坐标（km）序号站点 编R垃圾量T坐标（km）xyxy111.503220151.40199221.501521321.2022

21、5330.555422221.80210441.204723231.40279560.850824241.601519651.3031125251.601514771.207926261.002017882.309627272.002113991.4010228281.00242010101.5014029292.10251611111.1017330301.20281812122.7014631311.9051213131.8012932211.30171614141.80101233331.6025715200.6071434341.2092016161.5021635351.509151

22、7170.8061836361.30301218181.50111737371.7081019190.90151238380.0000附录二【源码】 code clear x=3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30 0;y=2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 167 20 15 12 0;t=1.50 1.50 0.55 1.20

23、0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.60 1.500.80 1.50 0.80 1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.30 1.601.20 1.50 1.30 0.00;i=1:37;a=1:37;plot(x,y, *r)for ii=1:37k=int2str(ii); k=strcat( P ,k);text(x(ii),y(ii),k);endw=i;x;y;t;a;w(5,:)=0;jg=zeros(11,11);% ? ?11

24、i ? ?for i=1:20sum=0;j1=1；s=0;m=37;i3=37;for j=1:36if (w(2,j)+w(3,j)s&w(5,j)=0)s=w(2,j)+w(3,j);jg(i,j1)=w(1,j)；sum=w(4,j);m=j；else continue ;endendw(5,m)=1;j1=j1+1;while 1js=0;q=40;for k=1:36if (qw(2,m)-w(2,k)+w(3,m)-w(3,k)&w(2,m)w(2,k)&w(3,m)w(3,k)&(6-sum)w(4,k)&w(5,k)=0q=w(2,m)+w(3,m)-w(2,k)-w(3,k

25、);js=1;jg(i,j1)=w(1,k);i3=k;else continue ;endendw(5,i3)=1;sum=sum+w(4,i3);j1=j1+1;m=i3;if (w(2,i3)=0&w(3,i3)=0|js=0)breakendendendkcost=0;zcost=0;allcost=0;n=0;for u1=1:11for u2=1:11if jg(u1,u2)=0n=jg(u1,u2);else continueendzcost=zcost+w(4,n)*1.8*(w(2,n)+w(3,n);endn=jg(u1,1);kcost=kcost+0.4*(w(2,n)

26、+w(3,n);endallcost=zcost+kcostzcostkcosti=1:11;time=i;time(1,:)=0;n1=0;n2=0;n3=0;for u4=1:11for u5=1:11if jg(u4,u5)=0n1=jg(u4,u5);n2=n2+1;else continueendendn3=jg(u4,1);time(1,u4)=(w(2,n3)+w(3,n3)*2)/40;endn2time附录三 源码 clearx=3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 2

27、528 5 17 25 9 9 30 0;y=2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 1812 16 7 20 15 12 0;t=1.50 1.50 0.55 1.20 0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.601.50 0.80 1.50 0.80 1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.301.60 1.20 1.50 1.30 0.00;

28、r=1:37;%plot(x,y,*r);%for ii=1:37% k=int2str(ii);% k=strcat(P,k);% text(x(ii),y(ii),k);%endw=r;x;y;t;a=1:11;point=30 28 36 24 34 20 19 14 22 11 31;3 5 21 15 2 9 8 1 22 10 6;a;point(3,:)=0;s=80;p=80;天天快乐k=2;j1=0;j2=0;m=1;b=1:11;pai=b;pai(1,:)=0;for j=1:11if s=w(2,point(1,j)+w(3,point(1,j)&point(3,j)=

29、0 s=w(2,point(1,j)+w(3,point(1,j);else continueendendj1=j;point(3,j1)=1;pai(1)=point(1,j1);while m=w(2,point(1,i)+w(3,point(1,i)-w(2,point(2,j1)-w(3,point(2,j1)&point(3,i)=0p=w(2,point(1,i)+w(3,point(1,i)-w(2,point(2,j1)-w(3,point(2,j1);else continueendj2=i;point(3,j2)=1;pai(k)=point(1,j2);k=k+1;end

30、j1=j2;m=m+1;endpai附录三 结果 pai =31 30 28 36 24 34 20 19 14 22 11附录四：clearx=3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 285 17 25 9 9 30 0;y=2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 167 20 15 12 0;t=1.50 1.50 0.55 1.20 0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.60 1.500.80 1.50 0.80 1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.0