关于解决垃圾运输问题

垃圾运输问题的解决 (一) 问题重述 某城区有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）