垃圾运输问题文档格式.docx
《垃圾运输问题文档格式.docx》由会员分享,可在线阅读,更多相关《垃圾运输问题文档格式.docx(24页珍藏版)》请在冰点文库上搜索。
三.主要变量的说明
|A|表示A点到原点的距离,恒正
|B|表示B点到原点的距离,恒正
|A-B|表示A,B两点之间的距离,恒正
Ta表示A点所在地的垃圾量
cost:
运费;
time:
时间消耗;
装的足够多运输车当前的载重离限载不大于0.55吨(垃圾点的最小垃圾量)
序数号所在点的编号
四.问题的分析与模型的建立
垃圾运输问题最终可以归结为最优路径搜索问题,但注意到此图为森林而不是树,不能直接套用Krusal,Prim等现成算法,于是根据具体问题设计出随机下山法,用计算模拟搜索,可以搜寻到令人满意的可行解。
先注意到两点的情况,设两点分别为A(x1,y1),B(x2,y2)。
主要有以下两种情况:
一.A,B明显有先后次序。
--递减状态(如图1)
不妨设x1>
x2,y1>
y2,不难看出A在B的后方,即A比B远。
对于前方参考点O,要将A,B对应垃圾点的垃圾全部取回再返回O,一共有三种方式:
1.OAO,OBO
单独运输。
这种情况下,总的路程消费等于空载运行费用(0.4元/公里)与装载时运行费用(1.8元/公里吨)的总和。
所需的总时间等于车辆所走过的总路程与速度(40公里/小时)的比值再加上在A,B两点停留的时间(每个垃圾点上停留了10分钟,1/6小时),于是有:
Cost=0.4*|A|+1.8*|A|*Ta+0.4*|B|+1.8*|B|*Tb
Time=(2*|A|+2*|B|)/40+1/6*2
2.OABO
先远点再近点,即先空载至最远处,装完A点垃圾后再返回至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+1/6*2
3.OBAO
先近点在远点,即先装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+1/6*2
比较以上三种情况,远近点的遍历顺序,可以看出,“先远后近”绝对比“先近后远”在花费钱的数量上要少的多,省出1.8*|A-B|*2*Tb这部分的钱主要是车载着B点的垃圾奔到A点再返回B点。
而又注意到两者的时间花费是相等的。
所以在其余同等的情况下选择“先远后近”。
考虑到时间上单独运输比其余的两种运输要大的多,多一一倍,而且花费的钱仍不比“先远后近”省,还多了0.4*|B|,所以一般情况下,不采用单独运输。
二.A,B两点没有明显先后顺序。
--并邻状态(如图2)
还是一共有三种情况:
这种情况下,跟A,B两点有先后顺序中的情况完全相同,即有:
time=(2*|A|+2*|B|)/40+1/6*2
2.OABO
Cost=0.4*|A|+1.8*|A-B|*Ta+1.8*|B|*(Ta+Tb)----〈1〉
Time=(|A|+|A-B|+|B|)/40+1/6*2
3.OBAO
Cost=0.4*|B|+1.8*|A-B|*Tb+1.8*|A|*(Ta+Tb)----〈2〉
Time=(|A|+|A-B|+|B|)/40+1/6*2
相比之下,清晰可见并邻状态下的单独运输所花的费用最少,所以在不要求时间的情况下对于并邻两点,采用单独运输的方式最节约钱。
用<
1>
式与<
2>
式相减除以1.8,得到如下判断式:
|A-B|*(Ta-Tb)+(Ta+Tb)*(|B|-|A|)
----<
3>
上式<
0时,选0ABO;
上式>
0时,选OBAO;
上式=0时,任意选上述两路线。
三.两点选择趋势的讨论。
(如图3)
由图中看到B,C两点没有明显的先后顺序,属于并邻点。
因为当运输车载重行驶时费用会成倍的增长,比其空载时所花费用要大的多,所以排除ABC或ACB这样的一次经过3点的往返路线,仅选择B,C中的某一点与A完成此次运输,将另一点留到下次。
那么A点选择B还是C呢?
不妨假设|B|>
|C|,即B点离原点的距离比C点的更远,因为A在B,C之后,所以也就是B点离A点更近。
这样,此次的运输我们更趋向于选择AB,因为就这三点而论,A无论是选B还是C,三点的垃圾总要运完,所以花费的钱是一样的。
但选择AB后,下次运输车运C点垃圾时就无需跑的更远。
四.关于垃圾点的垃圾是否一次清除的讨论(以6吨车例)
由假设2知,每天的垃圾必须清除完毕,全部运往37点。
这里说的一次清除问题不是指一天,而是指当一辆运输车已经装载了足够多的垃圾,不能完全清理下一个垃圾点的时候,车在下一个站点“停还是不停”的问题。
例如,一辆运输车选择了3026183520的路线(即先将空车开往30,清理装载30点的垃圾,然后依次到26,18,35,20),它从20返回时车已经装载了5.8吨垃圾,仍可以装0.2吨(小于垃圾点垃圾量的最小值0.5,称这种情况为“装的足够多”)。
在20点下方仍有不少的点,但肯定不能将下面的任意点的垃圾装完,那么此车是直接返回37点呢,还是继续装直至车装满为止呢?
我们判断前者更好,就是车在装的足够多的情况下应该直接返回原点(37点)。
这是因为对于下一垃圾点(假设为A点)内的垃圾而言,无论是一次装完还是分两次装完,将它们运回所花费用是恒定的,等于1.8*Ta*|A|。
整体而言,两者花费的钱是相等的,但分两次装要多花10分钟的装车时间,所以选择前者。
综上所述,得出搜索的基本原则:
1.在两点递减的情况下,不采用单独运输;
2.在其余同等的情况下选择“先远后近”;
3.不要求时间的情况下对于并邻两点,采用单独运输的方式最节约钱;
一般情况下用式<
3〉作判断;
4.车在装的足够多的情况下应该直接返回原点(37点);
5.每一次布局和每条线路的搜索不妨由剩下未搜点中的最大值开始。
五.模型的求解
问题一.在不考虑铲车的情况下。
首先根据题所给的数据画出散点图:
求得总运营费用为2345.4元,总时间为22.5小时,求解程序如附录二,运输车的最优路线如下图所示:
站点序号
空载费用
所花时间
一号线
0-30-29-27-3-0
18.4
2.3+2/3
二号线
0-28-26-32-25-5-0
17.6
2.2+5/6
三号线
0-36-23-33-21-0
16.8
2.1+2/3
四号线
0-24-18-35-15-0
13.6
1.7+2/3
五号线
0-34-17-16-2-0
12
1.45+2/3
六号线
0-20-11-10-0
11.2
1.4+1/2
七号线
0-19-13-8-0
10.8
1.35+1/2
八号线
0-14-7-4-1-0
8.8
1.1+1/2
九号线
0-22-0
8.4
1.05+1/6
十号线
0-12-9-0
8
1+1/3
十一号线
0-31-6-0
6.8
0.85+1/3
问题二.铲车加入后的讨论
当加入铲车后,我们应该让铲车将就运输车,因为铲车的空载费用为0.4元/小时.铲车加入垃圾后为1.8元/公里小时.若改变一条线,则会造成几公里的误差,甚至十几公里的误差,这一项的数目就很大.若是铲车将就运输车,则即使路线误差大一点,但所需费用也不会变得很大.故我们以第一个方案的路线为准.这时我们只要保证前一条线路的末节点,与后一条线路的首节点的路程差分别相加之和最小即可.根据这一思路.我们设一个结构数组变量,他有11个元素(代表11条元素).其中每个元素里面有两个结构成员,这样一个元素就代表一条线路.对这11个元素进行排列,这样每一个排列就是一个线路方案.这样便能通过排列,遍历每种方案.就求出最优解.再考虑了最短路径的情况下,由于要考虑和各车在时间地衔接,以及尽量要在规定的时间内作完,我们进行相应的调整。
这部分由于考虑到计算复杂性,我们用手工调整,由于前面有最短路径的保证,我们调整的结果接近最优解。
程序代码如附录三【源码】
程序运行结果见附录三【结果】
线路
时间
0-30-29-27-3-0
2.3+4/6
2.1+4/6
0-24-18-35-15-0
1.7+4/6
0-20-12-9-0
1.0+1/2
0-11-10-0
0.7+1/3
0.55+4/6
13.5小时
根据总时间和个线路的耗时,依平均工作6小时为条件得出需要三量铲车,三辆铲车的起始点分别为36,31,28;
因为运输车时速为40km/h,则铲车速度无须大于40km/h.
若速度小于40km/h,则至少要多买一辆铲车,这样造成重复,故最好多花点钱买大功率的铲车.为了保证能在晚上干完,
我们可以多条路同时干,但考虑到新加铲车费用,我们只让三辆铲车同时工作,就能在规定时间干完。
总费用为81.6元。
问题三:
存在4吨,6吨,8吨三种运输车时的调度
若存在4吨,6吨,8吨三种,我们应把握的原则是:
尽量让8吨的车,拉远处的垃圾,远处垃圾拉得越多,以后车的空载路程就越少,而不考虑空载费用,只把垃圾运回垃圾处理厂,它的这部分费用不变.
同时,我们考虑到8吨,6吨,4吨的运输车费用问题,故8吨的车不宜太多.我们在分析过程中,发现主要是第15点比较难处理,因此8吨的车应将这一点在30那条线上一并处理.
而象第2点,用6吨车单独拉一次太浪费,应用4吨车
还有11,22这两条线也可改用4吨车.
运营总费用为:
2325.8其中运输费用是2213.4空载费用为112.4
求解程序如附录四:
垃圾量
30-29-27-20-11-0
2.3+5/6
7.8
28-26-32-25-14-7-0
2.2+1
7.9
36-23-33-21-22-0
2.1+5/6
7
24-18-35-15-31-5-0
1.7+1
7.95
34-17-16-2-0
5
19-13-8-3-1-0
1.35+5/6
6.95
12-9-0
1.0+1/3
4.1
10-0
0.7+1/6
1.5
6-0
1.3
4-0
0.55+1/6
1.2
运输车
数量
8吨
6吨
2
4吨
3
铲车路线:
铲车跟随运输厂车行驶,先行驶到远点、伴随运输车网回路行驶,铲完一趟后就寻找该离铲车最近的另外一条运输线的起始点(运输车远端),然后再跟着运输车行驶。
六.模型优缺点分析
然而,该问题在站点众多,运输半径较大的前提下,缺点就会显得尤为突出。
首先是运输车载重的不足,当运输车的载重不能满足其中任一点的垃圾量时,模型就可能不能适用了,该模型优点是算法简单容易实现,精度特别是后两个模型的精度不是很高.前两问只要进行穷举就能得出最优解.第三问的处理原则不算很精确,有待改进
七.模型的推广和应用
该模型可以应用在很多方面,比如说货物运输、车辆分配等。
八.参考文献
全国大学生数学建模竞赛优秀论文汇编。
中国物价出版社,2002
宋兆基,徐流美等。
MATLAB6.5在科学计算中的应用。
清华大学出版社,2005
九.附录
附录一:
垃圾点地理坐标数据表
序号
站点编号
垃圾量T
坐标(km)
站点
编号
垃圾量T
x
y
1
1.50
3
2
20
15
1.40
19
9
5
21
32
1.20
22
0.55
4
1.80
0
7
23
27
6
0.85
8
24
1.60
1.30
11
25
14
26
1.00
17
2.30
2.00
13
10
28
29
2.10
16
1.10
30
18
12
2.70
31
1.90
33
0.60
34
35
0.80
36
37
0.00
附录二【源码】
[code]
clear
x=[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:
plot(x,y,'
*r'
)
forii=1:
37
k=int2str(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Ì
õ
Â
¾
¶
fori=1:
20
sum=0;
j1=1;
s=0;
m=37;
i3=37;
forj=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;
elsecontinue;
end
w(5,m)=1;
j1=j1+1;
while1
js=0;
q=40;
fork=1:
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;
w(5,i3)=1;
sum=sum+w(4,i3);
m=i3;
if(w(2,i3)==0&
w(3,i3)==0|js==0)
break
kcost=0;
zcost=0;
allcost=0;
n=0;
foru1=1:
11
foru2=1:
ifjg(u1,u2)~=0
n=jg(u1,u2);
elsecontinue
zcost=zcost+w(4,n)*1.8*(w(2,n)+w(3,n));
n=jg(u1,1);
kcost=kcost+0.4*(w(2,n)+w(3,n));
allcost=zcost+kcost
zcost
kcost
11;
time=[i];
time(1,:
n1=0;
n2=0;
n3=0;
foru4=1:
foru5=1:
ifjg(u4,u5)~=0
n1=jg(u4,u5);
n2=n2+1;
n3=jg(u4,1);
time(1,u4)=((w(2,n3)+w(3,n3))*2)/40;
n2
time
附录三[源码]
r=1:
%plot(x,y,'
);
%forii=1:
%k=int2str(ii);
%k=strcat('
%text(x(ii),y(ii),k);
%end
w=[r;
t];
point=[3028362434201914221131;
352115298122106;
point(3,:
s=80;
p=80;
k=2;
j1=0;
j2=0;
m=1;
b=1:
pai=[b];
pai(1,:
ifs>
=w(2,point(1,j))+w(3,point(1,j))&
point(3,j)==0
s=w(2,point(1,j))+w(3,point(1,j));
j1=j;
point(3,j1)=1;
pai
(1)=point(1,j1);
whilem