垃圾运输问题的模型及其求解’刘育兴，钟剑(赣南师范学院a．数学与计算机科学学院；b．网络中心，江西赣州341000)摘要：本文通过垃圾运输问题的模型建立与求解，总结出这类问题的一般性解法，即根据实际问题构造恰当的有向或无向赋权图，把问题转化成mecq,的TSP问题，通过解决这类TSP问题，从而使原问题获得满意的解答．关1有关概念定义l【I1设G=(，E)是连通无向图，(1)经过G的每一个顶点正好一次的路，称为G的一条哈密顿路或日路；(2)经过G的每一个顶点正好一次的圈，称为G的一条哈密顿圈或日圈；(3)含日圈的图称为哈密顿图或日图．．定义2【i1设D=(，A)是连通有向图，(1)经过D的每一个顶点正好一次的圈，称为D的生成圈；(2)含生成圈的图称为哈密顿图或日图．定义3⋯设G是完全(有向或无向)赋权图，在C中寻找权最小闭迹的问题称为TSP问题(即TravelingSalesmanProblem)．若此闭迹是日圈，则称此闭迹为最佳日圈．容易证明：在满足条件t‘}()+t‘}(，)下，TSP问题可转化为寻找最佳H圈的问题，这可通过构造一个完全图来实现．2垃圾运输问题例l某城区有若干个垃圾集中点，每天都要从垃圾处理厂(第37号节点)出发将垃圾运回．假定运输图1运输车线路图车的线路已确定下来共lO条(如图1所示)．为了节省费用，运输车在每条线路上总是先从远离处理厂的垃圾集中点开始运送垃圾．现有6辆载重6吨的运输车及装垃圾用的铲车，它们的平均速度为40kin／h(夜里运输，不考虑塞车现象)，每个垃圾点需要用10rain的时间装车，每台运输车每日平均工作4h．运输车重载运费1．8元／吨km；运输车和装垃圾用的铲车空载费用0．4km．并且假定街道方向均平行于坐标轴．请你给出满意的运输调度方案(每台运输车的调度方案，每台铲车的行走路线及总运营费用)．鼍收稿日期：2005一l1一O8作者简介：刘育兴(1968一)，男，江西吉安人，赣南师范学院数学与计算机科学学院讲师，主要从事图论研究．维普资讯wwcqvip第3期刘育兴，钟剑垃圾运输问题的模型及其求解53表l垃圾点地理坐标数据表问题分析：这是一个遍历问题，此问题的困难之处在于确定铲车的行走路线，并使得运输车工作时尽量不要等待铲车，才能使得运输车的工作时间满足题目的要求——每日平均工作4h．为此，应使铲车跟着运输车跑完一条线路，也就是说，应使铲车铲完一条线路后再接着铲下一条线路．问题解答：为叙述方便，每条路线上开始的垃圾集中点称为这条路线的始点，最后的垃圾集中点称为这条路线的终点．每条线路上运输车行走的路程与花费的时间列表如表2：莽表2运输路程与时问根据表2中各路线上运输车花费的时间，各运输车运输路线安排如表3所示：表3运输线路时间安排为了寻找铲车合理的行走路线，构造一有向图D如下：将各条线路看成一个点，路线①、②、⋯、⑩分别看成点1、2、⋯、lO．点i到点j的弧上的权等于铲车由路i的终点到路j的始点的空载费用，而由点4、5、⋯、l0分别到点1、2、3的弧上的权等于∞；其次，将原点0用3阶完全有向图来代替，三点分别为Ol、o2、O3，弧上的权均为∞，Oi(i_1，2，3)与其他各点之间的弧上权如下确定：Oi分别到点1，2，3的弧上的权等于铲车由点0分别到路①，②，③的起点的空载费用，点4，5，⋯，lO分别到点Oi的弧上的权分别等于铲车由路4，5，⋯。lO的终点分别到点0的空载费用，其余各弧上的权均等于∞．于是，D是一个完全赋权有向图，问题转化成在D中寻找最小哈密顿有向圈，可采用对调调优算法，通过编程计算，得到近似最优哈密顿有向圈(把Oi(i=1，2，3)收缩为点0)：O一十1—-+一十7—÷6-+O一十3-+lO-+89-+O，因此，3辆铲车维普资讯wwcqvip赣南师范学院学报2006年的行走路线分别为：铲车1：O—l一5一O；铲车2：O一2—7-÷6一O；铲车3：O一3一l0—8—9一O．由于各铲车的行走路线已确定且它们花在各条路线上的时间可精确计算出来，因此，根据铲车的情况和各运输车的行走路线，可安排出如表4所示的较为满意的调度方案：表4行走路线与时间安排运输车辆行走路线及时问安排110：00从点O发车一l1：06到达路线①的起点一l：02返回点O210：58从点O发车—+o：07到达路线②的起点一l：46返回点O1O：00从点O发车一l1：03到达路线③的起点...