《数学建模垃圾运输问题论文.doc》由会员分享，可在线阅读，更多相关《数学建模垃圾运输问题论文.doc（21页珍藏版）》请在三一办公上搜索。
1、垃圾运输问题 垃圾运输问题摘要本文对于垃圾运输问题的优化，通过运用目标规划的有关知识对题目给出的坐标数据进行了处理，根据从最远点开始运载垃圾运输费用最低的原则，以及不走回路的前提，采用规划的理论建立了运输车和铲车的调度优化模型，运用MATLAB软件得到了全局最优解，对此类问题的求解提供了一种较优的方案，以达到最少运输费用。问题（1）包含着垃圾量和运输费用的累积计算问题，因此，文中以运输车所花费用最少为目标函数，以运输车载重量的大小、当天必须将所有垃圾清理完等为约束条件，以运输车是否从一个垃圾站点到达另一个垃圾站点为决策变量，建立了使得运输费用最小的单目标的非线性规划模型。运用MATLAB求解，
2、得出了最优的运输路线为10条，此时运输所花费用为2335.05元。通过分析，发现只需6辆运输车（载重量为6吨）即可完成所有任务，且每辆运输车的工作时间均在4个小时左右。具体结果见文中表3。问题（2），建立了以运行路径最短为目标的单目标非线性规划模型。从而求出了使铲车费用最少的3条运行路线，且各条路线的工作时间较均衡。因此，处理站需投入3台铲车才能完成所有装载任务，且求得铲车所花费用为142.8元，三辆铲车的具体运行路线见文中表4。文中，我们假定垃圾处理站的运输工作从凌晨0：00开始，根据各铲车的运输路线和所花时间的大小，将铲车和运输车相互配合进行工作的时间做出了详细的安排见表5。问题（3），要
3、求给出当有载重量为6吨、10吨两种运输车时的最优的调度方案。基于第（1）问中的模型，修改载重量的约束条件，用分别求解，得出两种调度方案，但总的运输费用不变，均为2508.63元；对于方案一，有9条路径，分别需要6吨的运输车2辆；10吨的运输车5辆，各运输车具体的运输线路见文中表8。对于方案二，有10条路径，分别需要6吨的运输车1辆；10吨的运输车4辆，各运输车具体的运输线路见文中表10。问题（4），基于问题（1）、问题（2）、问题（3），修改每个站点的垃圾量，用MATLAB分别求解，得到最优的调整方案最后，对模型的优缺点进行了分析，并给出了模型的改进意见，对解决实际问题具有一定的指导意义。关键
4、词：目标规划；最优解； MATLAB；调度优化模型一问题的重述某城区有36个垃圾站，每天都要从垃圾处理厂（第37号节点）出发将垃圾运回。现有一种载重6吨的运输车。每个垃圾点需要用10分钟的时间装车，运输车平均速度为40公里/小时（夜里运输，不考虑堵车现象）；每台车每日平均工作4小时（0:00-4:00,5:00前必须结束）。运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴，请你给出满意的运输调度方案以及计算程序。问题：1）运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）2）铲车应如何调度（需要多少台铲车，每台铲车的
5、行走路线，运营费用）3）如果有载重量为6吨、10吨两种运输车，又如何调度？（垃圾点地理坐标数据表见附录一）4）如果每个垃圾站点的垃圾量是随机数，标准差为该站点平均垃圾量的10%，该如何调整？二问题的分析这是图论中的一个遍历问题，此问题的困难之处在于确定铲车的行走路线，并使得运输车工作时尽量不要等待铲车，才能使得运输车的工作时间满足题目的要求每日平均工作四小时，为此，应该使铲车跟着运输车跑完一条线路，也就是说，应该使铲车铲完一条线路后再接着铲下一条线路。第（1）问，对于运输车调度方案的设计，不能仅仅考虑使运输车的行走路线最短，因为此处还存在着垃圾的累积运输的花费问题，因此，我们的目标函数应该是使
6、得所有运输的花费最少。在建模过程中，我们无需考虑投入的运输车台数，只需对各条路径所花费的时间进行和各运输车载重量约束即可，至于投入的车辆数，在各条路径确定后，计算出各路径运输所花费的时间，再根据题目中要求的每辆车平均工作时间为4小时左右进行计算即可。第（2）问，对于铲车的调度方案，因其无累积计算问题，因此只需要在已确定的各运输路径的基础上，使得铲车的行驶路径为最短。在此方案中，我们将已确定的各条路径看作为节点，建立使铲车运费最少（亦即路径最短）的非线性规划模型，在此需注意的是，由于垃圾运输为夜间运输，所以每辆铲车的工作时间也受到一定的限制，文中，我们假定铲车的工作时间为从（零晨0：00早4：0
7、0），因此每辆铲车的工作时间最多为5个小时，再由所有运输车完成任务所需的总时间判定所需铲车的台数，之后可以根据具体情况进行调整。同时应注意，由于运输车有工作时间的限制，而铲车没有严格的限制（除工作时间不能超过9小时以外），所以，在确定铲车出行的时间时，应保证只可让铲车等待运输车，而不能让运输车等待铲车。第（3）问，是在第一问的基础上将对运输车载重的约束条件从不大于6吨改为不大于10吨，在求得各条路线中，对于垃圾量不大于6吨的路线，调用6吨的运输车；对于垃圾量在（610吨）之间的路线，调用10吨的运输车。 第（4）问，是在前三问的基础上将对每个站点的垃圾量进行随机调整，使得其标准差为该点平均垃圾
8、量的10%。三模型的假设与符号说明1模型假设（1）假设各站点每天的垃圾量基本相同；（2）假设各站点的垃圾都必须在当天清理完,不允许滞留；（3）不考虑运输车和铲车在行驶过程中出现的堵车、抛锚等耽误时间的情况；（4）不允许运输车有超载现象；（5）每个垃圾站点均位于街道路口，便于垃圾的集中、运输；（6）垃圾只在晚上运输，基本保证运完后，当天不会再有新的垃圾产生；（7）假设卸垃圾及倒车均在10分钟内完成；（8）车在装的足够多的情况下应该直接返回原点2 符号说明 第个垃圾站点向第个垃圾站点运输的垃圾量； 运输车是否从第个垃圾站点向第个垃圾站点运输的0-1变量；第辆铲车是否从第条路径向第条路径运输的0-1
9、变量； 假设所需要的铲车的台数 ：垃圾运输路线总条数；：第条路线上垃圾集中点的个数，；：第条路线上的第个垃圾集中点的横坐标，；：条路线上的第个垃圾集中点的纵坐标：第条路线上的第个垃圾集中点的垃圾量，；:第条路线所需要的总时间；：第辆车的运输总时间；：运输车空载的总费用；：运输车重载的总费用；：运输车的总费用；：铲车空载的总费用四模型的建立与求解模型的建立41 运输车调度方案的模型由于最远的垃圾集中点的运输时间不超过运输车每天平均工作时间，所以可以先不考虑时间的约束。从而建立如下算法：1) 确定重载起点 由于每个垃圾集中点的垃圾量及其坐标是不变，重载运输的费用是不变的，所以为了使总运输费用最少，
10、只要使空载的费用最少，即尽量安排较远的垃圾集中点在同一路线上，从而确定重载起点.2）确定运输车路线走向要求运输时走最短的路线，以及运输费用最低，而且由于运输车的重载费用1.8元/吨是空载费用0.4元/吨的4.5倍，为了使运输总费用最少,那只能从最远的点（）开始运载垃圾，下一个点编号为，走一条路线，向垃圾处理站（坐标原点）方向运回。顺次经过的点遵循满足条件：即其横坐标以及纵坐标均不超过前一点的横、纵坐标，并且各点横、纵坐标递减进行搭配，由若干个点组成一条路线。3）确定运输车路线垃圾集中点数根据每个垃圾集中点的垃圾量，每条路线上的垃圾总量不超过运输车的最大运输量：根据上面算法,建立运输车费用优化模
11、型:4.1.1 运输车调度方案在运输过程中假设没有运输车等待的情况,在四个小时的工作时间里,根据垃圾运输费用优化模型，得到垃圾集中点分配的路线及其时间,为了达到安排运输车最少，把所有的路线分成()类，每类配置一辆运输车，每辆运输车的工作时间：4.2 铲车调度方案的模型此模型的建立基于上问模型的结果，从以上运输车的调度方案得出共有10条路径，在此模型中，我们将10条路径分别看作10个节点，而把垃圾处理站看作为第11个节点（以下将各路径均称作节点），建立了使铲车行驶所需费用最小的模型。在此需要说明的是，由于运输车的路径已经确定，我们只能让铲车跟随着运输车，而不能让运输车在垃圾站点等待铲车。由此可以
12、确定,铲车必须跟随着运输车行走完一条路径，才能转到其他路径继续工作。而对于各路径，其行走方案已定，所以各路径内的费用已经确定。因此，我们需要做的是，找出一种调度方案使铲车在各路径之间的行走所需的费用为最小。4.2.1目标函数的建立各路径内的费用已定，因此我们建立以下使铲车在各路径之间行走所需费用最小的目标函数如下：2.2.2 约束条件的确立：（1）对于1到10号的每个节点，只允许一辆铲车通过，且只通过一次：（2）所有的铲车必须从第11号节点（垃圾处理站）出发，并最终回到11号节点，即从11号节点发出的铲车数和最终返回11号节点的铲车数均为N：（3）为保证每辆铲车均从11号节点出发最终回到11号
13、节点，且不重复已走的路径，则需控制铲车所走路径均为一个环，即对于每个节点，只要有铲车进入则必有铲车出，不进则无出，进与出的状态保持一致： （4）对于每个节点，不允许出现铲车向自己节点运行的路径：（5）不允许出现铲车的路径为，除11号节点以外，在其他节点相互运行的路径：（6）由于垃圾的运输均在夜间进行，则每辆铲车的工作时间不能大于5个小时（即假定工作时间为（凌晨0：00早4：00），另外，由于题目中给定铲车的运行速度，均速度与运输车的平均速度相同，为40公里/小时，的约束条件为：4.2.3铲车规划模型在给出了目标函数和约束条件后，即可得到一个使得铲车运行费用最小的单目标规划模型如下：4.3 载重
14、量不同的运输车调度方案模型此问在第一问的基础上，通过改变垃圾运输车载重量的大小，从而得到垃圾处理厂在拥有不同载重量的运输车时，采用怎样的运输方案使得所花运输费用最少。此模型的目标函数与第一问中的运输车调度方案模型相同，只是在约束条件上将第（6）个约束条件中的载重最多为6吨变成最多为10吨，： 从而可求出在拥有不同载重量运输车的情况下，各运输车的调度方案。模型的求解运输车调度方案模型的求解在不考虑铲车的情况下，利用SPSS，首先据题画出散点图：利用MATLAB编程（见附录二），对运输车调度方案的模型（1）进行求解,求得各垃圾站点的运输方案如表2所示，此时，求得将所有垃圾运回到37号站点运输车所需
15、费用为2335.05元。表2：各运输路径所包含的垃圾站点、运输量及所需时间路径包含的站点运输垃圾总量每条线路所需时间 15.3吨3小时46分钟25.7吨3小时02分钟35.5吨2小时46分钟45.2吨2小时22分钟55.0吨2小时7分钟65.6吨2小时4分钟75.85吨1小时46分钟83.3吨1小时23分钟95.55吨1小时30分钟104.0吨1小时30分钟 从上表可以看出，对于这10条路径上的垃圾总量，有8条都超过了5吨，另两条也超过了载重量的一半，运输车得到了充分地利用，结果非常好。各运输路径以图示表示如下：由题目可知，每台运输车的平均工作时间为4小时，根据此条件对以上10条路径进行规划，
16、发现用6台运输车即可按要求行走完10条路径，所以，处理站只需投入6台垃圾运输车即可完成任务。各运输车行走的路径分别表示如下：表3：各运输车的行走路径、具体路线及所需时间运输车编号路径编号行走路线所需时间第一辆23小时02分钟第二辆13小时46分钟第三辆84小时9分钟3第四辆93小时37分钟5第五辆43小时52分钟10第六辆63小时50分钟7由上表可发现，每辆运输车的运输时间均在4个小时左右，相差很少，很好地达到了时间上的要求，且结果很理想。3.1铲车调度方案模型的求解利用LINGO10编程，对铲车调度方案模型（2）进行求解，得到了使铲车运费最少的行走路线。此时，需要投入的铲车数为3台，且所有铲
17、车完成任务所需费用为202.0元，各铲车的具体行驶路线及所花费的时间如下表.表4：各铲车的具体行驶路线及所花费的时间铲车行走路径具体路线所需时间第一台 8，9，6，54小时22分第二台1，3，104小时30分第三台2，4，74小时26分由上表可以看出3台铲车的工作时间均为4个多小时，相差不大，工作分配地非常合理。铲车及运输车调度方案的具体时间安排在问题的分析中，我们知道，运输车及铲车的工作时间从凌晨0：00早4：00，对于运输车调度方案，由于第三辆第六辆都要运输两条路径上的垃圾，因此，需要确定这4辆运输车具体先行驶哪条路径，而此方案的确定依赖于铲车的行走方案。根据以上求得的各铲车和运输车工作所
18、需时间的多少及铲车应配合运输车进行工作的原则，对他们的工作时间进行安排如下表所示。表5：铲车及运输车相互配合的具体时间安排铲车1：运输路线8965包含站点时间及车号到达时间车辆编号到达时间车辆编号到达时间车辆编号到达时间车辆编号铲车0:3111:1112:2613:581运输车0:3141:1132:2663:584铲车2：运输路线1310包含站点时间到达时间车辆编号到达时间车辆编号到达时间车辆编号铲车1:0922:1224:302运输车1:0923:2034:505铲车3：运输路线247包含站点时间到达时间车辆编号到达时间车辆编号到达时间车辆编号铲车1:0632:4233:493运输车1:0
19、612:4254:236以上时间安排均是基于工作时间从凌晨0：00开始，从上表3和表4可以看出，每辆运输车和每台铲车的工作时间都不超过5个小时，因此，垃圾处理站可根据实际情况将工作开始的时间向前或向后推相应的时间即可。由表5的时间安排可以确定出各运输车的具体行驶路线及出发、返回时间如表6所示.表6:运输车的行走路线运输车编号从37号站点出发时间行走路线返回37号站点时间第一辆 0:00 3:02第二辆0:00 3:46第三辆 0:11 1:41 1:47 4:33第四辆0:201:232:154:22第五辆0:513:133:154:45第六辆0:442:482:504:363.3 载重量不同
20、的运输车的调度方案3.3.1 方案一运用LINGO对模型（3）进行求解可以得到以下7条运输路径，以问题分析中运输车选择的原则即：对于垃圾量不大于6吨的路线，调用6吨的运输车；对于垃圾量在（610吨）之间的路线，调用10吨的运输车；，具体数据如表7所示。此情况下求得的运输费用为2326.17元。表7：方案一的各运输各路径、运输的总垃圾量及运输所需时间运输路径包含的垃圾站点运输总垃圾量运输所需时间112，10 95.6 吨1.33小时213，8 19，285.6 吨1.38小时318，14，31，5，67.35 吨2.23小时424，17，3，1，265.45吨2.37小时530，29，27，15
21、，11，168.7吨3.13小时634，35，20，7，4，2,218.4 吨2.45小时736，23，33，32，22,259.9 吨2.93小时由以上各条路径上的垃圾总量的大小来对运输车辆进行选择，根据各路径运输所需时间的大小，对各辆运输车的行驶方案进行规划，得到结果如下表。根据以上数据可得，当有载重量为6吨、10吨二种运输车时，需要各类载重的运输车辆分别为：对于6吨的运输车，需要3辆；对于10吨的运输车，需要4辆。3.3.2方案二运用MATLAB编程对模型（3）求解（见附录三），可以得到另外一种调度方案，共有8条运输路径，所花费用为2326.17元。各路径的垃圾总量、运输所需时间分别表示
22、如下：表9：方案二的各路径包含的垃圾站点、垃圾总量及运输所需时间运输路径包含的垃圾站点运输的总垃圾量运输所需时间1,29，27，155.52.97小时228，26，21，25，19，14,58.83.2小时336，23，33，32，22,98.72.93小时424，18，35，315.72.53小时534，17，16，6，305.592.12小时613，7，4，25.71.72小时712，8，3，5.551.67小时811，10，20，15.51.33小时同方案一，可根据各路径的垃圾总量选择运输车辆，根据各路径运输所花时间对运输车的行走路径进行安排。对于方案二，由以上数据可得：当有载重量为6吨
23、、10吨三种运输车时，需要各类载重的运输车辆分别为：对于6吨的运输车，需要6辆；对于10吨的运输车，需要2辆。相比较来说，对于两种方案，方案二的结果较好。 3.4 每个垃圾站点的垃圾量是随机数，标准差为该站点平均垃圾量的10%模型五模型结果的分析与检验由于题目中没有给出司机的工资额，因此文中只考虑了垃圾的运输费用。但实际生活中，对于垃圾处理站来说，垃圾的运输所需花费不仅包括运输费用还包括付给司机的工资。运输路径越长，运输所需要的时间就越长，所需要的运输车辆越多，从而需要更多的司机，因而花费更大。因此，在给出了司机工资额的情况下，目标函数中还包括付给司机的工资。另外，此时目标函数不再是单目标函数
24、，而是双目标函数。第二个目标函数是使得运输车行驶的路径最短。六模型的推广与改进方向该模型可以应用在很多方面，比如说货物运输、车辆分配等。七模型的优缺点然而，该问题在站点众多，运输路径较大的前提下，缺点就会显得尤为突出。首先是运输车载重的不足，当运输车的载重不能满足其中任一点的垃圾量时，模型就可能不能适用了，该模型优点是算法简单容易实现,精度特别是后两个模型的精度不是很高.前两问只要进行穷举就能得出最优解.第三问的处理原则不算很精确,有待改进参考文献 【1】全国大学生数学建模竞赛 优秀论文汇编。中国物价出版社，2002【2】宋兆基，徐流美等。MATLAB6.5在科学计算中的应用。清华大学出版社，
25、2005【3】耿素云.集合论与图论(离散数学二分册)M.北京:北京大学出版社,1997.【4】赵可培.运筹学M.上海:上海财经大学出版社,2000.附录附录一：垃圾站地理坐标数据表序号站点编号垃圾量T坐标x(km)坐标y (km)111.5032221.8015332.5554441.2047560.8508651.30311773.2079882.3096991.4010210101.5014011111.1017312122.7014613131.8012914142.80101215200.6071416161.5021617170.8061818181.50111719190.8015
26、12202115321.401.2019229522221.8021023231.4027924241.60151925252.60151426261.00201727272.00211328281.00242029292.10251630301.20281831311.9051232211.30171633333.2025734341.2092035352.5091536361.303012附录二：codeclearx=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
27、9 9 30 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 0;t=1.50 1.50 0.55 1.20 0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.60 1.50 0.80 1.50 0.80 1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.30 1.60 1.20 1.50 1.30 0.00;i=1:37;a=
28、1:37;plot(x,y,*r)for ii=1:37 k=int2str(ii); k=strcat(P,k); text(x(ii),y(ii),k);endw=i;x;y;t;a;w(5,:)=0;jg=zeros(11,11);for i=1:20 sum=0; 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; j1=j1+1; while 1
29、 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; 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=
30、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)+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; els
31、e continue end end n3=jg(u4,1); time(1,u4)=(w(2,n3)+w(3,n3)*2)/40;endn2 time 附录三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 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 0;t=1.50 1.50 0.55 1.20
32、0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.60 1.50 0.80 1.50 0.80 1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.30 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);endw=i;x;y;t;a;w(5,:)=0;jg=zeros(10,10);%11for
33、i=1:20 sum=0; 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; j1=j1+1; while 1 js=0; q=40; for k=1:36 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)
34、-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=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
35、=jg(u1,1); kcost=kcost+0.4*(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 附录四std=normrnd(1.66,0.027556,1,36)std =
36、Columns 1 through 11 1.6414 1.7368 1.6595 1.6675 1.6348 1.6062 1.6513 1.6762 1.6828 1.6138 1.6070 Columns 12 through 22 1.6480 1.6612 1.7266 1.6515 1.6652 1.6861 1.6455 1.6293 1.6161 1.6924 1.6734 Columns 23 through 33 1.7053 1.6475 1.6878 1.7165 1.6766 1.6605 1.6156 1.6941 1.6788 1.6385 1.6746 Columns 34 through 36 1.7188 1.6698 1.6664
