垃圾运输问题模型及求解.doc

垃圾运输问题的建模及其求解东南大学第一届数学建模竞赛A题垃圾运输问题模型及其求解Modeling and Solution of Litter Transportation Problem A 08005137 庄晓波08005332 张 坤08005333 余 翔2007年5月27日标题垃圾运运输问题的建模及其求解关键词垃圾运输问题、优化、搜索摘要这是一个求解最优路径的优化问题。通过简单分析求得所需最少运输车辆数，从而解决问题一。在题设基础上，进行合理假设，简化问题。根据运筹学原理提出运输的基本原则，并以此作为条件，运用Visual C+进行编程，搜索可能最优路径，从而获得问题的解决方案。该题中至少需要5辆车，在此基础上的我们所寻找出的最优路径如下图所示，所用经费为1726.04元。每台车的调度方案如表1所示（假设零点整开始发车）。 图1车T11T12所经过点T21T22所经过点A0:003:0822,21,20N/AN/AN/AB0:002:3819,15,92:393:0212,2C0:002:3717,18,14,102:383:506,1D0:002:3725,13,26,11,52:38N/AN/AE0:002:3024,16,8,72:314:0023,4,3表1注释：T11：第一次出发时刻；T12：第一次回来时刻；T21：第二次出发时刻；T22：第二次回来时刻；正文一、 问题分析该问题是一个关于路径选择的优化问题。问题一较易解决，通过适当地分析并找出一个合理解即可解决。问题二，由于涉用运输点多且分散无规律，必须采用计算机辅助处理。受目前所学知识及时间限制，只能在简化模型并提出合理约束条件的基础上，采用随机搜索，以期获得理想的最优解。 问题三限制条件较少，则在可能的情况下，尽可能地使用载重为8吨的运输车，方能减少车辆使用及运费支出。二、 变量说明父点：本点的上一点；子点：本点的下一点；Spend：运费；Time：时间消耗；|A|：A点横纵坐标之和；三、 模型假设1 只要平行于坐标轴即有街道存在；2 无论垃圾量多少，都能在10分钟内装上运输车；3 运输车匀速行驶且不计一切拐弯损耗时间；4 不允许将同一个中转站的垃圾分两次运输；四、 模型建立将中转站抽象成坐标平面上的点，该点具有两个属性，即位置属性和重量属性；城市抽象成一个30*20的一个方格网络。该模型假设如第二项中所述。垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，不能直接套用Krusal，Prim等现成算法，于是根据具体问题设计出随机下山法，用计算模拟搜索，可以搜寻到令人满意的可行解。先注意到两点的情况，设两点分别为A(x1,y1),B(x2,y2)。主要有以下两种情况：一 A,B明显有先后次序。-递减状态（如图）不妨设x1x2, y1y2,不难看出A在B的后方,即A比B远。对于前方参考点O,要将A,B对应垃圾点的垃圾全部取回再返回O,一共有三种方式：1 OAO, OBO单独运输。这种情况下，总的路程消费等于空载运行费用(0.4元/公里)与装载时运行费用（1.8元/公里吨）的总和。所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值再加上在A,B两点停留的时间(每个垃圾点上停留了10分钟，1/6小时)，于是有：Spend = 0.4*|A| + 1.8*|A|*Ta + 0.4*|B| + 1.8*|B|*TbTime = (2*|A| + 2*|B|)/35 + 1/6*22. OABO 先远点再近点，即先空载至最远处，装完A点垃圾后再返回至B,再回O点，有： Spend = 0.4*|A| + 1.8*|A-B|*Ta +1.8*|B|*(Ta+Tb) = 0.4*|A| + 1.8*|A|*Ta + 1.8*|B|*Tb Time = 2*|A|/35 + 1/6*23. OBAO 先近点在远点，即先装B点垃圾，然后载着B点的垃圾奔至A点，再回O点，有： Spend = 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|/35 + 1/6*2比较以上三种情况，远近点的遍历顺序，可以看出，“先远后近”绝对比“先近后远”在花费钱的数量上要少的多，省出1.8*|A-B|*2*Tb这部分的钱主要是车载着B点的垃圾奔到A点再返回B点。而又注意到两者的时间花费是相等的。所以在其余同等的情况下选择“先远后近”。考虑到时间上单独运输比其余的两种运输要大的多，多一一倍，而且花费的钱仍不比“先远后近”省，还多了0.4*|B|，所以一般情况下，不采用单独运输。二A，B两点没有明显先后顺序。 -并邻状态（如图）图还是一共有三种情况： 1 OAO, OBO单独运输。这种情况下，跟A,B两点有先后顺序中的情况完全相同，即有：spend = 0.4*|A| + 1.8*|A|*Ta + 0.4*|B| + 1.8*|B|*Tbtime = (2*|A| + 2*|B|)/35 + 1/6*22 OABOSpend = 0.4*|A| + 1.8*|A-B|*Ta + 1.8*|B|*(Ta+Tb) -1Time = (|A| + |A-B| + |B|)/35 + 1/6*23.OBAOSpend = 0.4*|B| + 1.8*|A-B|*Tb + 1.8*|A|*(Ta+Tb) -2Time = (|A| + |A-B| + |B|)/35 +1/6*2相比之下，清晰可见并邻状态下的单独运输所花的费用最少，所以在不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱。用式与式相减除以1.8， 得到如下判断式：|A-B|*(Ta-Tb) + (Ta+Tb)*(|B|-|A|) -上式 0时， 选 OBAO;上式 = 0时， 任意选上述两路线。三 两点选择趋势的讨论。 （如图）图由图中看到B,C两点没有明显的先后顺序，属于并邻点。因为当运输车载重行驶时费用会成倍的增长，比其空载时所花费用要大的多，所以排除ABC或ACB这样的一次经过3点的往返路线，仅选择B,C中的某一点与A完成此次运输，将另一点留到下次。那么A点选择B还是C呢？不妨假设|B|C|,即B点离原点的距离比C点的更远，因为A在B,C之后，所以也就是B点离A点更近。这样，此次的运输我们更趋向于选择AB,因为就这三点而论，A无论是选B还是C，三点的垃圾总要运完，所以花费的钱是一样的。但选择AB后，下次运输车运C点垃圾时就无需跑的更远。五、 公式推导及数学论证1 关于问题一中运输车辆的数量，先从离原点最远的几个点进行分析：（1）第22号点：设不经过其它中转站，运输车来回一趟所走的最短路程为92公里，加上装载垃圾所需的10分钟，将远远超过2小时；（2）第号点：由于6吨载重的限制，经过22号点的车不可能将21点、20点与19点全部运走，故19点必须单独派一辆车来运；（3）25点必须单独在一条线中；（4）17点必须单独在一条线中。这样，必须派至少四辆，而中间仍有大量的点需要运输，且24点等点光是来回加上装载时间就达2小时。初步分析至少需要五辆运输车。2问题二中应遵循的原则（1）离原点较远的区域尽量不再去第二次，即较远区域的点集中运输；（2）离原点较近的区域的点，尽量用运送较远区域的剩余时间来运输，以期时间利用的最大化；（3）“左下角行进”原则，即一辆车一次运输所经过的几个点尽量从右上方向左下方递减的；六、 计算方法设计和计算机实现1将一个垃圾中转站的集合看作一个类，而将单个的垃圾中转站看作一个对象，建立一个类。对象包含的元素有：x轴坐标、y轴坐标、垃圾重量。2分别建立三个搜索函数，并引入随机数函数explore()（基于rand()实现），得出若干种方案。算法设计主要思想如下：计算机搜索出可能的五组远点运运输路径，得出所用时间及经费总和；在此基础上，分析剩下点是否有可能能够满足五辆车运输条件，比较之后得出优化解。源程序见附页七、 问题结果1问题用计算机搜索所得结果如下车T11T12所经过点T21T22所经过点A0:003:0822,21,20N/AN/AN/AB0:002:3819,15,92:393:0212,2C0:002:3717,18,14,102:383:506,1D0:002:3725,13,26,11,52:38N/AN/AE0:002:3024,16,8,72:314:0023,4,3表1注释：T11：第一次出发时刻；T12：第一次回来时刻；T21：第二次出发时刻；T22：第二次回来时刻；2存在4吨、6吨、8吨三种运输车时的调度 问题3的解答若存在4吨、6吨、8吨三种,我们应把握的原则是:尽量让8吨的车,拉远处的垃圾,远处垃圾拉得越多，以后车的空载路程就越少，而不考虑空载费用，把垃圾运回垃圾处理厂，它的这部分费用不变。同时，我们考虑到8吨，6吨，4吨的运输车费用问题，故8吨的车不宜太多。离原点较远的点，应用8吨的车运（以减少路程）；而第2点，用6吨车单独拉一次太浪费，应用4吨车还有11、22这两条线也可改用4吨车。八、 结果分析和检验通过问题一的分析，可知不可能使用比五辆车更少的车辆。问题二中，由于简化了问题，不考虑同一个路线中的先后次序问题，事实上空载与重载的价格差异及重载运费与重量的正比规律会对运费产生比较大的影响。九、 优缺点和改进方向1优缺点：“远点集中运输，近点尽量用运远点剩余时间运输”的构想降低了程序设计的难度。事实上，如结果分析中所述，路径最短并不一定是经费最少的方案。“不允许将同一个中转站的垃圾分次运输”，事实上也可能使所得方案优越性变差。当然，我们也存在这样的担心，是否存在四辆车就能满足条件的可能？或许这就应该是改进方向。2改进方向：（1）减少问题二约束条件，使搜索范围扩大；（1）寻找更好的约束条件及算法，使得搜索范围扩大的同时，不大幅度地提高程序设计的复杂度，及程序本身的时间和空间复杂度；（3）换用Matlab作为编程工具，利用Matlab中已有的工具进行编程，以期简化编程。参考文献1 刘育兴、钟剑垃圾运输问题的模型及其求解赣南师范学院学报2006年第3期2 罗小凯等垃圾问输问题的解决哈工大2001年数学建模竞赛A题解答3 谭浩强C+程序设计实践指导清华大学出版社2005.7P73-79附：C+源程序#include#include#include#includeclass point public: int x; int y; double t; void setp(int a,int b,double c) x=a; y=b; t=c; ;point points27;int max() int m=0; for(int i=0;i(pointsm.x+pointsm.y) m=i; return m;int explore1(point a)int m25;int k=0; for(int j=0;j=pointsj.x)|(a.y=pointsj.y) if(pointsj.x+pointsj.y!=0) if(a.x!=pointsj.x)&(a.y!=pointsj.y) if(abs(a.x-pointsj.x)+abs(a.y-pointsj.y)(a.x+a.y)/2) mk=j; k+; int q;if(k) q=rand()%k; return mq;elsereturn 26 ;int explore2(point a,point b)int m25;int k=0; for(int j=0;j26;j+)if(a.t+b.t+pointsj.t=pointsj.x)|(a.y=pointsj.y)if(pointsj.y+pointsj.x!=0) if(abs(a.x-pointsj.x)+abs(a.y-pointsj.y)(a.x+a.y)/3) mk=j; k+; int q;if(k) q=rand()%k; return mq;elsereturn 26 ;int explore3(point a,point b,point c)int m25;int k=0; for(int j=0;j26;j+) if(a.t+b.t+c.t+pointsj.t=4.2)if(c.x!=pointsj.x)&(c.y!=pointsj.y)&(b.x!=pointsj.x)&(b.y!=pointsj.y)&(a.x!=pointsj.x)&(a.y!=pointsj.y) if(a.x=pointsj.x)&(a.y=pointsj.y)&(pointsj.y+pointsj.x!=0) /if(abs(a.x-pointsj.x)+abs(a.y-pointsj.y)(a.x+a.y)/3) mk=j; k+; intq;if(k) q=rand()%k; return mq;elsereturn 26 ;double result(point a,point b,point c,point d)double T=(a.x+a.y+abs(a.x-b.x)+abs(a.y-b.y)+abs(c.x-b.x)+abs(c.y-b.y)+abs(c.x-d.x)+abs(c.y-d.y)+d.x+d.y)*1.0/35+1.0/6;if(b.t!=0)T+=1.0/6;if(c.t!=0)T+=1.0/6;if(d.t!=0)T+=1.0/6;double M=(a.x+a.y)*0.4+(abs(a.x-b.x)+abs(a.y-b.y)*a.t*1.8+(abs(c.x-b.x)+abs(c.y-b.y)*(a.t+b.t)*1.8+(abs(c.x-d.x)+abs(c.y-d.y)*(a.t+c.t+b.t)*1.8+(d.x+d.y)*(a.t+d.t+c.t+b.t)*1.8; cout时间：Tn花费：Mn;return M;void main() for(int w=0;w8;w+) cout第w组结果：nn; srand(time(NULL); points0.setp(3,2,1.50); points1.setp(1,5,1.50); points2.setp(0,8,0.85); points3.setp(3,11,1.3); points4.setp(7,9,1.2); points5.setp(9,6,2.3); points6.setp(14,0,1.5); points7.setp(17,3,1.1); points8.setp(14,6,2.5); points9.setp(10,12,1.8); points10.setp(7,14,0.6); points11.setp(2,16,1.5); points12.setp(11,17,1.5); points13.setp(15,12,0.8); points14.setp(19,9,1.4); points15.setp(22,5,1.2); points16.setp(15,19,1.6); points17.setp(15,14,1.6); points18.setp(20,17,1); points19.setp(21,13,2); points20.setp(25,16,