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

垃圾运输问题的模型及其求解刘育兴 ，钟剑(赣南师范学院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问题(即TravelingSalesman Problem)若此闭迹是日圈，则称此闭迹为最佳日圈容易证明：在满足条件t( )+t( ， )下，TSP问题可转化为寻找最佳H圈的问题，这可通过构造一个完全图来实现2 垃圾运输问题例l 某城区有若干个垃圾集中点，每天都要从垃圾处理厂(第37号节点)出发将垃圾运回假定运输图1 运输车线路图车的线路已确定下来共lO条(如图1所示)为了节省费用，运输车在每条线路上总是先从远离处理厂的垃圾集中点开始运送垃圾现有6辆载重6吨的运输车及装垃圾用的铲车，它们的平均速度为40 kinh(夜里运输，不考虑塞车现象)，每个垃圾点需要用10 rain的时间装车，每台运输车每日平均工作4 h运输车重载运费18元吨km；运输车和装垃圾用的铲车空载费用04 km并且假定街道方向均平行于坐标轴请你给出满意的运输调度方案(每台运输车的调度方案，每台铲车的行走路线及总运营费用)鼍收稿日期：2005一l1一O8作者简介：刘育兴(1968一)，男，江西吉安人，赣南师范学院数学与计算机科学学院讲师，主要从事图论研究维普资讯 第3期 刘育兴，钟剑垃圾运输问题的模型及其求解 53表l 垃圾点地理坐标数据表问题分析：这是一个遍历问题，此问题的困难之处在于确定铲车的行走路线，并使得运输车工作时尽量不要等待铲车，才能使得运输车的工作时间满足题目的要求每日平均工作4 h为此，应使铲车跟着运输车跑完一条线路，也就是说，应使铲车铲完一条线路后再接着铲下一条线路问题解答：为叙述方便，每条路线上开始的垃圾集中点称为这条路线的始点，最后的垃圾集中点称为这条路线的终点每条线路上运输车行走的路程与花费的时间列表如表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 -+ 一十76-+O一十3-+lO-+8 9-+O，因此，3辆铲车维普资讯 赣南师范学院学报 2006年的行走路线分别为：铲车1：Ol一5 一O；铲车2：O一27-6一O；铲车3：O一3一l089一O由于各铲车的行走路线已确定且它们花在各条路线上的时间可精确计算出来，因此，根据铲车的情况和各运输车的行走路线，可安排出如表4所示的较为满意的调度方案：表4 行走路线与时间安排运输车辆 行走路线及时问安排1 10：00从点O发车一l1：06到达路线 的起点一l：02返回点O2 10：58从点O发车+o：07到达路线的起点一l：46返回点O1O：00从点O发车一l1：03到达路线 的起点加：46返回点O，再次从点O发车一l：l6到达路线 的起点 ：O6返回点O 11：43从点O发车加：145到达路线 的起点一l：06返回点O，再次从点O发车一l：435。 到达路线 的起点 ：l3返回点O11：41从点O发车加：32到达路线的起点一2：达路线 的起点 ：33返回点OO：15从点O发车一l：055到达路线 的起点+2：达路线的起点 ：o5返回点OO3返回点O，再次从点O发车一2：33到l9返回点O，再次从点O发车+2：52到铲车 行走路线及时问安排l lO：00从点O发车加：32到达路线 的起点一l：435到达路线 的起点一3：l3返回点O1O：58从点O发车一l：O55到达路线 的起点一2：275到达路线 的起点，在此需等待。 24 5分钟 ：o5返回点O1O：00从点O发车加：145到达路线 的起点加：54到达路线 的起点，在此需等待22分钟 ：22到达路线 的起点，在此需等待11分钟 ：33返回点O运输车运送垃圾的费用为：(15 jIc5+15 jIc6+055 9+13 jIc42)jIc 18=123165 jIc 18=221697(元)运输车空载费用为：(88+92+84+42)jIc 04=612 jIc 04=2448(元)铲车1的空载费用为：(44+l7+7+l3+8+29)jIc 04=472(元)铲车2的空载费用为：(46+35+11+22)jIc 04=456(元)铲车3的空载费用为：(42+28+6+11+l3+20)jIc04=48(元)所以，三辆铲车的总费用为：472+456+48=1408(元)运输车和铲车的总费用为：221697+248+1408=260257(元)3 总结与推广上面通过对垃圾运输问题的解答，我们将其归结为数学建模中的一类较为普遍的问题，即要求经过所有对象的遍历问题垃圾运输问题就是这类问题的一个典型代表，这类问题的共同点是，它们都可以通过构造一个恰当的网络(即赋权图)或有向网络，将问题转化成TSP问题或寻找最佳H路的问题，再用合适的方法求出近似最优解或最优解，问题便可迎刃而解问题的关键就在于如何构造一个有效的网络，在实际问题中应具体问题具体分析，有些问题并不是很容易地就能构造出有效的网络，而需要根据自己的经验创造性地构造合适的网络下面再举几个例子加以说明例2【2 (工件加工顺序问题)现有l4件工件等待在一台机床上加工某些工件加工必须安排在另一些工件完工后才能开始，第j号工件的先期必须完工的工件如表5：表5 工件加工顺序维普资讯 第3期 刘育兴，钟剑垃圾运输问题的模型及其求解 55试设计一个满足条件的加工顺序，使机床花费的总时间最少问题分析：若将工件序号j用点j表示，点i到点J的弧上的权等于加工完第1号工件后再接着加工第i号工件时机床的准备时间tij，得赋权有向图D，于是问题就转化成：在赋权有向图D中，满足工件加工次序的限制条件下，寻找最佳H路 问题解答：如下构造有向图D(V，A)：D中的顶点i表示工作序号i，弧(i，j)表示工件i是工件j的前期工件，弧(i，j)上的权等于tij，并根据各工序之间的加工次序的限制条件画出D中的一条主要路径P：471l 一38 一14一l2一l3，所谓主要路径就是加工所有工件时，必须符合其先后次序而不能调换或改变这种次序的路径但主要路径中间可以插人别的在主要路径中未出现的工序于是问题就变成在满足主要路径P的条件下，在D中寻找最佳H路由表可知：工序lO应在工序5之前，工序9应在工序3之前工序4之后，工序1应在工序3之后工序l4之前，工序6应在工序8之后工序l4之前，故可将P分成两段：Pl：47一ll 一3，P2：382一l4一l2一l3将工序lO与9插人Pl中可得如下图2：图2 部分工件加工顺序图图2中共有l9条不同的H路，其中的最短H路可用穷举法，也可用下面的近似方法：先用Dijkstra算法求出43的最短有向路为Pl 479 3，总权值为39再将工序lO和11插人到Pl中，由于弧(10，9)和弧(11，10)的权都是2，用子路711一lO一9替代路Pl冲的弧(7，9)，得最短有向路为Pl，47一l 1一lO一9 一3，总权值为45这恰好就是这l9条H路中的最短H路下面考虑将工序1与6插入P2中，共有8条不同的路，其中最短有向路为P28 一1一l4一l2一l3，总权值为29因此，所求加工顺序为Pl P