垃圾运输问题ecnn.docx

《垃圾运输问题ecnn.docx》由会员分享，可在线阅读，更多相关《垃圾运输问题ecnn.docx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、垃圾运输输问题10600101101221王凌凌竹10600101101118于仁仁富10600702201333杨文文刚垃圾运输输问题摘要：该该题我们们的主要要解题思思路分三三阶段：第一阶段段，我们们先根据据题设条条件和基基本假设设画出该该题的图图。第二阶段段，我们们根据图图和点的的位置关关系结合合题设，归归纳出一一些最基基本的确确定路线线的原则则：在仔细分分析该题题后，我我们认为为该题为为一个单单目标规规划题。我我们先抛抛开空载载费用，若若要把所所有的垃垃圾运回回垃圾处处理站，这这部分有有效工的的费用为为1.88|XXi|Yi(|Xii|为垃圾圾点Xii到原点点的距离离,Yii为垃圾圾点的

2、垃垃圾量)，是恒恒定不变变的。只只要我们们能保证证空载路路线最小小，则所所花的时时间和费费用都最最小。因因此解题题的关键键在于找找出一个个调度方方案，使使空载行行驶的线线路最小小。第三阶段段则是编编制程序序阶段，采采用计算算机模拟拟搜索的的计算方方法，搜搜索出运运输车投投入辆数数以及运运输车最最佳调配配方案，使使得在不不考虑铲铲车的情情况下运运营费用用最低。总总运营费费用为运运输车空空载费与与实际运运输费之之和。问题的解解答如下下：第一一问，求求得所需需总费用用为23345.4元，所所需总时时间为222.55小时，路路线分配配图见正正文；第第二问，求求得需33辆铲车车，铲车车费用为为81.6元

3、，分分配图及及运输车车调度表表见正文文；第三三问，运运营总费费用为：23225.8，其中中8吨、66吨、44吨载重重量的运运输车各各需5、22、3辆辆，路线线分配图图见正文文。关键词：单目标标优化 计算机机搜索一 问题的重重述某城区有有 366 个垃垃圾集中中点，每每天都要要从垃圾圾处理厂厂（第 37 号节点点）出发发将垃圾圾运回。现现有一种种载重 6 吨吨的运输输车。每每个垃圾圾点需要要用 110 分分钟的时时间装车车，运输输车平均均速度为为 400 公里里小时时（夜里里运输，不不考虑塞塞车现象象）；每每台车每每日平均均工作 4 小小时。运运输车重重载运费费 1.8 元元 / 吨公里里；运输

4、输车和装装垃圾用用的铲车车空载费费用 00.4 元 / 公里里；并且且假定街街道方向向均平行行于坐标标轴。请请你给出出满意的的运输调调度方案案以及计计算程序序。问题：1. 运输车应应如何调调度（需需要投入入多少台台运输车车，每台台车的调调度方案案，运营营费用）2. 铲车应如如何调度度（需要要多少台台铲车，每每台铲车车的行走走路线，运运营费用用）3. 如果有载载重量为为 4 吨、 6 吨吨、 88 吨三三种运输输车，又又如何调调度？ （垃圾圾点地理理坐标数数据表见见附录一一）二 模型的假假设1车辆辆在拐弯弯时的时时间损耗耗忽略。2车辆辆在任意意两站点点中途不不停车，保保持稳定定的速率率。3只要要

5、平行于于坐标轴轴即有街街道存在在。4无论论垃圾量量多少，都都能在十十分钟内内装上运运输车。5每个个垃圾站站点的垃垃圾只能能由一辆辆运输车车运载。6.假设设运输车车、铲车车从A垃垃圾站到到B垃圾圾站总走走最短路路线。7. 任意两两垃圾站站间的最最短路线线为以两两垃圾站站连线为为斜边的的直角三三角形的的两直角角边之和和。8. 建设在在运输垃垃圾过程程中没有有新垃圾圾入站。9. 假设铲铲车、运运输车载载工作途途中不发发生意外外也不遇遇到意外外；10. 各垃圾圾站每天天的垃圾圾量相对对稳定。三 主要变量量的说明明|A| 表表示A点点到原点点的距离离，恒正正|B| 表表示B点点到原点点的距离离，恒正正|

6、A-BB| 表表示A,B两点点之间的的距离,恒正Ta 表表示A点点所在地地的垃圾圾量costt：运费费；timee：时间间消耗；装的足够够多 运运输车当当前的载载重离限限载不大大于0.55吨吨(垃圾圾点的最最小垃圾圾量)序数号 所在点点的编号号四 问题的分分析与模模型的建建立垃圾运输输问题最最终可以以归结为为最优路路径搜索索问题，但但注意到到此图为为森林而而不是树树，不能能直接套套用Krrusaal，PPrimm等现成成算法，于于是根据据具体问问题设计计出随机机下山法法，用计计算模拟拟搜索，可可以搜寻寻到令人人满意的的可行解解。先注意到到两点的的情况，设设两点分分别为AA(x1,y1),B(x

7、2,y2)。主要有以以下两种种情况：一 A,B明明显有先先后次序序。-递减状状态（如如图1）不妨设xx1x2, y1y2,不难难看出AA在B的后方方,即AA比B远。对对于前方方参考点点O,要将将A,BB对应垃垃圾点的的垃圾全全部取回回再返回回O,一一共有三三种方式式：1 OAO, OBO单独运输输。这种种情况下下，总的的路程消消费等于于空载运运行费用用(0.4元/公里)与装载载时运行行费用（11.8元元/公里里吨）的的总和。所所需的总总时间等等于车辆辆所走过过的总路路程与速速度（440公里里/小时时）的比比值再加加上在AA,B两两点停留留的时间间(每个个垃圾点点上停留留了100分钟，11/6小

8、小时)，于于是有：Costt = 0.44*|AA| + 1.8*|A|*Ta + 0.44*|B| + 1.8*|B|*TbbTimee = (22*|AA| + 2*|B|)/440 + 1/6*222. OOABO先远点再再近点，即即先空载载至最远远处，装装完A点点垃圾后后再返回回至B,再回OO点，有有：Costt = 0.44*|AA| + 1.8*|A-BB|*Taa +11.8*|B|*(Ta+Tb) = 00.4*|A| + 1.8*|A|*Taa + 1.88*|BB|*TbbTimee = 2*|A|/440 + 1/6*223. OOBAO 先近点点在远点点，即先先装B点点

9、垃圾，然然后载着着B点的的垃圾奔奔至A点点，再回回O点，有有：Costt= 00.4*|B| + 1.8*|A-B|*TTb + 1.8*|A|*(Ta+Tb) = 00.4*|B| + 1.8*|A|*Taa + 1.88*|BB|*Tbb + 1.88*|AA-B|*22*TbbTimee = 2*|A|/440 + 1/6*22比较以上上三种情情况，远远近点的的遍历顺顺序，可可以看出出，“先远后后近”绝对比比“先近后后远”在花费费钱的数数量上要要少的多多，省出出1.88*|AA-B|*22*Tbb这部分分的钱主主要是车车载着BB点的垃垃圾奔到到A点再再返回BB点。而而又注意意到两者者的时

10、间间花费是是相等的的。所以以在其余余同等的的情况下下选择“先远后后近”。考虑到到时间上上单独运运输比其其余的两两种运输输要大的的多，多多一一倍倍，而且且花费的的钱仍不不比“先远后后近”省，还还多了00.4*|B|，所所以一般般情况下下，不采采用单独独运输。二A，B两点没没有明显显先后顺顺序。 -并邻邻状态（如如图2）还是一共共有三种种情况：1 OAO, OBBO单独运输输。这种种情况下下，跟AA,B两两点有先先后顺序序中的情情况完全全相同，即即有：Costt = 0.44*|AA| + 1.8*|A|*Ta + 00.4*|B| + 1.88*|BB|*TTbtimee = (22*|AA|

11、+ 2*|B|)/440 + 1/6*222 OABOOCostt = 0.44*|AA| + 1.8*|A-BB|*Taa + 1.88*|BB|*(Ta+Tb) -11Timee = (|A| + |A-B| + |B|)/40 + 11/6*23.OBBAOCostt = 0.44*|BB| + 1.8*|A-BB|*Tbb + 1.88*|AA|*(Ta+Tb) -22Timee = (|AA| + |AA-B| + |BB|)/40 +1/6*22相比之下下，清晰晰可见并并邻状态态下的单单独运输输所花的的费用最最少，所所以在不不要求时时间的情情况下对对于并邻邻两点，采采用单独独运输的

12、的方式最最节约钱钱。用式与与式相减减除以11.8， 得到如如下判断断式：|A-BB|*(Ta-Tb) + (Taa+Tbb)*(|B|-|A|) -上式 0时时， 选选 OBAO;上式 = 0时时， 任任意选上上述两路路线。三 两点选择择趋势的的讨论。 （如图图3）由图中看看到B,C两点点没有明明显的先先后顺序序，属于于并邻点点。因为为当运输输车载重重行驶时时费用会会成倍的的增长，比比其空载载时所花花费用要要大的多多，所以以排除AABC或ACB这样的的一次经经过3点点的往返返路线，仅仅选择BB,C中中的某一一点与AA完成此此次运输输，将另另一点留留到下次次。那么么A点选择择B还是C呢？不妨假设

13、设|B|C|,即即B点离离原点的的距离比比C点的更更远，因因为A在B,CC之后，所所以也就就是B点离A点更近近。这样样，此次次的运输输我们更更趋向于于选择AAB,因为为就这三三点而论论，A无论是是选B还是C，三点点的垃圾圾总要运运完，所所以花费费的钱是是一样的的。但选选择AB后，下下次运输输车运CC点垃圾圾时就无无需跑的的更远。四 关于垃圾圾点的垃垃圾是否否一次清清除的讨讨论（以以6吨车车例）由假设22知，每每天的垃垃圾必须须清除完完毕，全全部运往往37点点。这里里说的一一次清除除问题不不是指一一天，而而是指当当一辆运运输车已已经装载载了足够够多的垃垃圾，不不能完全全清理下下一个垃垃圾点的的时

14、候，车车在下一一个站点点“停还是是不停”的问题题。例如如，一辆辆运输车车选择了了3022618835200的路线线（即先先将空车车开往330，清清理装载载30点点的垃圾圾，然后后依次到到26，118，335，220），它它从200返回时时车已经经装载了了5.88吨垃圾圾，仍可可以装00.2吨吨(小于于垃圾点点垃圾量量的最小小值0.5，称称这种情情况为“装的足足够多”)。在在20点点下方仍仍有不少少的点，但但肯定不不能将下下面的任任意点的的垃圾装装完，那那么此车车是直接接返回337点呢呢，还是是继续装装直至车车装满为为止呢？我们判断断前者更更好，就就是车在在装的足足够多的的情况下下应该直直接返回

15、回原点（337点）。这这是因为为对于下下一垃圾圾点(假假设为AA点)内内的垃圾圾而言，无无论是一一次装完完还是分分两次装装完，将将它们运运回所花花费用是是恒定的的，等于于1.88*Taa*|A|。整整体而言言，两者者花费的的钱是相相等的，但但分两次次装要多多花100分钟的的装车时时间，所所以选择择前者。综上所述述，得出出搜索的的基本原原则：1 在两点递递减的情情况下，不不采用单单独运输输；2 在其余同同等的情情况下选选择“先远后后近”；3 不要求时时间的情情况下对对于并邻邻两点，采采用单独独运输的的方式最最节约钱钱；一般般情况下下用式s&w(55,j)=00) s=w(22,j)+w(3,jj

16、); jjg(ii,j11)=ww(1,j); summ=w(4,jj); m=jj;elseeconntinnue;endend ww(5,m)=1; jj1=jj1+11;whille 11 js=0; q=440;for k=11:366if(qqw(2,mm)-ww(2,k)+w(33,m)-w(3,kk)&w(22,m)w(2,kk)&ww(3,m)w(33,k)&(66-suum)w(44,k)&w(5,kk)=0 q=w(22,m)+w(3,mm)-ww(2,k)-w(33,k); jss=1; jgg(i,j1)=w(1,kk); i33=k;elseeconntinnue;e

17、ndend w(55,i33)=11; summ=suum+ww(4,i3); j1=j1+1; m=ii3;if(ww(2,i3)=00&w(3,ii3)=0|js=0)breaakendendendkcosst=00;zcosst=00;allccostt=0;n=0;for u1=1:111for u2=1:111if jjg(uu1,uu2)=0 n=jg(u1,u2);elseeconntinnueend zccostt=zccostt+w(4,nn)*11.8*(w(2,nn)+ww(3,n);end n=jjg(uu1,11); kccostt=kccostt+0.4*(w(22

18、,n)+w(3,nn);endallccostt=zccostt+kccosttzcosstkcossti=1:11;timee=ii;timee(1,:)=0;n1=00;n2=00;n3=00;for u4=1:111for u5=1:111if jjg(uu4,uu5)=0 nn1=jjg(uu4,uu5); n2=n2+1;elseeconntinnueendend n3=jg(u4,1); tiime(1,uu4)=(ww(2,n3)+w(3,nn3)*2)/400;endn2 timme 附录三源码cleaarx=33 1 5 44 0 3 77 9 10 14 17 14 12

19、10 7 22 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 117 225 99 9 30 0;y=22 5 4 77 8 11 9 66 2 0 33 6 9 112 114 116 118 117 112 99 5 0 99 199 144 177 133 200 166 188 122 166 7 20 15 12 0;t=11.500 1.50 0.555 11.200 0.85 1.330 11.200 2.30 1.440 11.500 1.10 2.770 11.800 1.80 0.660 11.500 0.80 1.550 00.80

20、0 1.40 1.220 11.800 1.40 1.660 11.600 1.00 2.000 11.000 2.10 1.220 11.900 1.30 1.660 11.200 1.50 1.330 00.000;r=1:37;%ploot(xx,y,*rr);%forr iii=1:37 % k=intt2sttr(iii); % k=strrcatt(PP,kk); % teext(x(iii),y(iii),k);%enddw=rr;x;y;tt;a=1:11;poinnt=30 28 36 24 34 20 19 14 22 11 31; 33 5 21 15 2 99 8 1

21、222 110 66;a;poinnt(33,:)=0;s=800;p=800;k=2;j1=00;j2=00;m=1;b=1:11;pai=b;pai(1,:)=00; foor jj=1:11 iif ss=ww(2,poiint(1,jj)+w(33,poointt(1,j)&poointt(3,j)=0 ss=w(2,ppoinnt(11,j)+ww(3,poiint(1,jj); eelsee coontiinuee eend ennd j11=j; ppoinnt(33,j11)=11; ppai(1)=poiint(1,jj1); wwhille mm=w(2,ppoinnt(1

22、1,i)+ww(3,poiint(1,ii)-w(22,poointt(2,j1)-ww(3,poiint(2,jj1)&ppoinnt(33,i)=00 p=ww(2,poiint(1,ii)+w(33,poointt(1,i)-w(2,ppoinnt(22,j11)-w(33,poointt(2,j1); elsse cconttinuue endd jj2=ii; poiint(3,jj2)=1; paii(k)=poointt(1,j2); k=kk+1; endd j11=j22; m=m+11; ennd paii 附录三结果pai = 31 30 28 36 24 34 20 1

23、9 14 22 11 附录四：cleaarx=33 1 5 44 0 3 77 9 10 14 17 14 12 10 7 22 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 117 225 99 9 30 0;y=22 5 4 77 8 11 9 66 2 0 33 6 9 112 114 116 118 117 112 99 5 0 99 199 144 177 133 200 166 188 122 166 7 20 15 12 0;t=11.500 1.50 0.555 11.200 0.85 1.330 11.200 2.30 1.440 11

24、.500 1.10 2.770 11.800 1.80 0.660 11.500 0.80 1.550 00.800 1.40 1.220 11.800 1.40 1.660 11.600 1.00 2.000 11.000 2.10 1.220 11.900 1.30 1.660 11.200 1.50 1.330 00.000;i=1:37;a=1:37;plott(x,y,*r)for ii=1:337 k=iint22strr(iii); k=sstrccat(P,k); texxt(xx(iii),yy(iii),kk);endw=ii;x;y;tt;a;w(5,:)=0;jg=zz

25、eroos(110,110);%111for i=11:200 summ=0; j1=1; s=00; m=337; i3=37;for j=11:366if(ww(2,j)+w(33,j)=ss&w(5,jj)=0) s=w(22,j)+w(3,jj); jjg(ii,j11)=ww(1,j); summ=w(4,jj); m=jj;elseeconntinnue;endend ww(5,m)=1; jj1=jj1+11;whille 11 js=0; q=440;for k=11:366if(qq=ww(2,m)-w(22,k)+w(3,mm)-ww(3,k)&w(2,mm)ww(2,k)&w(33,m)w(3,kk)&(8-ssum)=ww(4,k)&w(55,k)=00 q=w(22,m)+w(3,mm)-ww(2,k)-w(33,k); jss=1; jgg(i,j1)=w(1,kk); i33=k;elseeconntinnue;endend