文件名称:关于垃圾运输问题的解决
文件大小:249KB
文件格式:DOC
更新时间:2012-01-12 17:33:16
垃圾运输问题的解决
垃圾运输问题的解决 (一) 问题重述 某城区有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)