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