数学模型垃圾车调度问题

1、实用文档 文案大全 作业题之一 垃圾运输调度问题 1.问题重述 某城区有36个垃圾集中点，每天都要从垃圾处理厂（第37号节点）出发将垃圾运回。不考虑垃圾的装车时间。现有一种载重6吨的运输车，运输车平均速度为40公里小时（夜里运输，不考虑塞车现象）；每台车每日平均工作4小时。运输车重载运费1.8元/吨公里；运输车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴。运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）? 序号 站点 编号 垃圾量T 坐标(km) 序号 站点 编号 垃圾量T 坐标(km) x y x y 1 1 1.50 3 2 20 15 1.40 19 9 2

2、 2 1.50 1 5 21 32 1.20 22 5 3 3 0.55 5 4 22 22 1.80 21 0 4 4 1.20 4 7 23 23 1.40 27 9 5 6 0.85 0 8 24 24 1.60 15 19 6 5 1.30 3 11 25 25 1.60 15 14 7 7 1.20 7 9 26 26 1.00 20 17 8 8 2.30 9 6 27 27 2.00 21 13 9 9 1.40 10 2 28 28 1.00 24 20 10 10 1.50 14 0 29 29 2.10 25 16 11 11 1.10 17 3 30 30 1.20 28

3、 18 12 12 2.70 14 6 31 31 1.90 5 12 13 13 1.80 12 9 32 21 1.30 17 16 14 14 1.80 10 12 33 33 1.60 25 7 15 20 0.60 7 14 34 34 1.20 9 20 16 16 1.50 2 16 35 35 1.50 9 15 17 17 0.80 6 18 36 36 1.30 30 12 18 18 1.50 11 17 37 37 0.00 0 0 19 19 0.80 15 12 表1-1 垃圾点地理坐标数据表 2.模型的基本假设与符号说明 2.2 基本假设 1车辆在拐弯时的时间损耗

4、忽略。 2车辆在任意两站点中途不停车，保持稳定的速率。 3只要平行于坐标轴即有街道存在。 4无论垃圾量多少，都不计装车时间。 5 每个垃圾站点的垃圾只能由一辆运输车运载。 6. 假设运输车从A垃圾站到B垃圾站总走最短路线。 7. 任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直角边之和。 实用文档 文案大全 8. 每辆垃圾运输车每次运的足够多，且不允许运输车有超载现象； 9. 假设在运输垃圾过程中没有新垃圾入站。 10. 假设运输车和铲车在行驶过程中不出现的塞车、抛锚等耽误时间的情况； 11. 各垃圾站每天的垃圾量相对稳定。 2.2 符号说明 kT：第k个垃圾集中点的垃圾量,3

5、6,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：运输车的总

6、费用； 3模型的建立 3.1 确定运输车路线算法 由于最远的垃圾集中点的运输时间不超过运输车每天平均工作时间，所以可以先不考虑时间的约束。从而建立如下算法： 1) 确定重载起点 由于每个垃圾集中点的垃圾量及其坐标是不变，重载运输的费用是不变的，所以为了使总运输费用W最少，只要使空载的费用最少，即尽量安排较远的垃圾集中点在同一路线上，从而确定重载起点1iX. 2）确定运输车路线走向 要求运输时走最短的路线，以及运输费用最低，而且由于运输车的重载费用1.8元/吨是空载费用0.4元/吨的4.5倍，为了使运输总费用W最少,那只能从最远的点（1?j）开始运载垃圾，下一个点编号为1?j，走一条路线，向垃圾

7、处理站（坐标原点）方向运回。顺次经过的点遵循满足条件： ?11ijijijijYYXX 即其横坐标以及纵坐标均不超过前一点的横、纵坐标，并且各点横、纵坐标递减进行搭配，由若干个点组成一条路线。 3）确定运输车路线垃圾集中点数 实用文档 文案大全 根据每个垃圾集中点的垃圾量，每条路线上的垃圾总量不超过运输车的最大运输量：LiTiCjij,2,1,61? 根据上面算法,建立运输车费用优化模型: LiTYYXXtsXWiCjijijijijijLii,2,1,6.*4.0min111111? 3.2 运输车调度方案 在运输过程中假设没有运输车等待的情况,在四个小时的工作时间里,根据垃圾运输费用优化模

8、型，得到垃圾集中点分配的路线及其时间ih,为了达到安排运输车最少，把所有的路线分成N(LN?)类，每类配置一辆运输车，每辆运输车的工作时间nH： 4,2,1,1,00,2,1,1?niLiiinHNnniniELiEhH?类条路线在第类条路线不在第 4.模型的求解 4.1 运输车路线的计算 首先根据题所给的数据画出散点图 垃圾点地理坐标 0 5 10 15 20 25 9 24 6 15 28 2 11 17 20 25 7 9 15 5 10 15 21 30 3 0 7 12 19 27 4 9 14 25 1 5 22 3 10 17 0 0 5 10 14 15 2021 25 30

9、35 求解程序(见附录1),得到以下运行结果: 实用文档 文案大全 30 29 27 3 0 0 0 0 0 0 0 28 26 32 25 5 0 0 0 0 0 0 36 23 33 21 0 0 0 0 0 0 0 24 18 35 15 0 0 0 0 0 0 0 34 17 16 2 0 0 0 0 0 0 运输路线 先后经过的垃圾站点序号 空载费用 (元) 重载费用 (元) 运输路程 (km) 运输所需时间（h） 一号线 0-22-0 8.4 45.36 42 1.05 二号线 0-31-6-0 6.8 90.9 34 0.85 三号线 0-12-9-0 8 127.44 40 1

10、.0 四号线 0-20-11-10-0 11.2 147.96 56 1.4 五号线 0-19-13-8-0 10.8 169.02 54 1.35 六号线 0-14-7-4-1-0 8.8 143.1 44 1.1 0 20 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 0 0 0 0 0 0 0 31 6 0 0 0 0 0 0 0 0 0 运输车的最优路线如下图所示： 表1-2 运输路线安排及其费用 实用文档 文案大全 七号线 0-3

11、4-17-16-2-0 11.6 162 58 1.45 八号线 0-24-18-35-15-0 13.6 261 68 1.7 九号线 0-36-23-33-21-0 16.8 339.48 84 2.1 十号线 0-30-29-27-3-0 18.4 385.65 92 2.3 十一号线 0-28-26-32-25-5-0 17.6 318.78 88 2.2 由此得出，运输车空载的总运费为各路线总和的一半乘以空载的运输费用： ?元132*4.01111?LiiiYXW 运输车重载的总运费为各路线的最远点开始至垃圾处理站各自线路上的各个垃圾集中点将线路划分的若干部分，各部分运输车上垃圾量乘

12、以该部分的路程，再将各部分所得的积的总和乘以运输车重载的运输费用： .4.2213)(*8.13612元?kkkkYXTW 运输车总的运输费用为： 元4.234565.22124.12221?WWW。 4.2 运输车调度最优方案 根据计算各路线所需时间的，在运输车每日平均工作四小时左右的前提下，得出路线的最优搭配，从而得出所需最少的卡车数量。由上表1-2中运输所需时间，我们得到如下路线搭配，如表1-3： 表1-3 运输车路线及其时间安排 运输线路车辆安排 运输车 线路 时间 总时间 1 一、十 2小时18分 1小时03分 3小时21分 2 六、十一 2小时12分 1小时06分 3小时18分 3

13、 二、三、五 1小时21分 1小时 51分 3小时12分 4 七、八 1小时42分 1小时27分 3小时9分 5 四、九 2小时6分 1小时24分 3小时30分 由表1-3得出，最少安排五辆运输车对垃圾集中点进行运输，达到最优运输方案。 5. 附录 附录1： 运输车调度方案的程序 clear x=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

14、 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=1:37; plot(x,y,'*r') for ii=1:37 k=int2str

15、(ii); k=strcat('P',k); text(x(ii),y(ii),k); end w=i;x;y;t;a; w(5,:)=0; jg=zeros(11,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+

16、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)&(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 end end kcost=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=