资源描述：
《垃圾运输问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、垃圾运输问题10601010121王凌竹10601010118于仁富10607020133杨文刚垃圾运输问题摘要：该题我们的主要解题思路分三阶段：第一阶段，我们先根据题设条件和基本假设画出该题的图。第二阶段，我们根据图和点的位置关系结合题设，归纳出一些最基本的确定路线的原则：在仔细分析该题后，我们认为该题为一个单目标规划题。我们先抛开空载费用，若要把所有的垃圾运回垃圾处理站，这部分有效工的费用为∑1.8＊
2、Xi
3、＊Yi(
4、Xi
5、为垃圾点Xi到原点的距离,Yi为垃圾点的垃圾量)，是恒定不变的。只要我们能保证空载路线最小，则所花的时间和费用都最小。因此解题的关键在于找出
6、一个调度方案，使空载行驶的线路最小。第三阶段则是编制程序阶段，采用计算机模拟搜索的计算方法，搜索出运输车投入辆数以及运输车最佳调配方案，使得在不考虑铲车的情况下运营费用最低。总运营费用为运输车空载费与实际运输费之和。问题的解答如下：第一问，求得所需总费用为2345.4元，所需总时间为22.5小时，路线分配图见正文；第二问，求得需3辆铲车，铲车费用为81.6元，分配图及运输车调度表见正文；第三问，运营总费用为：2325.8，其中8吨、6吨、4吨载重量的运输车各需5、2、3辆，路线分配图见正文。关键词：单目标优化计算机搜索一．问题的重述某城区有36个垃圾集中点，每天都要
7、从垃圾处理厂（第37号节点）出发将垃圾运回。现有一种载重6吨的运输车。每个垃圾点需要用10分钟的时间装车，运输车平均速度为40公里／小时（夜里运输，不考虑塞车现象）；每台车每日平均工作4小时。运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴。请你给出满意的运输调度方案以及计算程序。问题：1.运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）2.铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用）3.如果有载重量为4吨、6吨、8吨三种运输车，又如何调度？（垃圾点地理坐标数据表见附录
8、一）一．模型的假设1．车辆在拐弯时的时间损耗忽略。2．车辆在任意两站点中途不停车，保持稳定的速率。3．只要平行于坐标轴即有街道存在。4．无论垃圾量多少，都能在十分钟内装上运输车。5．每个垃圾站点的垃圾只能由一辆运输车运载。6.假设运输车、铲车从A垃圾站到B垃圾站总走最短路线。7.任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直角边之和。8.建设在运输垃圾过程中没有新垃圾入站。9.假设铲车、运输车载工作途中不发生意外也不遇到意外；10.各垃圾站每天的垃圾量相对稳定。二．主要变量的说明
9、A
10、表示A点到原点的距离，恒正
11、B
12、表示B点到原点的距离，恒正
13、A-
14、B
15、表示A,B两点之间的距离,恒正Ta表示A点所在地的垃圾量cost：运费；time：时间消耗；装的足够多运输车当前的载重离限载不大于0.55吨(垃圾点的最小垃圾量)序数号所在点的编号三．问题的分析与模型的建立垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，不能直接套用Krusal，Prim等现成算法，于是根据具体问题设计出随机下山法，用计算模拟搜索，可以搜寻到令人满意的可行解。先注意到两点的情况，设两点分别为A(x1,y1),B(x2,y2)。主要有以下两种情况：一．A,B明显有先后次序。--递减状态（如图1）不妨设x1>x2,y1>y2,
16、不难看出A在B的后方,即A比B远。对于前方参考点O,要将A,B对应垃圾点的垃圾全部取回再返回O,一共有三种方式：1．OàAàO,OàBàO单独运输。这种情况下，总的路程消费等于空载运行费用(0.4元/公里)与装载时运行费用（1.8元/公里吨）的总和。所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值再加上在A,B两点停留的时间(每个垃圾点上停留了10分钟，1/6小时)，于是有：Cost=0.4*
17、A
18、+1.8*
19、A
20、*Ta+0.4*
21、B
22、+1.8*
23、B
24、*TbTime=(2*
25、A
26、+2*
27、B
28、)/40+1/6*22.OàAàBàO先远点再近点，即先空载
29、至最远处，装完A点垃圾后再返回至B,再回O点，有：Cost=0.4*
30、A
31、+1.8*
32、A-B
33、*Ta+1.8*
34、B
35、*(Ta+Tb)=0.4*
36、A
37、+1.8*
38、A
39、*Ta+1.8*
40、B
41、*TbTime=2*
42、A
43、/40+1/6*23.OàBàAàO先近点在远点，即先装B点垃圾，然后载着B点的垃圾奔至A点，再回O点，有：Cost=0.4*
44、B
45、+1.8*
46、A-B
47、*Tb+1.8*
48、A
49、*(Ta+Tb)=0.4*
50、B
51、+1.8*
52、A
53、*Ta+1.8*
54、B
55、*Tb+1.8*
56、A-B
57、*2*TbTime=2*
58、A
59、/40+1/6*2比较以上三种情况，远近点的遍历顺序，可
