城市垃圾运输问题

1、魅力数模 美丽师大浙江师范大学“同梦杯”第八届数学建模竞赛自信 创新 合作 快乐a b论文题目 城市垃圾运输问题 编 号 56组 评 分 监 制：浙江师范大学数学建模研究会（2009年5月7日）（说明：评分一栏为评阅人填写，请参赛者不要填写）垃圾运输问题摘要：该题我们的主要解题思路分三阶段：第一阶段，我们先根据题设条件和基本假设画出该题的图。第二阶段，我们根据图和点的位置关系结合题设，归纳出一些最基本的确定路线的原则：在仔细分析该题后，我们认为该题为一个tsp与vrt相结合的问题。我们先抛开空载费用，若要把所有的垃圾运回垃圾处理站，这部分有效工的费用为2.0|xi|yi(|xi|为垃圾点xi到

2、原点的距离,yi为垃圾点的垃圾量)，是恒定不变的。只要我们能保证空载路线最小，则所花的时间和费用都最小。因此解题的关键在于找出一个调度方案，使空载行驶的线路最小。第三阶段则是编制程序阶段，我们结合下山法逐点搜索，并引入随机生成器。在出现后继点权值相等难以判断以哪点继续搜索时，由随机生成器确定。为了让算法更接近人的思维，我们让更靠近父点的子点有更高的几率被作为下一个将去的垃圾点，这也与我们的算法原则对应。采用计算机模拟搜索的计算方法，搜索出运输车投入辆数以及运输车最佳调配方案，使得在不考虑铲车的情况下运营费用最低。总运营费用为运输车空载费与实际运输费之和。问题的解答如下：第一问，求得所需总费用为

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

4、垃圾用的铲车空载费用 0.5 元 / 公里；并且假定街道方向均平行于坐标轴。请你给出满意的运输调度方案以及计算程序。问题：1. 运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）2. 铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用）3. 如果有载重量为 4 吨、 6 吨、 8 吨三种运输车，又如何调度？（垃圾点地理坐标数据表见附录一）二、 模型的假设1. 运输车匀速行驶且不计一切拐弯损耗时间；2. 车辆在任意两站点中途不停车；3. 只要平行于坐标轴即有街道存在；。4. 无论垃圾量多少，都能在十分钟内装上运输车；5. 每个垃圾站点的垃圾不允许分两次运输，而且也只需

5、要一辆铲车。6. 假设运输车、铲车从a垃圾站到b垃圾站总走最短路线；7. 任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直角边之和；8. 如果车可以跑第二趟，中间无休息时间；9. 假设铲车、运输车载工作途中不发生意外也不遇到意外；10. 所有运输车和铲车均从第38号点出发，且最后均回到38号点；三、 主要变量的说明1、子点：本点的下一点； 2、spend：运费； 3、time：时间消耗； 4、|a|：a点横纵坐标之和，；5、垃圾集中点在后面用顶点表示6、vi：第i个顶点7、vi.x：第i个顶点的x坐标；vi.y表示第i个顶点的y坐标；8、vi.laji：第i个顶点上有的垃圾重量

6、，单位是吨；9、lij:顶点i到顶点j的距离；10、sumi:顶点i的横纵坐标之和；11、访问一个顶点表示把它的垃圾装上车；12、用到的相关定义 设 g = (v, e) 是连通无向图,(1) 经过 g的每一个顶点正好一次的路,称为 g的一条哈密顿路或 h路;(2) 经过 g的每一个顶点正好一次的圈,称为 g的一条哈密顿圈或 h圈;(3) 含 h圈的图称为哈密顿图或 h图.|a| a点横纵坐标之和|b| b点横纵坐标之和|a-b| 表示a,b两点之间的距离ta 表示a点所在地的垃圾量cost：运费；time：时间消耗；装的足够多 运输车当前的载重离限载不大于0.55吨(垃圾点的最小垃圾量)序数

7、号 所在点的编号四、 问题的分析与模型的建立这是一个遍历问题。由于运输车的载重与时间的约束，它不在是最小树能解决的问题，而是森林，包含了多个树。每一个树用一辆车去把其上面的垃圾运输回来，只要时间足够，同一辆车可能运输不止一颗树的垃圾。问题就变成了，在一个森林中，找到这样一些树，使其能用尽可能少的车遍历完所有顶点的，且这些树够成哈密顿圈。将垃圾集中点抽象成坐标平面上的点，该点具有两个属性，即位置属性和重量属性；城市抽象成一个30*20的一个坐标方格网络。该模型假设如第二项中所述。垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，不能直接套用krusal，prim等现成算法，

8、于是根据具体问题设计出随机下山法，用计算模拟搜索，可以搜寻到令人满意的可行解先注意到两点的情况，设两点分别为a(x1,y1),b(x2,y2)。主要有以下两种情况：一 a,b明显有先后次序。-递减状态（如图1）不妨设x1x2, y1y2,不难看出a在b的后方,即a比b远。对于前方参考点o,要将a,b对应垃圾点的垃圾全部取回再返回o,一共有三种方式：1 oao, obo单独运输。这种情况下，总的路程消费等于空载运行费用(0.5元/公里)与装载时运行费用（2.0元/公里吨）的总和。所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值再加上在a,b两点停留的时间(每个垃圾点上停留了10分

9、钟，1/6小时)，于是有：cost = 0.5*|a| + 2.0*|a|*ta + 0.5*|b| + 2.0*|b|*tbtime = (2*|a| + 2*|b|)/40 + 1/6*22. oabo 先远点再近点，即先空载至最远处，装完a点垃圾后再返回至b,再回o点，有： cost = 0.5*|a| + 2.0*|a-b|*ta +2.0*|b|*(ta+tb) = 0.5*|a| + 2.0*|a|*ta + 2.0*|b|*tb time = 2*|a|/40 + 1/6*23. obao 先近点在远点，即先装b点垃圾，然后载着b点的垃圾奔至a点，再回o点，有： cost= 0.

10、5*|b| + 2.0*|a-b|*tb + 2.0*|a|*(ta+tb) = 0.5*|b| + 2.0*|a|*ta + 2.0*|b|*tb + 2.0*|a-b|*2*tb time = 2*|a|/40 + 1/6*2比较以上三种情况，远近点的遍历顺序，可以看出，“先远后近”绝对比“先近后远”在花费钱的数量上要少的多，省出2.0*|a-b|*2*tb这部分的钱主要是车载着b点的垃圾奔到a点再返回b点。而又注意到两者的时间花费是相等的。所以在其余同等的情况下选择“先远后近”。考虑到时间上单独运输比其余的两种运输要大的多，多一一倍，而且花费的钱仍不比“先远后近”省，还多了0.5*|b|

11、，所以一般情况下，不采用单独运输。二a，b两点没有明显先后顺序。 -并邻状态（如图2）还是一共有三种情况： 1 oao, obo单独运输。这种情况下，跟a,b两点有先后顺序中的情况完全相同，即有：cost = 0.5*|a| + 2.0*|a|*ta + 0.5*|b| + 2.0*|b|*tbtime = (2*|a| + 2*|b|)/40 + 1/6*22 oabocost = 0.5*|a| + 2.0*|a-b|*ta + 2.0*|b|*(ta+tb) -1time = (|a| + |a-b| + |b|)/40 + 1/6*23.obaocost = 0.5*|b| + 2.0

12、*|a-b|*tb + 2.0*|a|*(ta+tb) -2time = (|a| + |a-b| + |b|)/40 +1/6*2相比之下，清晰可见并邻状态下的单独运输所花的费用最少，所以在不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱。用式与式相减除以2.0， 得到如下判断式：|a-b|*(ta-tb) + (ta+tb)*(|b|-|a|) -上式 0时， 选 obao;上式 = 0时， 任意选上述两路线。三 两点选择趋势的讨论。 （如图3）由图中看到b,c两点没有明显的先后顺序，属于并邻点。因为当运输车载重行驶时费用会成倍的增长，比其空载时所花费用要大的多，所以排除abc或

13、acb这样的一次经过3点的往返路线，仅选择b,c中的某一点与a完成此次运输，将另一点留到下次。那么a点选择b还是c呢？不妨假设|b|c|,即b点离原点的距离比c点的更远，因为a在b,c之后，所以也就是b点离a点更近。这样，此次的运输我们更趋向于选择ab,因为就这三点而论，a无论是选b还是c，三点的垃圾总要运完，所以花费的钱是一样的。但选择ab后，下次运输车运c点垃圾时就无需跑的更远。四 关于垃圾点的垃圾是否一次清除的讨论（以6吨车例）由假设2知，每天的垃圾必须清除完毕，全部运往38点。这里说的一次清除问题不是指一天，而是指当一辆运输车已经装载了足够多的垃圾，不能完全清理下一个垃圾点的时候，车在

14、下一个站点“停还是不停”的问题。例如，一辆运输车选择了282621119的路线（即先将空车开往28，清理装载28点的垃圾，然后依次到26，21，11，9），它从9返回时车已经装载了5.7吨垃圾，仍可以装0.3吨(小于垃圾点垃圾量的最小值0.6，称这种情况为“装的足够多”)。在9点下方仍有不少的点，但肯定不能将下面的任意点的垃圾装完，那么此车是直接返回38点呢，还是继续装直至车装满为止呢？我们判断前者更好，就是车在装的足够多的情况下应该直接返回原点（38点）。这是因为对于下一垃圾点(假设为a点)内的垃圾而言，无论是一次装完还是分两次装完，将它们运回所花费用是恒定的，等于2.0*ta*|a|。整体

15、而言，两者花费的钱是相等的，但分两次装要多花10分钟的装车时间，所以选择前者。(五) 计算机随机搜索算法的编制和实现一随机搜索算法具体叙述1基本思想。问题要求搜索出一条最短路线，但又与中国邮递员等问题有所区别，本问题搜索的不完全是最优回路问题，而更像是单支路覆盖问题，也是np难问题，没有现成的多项式次数的算法，所以自行设计了一种随机搜索算法。基本思想是结合下山法逐点搜索，并尝试引入随机生成器剪枝提高搜索速度，整个算法利用链表结构实现。2算法流程一次布局开始 确定搜索点总集p ，判断集p非空：若空，则一次布局结束；非空，则m=max(|p|),即m为p集中距离原点(0,0)的最远点。l=m,。（

16、具体见下面的流程图，图4） 求p集中的max点以l为中心搜索new_point找到new_pointweight合适yes随机发生器父不是l父为l直接连接父不是l父为l父非0子非0父非0子为-1父为0子为-1父为0子非0父为0子为0以下根据父点与子点情况进行分类yes变权值通过后，则有将此点独立，将new_point父点设为l；将new_point子点设为 0随机发生器随机发生器l无子点，直接连接；l有子点，将子点独立；随机发生器随机发生器别的环中点。若变，则连接；不变则保持。自己环中点，保持。即,new_point=l;next new_point别的环中末点。若变，则将此点连接；不变，则寻

17、找next_loop环中末点若变则将此点独立；若不变，则继续找对l赋值为下次循环做准备循环继续综上所述，得出搜索的基本原则：1 在两点递减的情况下，不采用单独运输；2 在其余同等的情况下选择“先远后近”；3 不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱；一般情况下用式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; end end w(5,m)=1; j1=j1+1; while 1 js=0; q=40; for k=1:37 if(qw(2,m)-w(2,k)+w(3,m

18、)-w(3,k)&w(2,m)w(2,k)&w(3,m)w(3,k)&(6-sum)w(4,k)&w(5,k)=0 q=w(2,m)+w(3,m)-w(2,k)-w(3,k); js=1; jg(i,j1)=w(1,k); i3=k; else continue; end end w(5,i3)=1; sum=sum+w(4,i3); j1=j1+1; m=i3; if(w(2,i3)=0&w(3,i3)=0|js=0) break end endendkcost=0;zcost=0;allcost=0;n=0;for u1=1:11 for u2=1:11 if jg(u1,u2)=0 n=

19、jg(u1,u2); else continue end zcost=zcost+w(4,n)*1.8*(w(2,n)+w(3,n); end n=jg(u1,1); kcost=kcost+0.4*(w(2,n)+w(3,n);endallcost=zcost+kcostzcostkcosti=1:11;time=i;time(1,:)=0;n1=0;n2=0;n3=0;for u4=1:11 for u5=1:11 if jg(u4,u5)=0 n1=jg(u4,u5); n2=n2+1; else continue end end n3=jg(u4,1); time(1,u4)=(w(2

20、,n3)+w(3,n3)*2)/40;endn2 time jg附录四【源码】 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 28 5 17 25 9 9 30 8 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 16 7 20 15 12 10 0;t=1.50 1.50 0.75 1.20 0.85 1.30 1.20 2.30 1.40 1.80 1.10

21、2.70 1.80 1.80 0.60 1.50 0.80 1.50 0.90 1.40 1.20 1.80 1.40 1.60 1.90 1.00 2.00 1.00 2.10 1.20 1.90 1.30 1.60 1.20 1.50 2.30 1.70 0.00;i=1:38;a=1:38;plot(x,y,*r)for ii=1:38 k=int2str(ii); k=strcat(p,k); text(x(ii),y(ii),k);endw=i;x;y;t;a;w(5,:)=0;jg=zeros(10,10);%?11?for i=1:20 sum=0; j1=1; s=0; m=3

22、8; i3=38; for j=1:37 if(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; end end w(5,m)=1; j1=j1+1; while 1 js=0; q=40; for k=1:37 if(q=w(2,m)-w(2,k)+w(3,m)-w(3,k)&w(2,m)w(2,k)&w(3,m)w(3,k)&(8-sum)=w(4,k)&w(5,k)=0 q=w(2,m)+w(3,m)-w(2,k)-w(3,k); js=1; jg(i,j

23、1)=w(1,k); i3=k; else continue; end end w(5,i3)=1; sum=sum+w(4,i3); j1=j1+1; m=i3; if(w(2,i3)=0&w(3,i3)=0|js=0) break end endendkcost=0;zcost=0;allcost=0;n=1;for u1=1:10 for u2=1:10 if jg(u1,u2)=0 n=jg(u1,u2); else continue end zcost=zcost+w(4,n)*1.8*(w(2,n)+w(3,n); end n=jg(u1,1); kcost=kcost+0.4*(

24、w(2,n)+w(3,n);endallcost=zcost+kcostzcostkcosti=1:10;time=i;time(1,:)=0;n1=0;n2=0;n3=0;for u4=1:10 for u5=1:10 if jg(u4,u5)=0 n1=jg(u4,u5); n2=n2+1; else continue end end n3=jg(u4,1); time(1,u4)=(w(2,n3)+w(3,n3)*2)/40;endn2 time jg 附录四结果allcost = 2.4606e+003zcost = 2.3426e+003kcost = 118n2 = 36time

25、= columns 1 through 8 2.3000 2.2000 2.1000 1.7000 1.4500 1.3500 1.0500 1.0000 columns 9 through 10 0.9000 0.7000jg = 30 29 27 20 11 0 0 0 0 0 28 26 32 25 14 3 0 0 0 0 36 23 33 21 9 0 0 0 0 0 24 18 35 15 31 5 0 0 0 0 34 17 16 2 0 0 0 0 0 0 19 13 8 1 0 0 0 0 0 0 22 0 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0

26、 0 37 7 4 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0附录五【源码】clear allclose allclc%初始化蚁群m=31;%蚁群中蚂蚁的数量，当m接近或等于城市个数n时，本算法可以在最少的迭代次数内找到最优解c=3 2;1 5;5 4;4 7;0 8;3 11;7 9;9 6;10 2;14 0;17 3;14 6;12 9;10 12;7 14;2 16;6 18;11 17;15 12;19 9;22 5;21 0;27 9;15 19;15 14;20 17;21 13;24 20;25 16;28 18

27、;5 12;17 16;25 7;9 20;9 15;30 12;8 10;0 0;%城市的坐标矩阵nc_max=200;%最大循环次数，即算法迭代的次数，亦即蚂蚁出动的拨数（每拨蚂蚁的数量当然都是m）alpha=1;%蚂蚁在运动过程中所积累信息（即信息素）在蚂蚁选择路径时的相对重要程度，alpha过大时，算法迭代到一定代数后将出现停滞现象beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度rho=0.5;%0rho1,表示路径上信息素的衰减系数（亦称挥发系数、蒸发系数），1-rho表示信息素的持久性系数q=100;%蚂蚁释放的信息素量，对本算法的性能影响不大%变量初始化n=size(c,1);%表示tsp问题的规模，亦