垃圾运输车调度与企业招聘问题(数学建模)

1、数学建模作业题之一 垃圾运输调度问题某城区有个垃圾集中点，每天都要从垃圾处理厂（第号节点）出发将垃圾运回。不考虑垃圾的装车时间。现有一种载重 6吨的运输车，运输车平均速度为40公里小时（夜里运输，不考虑塞车现象）；每台车每日平均工作 4小时。运输车重载运费1.8元/吨公里；运输车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴。运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）? 请给出满意的运输调度方案以及计算程序。附：垃圾点地理坐标数据表序号站点编号垃圾量T坐标(km)序号站点编号垃圾量T坐标(km)xyxy111.503220151.40199221.501521

2、321.20225330.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.502163535

3、1.5091517170.8061836361.30301218181.50111737370.000019190.801512垃圾运输车调度建模求解摘要：本文垃圾车运输调度问题属于离散型最优化问题，通过遗传算法对其进行分析求解。首先对垃圾站点之间分布位置的分析，构造出解决垃圾运输问题的模型，对所给数据绘制其xy散点图，根据题设提出自己假设的条件。其次，结合已有的模型，对垃圾点之间的位置分布关系进行讨论及证明，从而确定最基本的行车路线原则。然后，利用MATLAB软件编写程序，利用计算机进行模拟，从而搜索出各运输车辆的数量以及最佳的分配方案，使得在不考虑铲车及其装车的情况下合理调度，使得运输费用

4、最少。最后求解求得全部的运输费用是2345.4元，花费的总时间是16.5小时；具体的路线分配图及车辆调度图见正文部分。本文讨论的解题方法模型简单，得出的结果只是一个近似最优解的可行解，所以还有很大的改进空间，比如我们可以采用更加智能的算法等。 关键词：计算机模拟 离散型 最优化 MATLAB 运输车调度0. 问题的提出某城区有个垃圾集中点，每天都要从垃圾处理厂（第号节点）出发将垃圾运回。不考虑垃圾的装车时间。现有一种载重 6吨的运输车，运输车平均速度为40公里小时（夜里运输，不考虑塞车现象）；每台车每日平均工作 4小时。运输车重载运费1.8元/吨公里；运输车空载费用0.4元/公里；并且假定街道

5、方向均平行于坐标轴。运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）?1.模型的基本假设与符号说明（一）基本假设1车辆在拐弯时的时间损耗忽略。2车辆在任意两站点中途不停车，保持稳定的速率。3只要平行于坐标轴即有街道存在。4无论垃圾量多少，不考虑装车时间。5每个垃圾站点的垃圾只能由一辆运输车运载。6. 假设运输车从A垃圾站到B垃圾站总走最短路线。7. 任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直角边之和。8. 建设在运输垃圾过程中没有新垃圾入站。9. 假设运输车载工作途中不发生意外也不遇到意外；10.各垃圾站每天的垃圾量相对稳定。（二）符号说明|A| 表示

6、A点到原点的距离，恒正|B| 表示B点到原点的距离，恒正|A-B| 表示A,B两点之间的距离,恒正Ta 表示A点所在地的垃圾量Tb 表示B点所在地的垃圾量cost：运费； time：时间消耗；装的足够多:运输车当前的载重离限载不大于0.55t(垃圾点的最小垃圾量)站点编号: 所在点的编号2模型的建立垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，不能直接套用Krusal，Prim等现成算法，于是根据具体问题设计出随机下山法，用计算模拟搜索，可以搜寻到令人满意的可行解。先注意到两点的情况，设两点分别为A(x1,y1),B(x2,y2)。主要有以下两种情况：一A,B明显有先

7、后次序。-递减状态（如图1所示）不妨设x1x2, y1y2,不难看出A在B的后方,即A比B远。对于前方参考点O,要将A,B对应垃圾点的垃圾全部取回再返回O,一共有三种方式：1O-A-O, O-B-O单独运输。这种情况下，总的路程消费等于空载运行费用(0.4元/公里)与装载时运行费用（1.8元/公里吨）的总和。所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值，于是有：Cost = 0.4*|A| + 1.8*|A|*Ta + 0.4*|B| + 1.8*|B|*TbTime = (2*|A| + 2*|B|)/402. O-A-B-O 先远点再近点，即先空载至最远处，装完A点垃圾

8、后再返回至B,再回O点，有： Cost = 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|/40 3. 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 比较以上三种情况，远近点的遍历顺序，可以看出

9、，“先远后近”绝对比“先近后远”在花费钱的数量上要少的多，省出1.8*|A-B|*2*Tb这部分的钱主要是车载着B点的垃圾奔到A点再返回B点。而又注意到两者的时间花费是相等的。所以在其余同等的情况下选择“先远后近”。考虑到时间上单独运输比其余的两种运输要大的多，而且花费的钱仍不比“先远后近”省，还多了0.4*|B|，所以一般情况下，不采用单独运输。二A，B两点没有明显先后顺序（|A|=|B|且相聚较远）。 -并邻状态（如图2）还是一共有三种情况： 1O-A-O, O-B-O单独运输。这种情况下，跟A,B两点有先后顺序中的情况完全相同，即有：Cost = 0.4*|A| + 1.8*|A|*Ta

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

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

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

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

14、钱；4车在装的足够多的情况下应该直接返回原点（37点）；5每一次布局和每条线路的搜索不妨由剩下未搜点中的最大值开始。3模型的求解（1）首先根据题所给的数据，利用MATLAB软件画出散点图，如图四所示。图四 垃圾站位置坐标图（程序如附录一所示）（2）在不考虑铲车的情况下，及其装载时间，根据基本原则编写程序，进行求解。可得到运输车的最优路线和运营费用及其时间。（程序见附录二）求得运输车总运营费用为2345.4元,重载总费用2213.4元，空载总费用132元，总时间为16.5小时(见表一)。其中运输车共有十一辆，路线共有十一条，运输车的最优路线为（运输路线图如下图图五所示）：表一:各个线路的费用和所

15、需时间站点编号空载费用（元）运营吨位（t）所花时间（h）一号线0-30-29-27-3-018.45.852.3二号线0-28-26-21-25-6-017.65.752.2三号线0-36-23-33-32-016.85.52.1四号线0-24-18-35-20-013.65.21.7五号线0-34-17-16-2-011.651.45六号线0-15-11-10-011.241.4七号线0-19-13-8-010.84.91.35八号线0-14-7-4-1-08.85.71.1九号线0-22-08.41.81.05十号线0-12-9-084.11十一号线0-31-5-06.83.20.85合计

16、1325116.55模型优缺点分析然而，该问题在站点众多，运输半径较大的前提下，缺点就会显得尤为突出。首先是运输车载重的不足，当运输车的载重不能满足其中任一点的垃圾量时，模型就可能不能适用了，该模型优点是算法简单容易实现。参考文献 1全国大学生数学建模竞赛 优秀论文汇编.中国物价出版社，20022宋兆基，徐流美等.数学MATLAB6.5在科学计算中的应用.北京：清华大学出版社，20053薛定宇，陈阳泉著.高等应用数学问题的MATLAB求解.北京：清华大学出版社，2011附录附录一：（各个垃圾站的位置坐标）clearx=3 1 5 4 3 0 7 9 10 14 17 14 12 10 19 2

17、 6 11 15 7 17 21 27 15 15 20 21 24 25 28 5 22 25 9 9 30 0;y=2 5 4 7 11 8 9 6 2 0 3 6 9 12 9 16 18 17 12 14 16 0 9 19 14 17 13 20 16 18 12 5 7 20 15 12 0;t=1.50 1.50 0.55 1.20 1.3 0.85 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 1.4 1.50 0.80 1.50 0.80 0.6 1.3 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20

18、 1.90 1.2 1.60 1.20 1.50 1.30 0.00;i=1:37;a=1:37;plot(x,y,*r)for ii=1:37 k=int2str(ii); k=strcat(P,k); text(x(ii),y(ii),k);end附录二：（运输车的调度）clearx=3 1 5 4 3 0 7 9 10 14 17 14 12 10 19 2 6 11 15 7 17 21 27 15 15 20 21 24 25 28 5 22 25 9 9 30 0;y=2 5 4 7 11 8 9 6 2 0 3 6 9 12 9 16 18 17 12 14 16 0 9 19

19、14 17 13 20 16 18 12 5 7 20 15 12 0;t=1.50 1.50 0.55 1.20 1.3 0.85 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 1.4 1.50 0.80 1.50 0.80 0.6 1.3 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.2 1.60 1.20 1.50 1.30 0.00;i=1:37;a=1:37;plot(x,y,*r)for ii=1:37 k=int2str(ii); k=strcat(P,k); text(x(ii),y(i

20、i),k);end %描出垃圾点坐标散点图w=i;x;y;t;a;w(5,:)=0; %标志位置零jg=zeros(11,11); %记录矩阵for i=1:20 %假定需要20条路线 sum=0; %sum记录垃圾点的垃圾量 j1=1; s=0; m=37; %当前点指示符 i3=37; for j=1:36 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; %标志位置1，表示已到过该点 j

21、1=j1+1; %记录矩阵移至所在行的下一个元素，以记录下一个所到的点 while 1 js=0; q=40; for k=1:36 if(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)=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; %

22、标志位置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=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

23、)+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,n3)+w(3,n3)*2)/40;endn2 time jg计算结果：allcost = 2.3454e+003zcost = 2.2134e+003kcost =132time =2.3000 2.2000

24、 2.1000 1.7000 1.4500 1.4000 1.3500 1.1000 1.0500 1.0000 0.8500jg = 30 29 27 3 0 0 0 0 0 0 0 28 26 21 25 6 0 0 0 0 0 0 36 23 33 32 0 0 0 0 0 0 0 24 18 35 20 0 0 0 0 0 0 0 34 17 16 2 0 0 0 0 0 0 0 15 11 10 0 0 0 0 0 0 0 0 19 13 8 0 0 0 0 0 0 0 0 14 7 4 1 0 0 0 0 0 0 0 22 0 0 0 0 0 0 0 0 0 0 12 9 0 0

25、0 0 0 0 0 0 0 31 5 0 0 0 0 0 0 0 0 0作业题之二：招聘问题某单位组成了一个五人专家小组，对101名应试者进行了招聘测试，各位专家对每位应聘者进行了打分（见附表），请你运用数学建模方法解决下列问题：（1）补齐表中缺失的数据,给出补缺的方法及理由。（2）给出101名应聘者的录取顺序。（3）五位专家中哪位专家打分比较严格，哪位专家打分比较宽松。（4）你认为哪些应聘者应给予第二次应聘的机会。（5）如果第二次应聘的专家小组只由其中的3位专家组成，你认为这个专家组应由哪3位专家组成。数据附表表一序号专家甲专家乙专家丙专家丁专家戊序号专家甲专家乙专家丙专家丁专家戊16873

26、85888623699065657629269746583249285826668388767670802568*65848748173849894267166617594583799583982761747687786846786566628638069768477676686486298668957184853966595943064836190969*977687643160859667871066938090733282849778601185958181693388926659951278669990713460917878811358867263813559977576881494

27、847078863665878664961594818066923784788361851693669174973865936299831763749063923992997986901891798385844084829295761994956496954194906566842056679197564290798581582161807970694367898475932286967984754463826569664585978384707463719286684686766487697567828763864788889680877691739079744862987493627763

28、93979076498093858272788783659168508784809364796584738798519485947493807864828590525575938460818192657782539068889283829082926690545995697574836473845876559863806384847894776795569355668496856184756972577564659463869093729473586394*827687937383909059718261576188697288947460557295856489886388766661865

29、567628090765672758262516578948091827494898763819473639592606584857364906395918793758466707565608364798394797478638566749496897695746491947967637491948396705595836968586384847297939474738569689391829198858379957170708375967699816370799571867373759410086859287747297839764681019278857093737881877869注：*

30、表示专家有事外出未给应聘者打分企业招聘问题建模求解摘要：随着社会的高度细化发展，企业对人才的要求也日趋严格。在大量面试招聘数据下，通过运用数学知识进行相应数据处理显得尤为重要。常见的招聘问题，在给定大量招聘成绩后，使用数理统计中的样本均值和样本标准差进行筛选和排名，辅助以相关统计软件工具（SPSS,EXCEL，MTLAB)，可以使问题得到很好的解决。同时，通过概率论中的正态分布，可以大体把握招聘数据的基本规律。运用MATLAB拟合功能可以很好地求得残缺数据。关键字：数理统计、样本均值、标准差、正态分布、招聘测试0.问题的提出某单位组成了一个五人专家小组，对101名应试者进行了招聘测试，各位专家

31、对每位应聘者进行了打分（见表1），请你运用数学建模方法解决下列问题：（1）补齐表中缺失的数据,给出补缺的方法及理由；（2）给出101名应聘者的录取顺序；（3）五位专家中哪位专家打分比较严格，哪位专家打分比较宽松；（4）你认为哪些应聘者应给予第二次应聘的机会；（5）如果第二次应聘的专家小组只由其中的3位专家组成，你认为这个专家组应由哪3位专家组成。1.模型的基本假设及其分析本招聘问题是五位专家对101个应试者评分，并且每一位专家的评分标准各有差异，如何采用有效的数学方法对各位专家的打分进行综合分析，从而选择出真正的优秀应聘者是我们建立此模型的原因所在。我们运用数学知识对该应聘进行分析，由多数据的

32、标出可知，发现该题是个统计分析问题。由于面试过程绝对的公平是做不到的，只能体现相对公平公正。我们通过数据要能体现实际真实情况，必须要求数据具有很强的代表性和客观性。为此对问题中的数据做以下合理假设，以满足数理统计问题中的基本要求，从而可以对问题合理的简化建模处理。我们对本招聘问题进行一下假设：1) 保证招聘过程中专家打分都是客观公平公正，并且通过招聘成绩数据能够真实反应应聘者的综合能力。2) 专家与专家，应聘者与应聘者，专家与应聘者之间的关系都是相互独立的。3) 假定面试专家组的各位专家打分情况符合各自打分要求，打分风格，并且符合一定的数学规律，具有参考价值。4) 用人单位对每位专家的重视程度

33、都一样，每位专家的打分权重假设都一样。5) 在给定的数据中，我们假设都很好地符合数理统计规律，满足正态分布的特点。我们可以利用正态分布函数的一些规律，对相应的数据参量进行求解。2.模型的符号简要说明EA 专家甲的打分分值期望；A 专家甲的打分标准值。EB 专家乙的打分分值期望；B专家乙的打分标准值。EC 专家丙的打分分值期望；C专家丙的打分标准值。ED 专家丁的打分分值期望；D专家丁的打分标准值。EE 专家戊的打分分值期望；E专家戊的打分标准值。G（i）i=1、2、3、4 .101 第1至101位应聘者专家打分的平均值 参加第二次应聘人数的加权比例系数 3.模型的建立和求解1) 对缺损数据的求

34、解首先，通过问题中的表1数据，运用EXCEL软件和数理统计中样本均值的求解方法，将相关数据处理分析，并求出每一位应试者的原始总分和平均分（残缺的分数先不做处理），并且按照各位考生的平均分排序，得到整合后的表2，由此，可以很好地反应出应试者的整体成绩面貌。由于残缺的数据出现在专家甲乙丙中，构造正态分布函数： （式1） 以专家甲的情况为例，将甲对101名面试者的成绩分别带入到正态分布函数中，得到分布函数曲线，其模拟曲线方程如下（式2）所示，其中（x=N/5，N为序号数，下同）： (式2)这个过程通过MATLAB软件完成，要求注意的是带入数据必须按照（表2）的编号顺序进行，当输入36（EXCEL中对

35、应的残缺数据行序数）时，通过以上分布函数方程-式2，求的最后的结果为 （36）=68.253。同理可知，分别将专家乙，专家丙的打分分别带入到正态分布函数中，得到的模拟曲线方程分别如下（式3），（式4）所示： （式3）(式4)由MATLAB拟合成对应函数，然后在对应函数中输入对应考生序列号。由表2知道，乙与丙的考生序号分别取74,59。然后再分别将这两个值带入到方程-式3，式4中计算，最终我们通过计算得缺损数据分别为：专家乙缺失数据为(74)=92.056，专家丙缺失数据为（59）=84.624。考虑到实际情况，考分保持一致取整数，所以甲，乙，丙三位专家的缺失数据分别取为：68, 92, 85.

36、表二编号考生序号专家甲专家乙专家丙专家丁专家戊原始总分平均分总分139929979869044689.2446219949564969544488.8444351948594749344088440447888896808743987.843955837995839843887.643864817384989443086430787937383909042985.8429840848292957642985.8429966749496897642985.84291064906395918742685.24261191827494898742685.24261269689391829142585

37、42513100868592877442484.84241418917983858442284.44221586909372947342284.44221616936691749742184.24211753906888928342184.2421188290829266904208442019228696798475420844202097939474738541983.84192145859783847041983.84192277639397907641983.841923101927885709341883.64182415948180669241382.641325988583799

38、57141382.64132614948470788641282.44122749809385827241282.44122811859581816941182.24112984789477679541182.24113072978397646840981.84093150878480936440881.64083243678984759340881.64083376917390797440781.44073479658473879840781.44073563819473639540681.240636968977687643248139237676374919483405814053829

39、866895718440480.84043912786699907140480.8404408539665959440380.64034195746491947940280.44024210669380907340280.44024338659362998340280.44024471867373759440180.24014532828497786040180.2401463388926659954008040047707083759676400804004816873858886400804004941949065668439979.83995080786482859039979.8399

40、5136658786649639879.63985281819265778239779.43975388697288947439779.4397543160859667873957939555355997757688395793955656935566849639478.83945778878365916839478.83945830648361909639478.83945958639484827631578.753996024928582666839378.63936142907985815839378.63936273788187786939378.6393633784788361853

41、9178.23916438876767080390783906548629874936238977.83896655986380638438877.63886799816370799538877.63886834609178788138877.63886975678287638638577385702926974658338376.63837146867664876938276.43827217637490639238276.43827389886388766638176.2381742568926584873047639675746371928668380763807694797478638537975.83797727617476877837675.23767896705595836937274.43727928638069768437274.43728054599569757437274.43728160557295856437174.237182776766864863707437083937584667075370743708465608364798336973.83698562516578948036873.6368862