魅力数模美丽师大浙江师范大学“同梦杯”第八届数学建模竞赛自信创新合作快乐A B论文题目城市垃圾运输问题编号 56组评分监制：浙江师范大学数学建模研究会（2009年5月7日）（说明：评分一栏为评阅人填写，请参赛者不要填写）垃圾运输问题摘要：该题我们的主要解题思路分三阶段：第一阶段，我们先根据题设条件和基本假设画出该题的图。
第二阶段，我们根据图和点的位置关系结合题设，归纳出一些最基本的确定路线的原则：在仔细分析该题后，我们认为该题为一个TSP与VRT相结合的问题。
我们先抛开空载费用，若要把所有的垃圾运回垃圾处理站，这部分有效工的费用为∑＊|Xi|＊Yi(|Xi|为垃圾点Xi到原点的距离,Yi为垃圾点的垃圾量)，是恒定不变的。
只要我们能保证空载路线最小，则所花的时间和费用都最小。
因此解题的关键在于找出一个调度方案，使空载行驶的线路最小。
第三阶段则是编制程序阶段，我们结合下山法逐点搜索，并引入随机生成器。
在出现后继点权值相等难以判断以哪点继续搜索时，由随机生成器确定。
为了让算法更接近人的思维，我们让更靠近父点的子点有更高的几率被作为下一个将去的垃圾点，这也与我们的算法原则对应。
采用计算机模拟搜索的计算方法，搜索出运输车投入辆数以及运输车最佳调配方案，使得在不考虑铲车的情况下运营费用最低。
总运营费用为运输车空载费与实际运输费之和。
问题的解答如下：第一问，求得所需总费用为元，所需总时间为23小时08分，路线分配图见正文；第二问，求得需4辆铲车，铲车费用为元，分配图及运输车调度表见正文；第三问，运营总费用为：，其中8吨、6吨、4吨载重量的运输车各需5、2、3辆，路线分配图见正文。
关键词：单目标优化计算机搜索 TSP一、问题的重述某城区有 38 个垃圾集中点，每天都要从垃圾处理厂（第 38 号节点）出发将垃圾运回。
现有一种载重 6 吨的运输车。
每个垃圾点需要用 10 分钟的时间装车，运输车平均速度为 40 公里／小时（夜里运输，不考虑塞车现象）；每台车每日平均工作 4 小时。
运输车重载运费元 / 吨公里；运输车和装垃圾用的铲车空载费用元 / 公里；并且假定街道方向均平行于坐标轴。
请你给出满意的运输调度方案以及计算程序。
问题：1.运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）2.铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用）3.如果有载重量为 4 吨、 6 吨、 8 吨三种运输车，又如何调度（垃圾点地理坐标数据表见附录一）二、模型的假设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：时间消耗；装的足够多运输车当前的载重离限载不大于吨(垃圾点的最小垃圾量)序数号所在点的编号四、问题的分析与模型的建立这是一个遍历问题。
由于运输车的载重与时间的约束，它不在是最小树能解决的问题，而是森林，包含了多个树。
每一个树用一辆车去把其上面的垃圾运输回来，只要时间足够，同一辆车可能运输不止一颗树的垃圾。
问题就变成了，在一个森林中，找到这样一些树，使其能用尽可能少的车遍历完所有顶点的，且这些树够成哈密顿圈。
将垃圾集中点抽象成坐标平面上的点，该点具有两个属性，即位置属性和重量属性；城市抽象成一个30*20的一个坐标方格网络。
该模型假设如第二项中所述。
垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，不能直接套用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单独运输。
这种情况下，总的路程消费等于空载运行费用元/公里)与装载时运行费用（元/公里吨）的总和。
所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值再加上在A,B两点停留的时间(每个垃圾点上停留了10分钟，1/6小时)，于是有：Cost = *|A| + *|A|*Ta + *|B| + *|B|*TbTime = (2*|A| + 2*|B|)/40 + 1/6*22. O A B O先远点再近点，即先空载至最远处，装完A点垃圾后再返回至B,再回O点，有：Cost = *|A| + *|A-B|*Ta +*|B|*(Ta+Tb)= *|A| + *|A|*Ta + *|B|*TbTime = 2*|A|/40 + 1/6*23. O B A O先近点在远点，即先装B点垃圾，然后载着B点的垃圾奔至A点，再回O点，有：Cost= *|B| + *|A-B|*Tb + *|A|*(Ta+Tb)= *|B| + *|A|*Ta + *|B|*Tb + *|A-B|*2*TbTime = 2*|A|/40 + 1/6*2比较以上三种情况，远近点的遍历顺序，可以看出，“先远后近”绝对比“先近后远”在花费钱的数量上要少的多，省出*|A-B|*2*Tb这部分的钱主要是车载着B点的垃圾奔到A点再返回B点。
而又注意到两者的时间花费是相等的。
所以在其余同等的情况下选择“先远后近”。
考虑到时间上单独运输比其余的两种运输要大的多，多一一倍，而且花费的钱仍不比“先远后近”省，还多了*|B|，所以一般情况下，不采用单独运输。
二．A，B两点没有明显先后顺序。
--并邻状态（如图2）还是一共有三种情况：1．O A O, O B O单独运输。
这种情况下，跟A,B两点有先后顺序中的情况完全相同，即有：Cost = *|A| + *|A|*Ta + *|B| + *|B|*Tbtime = (2*|A| + 2*|B|)/40 + 1/6*22．O A B OCost = *|A| + *|A-B|*Ta + *|B|*(Ta+Tb) ----〈1〉Time = (|A| + |A-B| + |B|)/40 + 1/6*2B A OCost = *|B| + *|A-B|*Tb + *|A|*(Ta+Tb) ----〈2〉Time = (|A| + |A-B| + |B|)/40 +1/6*2相比之下，清晰可见并邻状态下的单独运输所花的费用最少，所以在不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱。
用<1>式与<2>式相减除以，得到如下判断式：|A-B|*(Ta-Tb) + (Ta+Tb)*(|B|-|A|)----<3>上式 < 0时，选0A B O;上式 > 0时，选 O B A O;上式 = 0时，任意选上述两路线。
三．两点选择趋势的讨论。
（如图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知，每天的垃圾必须清除完毕，全部运往38点。
这里说的一次清除问题不是指一天，而是指当一辆运输车已经装载了足够多的垃圾，不能完全清理下一个垃圾点的时候，车在下一个站点“停还是不停”的问题。
例如，一辆运输车选择了28→26→21→11→9的路线（即先将空车开往28，清理装载28点的垃圾，然后依次到26，21，11，9），它从9返回时车已经装载了吨垃圾，仍可以装吨(小于垃圾点垃圾量的最小值，称这种情况为“装的足够多”)。
在9点下方仍有不少的点，但肯定不能将下面的任意点的垃圾装完，那么此车是直接返回38点呢，还是继续装直至车装满为止呢我们判断前者更好，就是车在装的足够多的情况下应该直接返回原点（38点）。
这是因为对于下一垃圾点(假设为A点)内的垃圾而言，无论是一次装完还是分两次装完，将它们运回所花费用是恒定的，等于*Ta*|A|。
整体而言，两者花费的钱是相等的，但分两次装要多花10分钟的装车时间，所以选择前者。
(五) 计算机随机搜索算法的编制和实现一．随机搜索算法具体叙述1．基本思想。
问题要求搜索出一条最短路线，但又与中国邮递员等问题有所区别，本问题搜索的不完全是最优回路问题，而更像是单支路覆盖问题，也是NP难问题，没有现成的多项式次数的算法，所以自行设计了一种随机搜索算法。
基本思想是结合下山法逐点搜索，并尝试引入随机生成器剪枝提高搜索速度，整个算法利用链表结构实现。
2．算法流程一次布局开始à确定搜索点总集P ，判断集P非空：若空，则一次布局结束；非空，则M=max(|P|),即M为P集中距离原点(0,0)的最远点。