数学模型-垃圾车调度问题

作业题之一垃圾运输调度问题1.问题重述某城区有36个垃圾集中点，每天都要从垃圾处理厂（第37号节点）出发将垃圾运回。不考虑垃圾的装车时间。现有一种载重6吨的运输车，运输车平均速度为40公里／小时（夜里运输，不考虑塞车现象）；每台车每日平均工作4小时。运输车重载运费1.8元/吨公里；运输车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴。运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）?表1-1垃圾点地理坐标数据表序号站点编号垃圾量T坐标(km)序号站点编号垃圾量T坐标(km)xyxy111.503220151.40199221.501521321.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.5021635351.5091517170.8061836361.30301218181.50111737370.000019190.8015122.模型的基本假设与符号说明2.2基本假设1．车辆在拐弯时的时间损耗忽略。2．车辆在任意两站点中途不停车，保持稳定的速率。3．只要平行于坐标轴即有街道存在。4．无论垃圾量多少，都不计装车时间。5．每个垃圾站点的垃圾只能由一辆运输车运载。6.假设运输车从A垃圾站到B垃圾站总走最短路线。7.任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直角边之和。8.每辆垃圾运输车每次运的足够多，且不允许运输车有超载现象；9.假设在运输垃圾过程中没有新垃圾入站。10.假设运输车和铲车在行驶过程中不出现的塞车、抛锚等耽误时间的情况；11.各垃圾站每天的垃圾量相对稳定。2.2符号说明kT：第k个垃圾集中点的垃圾量,36,,2,1k；kX：第k个垃圾集中点的横坐标，36,,2,1k；kY：第k个垃圾集中点的纵坐标，36,,2,1k；L：垃圾运输路线总条数；iC：第i条路线上垃圾集中点的个数，Li,,2,1；N:安排运输车的总数量；ijX：第i条路线上的第j个垃圾集中点的横坐标，iCjLi,2,1,,,2,1；ijY：第i条路线上的第j个垃圾集中点的纵坐标，iCjLi,2,1,,,2,1ijT：第i条路线上的第j个垃圾集中点的垃圾量，iCjLi,2,1,,,2,1；ih:第i条路线所需要的总时间；nH：第n辆车的运输总时间；1W：运输车空载的总费用；2W：运输车重载的总费用；W：运输车的总费用；3．模型的建立3.1确定运输车路线算法由于最远的垃圾集中点的运输时间不超过运输车每天平均工作时间，所以可以先不考虑时间的约束。从而建立如下算法：1)确定重载起点由于每个垃圾集中点的垃圾量及其坐标是不变，重载运输的费用是不变的，所以为了使总运输费用W最少，只要使空载的费用最少，即尽量安排较远的垃圾集中点在同一路线上，从而确定重载起点1iX.2）确定运输车路线走向要求运输时走最短的路线，以及运输费用最低，而且由于运输车的重载费用1.8元/吨是空载费用0.4元/吨的4.5倍，为了使运输总费用W最少,那只能从最远的点（1j）开始运载垃圾，下一个点编号为1j，走一条路线，向垃圾处理站（坐标原点）方向运回。顺次经过的点遵循满足条件：11ijijijijYYXX即其横坐标以及纵坐标均不超过前一点的横、纵坐标，并且各点横、纵坐标递减进行搭配，由若干个点组成一条路线。3）确定运输车路线垃圾集中点数根据每个垃圾集中点的垃圾量，每条路线上的垃圾总量不超过运输车的最大运输量：LiTiCjij,,2,1,61根据上面算法,建立运输车费用优化模型:LiTYYXXtsXWiCjijijijijijLii,,2,1,6..*4.0min1111113.2运输车调度方案在运输过程中假设没有运输车等待的情况,在四个小时的工作时间里,根据垃圾运输费用优化模型，得到垃圾集中点分配的路线及其时间ih,为了达到安排运输车最少，把所有的路线分成N(LN)类，每类配置一辆运输车，每辆运输车的工作时间nH：4,2,1,,1,00,,2,1,1niLiiinHNnniniELiEhH类条路线在第类条路线不在第4.模型的求解4.1运输车路线的计算首先根据题所给的数据画出散点图求解程序(见附录1),得到以下运行结果:垃圾点地理坐标315403791014171412107261115192221271515202124252851725993000510152025051015202530353029273000000028263225500000036233321000000024183515000000034171620000000201110000000001913800000000147410000000220000000000129000000000316000000000运输车的最优路线如下图所示：表1-2运输路线安排及其费用运输路线先后经过的垃圾站点序号空载费用(元)重载费用(元)运输路程(km)运输所需时间（h）一号线0-22-08.445.36421.05二号线0-31-6-06.890.9340.85三号线0-12-9-08127.44401.0四号线0-20-11-10-011.2147.96561.4五号线0-19-13-8-010.8169.02541.35六号线0-14-7-4-1-08.8143.1441.1七号线0-34-17-16-2-011.6162581.45八号线0-24-18-35-15-013.6261681.7九号线0-36-23-33-21-016.8339.48842.1十号线0-30-29-27-3-018.4385.65922.3十一号线0-28-26-32-25-5-017.6318.78882.2由此得出，运输车空载的总运费为各路线总和的一半乘以空载的运输费用：元132*4.01111LiiiYXW运输车重载的总运费为各路线的最远点开始至垃圾处理站各自线路上的各个垃圾集中点将线路划分的若干部分，各部分运输车上垃圾量乘以该部分的路程，再将各部分所得的积的总和乘以运输车重载的运输费用：.4.2213)(**8.13612元kkkkYXTW运输车总的运输费用为：元4.234565.22124.12221。4.2运输车调度最优方案根据计算各路线所需时间的，在运输车每日平均工作四小时左右的前提下，得出路线的最优搭配，从而得出所需最少的卡车数量。由上表1-2中运输所需时间，我们得到如下路线搭配，如表1-3：表1-3运输车路线及其时间安排运输线路车辆安排运输车线路时间总时间1一、十2小时18分1小时03分3小时21分2六、十一2小时12分1小时06分3小时18分3二、三、五1小时21分1小时51分3小时12分4七、八1小时42分1小时27分3小时9分5四、九2小时6分1小时24分3小时30分由表1-3得出，最少安排五辆运输车对垃圾集中点进行运输，达到最优运输方案。5.附录附录1：运输车调度方案的程序clearx=[31540379101417141210726111519222127151520212425285172599300];y=[25478119620369121416181712950919141713201618121672015120];t=[1.501.500.551.200.851.301.202.301.401.501.102.701.801.800.601.500.801.500.801.401.201.801.401.601.601.002.001.002.101.201.901.301.601.201.501.300.00];i=1:37;a=1:37;plot(x,y,'*r')forii=1:37k=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);%´æ·Å11Ìõ·¾¶fori=1:20sum=0;j1=1;s=0;m=37;i3=37;forj=1:36if(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;elsecontinue;endendw(5,m)=1;j1=j1+1;while1js=0;q=40;fork=1:36if(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)==0q=w(2,m)+w(3,m)-w(2,k)-w(3,k);js=1;jg(i,j1)=w(1,k);i3=k;elsecontinue;endendw(5,i3)=1;sum=sum+w(4,i3);j1=j1+1;m=i3;if(w(2,i3)==0&w(3,i3)==0|js==0)breakendendendkcost=0;zcost=0;allcost=0;n=0;foru1=1:11foru2=1:11ifjg(u1,u2)~=0n=jg(u1,u2);elsecontinueendzcost=zcost+w(4,n)*1.8*(w(2,n)+w(3,n));endn=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;foru4=1:11foru5=1:11ifjg(u4,u5)~=0n1=jg(u4,u5);n2=n2+1;elsecontinueendendn3=jg(u4,1);time(1,u4)=((w(2,n3)+w(3,n3))*2)/40;endn2time