垃圾运输问题的模型及其求解

1、垃圾运输问题的模型及其求解刘育兴 ，钟剑（赣南师范学院a.数学与计算机科学学院；b.网络中心，江西赣州341000）摘要：本文通过垃圾运输问题的模型建立与求解， 总结出这类问题的一般性 解法，即根据实际问题构造恰当的有向或无向赋权图，把问题转化成mecq的TSP问题，通过解决这类TSP 问题，从而使原问题获得满意的解答关1有关概念定义I【11设G=（，E）是连通无向图,（1）经过 G 的每一个顶点正好一次的路，称为G 的一条哈密顿路或日路；（2）经过 G 的每一个顶点正好一次的圈，称为G 的一条哈密顿圈或日圈；（3）含日圈的图称为哈密顿图或日图. .定义2【i1设D =（，A）是连通有向图,（

2、1）经过 D 的每一个顶点正好一次的圈，称为 D 的生成圈；（2）含生成圈的图称为哈密顿图或日图.定义 3? 设 G 是完全（有向或无向 ）赋权图， 在 C 中寻找权最小闭迹的问题称 为 TSP 问题（即 TraveIingSaIesman ProbIem.） 若此闭迹是日圈，则称此闭迹为最佳日圈.容易证明：在满足条件t （ ）+t （，）下，TSP问题可转化为寻找最佳H 圈的问题，这可通过构造一个完全图来实现.2 垃圾运输问题例 I 某城区有若干个垃圾集中点，每天都要从垃圾处理厂 （第 37 号节点）出 发将垃圾运回.假定运输图 1 运输车线路图车的线路已确定下来共 IO 条（如图 1 所示

3、）.为了节省费用，运输车在每条线路上总是先从远离处 理厂的垃圾集中点开始运送垃圾现有 6辆载重 6 吨的运输车及装垃圾用的铲车，它们的平均速度 为40 kin/h（夜里运输，不考虑塞车现象），每个垃 圾点需要用 10 rain 的时间装车，每台运输车每日 平均工作4 h.运输车重载运费1. 8元/吨km;运 输车和装垃圾用的铲车空载费用 0. 4 km.并 且假定街道方向均平行于坐标轴.请你给出满意 的运输调度方案 （每台运输车的调度方案，每台铲 车的行走路线及总运营费用 ）.鼍收稿日期： 2005一 l1 一 O8作者简介：刘育兴 （1968 一），男，江西吉安人，赣南师范学院数学与计算机

4、科学学院讲师，主要从事图论研究.维普资讯 第 3 期 刘育兴，钟剑垃圾运输问题的模型及其求解 53 表 l 垃圾点地理坐标数据表问题分析：这是一个遍历问题， 此问题的困难之处在于确定铲车的行走路线， 并使得运输车工作时尽量不要等待铲车，才能使得运输车的工作时间满足题目的要求每日平均工 作4 h.为此，应使铲车跟着运输车跑完一条线路，也就是说，应使铲车铲完一条线路后再接着铲下一条线路. 问题解答：为叙述方便，每条路线上开始的垃圾集中点称为这条路线的始点， 最后的垃圾集中点称为这条路线的终点. 每条线路上运输车行走的路程与花费的时间列表如表2： 莽表 2 运输路程与时问根据表 2中各路线上运输车花

5、费的时间， 各运输车运输路线安排如表 3所示： 表3运输线路时间安排 为了寻找铲车合理的行走路线，构造一有向图D如 下：将各条线路看成一个点，路线 、？、分别看成点1、2、？、10 点i到点j的弧上的权等于铲车由路i的终点到路j的始 点的空载费用，而由点 4、5、?、l0 分别到点 1、2、3的弧上的权等于；其次，将原点0用3阶完全有向图来代替，三点分别为01、02、03,弧上的权均为, 0i（i_1 , 2, 3）与其他各点 之间的弧上权如下确定： 0i 分别到点 1， 2， 3的弧上的权等于铲车由点0分别到路， 的起点的空载费用，点4, 5,?,10分别到点0i的弧上的权分别等于铲车由路

6、4, 5, ?。10的终点分别到点0的空载费用，其余各弧上的权均等于.于是，D是一个完全赋权有向图，问题转化成在D中寻找最小哈密顿有向圈,可采用对调调优算法,通过编程计算,得到 近似最优哈密顿有向圈 （把 0i（i=1 ， 2， 3）收缩为点 0）：0一十 1-+ 一十 7 H 6-+0 一十 3-+I0-+8 9-+0，因此，3 辆铲车维普资讯 赣南师范学院学报 2006年 的行走路线分别为：铲车 1: 0 I 一 5 一 0;铲车2: 0 一 27 6 一 0;铲车 3： 0一 3一 I089 一 0.由于各铲车的行走路线已确定且它们花在各条路线上的时间可精确计算出来，因 此，根据铲车的情况和各运输车的行走路线，可安排出如表 4 所示的较为满意的调度方案：表 4 行走路线与时间安排运输车辆 行走路线及时问安排1 10: 00从点0发车一 I1 : 06到达路线 的起点一 1: 02返回点02 10: 58从点0发车一+o: 07到达路线的起点一 1: 46返回点010: 00从点0发车一 I1 : 03到达路线 的起点一加：46