数学模型垃圾运输调度问题和招聘问题Word文档格式.docx
《数学模型垃圾运输调度问题和招聘问题Word文档格式.docx》由会员分享，可在线阅读，更多相关《数学模型垃圾运输调度问题和招聘问题Word文档格式.docx（50页珍藏版）》请在冰点文库上搜索。
15
1.40
19
9
5
21
32
1.20
22
0.55
4
1.80
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
1.2问题要求
根据上述基本情况建立的模型中的约束条件，利用计算机编程求解，得出满意的运输车调度方案，包括需要投入多少台运输车，每台车的调度方案以及运营费用。
2.模型建立
在建立模型之前，对垃圾车调度问题做一些基本的假设，并给出建立模型时所需要的符号说明，在分析问题的基础上，建立合理优化的模型。
2.1模型假设
根据题目要求给出如下模型假设条件：
（1）忽略运输车装载垃圾的时间；
（2）车辆在任意两站点中途不停车，保持稳定的速率；
（3）不考虑运输车在行驶过程中出现的塞车、抛锚等耽误时间的情况；
（4）每个垃圾站点均位于街道旁，保证运输车和铲车行驶顺畅
（5）只要平行于坐标轴即有街道存在；
（6）各站点每天的垃圾量是不变；
（7）在运输垃圾过程中没有新垃圾入站；
（8）各站点的垃圾都必须在当天清理完毕的；
（9）每个垃圾站点的垃圾只能由一辆运输车运载；
（10）不允许运输车有超载现象；
（11）运输车A垃圾站到B垃圾站总走最短路线。
2.2符号说明
根据题设条件，现在对其中的一些变量用字母符号代替，现在对其进行一个系统的说明，如下所示：
（1）（Xi，Yi）：
编号为i站点的坐标；
（2）Si：
编号为i站点的垃圾量；
（3）M载：
运输车负载的费用；
（4）M空：
运输车空载的费用；
（5）M总：
运输总费用；
（6）N：
所有运输车发车次数总和；
（7）Cj：
第j台车发车次数；
（8）Tj：
表示第j台发车所需的时间
（9）
（10）
2.3模型分析
本题中最需要考虑的是运输费用，在保证时间、载重量有限的前提下，如何安排车辆、如何选择路线都是为运营费用的最小化提供条件。
所以，首要考虑如何使运营费用最少，然后再考虑如何安排车辆和路线。
本题中运营费用包括运输重载时的费用和空载时的费用。
即：
M总=M载+M空
（1）
考虑到重载时费用远远高于空载时的费用，所以让运输车开到最远处然后再返回时沿途把垃圾运回，这样的营运费用最少。
由于题设中假定街道方向均平行于坐标轴，每个垃圾站到垃圾厂的距离可以记为
，所以运输过程中重载费用可以表示为：
M载=
（2）
从
（1）式中可以看出运输车的重载时的费用是一定的，所以运输总费用取决于空载费用M空，空载费用的取决于各车次最远点的选择问题，每次发车运输空载费用能否最少取决于路径的选择，为了使空载费用最少，在选择路径的时候应该秉着一下几个原则：
（1）由远及近。
某车次最远起始点的选择直接关系到运费多少，所以该车次在沿途返回中应尽量把较远点的垃圾带回，不让下一车次再把某较远点作为起始点。
设两点分别为A（Xa,Ya）,B（Xb,Yb）。
在坐标图中的位置如图1所示
图1
不难看出A在B的后方,即A比B远。
对于前方参考点（0，0）,要将A,B对应垃圾点的垃圾全部取回再返回（0，0）,一共有三种方式：
1）．0→A→0,0→B→0
单独运输。
这种情况下，总的路程消费等于空载运行费用（0.4元/公里）与装载时运行费用（1.8元/公里吨）的总和。
所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值。
于是有：
费用：
M总=0.4*（Xa+Ya）+1.8*（Xa+Ya）*Sa+0.4*（Xb+Yb）+1.8*（Xb+Yb）*Sb
时间：
T1=（2*（Xa+Ya）+2*（Xa+Ya））/40
2）.0→A→B→0
先远点再近点，即先空载至最远处，装完A点垃圾后再返回至B,再回0点，如图2所示：
图2
根据图2，可计算费用和时间如下：
费用：
M总=0.4*（Xa+Ya）+1.8*（Xa+Ya）*Sa+1.8*（Xb+Yb）*Sb
T1=2*（Xa+Ya）/40
3）.0→B→A→0
先近点在远点，即先装B点垃圾，然后载着B点的垃圾奔至A点，再回O点，如图3所示：
根据图3，可计算费用和时间如下：
M总=0.4*（Xb+Yb）+1.8*（Xa+Ya）*Sa+1.8*（2Xa+2Ya-Xb-Yb）*Sb
图3
（2）两站点之间走最近距离。
两个站点之间走的路径有很多，但是在运输过程中选择最短距离来行驶。
如图4所示，从A点到B点有很多路径，如路径1、2、3，路径1和路径2走的距离相等，但是路径3走的距离明显很大，所以运输车在行走的过程中应该选择路径1或2。
图4
（3）车次较少原则。
车次越多，选择的最远点越多，跑的空路就越多，费用也就越多。
考虑到目标函数（运输费用）之后，还要考虑一些约束条件，该模型中有如下几个约束条件需要考虑：
（1）载重量约束：
每个车次的载重量小于6吨；
（2）时间约束：
每个车次出车一次的时间小于4小时；
（3）路线约束：
每个车次走的路径中上一个站点离垃圾厂的距离比下一个站点离垃圾厂的距离远。
2.4模型建立
根据上述的基本假设、符号说明以及模型的分析，运输车的费用可以表示如下：
（1）重载费用：
（2）空载费用：
（3）总费用：
以上目标函数应该满足以下约束条件：
，
3.模型求解
3.1模型坐标图
从表1垃圾地理位置坐标数据表中可以看出，序号和站点标号不一致，为了避免建模过程中弄混，所以首先将站点编号与序号改为一致，得到如表2的坐标数据表。
表2修正后的坐标数据表
0.6
1.4
根据表2坐标利用MATLAB中plot函数画出垃圾厂坐标图如图5所示，P1~P36依次表示编号1~36的垃圾站点，P37表示垃圾厂。
程序见附录I。
图5垃圾厂坐标图
3.2求解结果
首先，我们不考虑一辆车一共发车多少次，即我们只考虑发车总共次数。
根据上述模型分析，不难看出，P28（24,20）、P30（28,18）、P36（30,12）应该作为某车次的最远点，根据约束条件
（1）和
（2）的要求，只有这三个发车最远点时远远不够的，所以又选入了一些发车的最远点，并做到统筹兼顾，一直满足约束条件最大为止。
根据MATLAB编程得到最远点选择。
程序见附录II，利用程序II，得到最远点（ZYD）结果为：
ZYD=30283624341514111222。
得到如下最远点，P24（15,19）、P34（9,20）、P15（19,9）、P14（10,12）、P11（17,3）、P12（14,6）、P22（21,0）。
确定最远点之后再确定行走路线。
利用MATLAB编程，对运输车调度方案的模型进行求解,程序见附录III，
其运行结果为RESULT=
3029273000000
282621251900000
36233332000000
24183520000000
3417162000000
151374000000
143156000000
12800000000
11910000000
221000000000
得到如下10个车次的行车路线：
第一车次路线：
第二车次路线：
第三车次路线：
第四车次路线：
第五车次路线：
第六车次路线：
第七车次路线：
第八车次路线：
第九车次路线：
第十车次路线：
此时，求得将所有垃圾运回到37号站点运输车载重费和空载费分别是2213.77元和122.4元，总计为2335.77元，总共花费时间是15时18分。
根据上面的求解结果，将各车次经过的站点、所花费的费用、花费的时间列表如表3所示：
表3各车次经过的垃圾站点、载输量、费用及所需时间
车次
经过的站点
载重量/吨
载重费/元
空载费/元
时间
37-30-29-27-3-37
5.85
386.1
18.4
2时18分
37-28-26-21-25-19-37
5.7
345.42
17.6
2时12分
37-36-23-33-32-37
5.5
339.48
16.8
2时6分
37-24-18-35-20-37
5.2
261
13.6
1时42分
37-34-17-16-2-37
5.0
162
11.6
1时27分
37-15-13-7-4-37
5.6
196.92
11.2
1时24分
37-14-31-5-6-37
5.85
174.42
8.8
1时06分
37-12-8-37
159.3
1时
37-11-9-1-37
4.0
84.34
37-22-10-37
3.3
105.84
8.4
1时03分
总和
51
2213.37
122.4
15时18分
从表3可以看出，这十个车次中前面八条车次的载重量都超过了5吨，只有两个车次的载重量在5吨以下，但是也都超过了3吨，所以运输车在载重上有充分的利用。
根据表3得到的各运输路径如图6所示，从图6可以看出，每条路径中垃圾车的运输都是由远及近，在载重量的约束下使用车次最少，都是按最小路径行驶的，满足模型分析中的三个要求。
路径5和7虽然交叉，但是到交叉点的路程时刻不一样，不会影响正常运输。
图6运输车路径图
3.3优化结果
根据3.2的分析，运输车在载重上有充分的利用，但是每个车次在时间上的利用不够充分，题设中允许每台车的平均每天可以行驶4小时，大部分车次都只花了2个小时左右，所以每个车次用一辆车的话车辆资源有点浪费，所以结果需要优化。
可以将十个车次用4辆车来完成任务，其结果如表4所示，只有一辆车超过4个小时几分钟，但满足平均所有的车每天工作不超过4个小时的题目要求。
表4各运输车走的车次、经过的站点及所需时间
运输车编号
车次编号
所需时间
3时42分
3时39分
3时49分
4时09分
4.结果分析
该模型中以运输费用为首要考虑问题，其他条件作为其目标函数的约束条件。
题目中没有给出司机的工资，装载垃圾消耗的时间等，因此文中只考虑了垃圾的运输费用。
这样的模型有点不现实，与日常生活中的问题有一定的出入，因为实际生活中，对于垃圾处理站来说，垃圾的运输所需花费不仅包括运输费用还包括付给司机的工资。
运输路径越长，运输所需要的时间就越长，所需要的运输车辆越多，从而需要更多的司机，因而花费更大。
因此，在给出了司机工资的情况下，目标函数中还包括付给司机的工资。
关于时间的约束条件，垃圾装载的时间没有考虑进来，每个垃圾站的垃圾量不一样，其装载花费的时间也不一样，该模型中并未给出关于这个时间的考虑，这是欠缺之处。
5.模型评价
在此，对该模型的优缺点进行分析：
模型的优点：
（1）该模型简单明了，便于理解和灵活运用。
（2）模型中将各约束条件均考虑在内，对问题的理解较全面，因此求出的结果为最优。
（3）建模方法和思想对其他类型也适用，如公交车调度问题、露天矿生产车辆安排问题等。
易于推广到其他领域问题。
（4）本模型直观，易于在计算机上实现。
模型的缺点：
（1）该模型简单，忽略了很多现实的因素，如垃圾装载时间、垃圾车车辆需要的司机费用等，所以在实践中还有待考虑。
（2）对于一个垃圾站点，一旦有运输车到此运输，则必须将所有垃圾带走，而不能分批次运输，从而导致第8和第10条路径的总垃圾量分别为3.3和4吨，运输量太少的情况，运输车不能得到充分地利用。
模型中将各约束条件均考虑在内，对问题的理解较全面，因此求出的结果为最优。
（3）该模型的精度有待考虑。
6.模型推广及应用
参考文献
[1]全国大学生数学建模竞赛优秀论文汇编。
中国物价出版社，2002.
[2]宋兆基，徐流美等。
MATLAB6.5在科学计算中的应用,清华大学出版社,2005.
[3]吴国建。
数学建模案例精编。
中国水利水电出版社，2005.5.
附录I坐标图求解程序
clear
x=[31543709101417141210192611157172127151520212425285222599300];
y=[25478119620369129161817121416091914171320161812572015120];
i=1:
37;
a=1:
plot（x,y,'
.r'
）
forii=1:
k=int2str（ii）;
k=strcat（'
P'
k）;
text（x（ii）,y（ii）,k）;
end
附录II路径最远点求解程序
x=[315430791014171412101926111572221271515202124252816222599300];
y=[2547118962036912916181712950141914221320161812572015120];
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];
r=1:
%plot（x,y,'
*r'
）;
%forii=1:
%k=int2str（ii）;
%k=strcat（'
%text（x（ii）,y（ii）,k）;
%end
w=[r;
x;
y;
t];
11;
point=[3028362434201914221131;
352115298122106;
a];
point（3,:
）=0;
s=80;
p=80;
k=2;
j1=0;
j2=0;
m=1;
b=1:
ZYD=[b];
ZYD（1,:
forj=1:
11
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））;
elsecontinue
end
j1=j;
point（3,j1）=1;
ZYD
（1）=point（1,j1）;
whilem<
40
fori=1:
if（p>
=w（2,point（1,i））+w（3,point（1,i））-w（2,point（2,j1））-w（3,point（2,j1）））&
point（3,i）==0
p=w（2,point（1,i））+w（3,point（1,i））-w（2,point（2,j1））-w（3,point（2,j1））;
j2=i;
point（3,j2）=1;
ZYD（k）=point（1,j2）;
k=k+1;
j1=j2;
m=m+1;
ZYD
附录III调度方案求解程序
x=[315430791014171412101926111572221271515202124252816222599300];
y=[2547118962036912916181712145091914221320161812572015120];
w=[i;
升级会员 