资源描述：
《垃圾运输问题中车辆调度优化模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数学建模竞赛C题垃圾运输问题中车辆调度优化模型摘要费用，若要把所有的垃圾运回垃圾处理站，这部分有效工的费用为∑1.8＊
2、Xi
3、＊Yi(
4、Xi
5、为垃圾点Xi到原点的距离,Yi为垃圾点的垃圾量)，是恒定不变的。只要我们能保证空载路线最小，则所花的时间和费用都最小。因此解题的关键在于找出一个调度方案，使空载行驶的线路最小。第三阶段则是编制程序阶段，我们结合下山法逐点搜索，并引入随机生成器。在出现后继点权值相等难以判断以哪点继续搜索时，由随机生成器确定。为了让算法更接近人的思维，我们让更靠近父点的子点有更高的几率被作为下一个将去的垃圾点，这也与我们的算法原则对应。问题的解答如下：
6、第一问，求得所需总费用为2338元，所需总时间为21。6小时，路线分配图见正文；第二问，求得需3辆铲车，铲车费用为81。6元，分配图及运输车调度表见正文；第三问，8吨，4吨运输车个需一辆。解决方案(一)问题重述某城区有36个垃圾集中点，每天都要从垃圾处理厂（第37号节点）出发将垃圾运回。现有一种载重6吨的运输车。每个垃圾点需要用10分钟的时间装车，运输车平均速度为40km/h(夜里运输，不考虑塞车现象)；每台车每日平均工作4小时。运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里1．要投入多少辆运输车，每台车的行走路线，方案的运营总费用2．要投入
7、多少辆铲车，每台铲车的行走路线，铲车的运营费用3．如果有载重量为4吨，6吨，8吨三种运输车，应该怎样调度(二)基本假设1．运输车行走拐弯的时间，路上的意外事故的耽搁时间忽略。2．各垃圾点的垃圾必须当天及时清除完，不允许滞留3．晚上9：00后不堵车4．每天各垃圾点的垃圾量基本相同5．每个垃圾点无论其中垃圾是否清理完全都需要10分钟装车时间6．每个垃圾点都在路口，便于垃圾的集中、运输7．垃圾只在晚上运输，基本保证运完后，当天不会再有新的垃圾产生(三)基本变量，符号和用语
8、A
9、表示A点到原点的距离，恒正
10、B
11、表示B点到原点的距离，恒正
12、A-B
13、表示A,B两点之间的距离,恒正Ta
14、表示A点所在地的垃圾量9数学建模竞赛C题Spend花费钱的数量Time花费的时间装的足够多运输车当前的载重离限载不大于0.55吨(垃圾点的最小垃圾量)序数号所在点的编号父点本点的上一点子点本点的下一点(四)问题分析和数学模型的建立垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，不能直接套用Krusal，Prim等现成算法，于是根据具体问题设计出随机下山法，用计算模拟搜索，可以搜寻到令人满意的可行解。先注意到两点的情况，设两点分别为A(x1,y1),B(x2,y2)。主要有以下两种情况：一．A,B明显有先后次序。--递减状态（如图1）不妨设x1>x2
15、,y1>y2,不难看出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小时)，于是有：Spend=0.4*
16、A
17、+1.8*
18、A
19、*Ta+0.4*
20、B
21、+1.8*
22、B
23、*TbTime=(2*
24、A
25、+2*
26、B
27、)/40+1/6*22.OàAàBàO先远点再近点
28、，即先空载至最远处，装完A点垃圾后再返回至B,再回O点，有：Spend=0.4*
29、A
30、+1.8*
31、A-B
32、*Ta+1.8*
33、B
34、*(Ta+Tb)=0.4*
35、A
36、+1.8*
37、A
38、*Ta+1.8*
39、B
40、*TbTime=2*
41、A
42、/40+1/6*29数学建模竞赛C题3.OàBàAàO先近点在远点，即先装B点垃圾，然后载着B点的垃圾奔至A点，再回O点，有：Spend=0.4*
43、B
44、+1.8*
45、A-B
46、*Tb+1.8*
47、A
48、*(Ta+Tb)=0.4*
49、B
50、+1.8*
51、A
52、*Ta+1.8*
53、B
54、*Tb+1.8*
55、A-B
56、*2*TbTime=2*
57、A
58、/40+1/6*2比较以上三种情况
59、，远近点的遍历顺序，可以看出，“先远后近”绝对比“先近后远”在花费钱的数量上要少的多，省出1.8*
60、A-B
61、*2*Tb这部分的钱主要是车载着B点的垃圾奔到A点再返回B点。而又注意到两者的时间花费是相等的。所以在其余同等的情况下选择“先远后近”。考虑到时间上单独运输比其余的两种运输要大的多，多一一倍，而且花费的钱仍不比“先远后近”省，还多了0.4*
62、B
63、，所以一般情况下，不采用单独运输。二．A，B两点没有明显先后顺序。--并邻状态（如图2）还是一共有三种情况：1．OàAàO,OàBàO单独运输。这种情况下，跟A,B两点有先后顺序
