建模B题论文.docx
- 文档编号:572219
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:23
- 大小:239.30KB
建模B题论文.docx
《建模B题论文.docx》由会员分享,可在线阅读,更多相关《建模B题论文.docx(23页珍藏版)》请在冰点文库上搜索。
建模B题论文
2012年
全国大学生数学建模竞赛
选拔赛
题目:
露天矿开采点到加工地间运输车辆的安排问题
参赛队员信息:
姓名
所在学院
班级
学号
参赛队员1
卢佳乐
土木学院
道桥101
101237
参赛队员2
安亚雄
土木学院
道桥101
101242
参赛队员3
朱忠
土木学院
道桥101
101265
露天采矿中车辆调度模型
摘要
本文讨论了露天采矿中车辆调度问题,该问题属于典型的车辆运输分配调度最省模型。
故此首先运用聚类法在以单位距离运载矿石质量最高为原则下将65个开采点划分成四个区域,且每个区域开采的矿石均运载至相应的加工厂,在此基础上首先计算出每个区域总的开采量进而得到各区域的开采量之比,再运用比例分布分配求出车站的最优位置。
对第二问,我们提出假设:
各个开采点的矿石只能一次性被运载完。
这样,对矿车每次装载矿石的重量给出了约束。
由于本题是一个数学规划问题,用常规方法计算时易陷入数字爆炸中,综合考虑,就物流管理系统中运输工具利用和行车路线优化制定问题,我们利用启发式算法中的一种——贪婪思想的扫描法(TheSweepMethod)反复进行扫描,并结合运输工具平均利用率得到多种可行方案,最后比选方案,找出最满意解,该方法简单实用。
对第三问,分别计算出各个区域与整个区域的平均运输效率,运用比较法确定应增加加工量能明显提高运输效率的加工厂。
在本文的末尾,讨论了模型的优缺点和实际应用中的改进方向。
本文利用以上算法较好地解决了问题,得到了问题的最优解。
对于问题一,解得车站应建立在坐标为(79.667,41)的点(如图所示)。
对于问题二,计算分析得出至少需要车辆4辆参与运输,每辆车的运输路线见图时才能使在完成每天的运输任务前提下,所有运输车行驶的总路程最小,此时工作时间分别为7,10.93,10.4,11.8各车辆每天行驶的总距离为217.87,338.7,322.948,367.22。
对于问题三,加大
加工点的最大日加工量可以明显提高运输效率。
关键词:
贪婪思想的扫描法(TheSweepMethod)车辆调度最优模型物流分配管理模型(LRP)
一、问题重述
某矿区有4个加工厂,65个开采点,(单位:
km)。
各加工厂每天有最大加工量,各开采点每天的开采量确定。
矿区位于一个平原地带,任意两点均可连通,它们之间的距离为几何距离。
现将这个矿区从开采点到加工厂的运输任务交给某运输队,运输队首先要根据运输任务大小及加工厂和开采点的分布确定一个车站位置,并建设车站的基础设施。
该车队所用运输车型最大载重量100t,行驶速度31km/h。
每天上午八点,运输车从车站出发,到达各个开采点并将开采点前一天开采的矿石运往加工厂。
晚上八点之前,所有前一天开采的矿石都需要被运往加工厂,运输车则要回到车站进行加油保养等处理。
现在,请根据给定的数据,回答以下问题:
1.给出车站的位置。
2.运输车耗油量很大,因此希望在完成每天的运输任务前提下,使所有运
输车行驶的总路程最小。
此时至少需要多少车辆参与运输,试给出每辆车的运输
路线和工作时间,求出各车辆每天行驶的总距离。
3.加大哪些加工点的最大日加工量可以明显提高运输效率。
二、问题分析
运输在物流中具有十分重要的地位,同时运输车辆优化问题是物流决策的关键所在。
目前,车辆运输耗油量大,油价高以及维护贵,使得物流管理的决策者在制定行车路线时,总是希望运输路线路程最小,并且能够充分利用运输工具的动力,从而减少车辆参加运输。
由于所有问题都涉及到运输车耗油量的问题,在求解时应确定运输路线,用常规算法计算65个开采点运往4个加工点的最优路线时常常会陷入到数字爆炸中,所以首先我们将65个开采点划分为4个区域,如此一来,各个区域的开采点只需将矿石运往相应的加工点,这样由局部(各个区域)运输的最优路线得到整体区域的运输最优路线。
划分完毕后,此时各加工点便成了其相应区域最具代表性的点。
对于问题一,加工点按以单位距离运载矿石质量最优的原则被划分到4个区域后,车站位置的确定便与4各加工点相关。
对于问题二,为确定运输车辆最优路线,先分别求出将各个区域的开采点的矿石运往相应加工点的最优路径,此时选择方便使用易行的GreedySweep算法,各个区域最优路线路程之和再加上运输车从车站出发到各个区域的距离之和便为露天矿开采点到加工地间运输车辆调度的最优路线,此时至少需要参与运输的车辆数,每辆车的运输
路线和工作时间以及各车辆每天行驶的总距离便可确定。
对于问题三,运输效率为运输矿石的质量与运输路线路程之比,在解决增加哪些加工点年加工量可以明显提高运输效率时,可分别算出各个区域以及整个区域的平均运输效率,然后比较大小,从而确定应增加那些加工点的加工量。
三、模型假设
(1)各个开采点的矿石必须一次性运载完毕;
(2)各个开采点每天的开采量达到最大;
(3)忽略在开采点和加工点装卸矿石花费的时间;
(4)车辆在行驶过程中保持匀速速度为31km/h,且不考虑在行驶过程中任意因素的影响;
四、符号说明
:
第
个采矿点的x轴坐标;
:
第
个采矿点的y坐标;
:
第
个采矿点的日最大采矿量;
:
第
加工场的x坐标;
:
第
加工场的y坐标;
:
第
加工场的日最大加工量;
:
车站横坐标;
:
车站纵坐标;
:
车站到第i个采矿点的距离;
:
第i个采矿点到第j个加工点的距离;
:
第i个加工点划分区域后所承担的加工量;
:
车辆到j点是车内的剩余可载货量;
:
归属于第i个加工点的采矿点的数目;
T1:
完成所有运输任务需要的总时间;
:
第i个区域完成运输任务时运输线路总路程;
L:
完成所用运输任务的最优化路线的总路程;
S:
整个区域矿石总开采量。
五、模型的建立与求解
本题是一个基于典型的车辆分配拉货最省模型的实际问题,即要求运输车辆先从车站出发在一定运输时间内经由一些装货点依次完成规定区域的任务达到一定的车辆承受极限后再运往卸货点进行加工的运输路线最短或者用时最短,效率最高的问题。
(一)问题一的建模与求解
我们采用效率最优方法而不是单方面考虑路程来决定车站最优位置。
即综合考虑各个加工点区域内的总加工任务比重与各加工点与待确定车站的距离,从而确定车站的合适位置。
首先考虑车站位置的决定性影响因素,包括四个加工点的占总加工量的比重即
,以及车站距离四个加工点的距离。
故可设目标函数为:
在matlab中编程(数据数据见附录)运行结果如下
车站横坐标为:
车站纵坐标为:
总最高效益为:
(二)问题二的建模与求解
采用启发式算法中的一种——贪婪思想的扫描法(TheSweepMethod),具体方法如下:
以一个仓库区域为例(见例图),首先自仓库始任一方向向外划一条直线,沿着逆时针方向旋转该直线直到与站点1相交,如果在某线路上增加该站点没有超过车辆的承载能力则继续旋转直线,直到与下一个站点相交,重复上述过程直到超过车辆的运载能力,此时,剔除最后的那个站点,运回仓库,随后,从不包含在上一路线中的站点开始,继续旋转直线寻找新的路线,继续该过程直到所有站点都被安排在路线中,得到将区域个站点货物都运送到仓库的一种运输路线。
再依次将站点12,11,10,9,8,7,6,5,4,3,2作为车辆经过的第一个站点重复上述过程,得到相应的运输路线,最后比选方案,找出运送路线最短的方案。
例图
即如果
则
=100,否则j=j+1继续返回重新判断。
直到某时刻j>
计算出此时的路程和
(
表示以顺序点i为起点时求得的最短路程)
即任意区域内的目标函数都为:
约束条件为:
按照上述方法思路使用Matlab编程【见附录】计算后每个区域的行车路线和加工点加工任务以及总的行车路程如下表:
加工点编号
包含采矿点位
日加工任务(单位:
吨)
区域内总最小行车路程(不考虑初始运输车从车站到加工点)(单位:
Km)
一辆车完成区域所有任务行车时间(单位:
h)
S1
23,24,31,32,33,34,35,37,38,44,45,46,49,50,51
388
157.6292
5.1
S2
3,4,5,6,7,15,16,17,19,20,21,22,29,30,42,43
454
366.6102
11.9
S3
1,2,8,9,10,11,12,13,14,18,25,26,27,36,39,40
467
252.8539
8.2
S4
28,41,47,48,52,53,54,55,56,57,58,59,60,61,62,63,64,65
458
270.2203
8.8
计算机编程求得结果经人工手动修改后使得运输路线总路程达到最优。
考虑初始从车站到加工点的距离后各区域内的最短行车里程为:
L1:
170.2538km
L2:
386.2988km
L3:
322.9484km
L4:
367.2203km
各个区域的各车辆行车线路顺序为:
区域S1:
车站→32→23→S1→33→31→37→S1→44→49→50→51→S1→45→46→38→35→34→S1→24→S1→车站,总里程为171.0712km
区域S2:
车站→13→12→S2→30→29→19→S2→20→15→16→S2→3→5→6→S2→21→S2→22→7→4→S2→车站→17→S2→车站,总里程为386.2988km
区域S3:
车站→18→8→1→S3→25→39→36→26→40→S3→27→14→11→12→S3→13→10→S3→9→2→S3→车站,总里程为322.9484km
区域S4:
车站→57→53→54→58→S4→52→48→41→28→47→56→S4→55→60→S4→64→63→S4→65→61→62→59→S4→车站,总里程为367.2203km
四辆车的行车路线:
车辆1:
车站→32→23→S1→33→31→37→S1→44→49→50→51→S1→45→46→38→35→34→S1→24→S1→车站→17→S2→车站
图一
车辆2:
车站→13→12→S2→30→29→19→S2→20→15→16→S2→3→5→6→S2→21→S2→22→7→4→S2→车站
图二
车辆3:
车站→18→8→1→S3→25→39→36→26→40→S3→27→14→11→12→S3→13→10→S3→9→2→S3→车站
图三
车辆4:
车站→57→53→54→58→S4→52→48→41→28→47→56→S4→55→60→S4→64→63→S4→65→61→62→59→S4→车站
图四
四辆车的总线路
图五
所以完成所有运输任务时,最优运输路线路程为1246.721km,此时至少需要车辆4辆参与运输,工作时间分别为,每天行驶的总距离
(三)问题三的建模与求解
运输效率为运输矿石的质量与运输路线路程之比,在解决增加哪些加工点年加工量可以明显提高运输效率时,可分别算出各个区域以及整个区域的平均运输效率,然后比较大小,从而确定应增加那些加工点的加工量。
当分区平均运输效率大于整个区域平均运输效率时,增加该区域加工点的最大加工量能明显提高运输效率,反之,则不能。
当分区平均运输效率大于整个区域平均运输效率时,则该分区平均单位距离运输矿石质量大于整个区域平均单位距离运输矿石质量,因此在增加该分区的最大日加工量,该分区可在相对较短的距离内实现矿石的运输,从而明显提高整个区域的运输效率。
具体计算过程如下:
各分区平均运输效率:
(
=1,2,3,4)
整个区域的平均运输效率:
求得:
比较得:
当增加
加工厂的日加工量时,可以明显提高运输效率。
六、模型评价
(一)特点:
方法简洁,实用,易于在计算机中实现,可处理数据量较大的模型。
(二)优点:
1、采用分区域的方法,简化模型的求解;
2、计算各个区域运输最优路线时采用GreedySweep算法,通过反复运算,依次通过比较排除法选出较优方案,最终得到最优路线,方法简单;
3、运用扫描法,在用Matlab编程计算出结果确定的路线一目了然,并且可以实现人工进一步优化,得到最优路线;
4、综合考虑距离和开采点的日最大开采量,使得模型的求解更加严谨,引入单位距离运输矿石质量(平均运输效率);
5、可以处理数据量较大的模型。
(三)缺点:
1、没有考虑运输车辆在开采点和加工点装卸矿石花费的时间,忽略了司机休息的时间;
2、假设车辆一直保持时速为31km/h,而实际生活中很难做到始终匀速行驶,并且忽略了车辆启动和制动时速度的变化;
3、无论车辆空载还是满载都认为单位时间耗油量为定值,而实际上单位时间耗油量并不相等;
4、分区域后,使得部分行车路线被排除到考虑范围外,无法确定是否还有在完成所有任务的前提下,行车路线路程更小的方案。
参考文献:
[1]杨启帆何勇谈之奕,《数学建模竞赛》,浙江大学:
浙江大学出版社,2005.5。
[2]姜启源谢金星叶俊,《数学模型》,北京:
高等教育出版社,2003.8。
[3]丁源李引珍,物流配送(集货)中运输车辆优化的GreedySweep算法,2012.8.31。
附录:
区域一的程序
z=c';
m=[1:
65];
fori=1:
65
text(x(i),y(i),num2str(m(i)))
end
holdon
x1=[8773.93333103.466715.66667];
y1=[49.43342.7333347.86667];
scatter(x1,y1,'g','filled')
text(x1
(1),y1
(1),'S1')
text(x1
(2),y1
(2),'S2')
text(x1(3),y1(3),'S3')
text(x1(4),y1(4),'S4')
A=[ab];
X=A(:
1);
Y=A(:
2);
N=length(X);
M=length(Y);
forI=1:
N
forJ=I+1:
M
Z(I,J)=sqrt((X(I)-X(J))*(X(I)-X(J))+(Y(I)-Y(J))*(Y(I)-Y(J)));
end
end
[I1J1]=size(Z);
forI=1:
I1
forJ=1:
J1
ifI>J;
Z(I,J)=Z(J,I);
end
end
end
Z;
SS=[388454467458];
B=[x1',y1'];
[p,n]=size(B);
f=1;
xx=0;
yy=0;
xfw=[min(B(:
1)),max(B(:
1))];
yfw=[min(B(:
2)),max(B(:
2))];
smin=1000000;
fori=xfw
(1):
f:
xfw
(2)
forj=yfw
(1):
f:
yfw
(2)
s=0;
fork=1:
p;
s=s+sqrt((i-B(k,1))^2+(j-B(k,2))^2)*SS(k)/1767;
end
ifs xx=i; yy=j; smin=s; end end end fprintf('×î´óµÄµãΪ: (%d,%d)\n',xx,yy); S1=[]; S2=[]; S3=[]; S4=[]; dmin=[,]; fori=1: 65 forj=1: 4 dmin(i,j)=sqrt((x(i)-x1(j))^2+(y(i)-y1(j))^2); end end [yy,pos]=min(dmin,[],2); fori=1: 65 ifpos(i)==1; S1(i)=i; elseifpos(i)==2; S2(i)=i; elseifpos(i)==3; S3(i)=i; elsepos(i)==4; S4(i)=i; end end end end S1jg=0; S2jg=0; S3jg=0; S4jg=0; fori=1: 51 ifS1(i)>0; scatter(x(i),y(i),'k*') S1jg=S1jg+z(S1(i)); end end fori=1: 54 ifS2(i)>0; scatter(x(i),y(i),'b^') S2jg=S2jg+z(S2(i)); end end fori=1: 40 ifS3(i)>0; scatter(x(i),y(i),'g*') S3jg=S3jg+z(S3(i)); end end fori=1: 65 ifS4(i)>0; scatter(x(i),y(i),'r') S4jg=S4jg+z(S4(i)); end end scatter(x(24),y(24),'k*') scatter(x(35),y(35),'k*') scatter(x(4),y(4),'b^') scatter(x(3),y(3),'b^') scatter(x(17),y(17),'b^') scatter(x(54),y(54),'r') scatter(79.96667,41.3,200,'r','filled') w=[]; j=1; S1(24)=24; S3(24)=0; S1(35)=35; S3(35)=0; S2(3)=3; S3(4)=0; S2(4)=4; S3(3)=0; S2(17)=17; S4(54)=54; fori=1: 51 ifS1(i)>0 w(j)=x(S1(i)); ww(j)=y(S1(i)); j=j+1; end end vx (1)=x(45);vx (2)=x(51);vx(3)=x(50);vx(4)=x(49); vx(5)=x(44);vx(6)=x(37);vx(7)=x(31);vx(8)=x(33); vx(12)=x(34);vx(11)=x(24);vx(10)=x(23);vx(9)=x(32); vx(13)=x(35);vx(14)=x(38);vx(15)=x(46); vy (1)=y(45);vy (2)=y(51);vy(3)=y(50);vy(4)=y(49); vy(5)=y(44);vy(6)=y(37);vy(7)=y(31);vy(8)=y(33); vy(12)=y(34);vy(11)=y(24);vy(10)=y(23);vy(9)=y(32); vy(13)=y(35);vy(14)=y(38);vy(15)=y(46); d1(1,2)=Z(45,51);d1(2,3)=Z(51,50);d1(3,4)=Z(50,49); d1(4,5)=Z(49,44);d1(5,6)=Z(44,37);d1(6,7)=Z(37,31); d1(7,8)=Z(31,33);d1(8,9)=Z(33,32);d1(9,10)=Z(33,23); d1(10,11)=Z(23,24);d1(11,12)=Z(24,34);d1(12,13)=Z(34,35); d1(13,14)=Z(35,38);d1(14,15)=Z(38,46);d1(15,16)=Z(46,45); d2 (1)=dmin(45,1);d2 (2)=dmin(51,1);d2(3)=dmin(50,1); d2(4)=dmin(49,1);d2(5)=dmin(44,1);d2(6)=dmin(37,1); d2(7)=dmin(31,1);d2(8)=dmin(33,1);d2(9)=dmin(32,1); d2(10)=dmin(23,1);d2(11)=dmin(24,1);d2(12)=dmin(34,1); d2(13)=dmin(35,1);d2(14)=dmin(38,1);d2(15)=dmin(46,1); d3 (1)=z(45);d3 (2)=z(51);d3(3)=z(50); d3(4)=z(49);d3(5)=z(44);d3(6)=z(37); d3(7)=z(31);d3(8)=z(33);d3(9)=z(32); d3(10)=z(23);d3(11)=z(24);d3(12)=z(34); d3(13)=z(35);d3(14)=z(38);d3(15)=z(46); zuixiao1=100000000; fork=1: 15; ifk>1; n=vx (1); m=vy (1); s=d2 (1); q=d3 (1); p=d1(1,2); fora=1: 14; vx(a)=vx(a+1); vy(a)=vy(a+1); d1(a,a+1)=d1(a+1,a+2); d2(a)=d2(a+1); d3(a)=d3(a+1); end vx(15)=n; vy(15)=m; d2(15)=s; d3(15)=q; d1(15,16)=p; end D3=0;j=0; D=d2 (1); fori=1: 15 D3=D3+d3(i); ifi<15 ifD3>100 j=j+1; D=D+d2(i-1)-d1(i-1,i); D3=0; D=D+d2(i)+d1(i,i+1); D3=D3+d3(i); else D=D+d1(i,i+1); end else ifD3>100 D=D+d2(15)*2-d1(i-1,i); else D=D+d2(15); end end end ifD u=k; zuixiao1=D; end end s1daochezhan=sqrt((x1 (1)-79.67)^2+(y1 (1)-41)^2); chezhandao32=sqrt((x(32)-79.67)^2+(y(32)-41)^2); s1dao32=sqrt((x1 (1)-x(32))^2+(y1 (1)-y(32))^2); zuixiao1=zuixiao1+s1daochezhan+chezhandao32-s1dao32 u line([x1 (1)x(34)],[y1 (1)y(34)]); line([x(34)x(35)],[y(34)y(35)]); line([x(35)x(38)],[y(35)y(38)]); line([x(38)x(46)],[y(38)y(46)]); line([x(46)x(45)],[y(46)y(45)]); line([x(45)x1 (1)],[y(45)y1 (1)]); line([x1 (1)x(51)],[y1 (1)y(51)]); line([x(51)x(50
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 建模 论文