摘要
该题我们的主要解题思路分三阶段：
第一阶段，我们先根据题设条件和基本假设画出该题的图。
第二阶段，我们根据图和点的位置关系结合题设，归纳出一些最基本的确定路线的原则：
在仔细分析该题后，我们认为该题为一个单目标规划题。我们先抛开空载费用，若要把所有的垃圾运回垃圾处理站，这部分有效工的费用为∑1.8＊|Xi|＊Yi(|Xi|为垃圾点Xi到原点的距离,Yi为垃圾点的垃圾量)，是恒定不变的。只要我们能保证空载路线最小，则所花的时间和费用都最小。因此解题的关键在于找出一个调度方案，使空载行驶的线路最小。
第三阶段则是编制程序阶段，我们结合下山法逐点搜索，并引入随机生成器。在出现后继点权值相等难以判断以哪点继续搜索时，由随机生成器确定。为了让算法更接近人的思维，我们让更靠近父点的子点有更高的几率被作为下一个将去的垃圾点，这也与我们的算法原则对应。
问题的解答如下：第一问，求得所需总费用为2338元，所需总时间为21。6小时，路线分配图见正文；第二问，求得需3辆铲车，铲车费用为81。6元，分配图及运输车调度表见正文；第三问，8吨，4吨运输车个需一辆。
垃圾运输问题的解决
(一) 问题重述
某城区有36个垃圾集中点，每天都要从垃圾处理厂（第37号节点）出发将垃圾运回。现有一种载重6吨的运输车。每个垃圾点需要用10分钟的时间装车，运输车平均速度为40km/h(夜里运输，不考虑塞车现象)；每台车每日平均工作4小时。运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里
1． 要投入多少辆运输车，每台车的行走路线，方案的运营总费用
2． 要投入多少辆铲车，每台铲车的行走路线，铲车的运营费用
3． 如果有载重量为4吨，6吨，8吨三种运输车，应该怎样调度
(二) 基本假设
1． 运输车行走拐弯的时间，路上的意外事故的耽搁时间忽略。
2． 各垃圾点的垃圾必须当天及时清除完，不允许滞留
3． 晚上9：00后不堵车
4． 每天各垃圾点的垃圾量基本相同
5． 每个垃圾点无论其中垃圾是否清理完全都需要10分钟装车时间
6． 每个垃圾点都在路口，便于垃圾的集中、运输
7． 垃圾只在晚上运输，基本保证运完后，当天不会再有新的垃圾产生
(三) 基本变量，符号和用语
|A| 表示A点到原点的距离，恒正
|B| 表示B点到原点的距离，恒正
|A-B| 表示A,B两点之间的距离,恒正
Ta 表示A点所在地的垃圾量
Spend 花费钱的数量
Time 花费的时间
装的足够多 运输车当前的载重离限载不大于0.55吨(垃圾点的最小垃圾量)
序数号 所在点的编号
父点 本点的上一点
子点 本点的下一点
(四) 问题分析和数学模型的建立
垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，不能直接套用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小时)，于是有：
Spend = 0.4*|A| + 1.8*|A|*Ta + 0.4*|B| + 1.8*|B|*Tb
Time = (2*|A| + 2*|B|)/40 + 1/6*2
2. OàAàBàO
先远点再近点，即先空载至最远处，装完A点垃圾后再返回至B,再回O点，有：
Spend = 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点，有：
Spend = 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）
还是一共有三种情况：
1． OàAàO, OàBàO
单独运输。这种情况下，跟A,B两点有先后顺序中的情况完全相同，即有：
spend = 0.4*|A| + 1.8*|A|*Ta + 0.4*|B| + 1.8*|B|*Tb
time = (2*|A| + 2*|B|)/40 + 1/6*2
2． OàAàBàO
Spend = 0.4*|A| + 1.8*|A-B|*Ta + 1.8*|B|*(Ta+Tb) ----〈1〉
Time = (|A| + |A-B| + |B|)/40 + 1/6*2
3.OàBàAàO
Spend = 0.4*|B| + 1.8*|A-B|*Tb + 1.8*|A|*(Ta+Tb) ----〈2〉
Time = (|A| + |A-B| + |B|)/40 +1/6*2
相比之下，清晰可见并邻状态下的单独运输所花的费用最少，所以在不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱。用<1>式与<2>式相减除以1.8， 得到如下判断式：
|A-B|*(Ta-Tb) + (Ta+Tb)*(|B|-|A|) ----<3>
上式 < 0时， 选 0àAà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知，每天的垃圾必须清除完毕，全部运往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． 每一次布局和每条线路的搜索不妨由剩下未搜点中的最大值开始。
(五) 计算机随机搜索算法的编制和实现
根据上面确立的几个搜索原则做出相应的随机算法应用计算机搜索出最优可行解。
一． 算法中点的数据结构简述
1。用数组表示链表结构
根据36个点状态做出一个36*5的大数组，如下表
序数号 父点 子点 垃圾量(吨) 权值
1 9 -1 1.5 5
2 0 -1 1.5 5
3 13 -1 0.6 5
。。。 。。。 。。。 。。。 。。。
。。。 。。。 。。。 。。。 。。。
35 18 7 1.5 5
36 0 23 1.3 5
规定，搜索方向由远到近（由上到下），其中序数号表示的是当前点的位置，父点即当前环中当前点的上点，子点即当前环中当前点的下一点，垃圾量即表示该点中的垃圾存放吨数，权值表示该点被修改过的次数。一个表与一个固定的布局（即一个搜索结果）一一对应，称这样的表为布局表。算法的最终目的就是要找到最好的布局表，使得花费的钱和时间最少，达到我们的目的。布局表表示了一个布局中各点的状态，它们的父点和子点以及权值，这样就能确定具体的连接路线。这样的叙述方式跟链表一致，这里是借助数组来建立链表关系，在搜索数目较少的情况下还是可行的。
2。基本信息的数组存放
为了搜索方便，此处将题目给的地理坐标数据表中各点的具体位置信息用数组的形式储存。用MAP来表示，MAP是一个30*20的大矩阵，如MAP(3,2) = 1就表示表示点1的X坐标为3，Y坐标为2，又如MAP(27,9) = 23就表示点23的X坐标为27，Y坐标为9；特别的在没有的点的地方一律用37来表示，即除了原点MAP(0,0)=37,外，在(4，8)这里也没有点，则有MAP(4,8)=37。
二． 随机搜索算法具体叙述
1． 基本思想。
问题要求搜索出一条最短路线，但又与中国邮递员等问题有所区别，本问题搜索的不完
全是最优回路问题，而更像是单支路覆盖问题，也是NP难问题，没有现成的多项式次数的算法，所以自行设计了一种随机搜索算法。基本思想是结合下山法逐点搜索，并尝试引入随机生成器剪枝提高搜索速度，整个算法利用链表结构实现。
2． 算法流程
一次布局开始à 确定搜索点总集P ，判断集P非空：若空，则一次布局结束；非空，则M=max(|P|),即M为P集中距离原点(0,0)的最远点。L=M,。。。。。。。。
（具体见下面的流程图，图4）
yes
yes
变
循环继续
(六) 问题的搜索结果
1．在不考虑铲车的情况下 --问题1的解答。运输车的最优路线如下：（见图5，图6）
工人工资，运输车的购买费用不记。
(2点单独算)总费用为2338.2元,总时间为21.6小时
2.铲车加入后的讨论 --问题2的解答
当加入铲车后,我们应该让铲车将就运输车,因为铲车的空载费用为0.4元/小时.铲车加入垃圾后为1.8元/公里小时.若改变一条线,则会造成几公里的误差,甚至十几公里的误差,这一项的数目就很大.若是铲车将就运输车,则即使路线误差大一点,但所需费用也不会变得很大.故我们以第一个方案的路线为准.这时我们只要保证前一条线路的末节点,与后一条线路的首节点的路程差分别相加之和最小即可.根据这一思路.我们设一个结构数组变量,他有11个元素(代表11条元素).其中每个元素里面有两个结构成员,这样一个元素就代表一条线路.对这11个元素进行排列,这样每一个排列就是一个线路方案.这样便能通过排列,遍历每种方案.就求出最优解.再考虑了最短路径的情况下，由于要考虑和各车在时间地衔接，以及尽量要在规定的时间内作完，我们进行相应的调整。
这部分由于考虑到计算复杂性，我们用手工调整，由于前面有最短路径的保证，我们调整的结果接近最优解。
其中三辆铲车的起始点分别为36 ，30 ，28；
车号趟数 一号 二号 三号 四号 五号 六号
第一趟 22：00至00：46 22：00至01：27 23：19至00：49 22：00 至01：02 23：44 至01：48 22：41 至00：11
第二趟 00：50至02：10 01：38至04：10 01：48 至03：55 00：28至00：56
第三趟 00：56至02：32
因为运输车时速为40km/h,则铲车速度无须大于40km/h(因为没有必要).
若速度小于40km/h,则至少要多买一辆铲车,这样造成重复,故最好多花点钱买大功率的铲车.为了保证能在晚上干完，
我们可以多条路同时干，但考虑到新加铲车费用，我们只让三辆铲车同时工作，就能在规定时间干完。总费用为81。6元。
3． 存在4吨，6吨，8吨三种运输车时的调度 –问题3的解答
若存在4吨,6吨,8吨三种,我们应把握的原则是:尽量让8吨的车,拉远处的垃圾,远处垃圾拉得越多,以后车的空载路程就越少,而不考虑空载费用,只把垃圾运回垃圾处理厂,它的这部分费用不变.
同时，我们考虑到8吨,6吨,4吨的运输车费用问题,故8吨的车不宜太多.我们在分析过程中,发现主要是第15点比较难处理,因此8吨的车应将这一点在30那条线上一并处理.
而象第2点,用6吨车单独拉一次太浪费,应用4吨车
还有11,22这两条线也可改用4吨车.
(七) 模型的优缺点
该模型优点是算法简单容易实现,精度特别是后两个模型的精度不是很高.前两问只要进行穷举就能得出最优解.第三问的处理原则不算很精确,有待改进.
(八) 模型的改进方向
1． 随机生成器的设计
2． 可以引入专家系统，增强算法的灵活性，更人性化
3． 若用模拟退火法或遗传算法,能更快地搜到较好的解
(九)精度分析
该模型经过了电脑数小时的分析,但当钱的数量小于2340时,电脑已很难再搜到最优解了.再根据电脑所作的图,基本上与我们的设想相乎,几乎满足我们的几点原则.
当然,我们也可以采用穷举法,算出最优解.但从计算复杂性来讲不可取.
|
发表于 2003-7-3 01:26:41