垃圾运输问题建模论文9.docx
《垃圾运输问题建模论文9.docx》由会员分享，可在线阅读，更多相关《垃圾运输问题建模论文9.docx（24页珍藏版）》请在冰点文库上搜索。
垃圾运输问题建模论文9
2012高教社杯全国大学生数学建模
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。
如有违反竞赛规则的行为，我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）：
我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）：
江西师范大学
参赛队员（打印并签名）：
1.王琨
2.刘莉
3.黄安枝
指导教师或指导教师组负责人（打印并签名）：
日期：
2013年8月3日
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
评
阅
人
评
分
备
注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
城市垃圾运输问题
摘要
城市垃圾运输问题是一个寻求最优路径的优化问题。
在解决第一问运输车的调度问题时，本文首先确立了一种构思，即缩短运输车的总路程。
在此基础上加大空载路程，缩短载重路程，并做到运输车的数量尽可能的少。
在第一问中，根据以上几点要求，我们进一步将其深入讨论得出必须使运输车空载至最远点，运用下山法的原理逐步找出下一个最合适的点，此时只需满足横纵坐标都逐渐减小，而所取点垃圾总量不大于6吨，最终通过运算我们得出了10条线路。
但是其中有几条线路用时较短，我们对其进行了人工优化，将用时较短的路线进行合并，最终得出只需6辆运输车。
在第二问铲车调度的问题中，本文延续并使用了第一问的结果和上述思想。
在保持运输车线路不变的情况下，本文估算了一下铲车由第一个工作点开始到最后一个工作点结束的同时再除以4小时，得出最少要三辆铲车。
将10条运输线路概括为3个部分，原则是使这3个部分的每个部分内铲车跑的总路程最短，通过人工的运算和时间的对照，我们得出了最终结果。
在第三问中，三种型号车的加入增加了解题的灵活性，此时我们的构思依然是缩短运输车的总路程，加大空载路程，而利用8吨车去尽可能的解决远处的垃圾显然可以在不增加总路程的情况下更加缩短空载路程。
我们的结果如下：
第一问，求得需要运输车6辆，所需总费用为2339.05元，调度方案见正文表5，最优路径见正文图4。
第二问，求得需要铲车3辆，所需总费用为142.8元，调度方案见正文表4。
第三问，求得需要铲车4辆和运输车5辆，所需总费用为2508.63元，运输车和铲车的调度方案见表6、表7，运输车的最优路径见图8。
关键词：
最优路径、哈密顿圈、下山法、模拟退火法
一、问题的重述
为了美化城市环境，环卫部门每天夜里都要对分布在城区各街道的定点垃圾及时进行处理。
假设某城区有37个垃圾集中点，环卫车辆每天都要从垃圾处理厂（第38号节点）出发将垃圾运回。
现有一种载重量6吨的运输车，每个垃圾点需要用8分钟的时间装车，运输车平均速度为40公里／小时（夜里运输，不考虑塞车现象）；每辆车每日平均工作4小时；运输车重载运费为2元/吨公里；运输车和装垃圾用的铲车空载费用均为0.5元/公里；并且假定街道方向均平行于坐标轴。
试给出满意的运输调度方案以及试给出满意的运输调度方案以及计算程序。
1.运输车应如何调度（需要投入多少台运输车，每台车的调度方案、运营费用）；
2.铲车应如何调度（需要多少台铲车，每台铲车的行走路线以及运营费用）；
3.如果改用载重为4吨、6吨、8吨的三种运输车，试给出运输车和铲车的调度方案。
二、问题的分析
2.1．问题一的分析
问题一是图论中的一个遍历问题。
由于运输车的载重与时间的约束，问题一不再是最小树能解决的问题，而是森林，即包含了多个树的图。
每一个树用一辆车去把其上面的垃圾运输回来，只要时间足够，同一辆车可能运输不止一棵树的垃圾。
问题就变成了在一个森林中，找到这样一些树，使其能用尽可能少的车遍历完所有顶点，且这些树构成哈密顿圈。
将垃圾集中点抽象成坐标平面上的点，该点具有两个属性，即位置属性和重量属性：
城市抽象成一个30
20的一个坐标方格网络。
该模型符合以上模型假设。
垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，更具具体问题设计出随即下山法，用计算模拟搜索，可以搜寻到令人满意的可行解。
通过分析“单独运输”“先远点再近点”“先近点再远点”三种方面和垃圾是否一次清除的情况可得搜索的基本原则。
2.2.问题二的分析
当加入铲车后,因为铲车的空载费用为0.5元/公里，铲车装入垃圾后为2元/公里小时，我们应该让铲车将就运输车。
若改变一条线,则会造成几公里的误差,甚至十几公里的误差,这一项的数目就很大。
若是铲车跟随运输车,则即使路线误差大一点,但所需费用也不会变得很大，故我们以第一个方案的路线为准。
这时我们只要保证前一条线路的末节点,与后一条线路的首节点的路程差分别相加之和最小即可。
根据这一思路，我们利用模拟退火方法，通过排列,遍历每种方案，就求出最优解。
再考虑最短路径的情况及考虑和各车在时间地衔接，尽量要在规定的时间内作完，再进行相应的调整得出最优解。
2.3问题三的分析
对于问题3中4吨、6吨和8吨3种型号的运输车，本文先通过计算机分别运算出只使用一种车时的最优解，然后将三者的运算结果人工优化，从而得出最终解，得出调度方案。
三、模型假设
1.运输车匀速行驶且不计一切拐弯损耗时间；
2.车辆在任意两站点中途不停车；
3.只要平行于坐标轴即有街道存在；。
4.无论垃圾量多少，都能在十分钟内装上运输车；
5.每个垃圾站点的垃圾不允许分两次运输，而且也只需要一辆铲车。
6.假设运输车、铲车从A垃圾站到B垃圾站总走最短路线；
7.任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直角边之和；
8.如果车可以跑第二趟，中间无休息时间；
9.假设铲车、运输车载工作途中不发生意外也不遇到意外；
10.所有运输车和铲车均从第38号点出发，且最后均回到38号点；
四、符号说明
1、子点：
本点的下一点；
2、Spend：
运费；
3、Time：
时间消耗；
4、|A|：
A点横纵坐标之和，；
5、垃圾集中点在后面用顶点表示
6、v[i]：
第i个顶点
7、v[i].X：
第i个顶点的X坐标；v[i].Y表示第i个顶点的Y坐标；
8、v[i].laji：
第i个顶点上有的垃圾重量，单位是吨；
9、L[i][j]:
顶点i到顶点j的距离；
10、sum[i]:
顶点i的横纵坐标之和；
11、访问一个顶点表示把它的垃圾装上车；
12、用到的相关定义
设G=（V,E）是连通无向图,
（1）经过G的每一个顶点正好一次的路,称为G的一条哈密顿路或H路;
（2）经过G的每一个顶点正好一次的圈,称为G的一条哈密顿圈或H圈;
（3）含H圈的图称为哈密顿图或H图.
|A|A点横纵坐标之和
|B|B点横纵坐标之和
|A-B|表示A,B两点之间的距离
Ta表示A点所在地的垃圾量
cost：
运费；
time：
时间消耗；
装的足够多运输车当前的载重离限载不大于0.55吨（垃圾点的最小垃圾量）
序数号所在点的编号
四、模型分析及建立模型
4.1问题分析
这是图论中的一个遍历问题。
由于运输车的载重与时间的约束，它不再是最小树能解决的问题，而是森林，即包含了多个树的图。
每一个树用一辆车去把其上面的垃圾运输回来，只要时间足够，同一辆车可能运输不止一棵树的垃圾。
问题就变成了，在一个森林中，找到这样一些树，使其能用尽可能少的车遍历完所有顶点，且这些树构成哈密顿圈。
将垃圾集中点抽象成坐标平面上的点，该点具有两个属性，即位置属性和重量属性：
城市抽象成一个30
20的一个坐标方格网络。
该模型符合以上模型假设。
垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，更具具体问题设计出随即下山法，用计算模拟搜索，可以搜寻到令人满意的可行解
4.11先注意分析两点的情况，设两点分别为A（x1,y1）,b（x2,y2）
主要有以下两种情况：
1.A,B明显有先后次序--递减状态（如图1）
图1
不妨设x1>x2,y1>y2,不难看出A在B的后方,即A比B远。
对于前方参考点O,要将A,B对应垃圾点的垃圾全部取回再返回O,一共有三种方式：
1）OAO,OBO
单独运输。
这种情况下，总的路程消费等于空载运行费用（0.4元/公里）与装载时运行费用（1.8元/公里吨）的总和。
所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值再加上在A,B两点停留的时间（每个垃圾点上停留了10分钟，1/6小时），于是有：
2）OABO
先远点再近点，即先空载至最远处，装完A点垃圾后再返回至B,再回O点，有：
3）OBAO
先近点在远点，即先装B点垃圾，然后载着B点的垃圾奔至A点，再回O点，有：
比较以上三种情况，远近点的遍历顺序，可以看出，“先远后近”绝对比“先近后远”在花费钱的数量上要少的多，省出1.8
|A-B|
2
Tb这部分的钱主要是车载着B点的垃圾奔到A点再返回B点。
而又注意到两者的时间花费是相等的。
所以在其余同等的情况下选择“先远后近”。
考虑到时间上单独运输比其余的两种运输要大的多，多一一倍，而且花费的钱仍不比“先远后近”省，还多了0.4
|B|，所以一般情况下，不采用单独运输。
4.12A，B两点没有明显先后顺序。
--并邻状态（如图2）
图2
还是一共有两种情况：
1）OAO,OBO
单独运输。
这种情况下，总的路程消费等于空载运行费用（0.4元/公里）与装载时运行费用（1.8元/吨公里）的总和。
所需的总时间等于车辆所走过的总路程与速度（35公里/小时）的比值再加上再A,B两点停留的时间（每个垃圾点上停留了10分钟，1/6小时），于是有：
2）OABO或OBAO
先空载到A或B，即先空载到其中的一个点，装完A（B）点的垃圾再返回B（A），再回到O点，有：
----〈1〉
通过上面两种方式的比较，第1种遍历的费用少，但时间稍多。
综合分析，由于时间可调，我们选择费用少的，时间稍多的遍历，即第1种方式。
两点选择趋势的讨论。
（如图3）
图3
由图中看到B,C两点没有明显的先后顺序，属于并邻点。
因为当运输车载重行驶时费用会成倍的增长，比其空载时所花费用要大的多，所以排除ABC或ACB这样的一次经过3点的往返路线，仅选择B,C中的某一点与A完成此次运输，将另一点留到下次。
那么A点选择B还是C呢？
不妨假设|B|>|C|,即B点离原点的距离比C点的更远，因为A在B,C之后，所以也就是B点离A点更近。
这样，此次的运输我们更趋向于选择AB,因为就这三点而论，A无论是选B还是C，三点的垃圾总要运完，所以花费的钱是一样的。
但选择AB下次运输车运C点垃圾时就无需跑的更远。
4.2关于垃圾点的垃圾是否一次清除的讨论
由假设4知，每天的垃圾必须清除完毕，全部运往37点。
这里说的一次清除问题不是指一天，而是指当一辆运输车已经装载了足够多的垃圾，不能完全清理下一个垃圾点的时候，车在下一个站点停还是不停的问题。
我们认为前者更好，就是车在装的足够多的情况下应该直接返回原点（37点）。
这是因为对于下一垃圾点（假设为A点）内的垃圾而言，无论是一次装完还是分两次装完，将它们运回所花费用是恒定的。
整体而言，两者花费的钱是相等的，但分两次装要多花10分钟的装车时间，所以选择前者。
综上所述，得出搜索的基本原则：
1.在两点递减的情况下，不采用单独运输，选择“先远后近”，
2.不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱；
3.车在装的足够多的情况下应该直接返回原点（37点）；
4.每条线路的搜索都由未搜点中的最大值开始。
五、模型的求解
5.1问题1的求解
在不考虑铲车的情况下，运输车的最优路线如下：
（见图4）
综合两点的分布情况与遍历路线分析，先空载至最远点，即哈密顿距离（横纵坐标和）最远点，如果它没有被访问，则访问它。
然后试着返回，途中找它的子点，即没有被访问过的哈密顿距离且车能装下其垃圾的顶点，找到后，访问子点：
再以子点为本点，以同样的方式找子点，直到没有子点可找，或车不能装下找到的子点为止。
这样就将图分成了多个哈密顿圈。
图4
对上图中的结果，可以在不改变最佳哈密顿圈且考虑到车载量的约束的基础上改进哈密顿圈，可得下表
路线：
途经顶点
垃圾量（吨）
耗时
A：
28-26-21-25-19
5.7
3小时02分
B：
30-29-27
5.3
2小时48分
C：
36-23-33-32
5.5
2小时46分
D：
34-17-16-2
5
2小时07分
E：
24-18-35-20
5.2
2小时22分
F：
14-31-5-6
5.85
1小时46分
G：
15-13-7-4
5.6
2小时04分
H：
12-8-3
5.55
1小时30分
I：
11-9-1
4
1小时30分
J：
22-10
3.3
1小时23分
表1运输耗时
通过表1与图4，得一下两种车辆分配与路线
运输车
路线
时间
总时间
1
A
3小时02分
3小时02分
2
B
2小时48分
2小时48分
3
C
2小时46分
2小时46分
4
D
2小时07分
4小时11分
G
2小时04分
5
E
2小时22分
4小时06分
F
1小时46分
6
H
1小时20分
4小时13分
I
1小时30分
J
1小时23分
表2运输线路时间安排1
运输车
路线
时间
总时间
1
A
3小时02分
3小时02分
2
B
2小时48分
2小时48分
3
C
2小时46分
4小时06分
H
1小时20分
4
J
1小时23分
3小时30分
D
2小时07分
5
E
2小时22分
3小时52分
I
1小时30分
6
G
2小时04分
3小时50分
F
1小时46分
表3运输车的调度方案
经比较分析表2中的路线时间安排更为合理。
我们算出所需总费用为2339.05元。
5.2问题2的求解
当加入铲车后,因为铲车的空载费用为0.4元/小时，铲车装入垃圾后为1.8元/公里小时，我们应该让铲车将就运输车。
若改变一条线,则会造成几公里的误差,甚至十几公里的误差,这一项的数目就很大。
若是铲车跟随运输车,则即使路线误差大一点,但所需费用也不会变得很大，故我们以第一个方案的路线为准。
这时我们只要保证前一条线路的末节点,与后一条线路的首节点的路程差分别相加之和最小即可。
根据这一思路，我们利用模拟退火方法，设一个结构数组变量,他有11个元素（代表11条元素）。
其中每个元素里面有两个结构成员,这样一个元素就代表一条线路，对这11个元素进行排列,这样每一个排列就是一个线路方案，这样便能通过排列,遍历每种方案，就求出最优解。
再考虑了最短路径的情况下，由于要考虑和各车在时间地衔接，以及尽量要在规定的时间内作完，我们进行相应的调整。
这部分由于考虑到计算复杂性，我们用手工调整，由于前面有最短路径的保证，我们调整的结果接近最优解。
车次
发车时间
线路
线内时间
1
10点
A
11点06分-0点11.5分
E
0点22分-1点21.5分
D
1点50.5分-3点14分
2
10点
B
11点09分-11点57分
G
0点06分-1点11.5分
F
2点11分-3点12分
3
10点
C
11点03分-0点05.5分
J
0点14.5分-0点45分
H
1点26分-2点12.5分
I
2点33分3点25.5分
表4：
铲车的调度
运输车
线路
发车时间
到达该线起点时间
从该线返回时间
1
A
10点
11点06分
0点11.5分
2
B
10点
11点09分
11点57分
3
C
10点
11点03分
0点05.5分
H
0点45.5分（等待40.5分）
2点12.5分
4
J
11点43分
0点14.5分
0点45分
D
1点59.5分
3点14分
5
E
11点31分
0点22分
1点21.5分
I
2点33分
3点25.5分
6
G
11点24分
0点06分
1点11.5分
F
2点11分
3点12分
表5运输车的调度
5.3问题3的求解
对于问题3中4吨、6吨和8吨3种型号的运输车，本文先通过计算机分别运算出只使用一种车时的最优解，然后将三者的运算结果人工优化，从而得出最终解。
仅使用4吨、6吨和8吨的最优路径如下图4、5、6所示：
1）只使用4吨运输车时：
图4
2）只使用6吨运输车时：
图5
3）只使用8吨运输车时：
图6
4）最终优化后的路径：
图7
对图7进行人工优化得出下表6中运输车的调度方案：
车次
吨数
线路
发车时间
到该线起点时间
从该线返回时间
1
8
A
10点
11点06分
0点29分
D
1点12分
2点03分
3点21.5分
2
8
B
10点
11点09分
0点38分
C
1点18分
2点31分
3点52.5分
3
6
E
1点38分
2点21.5分
3点36分
F
2点56分
3点39.5分
4点54分
4
6
G
0点17分
0点47分
1点23.5分
H
3点42分
4点03分
4点42.5分
5
4
I
0点58分
1点19分
1点48分
表6运输车的调度
依据题2中建立的模型和人工的优化可得到铲车的调度方案如下表：
车次
出发时间
线路
线内时间
回到O点的时间
1
10点
A
11点06分-0点29分
1点50分
F
0点36.5分-1点11.5分
I
1点19分-1点38分
2
10点
B
11点09分-0点38分
1点37分
G
0点47分-1点23.5分
3
1点18分
C
2点31分-3点2.5分
4点50分
H
4点03分-4点42.5分
4
1点12分
D
2点03分-3点21.5分
5点03分
E
3点39.5分-4点54分
表7铲车的调度
六、模型的优缺点分析
优点：
该模型算法简单容易实现，易懂；
缺点：
我们较多的采用人工方法，导致精度下降，有待改善。
七、模型的推广及应用
本文主要运用下山法原理，在回收垃圾的过程中，让重量由远到近逐渐增加，从而达到节约成本的目的。
如果我们从相反方向来看，似乎可以得到一个上山法的原理，我们可以将其运用到货物的配送中，由近及远逐渐减轻重量，同时，由近及远寻找下一个最优点，从而达到实现最优路径，节省更多的成本。
参考文献：
1.戴朝寿，孙世良数学建模简明教程北京：
高等教育出版社
2.叶其孝大学生数学建模竞赛辅导教材湖南：
湖南教育出版社
3.赵静，但琦数学建模与数学实验北京：
高等教育出版社
4.刘育兴，钟剑《赣南师范学院学报》2006年03期
5．谭浩强《C＋＋程序设计》清华大学出版社出版
附录（C++）运算程序：
#include
#include
#defineM37
#defineNM-1
intsum[M];
intsort[M];
intvisit[M];
intfinal=0;
intL[M][M];
intm,vmin,u;
doubleweight;
typedefstructnode{
doublelaji;
intX;
intY;
}node;
nodev[M];
voidaround（intw）
{
inti,min=1000;
for（i=1;i<=N;i++）
{
if（L[w][i]{
min=L[w][i];
vmin=i;
}
}
if（u!
=vmin）
{
weight=weight+v[vmin].laji;
if（weight<=6）
{
visit[vmin]=1;
cout<u=vmin;
around（vmin）;
}
else
cout<<"#";
}
elsecout<<"#";
}
voidmain（）
{
intmaxindex;
v[1].laji=1.50;v[1].X=3;v[1].Y=2;
v[2].laji=1.50;v[2].X=1;v[2].Y=5;
v[3].laji=0.55;v[3].X=5;v[3].Y=4;
v[4].laji=1.20;v[4].X=4;v[4].Y=7;
v[5].laji=0.85;v[5].X=0;v[5].Y=8;
v[6].laji=1.30;v[6].X=3;v[6].Y=11;
v[7].laji=1.20;v[7].X=7;v[7].Y=9;
v[8].laji=2.30;v[8].X=9;v[8].Y=6;
v[9].laji=1.40;v[9].X=10;v[9].Y=2;
v[10].laji=1.50;v[10].X=14;v[10].Y=0;
v[11].laji=1.10;v[1].X=17;v[1].Y=3;
v[12].laji=2.70;v[2].X=14;v[2].Y=6;
v[13].laji=1.80;v[3].X=12;v[3].Y=9;
v[14].laji=1.80;v[4].X=10;v[4].Y=12;
v[15].laji=1.40;v[5].X=19;v[5].Y=9;
v[16].laji=1.50;v[6].X=2;v[6].Y=16;
v[17].laji=0.80;v[7].X=6;v[7].Y=18;
v[18].laji=1.50;v[8].X=11;v[8].Y=17;
v[19].laji=0.80;v[9].X=15;v[9].Y=12;
v[20].laji=0.60;v[10].X=7;v[10
升级会员 