垃圾运输问题.docx
《垃圾运输问题.docx》由会员分享，可在线阅读，更多相关《垃圾运输问题.docx（11页珍藏版）》请在冰点文库上搜索。
垃圾运输问题
A题垃圾运输问题
01组
A题垃圾运输问题
摘要
本文通过对垃圾站点之间分布位置进行了讨论与分析，并构建了相应的模型。
鉴于运输路线的复杂性，我们先画出了站点的散点图，对其进行分析，考虑了投入运输车和铲车的台数、每台的调度方案、运营费用，通过MATLAB编程，得到了一组可行解：
第一问：
求得运输车运输过程中所需总费用为2329.4元，总时间为20.5小时。
第二问：
求得铲车的总运费为145.6元。
第三问：
求得运输车运输过程中总费用为2313.4元，所需总时间为17.5小时。
关键词：
哈密顿图
一、问题重述
某城区有36个垃圾集中点，告诉了垃圾站的地点，并给出了每个垃圾站的坐标和垃圾量，每天都要从垃圾处理厂（第37号节点）出发将垃圾运回。
现有一种载重6吨的运输车。
每个垃圾点需要用10分钟的时间装车，运输车平均速度为40公里/小时（夜里运输，不考虑塞车现象）；每台车每日平均工作4小时。
运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴。
请你给出满意的运输调度方案以及计算程序。
问题：
1.运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）？
2.铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用）？
3.如果有载重量为4吨、6吨、8吨三种运输车，又如何调度？
站点编号
垃圾量T
坐标（x，y）（km）
1
1.5
32
2
1.5
15
3
0.55
54
4
1.20
47
5
1.30
311
6
0.85
08
7
1.20
79
8
2.30
96
9
1.40
102
10
1.50
140
11
1.10
173
12
2.70
146
13
1.80
129
14
1.80
1012
15
1.40
199
16
1.50
216
17
0.80
618
18
1.50
1117
19
0.80
1512
20
0.60
714
21
1.30
1716
22
1.80
210
23
1.40
279
24
1.60
1519
25
1.60
1514
26
1.00
2017
27
2.00
2113
28
1.00
2420
29
2.10
2516
30
1.20
2818
31
1.90
512
32
1.20
225
33
1.60
257
34
1.20
920
35
1.50
915
36
1.30
3012
37
0.00
00
二、符号说明
运输车所需总费用；
铲车所需总费用；
载重量为4吨、6吨、8吨时运输车的总费用；
运输车所需总时间；
载重量为4吨、6吨、8吨时运输车的总时间；
三、模型假设
1、每个垃圾集中点的垃圾只能有一辆车运载；
2、运输车在垃圾集中点装载的垃圾都运到垃圾处理厂；
3、运输车启动和拐弯的时间忽略；
4、垃圾集中点都在街道边上；
5、在每一个垃圾集中点装垃圾所用时间为十分钟，不多也不少；
6、车辆在运输中，除了垃圾集中点之外不会在途中停车，也不出现任何交通事故；
四、模型的建立与求解
先研究两点的情况，设两点坐标分别为
，
，
点垃圾量设为
，
点垃圾量设为
，且
比
更靠近右上方，如下图所示：
1、当单独运输既
时，所需总费用为：
．
2、当运输路线为
时，所需总费用为：
．
3、当运输路线为
时，所需总费用为：
．
比较上述三种情况，显然第3个方案更加节省费用，即：
在一条运输线上，应该先开空车到距垃圾处理厂最远处的垃圾集中点，然后依次在垃圾集中点装运垃圾运往垃圾处理厂。
而考虑运输车的承载能力，载重不能超过6吨。
一、运输车的调度
1、根据题中给出的各垃圾集中点的坐标，通过MATLAB画出其平面坐标系中的坐标，如下图所示：
基本思路：
首先，确定某路线上距处理厂最远的垃圾站点。
其次，从该点依次找寻返回垃圾处理场路线上满足条件的垃圾集中点，同时满足以下三个条件：
1、下一个垃圾点必须位于上一个垃圾点的左下方，2、不能超载，即：
不能超过6吨，3、找寻下一个垃圾点时，使距上个点的间距要短。
最后，因为重载运费比空载运费高得多，所以让运输车空载开往某路线距处理厂最远的垃圾站，然后按该路线依次装运垃圾返回处理厂。
通过MATLAB编程，得到运输车运输时的路线如下表：
根据运输路线可以得到运输车所走的路线图，如下图所示：
站点编号
时间
一号线
37→30→36→23→33→37
2.3+4/6
二号线
37→28→29→27→19→37
2.2+4/6
三号线
37→26→21→25→14→37
1.85+4/6
四号线
37→24→18→35→20→3→37
1.7+5/6
五号线
37→34→17→16→5→4→37
1.45+5/6
六号线
37→15→13→12→37
1.4+3/6
七号线
37→32→22→10→37
1.3+3/6
八号线
37→11→9→1→37
1+3/6
九号线
37→31→7→8→37
0.85+3/6
十号线
37→6→2→37
0.4+2/6
综上。
可以看出一共投入了10运输车，每台车的调用方案如上表，运营总费用
元，总时间为：
小时。
二、铲车的调度
模型一：
铲车按照上述运输车的路线行走，设其速度和运输车的速度相同，为40公里/小时，每台铲车每日平均工作7小时。
分析可得，铲车所用的总时间和运输车所用时间相同，为20.5约所用铲车数为3，铲车空载运行时所需费用为：
．
模型二：
由于前两个模型比较不经济所以我们假定铲车在完成规定任务再回去，为了考虑方便我们考虑路线的逆向图，首先我们假定4辆铲车的终点线路端点为线路的末端，然后从首端依次寻找离上一个运输线路首段最近的下一个运输线的末端，依次类推，三条线路的首端同时比较同一条路线看看离哪个比较近，从而找到比较经济的线路
车辆号
运输路线图
1
37（站点）→1（线路）→6（线路）→7（线路）→8（线路）→37（站点）
2
37（站点）→3（线路）→9（线路）→37（站点）
3
37（站点）→5（线路）→10（线路）→37（站点）
4
37（站点）→2（线路）→4（线路）→37（站点）
经lingo解得，铲车总费用为145.6元。
三、当有4吨、6吨、8吨三种运输车的调度
1、先根据题中给出的各垃圾集中点的坐标，画出散点图，如图1.
然后对其运输路线进行分析：
基本思路：
首先，确定某路线上距处理厂最远的垃圾站点。
其次，从该点依次找寻返回垃圾处理场路线上满足条件的垃圾集中点，同时满足以下三个条件：
1、下一个垃圾点必须位于上一个垃圾点的左下方，2、不能超载，即：
不能超过8吨，3、找寻下一个垃圾点时，使距上个点的间距要短。
最后，因为重载运费比空载运费高得多，所以让运输车空载开往某路线距处理厂最远的垃圾站，然后按该路线依次装运垃圾返回处理厂。
通过MATLAB编程，得到运输车运输时的路线如下表：
根据运输路线可以得到运输车所走的路线图，如下图所示：
综上。
可以看出一共投入了8运输车，每台车的调用方案如上表，运营总费用为
元，总时间为
小时。
五、模型的优缺点及改进
优点：
对于城区垃圾回收过程中，我们对运输车、铲车如何调度的问题进行了分析，考虑了运输车、铲车的台数，每台车的调度方案及运营费，考虑了每条路线中，下一个垃圾点必须位于上一个垃圾点的左下方，不能超载，找寻下一个垃圾点时，使距上个点的间距要短，这样更加优化运营费用，通过MATLAB编程，得到了每个站点的散点图，运输路线，这样比较直观的看出每辆车的调度情况，同时也得到了运营费用和总时间，相对较优。
缺点：
假定条件过于理想化，运输车和铲车出现维修问题时怎么解决。
有些车没有满载，运输过于规矩化
改进：
考虑到垃圾集中点之间的运输，即：
从一条运输线上的垃圾不直接运会垃圾处理场，而是，放到其他垃圾集中点，由其他车来运回垃圾处理场，因为空载费用低，并且使每辆车尽量满载。
六、参考文献
[1]刘卫国编,MATLAB程序设计教程,北京:
中国水利水电出版社,2010.2.
升级会员 