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

垃圾运输问题的模型及其求解00730’刘育兴,钟剑(;,江西赣州341000)摘要:本文通过垃圾运输问题的模型建立与求解,总结出这类问题的一般性解法,即根据实际问题构造恰当的有向或无向赋权图,把问题转化成mecq,的TSP问题,通过解决这类TSP问题,【I1设G=(,E)是连通无向图,(1)经过G的每一个顶点正好一次的路,称为G的一条哈密顿路或日路;(2)经过G的每一个顶点正好一次的圈,称为G的一条哈密顿圈或日圈;(3)含日圈的图称为哈密顿图或日图..定义2【i1设D=(,A)是连通有向图,(1)经过D的每一个顶点正好一次的圈,称为D的生成圈;(2)?设G是完全(有向或无向)赋权图,在C中寻找权最小闭迹的问题称为TSP问题(即TravelingSalesmanProblem).若此闭迹是日圈,:在满足条件t‘}()+t‘}(,)下,TSP问题可转化为寻找最佳H圈的问题,,每天都要从垃圾处理厂(第37号节点)(如图1所示).为了节省费用,,它们的平均速度为40kin/h(夜里运输,不考虑塞车现象),每个垃圾点需要用10rain的时间装车,;(每台运输车的调度方案,每台铲车的行走路线及总运营费用).鼍收稿日期:2005一l1一O8作者简介:刘育兴(1968一),男,江西吉安人,赣南师范学院数学与计算机科学学院讲师,,钟剑垃圾运输问题的模型及其求解53表l垃圾点地理坐标数据表问题分析:这是一个遍历问题,此问题的困难之处在于确定铲车的行走路线,并使得运输车工作时尽量不要等待铲车,才能使得运输车的工作时间满足题目的要求——,应使铲车跟着运输车跑完一条线路,也就是说,:为叙述方便,每条路线上开始的垃圾集中点称为这条路线的始点,:莽表2运输路程与时问根据表2中各路线上运输车花费的时间,各运输车运输路线安排如表3所示:表3运输线路时间安排为了寻找铲车合理的行走路线,构造一有向图D如下:将各条线路看成一个点,路线①、②、?、⑩分别看成点1、2、?、,而由点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的终点分别到点