垃圾运输问题模型

关于垃圾运输问题的数学模型摘要 本文对于垃圾运输问题的优化，通过运用图论的TSP问题的有关知识对题目给出的坐标数据进行了处理，根据从最远点开始运载垃圾运输费用最低的原则，以及不走回路的前提，在条件时间约束下，建立了运输车和铲车的调度优化模型，得到运输车和铲车的安排路线和时间，在垃圾运输问题上，安排了六辆运输车，三辆铲车的最少调动车辆数目，达到最少运输费用。关键词：哈密顿图；TSP问题；垃圾集中点；重载起点；运输路线1 问题重述某城区有36个垃圾集中点，每天都要从垃圾处理厂（第 37 号节点）出发将垃圾运回。现用一种载重 6 吨的运输车到期每个垃圾点载运垃圾,并需要用 10 分钟的时间装车，运输车平均速度为 40 公里小时（夜里运输，不考虑塞车现象）；每台车每日平均工作 4 小时。运输车重载运费 1.8 元 / 吨公里；运输车和装垃圾用的铲车空载费用 0.4 元 / 公里；并且假定街道方向均平行于坐标轴。要求给出满意的运输调度方案，使总运费最少。问题：1. 运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）2. 铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用）垃圾集中点坐标数据表如下表1：表1:垃圾点地理坐标数据表序号 站点编号 垃圾量 T 坐标 (km) 序号 站点编号 垃圾量 T 坐标 (km) x y x y 1 1 1.50 3 2 20 15 1.40 19 9 2 2 1.50 1 5 21 32 1.20 22 5 3 3 0.55 5 4 22 22 1.80 21 0 4 4 1.20 4 7 23 23 1.40 27 9 5 6 0.85 0 8 24 24 1.60 15 19 6 5 1.30 3 11 25 25 1.60 15 14 7 7 1.20 7 9 26 26 1.00 20 17 8 8 2.30 9 6 27 27 2.00 21 13 9 9 1.40 10 2 28 28 1.00 24 20 10 10 1.50 14 0 29 29 2.10 25 16 11 11 1.10 17 3 30 30 1.20 28 18 12 12 2.70 14 6 31 31 1.90 5 12 13 13 1.80 12 9 32 21 1.30 17 16 14 14 1.80 10 12 33 33 1.60 25 7 15 20 0.60 7 14 34 34 1.20 9 20 16 16 1.50 2 16 35 35 1.50 9 15 17 17 0.80 6 18 36 36 1.30 30 12 18 18 1.50 11 17 37 37 0.00 0 0 19 19 0.80 15 12 2 模型假设2.1假设运输车重载与空载行走时间相同；2.2假设运输车在工作过程中没有任何耽误；2.3假设铲车的速度与运输车的速度一样；2.4只要在满足每辆运输车在每天平均工作四小时的前提下,假设运输车工作时间允许超过四小时；2.5假设运输车每天安排所走的路线不是固定不变的，有一个值班制度,使每辆运输车每天平均工作大约四小时。3 符号说明：第个垃圾集中点的垃圾量,；：第个垃圾集中点的横坐标，；：第个垃圾集中点的纵坐标，；：垃圾运输路线总条数；：第条路线上垃圾集中点的个数，；:安排运输车的总数量；：第条路线上的第个垃圾集中点的横坐标，；：第条路线上的第个垃圾集中点的垃圾量，；:第条路线所需要的总时间；：第辆车的运输总时间；：运输车空载的总费用；：运输车重载的总费用；：运输车的总费用；：铲车1的空载费用；：铲车2的空载费用；：铲车3的空载费用；：全部铲车空载的总费用。4 运输车调度优化模型4.1 确定运输车路线算法由于最远的垃圾集中点的运输时间不超过运输车每天平均工作时间，所以可以先不考虑时间的约束。从而建立如下算法：1) 确定重载起点 由于每个垃圾集中点的垃圾量及其坐标是不变，重载运输的费用是不变的，所以为了使总运输费用最少，只要使空载的费用最少，即尽量安排较远的垃圾集中点在同一路线上，从而确定重载起点.2）确定运输车路线走向要求运输时走最短的路线，以及运输费用最低，而且由于运输车的重载费用1.8元/吨是空载费用0.4元/吨的4.5倍，为了使运输总费用最少,那只能从最远的点（）开始运载垃圾，下一个点编号为，走一条路线，向垃圾处理站（坐标原点）方向运回。顺次经过的点遵循满足条件：即其横坐标以及纵坐标均不超过前一点的横、纵坐标，并且各点横、纵坐标递减进行搭配，由若干个点组成一条路线。3）确定运输车路线垃圾集中点数根据每个垃圾集中点的垃圾量，每条路线上的垃圾总量不超过运输车的最大运输量：根据上面算法,建立运输车费用优化模型:4.2 运输车调度方案在运输过程中假设没有运输车等待的情况,在四个小时的工作时间里,根据垃圾运输费用优化模型，得到垃圾集中点分配的路线及其时间,为了达到安排运输车最少，把所有的路线分成()类，每类配置一辆运输车，每辆运输车的工作时间：5 铲车调度优化模型这是一个遍历问题，要确定铲车的行走路线，并使得运输车工作时尽量不要等待铲车，为此，应使铲车跟着运输车跑完一条线路，也就是说，应使铲车跟着运输车铲完一条线路后再接着铲下一条线路。再跑下一条路线。可是运输车的工作时间有限制，都不能超过每日平均工作4 h那就是说，时间成了最大的问题约束，所以在安排铲车的行走路线，必需以垃圾运输车的时间以及铲车的时间同时考虑，而且题目并没有给出铲车的明确速度，为了使问题的简化，那我们就假定铲车的速度跟运输车的相同，构建有向图： 为了寻找铲车合理的行走路线，构造一有向图如下：将各条线路看成一个点，路线、分别看成点1、2、lO点到点的弧上的权等于铲车由路的终点到路的始点的空载费用，而由点4、5、l0分别到点1、2、3的弧上的权等于；其次，将原点0用3阶完全有向图来代替，三点分别为、，弧上的权均为，( =1，2，3)与其他各点之间的弧上权如下确定：分别到点1，2，3的弧上的权等于铲车由点O分别到路 ， ， 的起点的空载费用，点4，5，lO分别到点的弧上的权分别等于铲车由路4，5，lO的终点分别到点0的空载费用，其余各弧上的权均等于显然是一个完全赋权有向图，问题就转化成寻找最短的哈密顿回路，运用图论的TSP知识，就可以得到最优的铲车路线调度。6模型求解6.1 垃圾运输车费用依据题目给出各垃圾集中点的坐标，用的绘图功能绘点得到如图1所示：图1根据垃圾运输车路线算法，由此可以把垃圾集中点划分为十条最优路线如图2所示,使得运输路程最短。对应的运输方案如下表2：图2 表2：运输路线安排及其费用运输路线先后经过的垃圾集中点运输路程运输所需时间空载运输费用重载费用28-26-32-25-19883小时02分17.6345.4230-29-27922小时48分18.4376.7436-23-33-21842小时46分16.8339.4834-17-16-2582小时07分11.616224-18-35-15682小时22分13.626114-31-6-5441小时46分8.8174.4220-13-7-4562小时04分11.2196.9212-8-3401小时30分8168.2111-9-1401小时30分883.3410-22421小时23分8.4105.84由此得出，运输车空载的总运费为各路线总和的一半乘以空载的运输费用： 运输车重载的总运费为各路线的最远点开始至垃圾处理站各自线路上的各个垃圾集中点将线路划分的若干部分，各部分运输车上垃圾量乘以该部分的路程，再将各部分所得的积的总和乘以运输车重载的运输费用：运输车总的运输费用为：。6.2 运输车调度方案根据计算各路线所需时间的，在运输车每日平均工作四小时左右的前提下，得出路线的最优搭配，从而得出所需最少的卡车数量。由上表3中运输所需时间，我们得到如下路线搭配，如表3：表3：运输车路线及其时间安排后)此闭迹为最佳运输线路车辆安排运输车线路时间总时间13小时02分3小时02分22小时48分2小时48分3、2小时46分1小时23分4小时09分4、2小时07分1小时30分3小时37分5、2小时22分1小时30分3小时57分6、1小时46分2小时04分3小时50分由表3得出，最少安排六辆运输车对垃圾集中点进行运输，达到最优运输方案。6.3 铲车安排根据运输车和铲车调度优化模型,然而是一个完全赋权有向图，将问题转化成在D中寻找最小哈密顿有向图，通过计算得到近似最优哈密顿有向图。 我们把(=1，2，3)收缩为点，得到总路线为：- -，因此，3辆铲车的行走路线分别为：铲车1：- -；铲车2：-；铲车3：-。于各铲车的行走路线已确定且它们花在各条路线上的时间可精确计算出来，因此，代入数据得到表4、表5：表4: 运输车辆行走路线及时间安排运输车辆行走路线及时间安排1 10:00从点发车11:06到达路线 的起点1:02返回点2 10:58从点发车0:07到达路线的起点1:46返回点3 10:00从点发车11:03到达路线 的起点0:46返回点，再次从点发车1:27.5到达路线 的起点2:19返回点4 11：57.5从点发车0：27.5到达路线 的起点l：27.5返回点，再次从点发车2：05 到达路线 的起点3 ：34.5返回点5 11：41从点发车0：32到达路线的起点2：03返回点,再次从点发车2:33到达路线 的起点3 ：33返回点6 O：15从点发车l：055到达路线 的起点2：19返回点,再次从点到时达路线的起点 4：05返回点表5：铲车行走路线及时间安排铲车行走路线及时间安排1 lO：00从点发车11:06到达路线的起点0：32到达路线 的起点1:43.5到达路线 的起点,等待21.5分3：34.5返回点2 1O：58从点发车0:07到达路线的起点1:05.5到达路线的起点2:27.5到达路线的起点，在此需等待 24.5分钟4:05返回点3 1O：00从点发车11:03到达路线的起点0：275到达路线的起点1:27.5到达路线的起点 3：22到达路线 的起点，在此需等待11分钟3 ：33返回点由上表给出的铲车路线可以得出各铲车空载费用为:铲车的总费用为:。7模型的评价 线路模型运用了图论的知识对垃圾集中点的运输线路进行划分，大大地降低了问题的复杂程度，对于问题的费用求解，采用人工运算，放下了烦琐的编程，使求解的过程简明易懂。特别对于问题二的线路模型,通过计算,得到近似最优哈密顿有向图。这使铲车线路难安排的问题得到了一个较好的答案。它们都可以通过构造一个恰当的网络(即赋权图)或有向网络，将问题转化成TSP问题或寻找最佳H路的问题，再用合适的方法求出近似最优解或最优解，问题便可迎刃而解问题的关键就在于如何构造一个有效的网络，在实际问题中应具体问题具体分析，有些问题并不是很容易地就能构造出有效的网络，而需要根据自己的经验创造性地构建。8 参考文献1袁新生,邵大宏,郁时炼.LINGO和EXCLE在数学建模中的应用M.北京:科学出版社,2007.2耿素云.集合论与图论(离散数学二分册)M.北京:北京大学出版社,1997.3赵可培.运筹学M.上海:上海财经大学出版社,2000.4姜启源,谢金星,叶俊.数学模型(第三版)M.北京:高等教育出版社,2003.