第1页 / 共15页
第2页 / 共15页
第3页 / 共15页
第4页 / 共15页
第5页 / 共15页
第6页 / 共15页
第7页 / 共15页
第8页 / 共15页
数学建模—垃圾运输问题的求解及源代码.doc
垃圾运输问题
*** 信息工程学院 计算机应用专业 **********
摘要：本文通过对垃圾站点之间分布位置的分析，构造出解决垃圾运输问题的模型。
首先，我们对所给数据绘制其 xy 散点图，根据题设提出自己假设的条件，。
其次，结合已有的模型，对垃圾点之间的位置分布关系进行讨论及证明，从而确定最基
本的行车路线原则。
然后，编写 c 语言程序，利用计算机进行算法的模拟，从而搜索出各运输车辆的数量以
及最佳的分配方案，使得(1)在不考虑铲车的情况下运输费用最少、(2)考虑在有铲车的模型
中的最佳解、(3)对不同运输量的运输车进行合理分配调度，使得总费用最少。
根据我们确定的解题思路，最终我们得到了一组可行解，如下：
第一问，求得全部的运输费用是 2340.97 元，花费的总时间是 21.95 小时；
第二问：求得需要 3 辆铲车；
第三问：求得总的运输费用是 2323.77 元。其中 8 吨的车 4 辆，6 吨的车 3 辆，4 吨的
车 3 辆。
具体的路线分配图，车辆调度图见正文部分。
本文讨论的解题方法模型简单，得出的结果只是一个近似最优解的可行解，所以还有很
大的改进空间，比如我们可以采用更加智能的算法等。
关键词：计算机算法模拟
优化
1． 问题的重述
某城区有 37 个垃圾集中点，每天都要从垃圾处理厂（第 38 号节点）出发将垃圾运回。
现有一种载重 6 吨的运输车。每个垃圾点需要用 10 分钟的时间装车，运输车平均速度为
40 公里／小时（夜里运输，不考虑塞车现象）；每台车每日平均工作 4 小时。运输车重载
运费 2 元 / 吨公里；运输车和装垃圾用的铲车空载费用 0.5 元 / 公里；并且假定街道方
向均平行于坐标轴。请你给出满意的运输调度方案以及计算程序。
问题：
1.运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）
2.铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用）
3.如果有载重量为 4 吨、 6 吨、 8 吨三种运输车，又如何调度？
2． 模型的基本假设与符号说明
（一）基本假设
1．车辆在拐弯时的时间损耗忽略。
2．车辆在任意两站点中途不停车，保持稳定的速率。
3．只要平行于坐标轴即有街道存在。
4．无论垃圾量多少，都能在十分钟内装上运输车。
5． 每个垃圾站点的垃圾只能由一辆运输车运载。
6. 假设运输车、铲车从 A 垃圾站到 B 垃圾站总走最短路线。
7. 任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直角边之
和。
8. 建设在运输垃圾过程中没有新垃圾入站。
9. 假设铲车、运输车载工作途中不发生意外也不遇到意外；
10. 各垃圾站每天的垃圾量相对稳定。
（二）符号说明
表示 A 点所在地的垃圾量
|A| 表示 A 点到原点的距离，恒正
|B| 表示 B 点到原点的距离，恒正
|A-B| 表示 A,B 两点之间的距离,恒正
Ta
cost：运费；
time：时间消耗；
装的足够多
序数号 所在点的编号
运输车当前的载重离限载不大于 0.55 吨(垃圾点的最小垃圾量)
3．模型的建立
垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，不能
直接套用 Krusal，Prim 等现成算法，于是根据具体问题设计出随机下山法，用计算模拟搜
索，可以搜寻到令人满意的可行解。
先注意到两点的情况，设两点分别为 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 公里/
小时）的比值再加上在 A,B 两点停留的时间(每个垃圾点上停留了 10 分钟，1/6 小时)，于
是有：
Cost = 0.4*|A| + 1.8*|A|*Ta + 0.4*|B| + 1.8*|B|*Tb
Time =
2. O->A->B->O
(2*|A| + 2*|B|)/40 + 1/6*2
先远点再近点，即先空载至最远处，装完 A 点垃圾后再返回至 B,再回 O 点，有：
Cost = 0.4*|A| + 1.8*|A-B|*Ta +1.8*|B|*(Ta+Tb)
= 0.4*|A| + 1.8*|A|*Ta + 1.8*|B|*Tb
Time = 2*|A|/40 + 1/6*2
3. O->B->A->O
先近点在远点，即先装 B 点垃圾，然后载着 B 点的垃圾奔至 A 点，再回 O 点，有：
Cost= 0.4*|B| + 1.8*|A-B|*Tb + 1.8*|A|*(Ta+Tb)
= 0.4*|B| + 1.8*|A|*Ta + 1.8*|B|*Tb + 1.8*|A-B|*2*Tb
Time = 2*|A|/40 + 1/6*2
比较以上三种情况，远近点的遍历顺序，可以看出，“先远后近”绝对比“先近后远”
在花费钱的数量上要少的多，省出 1.8*|A-B|*2*Tb 这部分的钱主要是车载着 B 点的垃圾奔
到 A 点再返回 B 点。而又注意到两者的时间花费是相等的。所以在其余同等的情况下选择“先
远后近”。考虑到时间上单独运输比其余的两种运输要大的多，多一一倍，而且花费的钱仍
不比“先远后近”省，还多了 0.4*|B|，所以一般情况下，不采用单独运输。
二．A，B 两点没有明显先后顺序。 --并邻状态（如图 2）
(2*|A| + 2*|B|)/40 + 1/6*2
还是一共有三种情况：
1． O->A->O, O->B->O
单独运输。这种情况下，跟 A,B 两点有先后顺序中的情况完全相同，即有：
Cost = 0.4*|A| + 1.8*|A|*Ta + 0.4*|B| + 1.8*|B|*Tb
time =
2． O->A->B->O
Cost = 0.4*|A| + 1.8*|A-B|*Ta + 1.8*|B|*(Ta+Tb)
Time = (|A| + |A-B| + |B|)/40 + 1/6*2
3.O->B->A->O
Cost = 0.4*|B| + 1.8*|A-B|*Tb + 1.8*|A|*(Ta+Tb)
Time = (|A| + |A-B| + |B|)/40 +1/6*2
相比之下，清晰可见并邻状态下的单独运输所花的费用最少，所以在不要求时间的情况
下对于并邻两点，采用单独运输的方式最节约钱。用<1>式与<2>式相减除以 1.8， 得到如
下判断式：
----〈1〉
----〈2〉
|A-B|*(Ta-Tb) + (Ta+Tb)*(|B|-|A|)
上式 < 0 时， 选 0->A->B->O;
上式 > 0 时， 选 O->B->A->O;
上式 = 0 时， 任意选上述两路线。
三．
两点选择趋势的讨论。 （如图 3）
----<3>
由图中看到 B,C 两点没有明显的先后顺序，属于并邻点。因为当运输车载重行驶时费用
会成倍的增长，比其空载时所花费用要大的多，所以排除 A->B->C 或 A->C->B 这样的一次经
过 3 点的往返路线，仅选择 B,C 中的某一点与 A 完成此次运输，将另一点留到下次。那么 A
点选择 B 还是 C 呢？
不妨假设|B|>|C|,即 B 点离原点的距离比 C 点的更远，因为 A 在 B,C 之后，所以也就是
B 点离 A 点更近。这样，此次的运输我们更趋向于选择 A->B,因为就这三点而论，A 无论是
选 B 还是 C，三点的垃圾总要运完，所以花费的钱是一样的。但选择 A->B 后，下次运输车
运 C 点垃圾时就无需跑的更远。
关于垃圾点的垃圾是否一次清除的讨论（以 6 吨车例）
四．
由假设 2 知，每天的垃圾必须清除完毕，全部运往 37 点。这里说的一次清除问题不是
指一天，而是指当一辆运输车已经装载了足够多的垃圾，不能完全清理下一个垃圾点的时候，
车在下一个站点“停还是不停”的问题。例如，一辆运输车选择了 30->26->18->35->20 的
路线（即先将空车开往 30，清理装载 30 点的垃圾，然后依次到 26，18，35，20），它从 20
返回时车已经装载了 5.8 吨垃圾，仍可以装 0.2 吨(小于垃圾点垃圾量的最小值 0.5，称这
种情况为“装的足够多”)。在 20 点下方仍有不少的点，但肯定不能将下面的任意点的垃圾
装完，那么此车是直接返回 37 点呢，还是继续装直至车装满为止呢？
我们判断前者更好，就是车在装的足够多的情况下应该直接返回原点（37 点）。这是因
为对于下一垃圾点(假设为 A 点)内的垃圾而言，无论是一次装完还是分两次装完，将它们运
回所花费用是恒定的，等于 1.8*Ta*|A|。整体而言，两者花费的钱是相等的，但分两次装
要多花 10 分钟的装车时间，所以选择前者。
综上所述，得出搜索的基本原则：
1． 在两点递减的情况下，不采用单独运输；
2． 在其余同等的情况下选择“先远后近”；
3． 不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱；一般情况下用
式<3〉作判断；
4． 车在装的足够多的情况下应该直接返回原点（37 点）；
5． 每一次布局和每条线路的搜索不妨由剩下未搜点中的最大值开始。
4． 模型的求解
问题一．在不考虑铲车的情况下。
首先根据题所给的数据画出散点图
求得总运营费用为 2345.4 元,总时间为 22.5 小时，求解程序如附录二，运输车的最优
路线如下图所示：
表一:线路的费用和所用时间
站点序号
空载费用
所花时间
一号线
二号线
三号线
四号线
五号线
六号线
七号线
八号线
九号线
十号线
0-30-29-27-3-0
0-28-26-32-25-5-0
0-36-23-33-21-0
0-24-18-35-15-0
0-34-17-16-2-0
0-20-11-10-0
0-19-13-8-0
0-14-7-4-1-0
0-22-0
0-12-9-0
十一号线 0-31-6-0
18.4
17.6
16.8
13.6
12
11.2
10.8
8.8
8.4
8
6.8
2.3+2/3
2.2+5/6
2.1+2/3
1.7+2/3
1.45+2/3
1.4+1/2
1.35+1/2
1.1+1/2
1.05+1/6
1+1/3
0.85+1/3
问题二.铲车加入后的讨论
当加入铲车后,我们应该让铲车将就运输车,因为铲车的空载费用为 0.4 元/小时.铲车
加入垃圾后为 1.8 元/公里小时.若改变一条线,则会造成几公里的误差,甚至十几公里的误
差,这一项的数目就很大.若是铲车将就运输车,则即使路线误差大一点,但所需费用也不会
变得很大.故我们以第一个方案的路线为准.这时我们只要保证前一条线路的末节点,与后一
条线路的首节点的路程差分别相加之和最小即可.根据这一思路.我们设一个结构数组变量,
他有 11 个元素(代表 11 条元素).其中每个元素里面有两个结构成员,这样一个元素就代表一
条线路.对这 11 个元素进行排列,这样每一个排列就是一个线路方案.这样便能通过排列,遍
历每种方案.就求出最优解.再考虑了最短路径的情况下，由于要考虑和各车在时间地衔接，
以及尽量要在规定的时间内作完，我们进行相应的调整。
这部分由于考虑到计算复杂性，我们用手工调整，由于前面有最短路径的保证，我们调
整的结果接近最优解。
程序代码如附录三【源码】
程序运行结果见附录三【结果】
表二:行走线路和所用时间
线路
时间
0-30-29-27-3-0
2.3+4/6
0-28-26-32-25-5-0
2.2+5/6
0-36-23-33-21-0
0-24-18-35-15-0
0-34-17-16-2-0
0-19-13-8-0
0-20-12-9-0
0-11-10-0
0-31-6-0
2.1+4/6
1.7+4/6
1.45+2/3
1.35+1/2
1.0+1/2
0.7+1/3
0.7+1/3
0-14-7-4-1-0
0.55+4/6
13.5 小时
根据总时间和个线路的耗时，依平均工作 6 小时为条件得出需要三量铲车，三辆铲车的
起始点分别为 36 ，31 ，28；
因为运输车时速为 40km/h,则铲车速度无须大于 40km/h.
若速度小于 40km/h,则至少要多买一辆铲车,这样造成重复,故最好多花点钱买大功率
的铲车.为了保证能在晚上干完，
我们可以多条路同时干，但考虑到新加铲车费用，我们只让三辆铲车同时工作，就能在
规定时间干完。总费用为 81.6 元。
问题三： 存在 4 吨，6 吨，8 吨三种运输车时的调度
若存在 4 吨,6 吨,8 吨三种,我们应把握的原则是:尽量让 8 吨的车,拉远处的垃圾,远处
垃圾拉得越多,以后车的空载路程就越少,而不考虑空载费用,只把垃圾运回垃圾处理厂,它
的这部分费用不变.
同时，我们考虑到 8 吨,6 吨,4 吨的运输车费用问题,故 8 吨的车不宜太多.我们在分析
过程中,发现主要是第 15 点比较难处理,因此 8 吨的车应将这一点在 30 那条线上一并处理.
而象第 2 点,用 6 吨车单独拉一次太浪费,应用 4 吨车
还有 11,22 这两条线也可改用 4 吨车.
运营总费用为：2325.8 其中运输费用是 2213.4 空载费用为 112.4
求解程序如附录四：
表三:线路所用时间和承载垃圾量
线路
时间
垃圾量
30-29-27-20-11-0
2.3+5/6
28-26-32-25-14-7-0
2.2+1
36-23-33-21-22-0
2.1+5/6
24-18-35-15-31-5-0
1.7+1
34-17-16-2-0
19-13-8-3-1-0
12-9-0
10-0
6-0
4-0
1.45+2/3
1.35+5/6
1.0+1/3
0.7+1/6
0.7+1/6
0.55+1/6
7.8
7.9
7
7.95
5
6.95
4.1
1.5
1.3
1.2
表四：
运输车 数量
8 吨
6 吨
4 吨
5
2
3
铲车路线：
铲车跟随运输厂车行驶，先行驶到远点、伴随运输车网回路行驶，铲完一趟后就寻找该
离铲车最近的另外一条运输线的起始点（运输车远端），然后再跟着运输车行驶。
5．模型优缺点分析
然而，该问题在站点众多，运输半径较大的前提下，缺点就会显得尤为突出。首先是运
输车载重的不足，当运输车的载重不能满足其中任一点的垃圾量时，模型就可能不能适用了，
该模型优点是算法简单容易实现,精度特别是后两个模型的精度不是很高.前两问只要进行
穷举就能得出最优解.第三问的处理原则不算很精确,有待改进
6．模型的推广和应用
该模型可以应用在很多方面，比如说货物运输、车辆分配等。
7．参考文献
全国大学生数学建模竞赛 优秀论文汇编。中国物价出版社，2002
宋兆基，徐流美等。MATLAB6.5 在科学计算中的应用。清华大学出版社，2005
8．附录
附录一：
垃圾点地理坐标数据表
序号 站点编号 垃圾量 T 坐标 (km) 序号 站点
编号
x
y
1
2
3
4
5
6
7
8
9
10
11
12
13
1
2
3
4
6
5
7
8
9
10
11
12
13
1.50
1.50
0.55
1.20
0.85
1.30
1.20
2.30
1.40
1.50
1.10
2.70
1.80
3
1
5
4
0
3
7
9
10
14
17
14
12
2
5
4
7
8
11
9
6
2
0
3
6
9
20
21
22
23
24
25
26
27
28
29
30
31
32
15
32
22
23
24
25
26
27
28
29
30
31
21
垃圾量
T
1.40
1.20
1.80
1.40
1.60
1.60
1.00
2.00
1.00
2.10
1.20
1.90
1.30
坐标 (km)
x
19
22
21
27
15
15
20
21
24
25
28
5
17
y
9
5
0
9
19
14
17
13
20
16
18
12
16
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
