A组垃圾运输问题.doc

垃圾运输问题摘要本文针对生活中的垃圾运输问题进行讨论研究，通过对问题的分析和合理的假设，运用非线性规划的数学理论，建立了非线性规划的数学模型求解，运用matlab软件得到了全局最优解。针对问题一，对运输车的派遣和所行路线进行分析，将36个垃圾站点分成12个组，每辆负责3个站点，运用matlab软件对36个站点分组、计算路线长度、费用，运输车从原点出发，空车到离原点最远的垃圾站点，从最远开始运输垃圾再回到原点，如图(2)。针对问题二，铲车一直都处于空车运输的状态，无累计计算，所需要的费用就只有0.4元/公里，只要路径最短，则铲车的费用就最少，所以只需要计算出铲车的最短路径即可。针对问题三，在问题一的基础上，运输车的限载量从最大6吨变成了10吨，用matlab软件，求出12条路线中的最长的两条路线，合并起来，用10吨的运输车来运，在6吨以下的路线则调用6吨的运输车。针对问题四，由于每个垃圾站点的垃圾量是随机的，所以用matlab软件产生36个随机数，软件对36个站点进行分组、计算路线长度、求出最少费用，与问题一的算法一样，用matlab软件计算关键词：非线性规划 垃圾运输的调度 最优解1.问题重述老城区有36个垃圾站，每天都要从垃圾处理厂（原点）出发将垃圾运回。现有一种载重6吨的运输车。每个垃圾点需要用10分钟的时间装车，假设每个垃圾站点都用10分钟，运输车平均速度为40公里/小时；设运输车速度与载重无关，每台车每日平均工作4小时（0:00-4:00,5:00前必须结束）。运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里；各垃圾站数据见表1。假定街道方向均平行于坐标轴，请给出满意的运输调度方案以及计算程序。通过数学建模，本文需要解决如下四个问题：1）运输车应如何调度（运输车数量，调度方案，运营费用等）2）铲车应如何调度（铲车数量，行走路线，运营费用）3）如果有载重量为6吨、10吨两种运输车，又如何调度？4）如果每个垃圾站点的垃圾量是随机数，标准差为该站点平均垃圾量的10%，该如何调整？2.问题分析随着人民生活水平的不断提高和城市化的加剧，垃圾越来越多，研究垃圾运输车的调度方案和费用有重要意义，为了将老城区36个垃圾站点的垃圾进行清理，本文运用非线性规划的数学模型，对调度方案进行研究分析。问题(1)，针对运输车的调度方案，本文采取了非线性规划的数学模型，在运营费用最少的前提下，求运输车数量、调度方案的最优解，并用matlab求出每辆运输车的路线、工作时间和费用，若运输车完成工作所用时间小于5小时，可以返回继续运输其他站点的垃圾，将36个垃圾站点进行分组，平均分成12个组，每辆运输车负责3个垃圾站点，运用matlab软件对36个站点进行分组、计算路线长度、求出最少费用，运输车每天每台工作4个小时，0:00到4:00,5点之前必须结束，运输车载重6吨，每个垃圾站点用10分钟的时间装车，假设没个垃圾站点都用了10分钟，运输车的运输费用与载重无关，运输车重载运费1.8元/吨公里，为了使运输费用更少，使运输车从原点出发，先用空车走到离原点最远的垃圾站点，然后从最远开始运输垃圾再回到原点，如图(2)。对第二题来说，铲车一直都处于空车运输的状态，无累计计算，所需要的费用就只有0.4元/公里，只要路径最短，则铲车的费用就最少，所以只需要计算出铲车的最短路径即可，以运行路径最短为目标，求出铲车路径，数量和费用，铲车是跟随垃圾车一起工作的，为了将老城区36个垃圾站点的垃圾进行清理，计算出将铲车路线分为六条线路，标记为(n=1,2,3,4,5,6)线路，然后计算出线路的长度，根据0.4元/公里，计算出铲车经过线路所用的费用针对问题三，如果有6吨、10吨两种运输车，重新进行调度，每个垃圾站点的垃圾量不一样，最多有3.2吨，最少有0.6吨，在问题一的基础上，运输车的限载量从最大6吨变成了最大10吨，因此，利用matlab软件，求出12条路线中的最长的两条路线，合并起来，用10吨的运输车来运，在6吨以下的路线则调用6吨的运输车。针对问题四，由于每个垃圾站点的垃圾量是随机的，所以用matlab软件产生36个随机数，软件对36个站点进行分组、计算路线长度、求出最少费用，与问题一的算法一样，用matlab软件计算。最后，对模型的优缺点进行了分析，并给出了模型的改进意见，对解决实际问题具有一定的指导意义。3.模型假设：(1)假设各垃圾站点的垃圾量保持不变。(2)假设从一个垃圾站点到下一各垃圾站点的路径为直线。(3)假设运输车和铲车从一个垃圾站点到下一个站点行驶中的速度是均匀的。(4)假设运输车和铲车在街道行驶过程中畅通无阻且垃圾在运输车经过地方。(5)假设运输车和铲车在行驶过程中不发生抛锚。(6)假设不论垃圾站点的垃圾量的多少，都用10分钟装完。(7)假设每辆车每天工作结束后各垃圾站点的垃圾清理完毕。(8)假设每辆车的装载量都不超过运输车的最大装载量，工作时间都不超过4小时。(9)假设运输车在工作期间，不会因为铲车而耽误工作时间；43.符号说明s：12个运输车所走路线；sj：包含垃圾量和横纵坐标的文本文档；x：站点对应的横坐标；y：站点对应的纵坐标；：12个运输车工作各用时间 (k=1,2,312)；i：各个路线(i=1,2,312)；j：各个站点(j=1,2,336)；d1：各个站点到原点的距离；d：站点到原点的距离；f：运输车所用费用；t：运输车所用时间；T：垃圾量:运输车载重(k=1,2,312)；f10：10吨的运输车运完垃圾所用费用；t10：10吨的运输车工作完成后所用时间；f6：6吨的运输车运完垃圾所用费用；t6：6吨的运输车工作完成后所用时间；:铲车的路线(n=1,2,3,4,5,6)。5.模型的建立与求解5运输车调度方案的模型对于运输车的调度方案，我们建立单目标规划的非线性模型使得运输费用最小，模型如下。(1).目标函数的建立考虑使运输费用最小时，目标函数包括两个方面的费用：空载费用和重载费用,其中，空载费用为从原点到最远距离的站点的费用，而重载费用为上一个点到下一个点所花的费用，表示如下：min f=5.1.约束条件的确立（1）垃圾运输车不允许有超载现象，即每辆车的载重最多为6吨： =6(k=1,2,3,4,5)（2）运输车到达某个站点后，必须将此站点的所有垃圾带走当天不能由剩余垃圾： =59.9（3）每台车每日工作不能超过4小时：=4 (i=1,2,3,4,5)5.2.单目标规划模型在给出了目标函数和约束条件后，即可得到一个使得运输费用最小的单目标规划模型如下：min f= 各垃圾站点的坐标散点图如图(1)图(1)图(2)表(1)序号站点编号垃圾量T坐标x(km)坐标y(km)111.5032221.8015332.5554441.2047560.8508651.30311773.2079882.3096991.4010210101.5014011111.1017312122.7014613131.8012914142.80101215200.6071416161.5021617170.8061818181.50111719190.801512202115321.401.2019229522221.2022523231.8021024241.4027925251.60151926262.60151427271.00201728282.00211329291.00242030302.10251631311.20281832211.9051233331.30171634343.2025735351.2092036362.509151.3030122铲车调度方案的模型此模型是基于问题一的模型，铲车共有六条路径，因为铲车不考虑累计载重问题，所以只需要得出铲车走每条路径的长度，再与每公里所用费用相乘即可，由于运输车的路径已经确定，我们只能让铲车跟随着运输车，而不能让运输车在垃圾站点等待铲车。由此可以确定,铲车必须跟随着运输车行走完一条路径，才能转到其他路径继续工作，为了使运输车和铲车的工作效率更高，让一辆铲车工作完一条路线之后继续工作另一条路线，这样，就在规定的时间之内，一辆铲车可以服务两辆运输车。铲车工作的每条路径分别为： 030(28,18)15(7,14)3(5,4)0 033(25,7)21(22,5)5(0,8)0 035(9,15)17(6,18)9(10,2)0 026(20,17)18(11,17)22(21,0)0 027(21,13)19(15,12)16(2,16)0 023(27,9)12(14,6)1(3,2)0 024(15,19)7(7,9)4(4,7)0 028(24,20)29(25,16)2(1,5)0 025(15,14)13(12,9)11(17,3)0 036(30,12)14(10,12)6(3,11)0 032(17,16)34(9,20)20(19,9)0 031(5,12)8(9,6)10(14,0)0每辆铲车工作的路径确定之后，相应的费用自然就就确定了，铲车空载费用0.4元/公里：铲车费用：0.4*(36+25+12+23+5+8)=43.6 0.4*(24+6+20+25+9+27+21)=52.8 0.4*(34+7+17+32+16+15+5)=50.4 0.4*(34+18+5+33+5+35+6)=54.4 0.4*(29+8+11+22+20+8+14)=44.8 0.4*(33+12+21+17+10+11+14)=47.2所以可以计算出铲车所用的总费用为：293.2元铲车跟随运输车工作的路线，站点序号，铲车编号，载重，工作时间和总时间如表(2) 表(2)运输车路线站点序号载重（吨）时间（h）总时间(h)铲车时间(h)1(十二)0-30-15-3-04.351.15+0.725+0.5+0.225=2.64.852.6-0.225+2.25=4.625(一)0-33-21-5-05.250.8+0.75+0.5+0.2=2.252(二)0-35-17-9-04.70.6+0.65+0.5+0.3=2.054.92.05-0.3+2.85=4.6(十一)0-26-18-22-04.30.925+0.9+0.5+0.525=2.853(五)0-27-19-6-04.30.85+0.6+0.5+0.45=2.44.72.4-0.45+2.3=4.25(三)0-23-12-1-05.60.9+0.775+0.5+0.125=2.34(六)0-24-7-4-06.00.85+0.575+0.5+0.275=2.24.952.2-0.275+2.75=4.675(四)0-28-29-2-04.91.1+1.0+0.5+0.15=2.755(十)0-25-13-11-05.50.725+0.475+0.5+0.5=2.24.82.2-0.5+2.6=4.75(八)0-34-14-6-05.41.05+0.7+0.5+0.35=2.66(七)0-32-34-20-03.90.825+0.825+0.5+0.7=2.854.652.85-0.7+1.8=3.95(九)0-31-8-10-05.70.425+0.525+0.5+0.35=1.8总计59.928.8526.85 表(3) sj垃圾量T坐标x(km)坐标y(km)1.50321.80152.55541.20470.85081.303113.20792.30961.401021.501401.101732.701461.801292.8010120.607141.502160.806181.5011170.8015121.401991.202251.802101.402791.6015192.6015141.0020172.0021131.0024202.1025161.2028181.905121.3017163.202571.209202.509151.30301236吨，10吨的调度方案与问题一类似，运用matlab软件对36个站点进行分组，求出12条路线中的最长的两条路线，合并起来，用10吨的运输车来运，在6吨以下的路线则调用6吨的运输车。垃圾量在6吨以下的的路线调用6吨运输车，得出结果为，6吨运输车负责10条路线，所用费用共1583.3元，10吨运输车负责两条路线，所用费用共334.44元4垃圾量随机的站点对运输车进行调度由于各个站点的垃圾量是随机的，因此运用matlab软件产生36个随机数，并对这些随机数按问题一的方法分配线路，分配路线如下： 路线时间(h)0 8 14 21 01.90000 15 5 4 01.67500 22 18 26 02.45000 3 9 25 01.55000 30 7 24 03.25000 31 13 32 01.90000 2 35 28 01.75000 20 23 17 02.75000 36 6 12 03.00000 16 19 1 02.05000 27 34 33 03.27500 10 29 11 02.4000运输车所用时间分别为：1.9000 1.6750 2.4500 1.5500 3.2500 1.9000 1.7500 2.7500 3.0000 2.0500 3.2750 2.4000各集中点的垃圾量平均值为，标准差为=1.664*0.1=0.1664，不影响对运输车的调度方案。6.模型的评价 模型有优点也有缺点，优点是我们选择了让空车先到最远的站点运垃圾，再从最远的开始运起回到原点，这样就减少了载重的1.8元/吨公里的费用；对于铲车来说，本文让一个铲车跟随两个运输车工作，这样，既不超过工作的时间，又能减少一半的铲车费用，提高了工作的效率。缺点是可能并不是全部的运输车都是负责三个站点，导致了运输车可能利用不充分的情况。但总体来说，本文的优化方案会减少很多的人力、物力、财力和精力，为城区的发展起到了推动的作用。7.模型的推广与改进 模型的推广：对于日益发展的城市，为居民营造一个干净卫生的生活环境，为城市的清洁和形象努力是非常重要的，垃圾越来越多，每天清理垃圾的费用是一笔很大的开销，为此，为了节省不必要的费用，寻找运输车的最短路径和调度方案，以及运输车和铲车的比较有利的配合方案显得非常有意义，我们可以将优化模型推崇到各个大型城市的垃圾清理中，使得城区变得更加干净美丽。 模型的改进：在现实生活中，还有很多的因素我们都没有考虑进去，比如说，运输车和铲车使用时间长了会有一定的磨损，所以就会有车辆保养的资金；运输车和铲车需要司机，还需要一笔资金给司机发工资，在运输车和铲车不工作的时候，还需要将车辆停在停车场，所以也需要一笔停车的费用，为避免繁琐，将这些因素都归于理想，不予以考虑，若继续考虑的话，将会更加优化。8.参考文献1 韩中庚.数学建模竞赛获奖论文精选与点评.科学出版社，20072 李大潜.中国大学生数学建模竞赛（第三版）.北京：高等教育出版社，20083 赵静，但琦等.数学建模与数学实验.北京：高等教育出版社，20024 王兵团。数学建模基础。北京：清华大学出版社，20069.附录第一题垃圾量和站点所处位置的文本文档sj.txt：T x y1.50321.80152.55541.20470.85081.303113.20792.30961.401021.501401.101732.701461.801292.8010120.607141.502160.806181.5011170.8015121.40 19 91.202251.802101.402791.6015192.6015141.0020172.0021131.0024202.1025161.2028181.905121.3017163.202571.209202.509151.303012第一题求运输车路线和每条路线装载的垃圾量clc,clearload sj.txta=sj(:,1);x=sj(:,2);y=sj(:,3);s=(sort(s);s=s(:,3:-1:1)；sj=x y;s=randperm(36);s=reshape(s,12,3)for i=1:12 sum(i)=a(s(i,1)+a(s(i,2)+a(s(i,3);endif sum(:)=6sum=sum;else breakendsum第一题求运输车调度方案、最少费用、最短路径的程序：clc,clearload sj.txta=sj(:,1);x=sj(:,2);y=sj(:,3); %使a为矩阵的第一列，x为矩阵的第二列，y为矩阵的第三列；sj=x y;s=32 2 14;35 1 23;19 5 8;18 34 12;28 11 3;31 30 24 17 29 13;7 36 26;33 21 4;20 9 15;6 10 25;22 27 16;z=5.9 5.4 3.95 5.4 4.65 4.7 4.7 5.5 5.6 3.4 5.4 5.3;for i=1:12 for j=1:3d1(i,j)=sum(sj(s(i,j),:); %求出站点到远点的距离； endendd1=(sort(d1);d1=d1(:,3:-1:1); %使s中每一行的数据进行降序排列；s=(sort(s);s=s(:,3:-1:1)for i=1:12 d(i,1)=abs(sj(s(i,1),1)+sj(s(i,1),2); d(i,2)=abs(sj(s(i,2),1)-sj(s(i,1),1)+abs(sj(s(i,2),2)-sj(s(i,1),2); d(i,3)=abs(sj(s(i,3),1)-sj(s(i,2),1)+abs(sj(s(i,3),2)-sj(s(i,2),2);endd=(sort(d);d=d(:,3:-1:1);f=0;t=0;for i=1:12f=f+0.4*d1(i,1)+1.8*(a(s(i,1)*d(i,2)+(a(s(i,1)+a(s(i,2)*d(i,3)+d1(i,3)*(a(s(i,1)+a(s(i,2)+a(s(i,3); %运输车的费用t(i)=(d(i,1)+d(i,2)+d(i,3)+d1(i,3)/40+3*1/6; %运输车工作时间endf,t第一题用matlab求运输车调度方案、最少费用、最短路径结果：s = 33 21 535 17 9 23 12 9 28 29 2 27 19 16 24 7 4 32 34 20 36 14 6 31 8 10 25 13 11 26 18 22 30 15 3sum = Columns 1 through 7 5.2500 4.7000 5.6000 4.9000 4.3000 6.0000 3.9000 Columns 8 through 12 5.4000 5.7000 5.5000 4.3000 4.3500f = 2.9708e+003t = Columns 1 through 7 2.2500 2.0500 2.3000 2.7500 2.4000 2.2000 2.4500 Columns 8 through 12 2.6000 2.0750 2.2000 3.0750 2.8000第一题作站点的散点图程序：clear，clcx=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; %垃圾站点所处位置的横坐标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 16 7 20 15 12; %垃圾站点所处位置的纵坐标plot(x,y,*) %作出垃圾站点位置的散点图grid on %在散点图上画出网格图第三题求得6吨和10 吨的运输车调度方案、最少费用的程序：clc,clearload sj.txta=sj(:,1);x=sj(:,2);y=sj(:,3);sj=x y;s =33 21 5;35 17 9;23 12 1;28 29 2;27 19 16;24 7 4 32 34 20;36 14 6;31 8 10;25 13 11;26 18 22;30 15 3;z=5.25 4.7 5.6 4.9 4.3 6 3.9 5.4 5.7 5.5 4.3 4.35;for i=1:12for j=1:3d1(i,j)=sum(sj(s(i,j),:); endendd1=(sort(d1);d1=d1(:,3:-1:1);for i=1:12 d(i,1)=abs(sj(s(i,1),1)+sj(s(i,1),2); d(i,2)=abs(sj(s(i,2),1)-sj(s(i,1),1)+abs(sj(s(i,2),2)-sj(s(i,1),2); d(i,3)=abs(sj(s(i,3),1)-sj(s(i,2),1)+abs(sj(s(i,3),2)-sj(s(i,2),2);endd=(sort(d);d=d(:,3:-1:1);d2=(sum(d);d2=sort(d2);d2=d2(11:12,1);s6=33 21 5;35 17 9;23 12 1;27 19 16;24 7 4;32 34 20;31 8 10;25 13 11;s10=28 29 26 18 22 2;30 36 14 15 6 3;d6=32 25 5;24 20 6;36 16 15;34 17 7;34 18 5;33 21 12;42 20 8;17 11 10;29 11 8;37 27 9;d10=44 35 5;46 25 12;d16=32 27 8;24 24 12;36 20 5;34 27 18;34 16 11;33 29 28;42 22 14;17 15 14;29 21 20;37 28 21;d110=sort(44 41 6;46 21 9);d110=d110(:,3:-1:1);f6=0;t6=0;f10=0;t10=0;b6=0;b10=0;for j=2:3b6(j)=b6(j-1)+a(s6(1,j)+a(s6(2,j);endfor i=1:10f6=f6+0.4*d16(i,1)+1.8*(b6(1)*d6(i,2)+b6(2)*d6(i,3)+d16(i,3)*b6(3);t6(i)=(sum(d6(i,1:3)+d16(i,3)/40+3*1/6;endfor j=2:3b10(j)=b10(j-1)+a(s10(1,j)+a(s10(2,j);endfor i=1:2f10=f10+0.4*d110(i,1)+1.8*(b10(1)*d10(i,2)+b10(2)*d10(i,3)+d110(i,3)*b10(3);t10(i)=(sum(d10(i,1:3)+d110(i,3)/40+6*1/6;endf6,t6,f10,t10第三题求得6吨和10 吨的运输车调度方案、最少费用结果的程序：f6 = 1.5883e+003t6 = Columns 1 through 7 2.2500 2.0500 2.3000 2.4000 2.2000 2.8500 2.6000 Columns 8 through 10 1.8000 2.2000 2.8500f10 = 334.4400t10 = 3.2500 3.3000第四题运输车的调度程序：clc,clearload sj.txta=sj(:,1);x=sj(:,2);y=sj(:,3);sj=x y;b=mean(a);c=b*0.1;a=random(norm