数学建模论文基于遗传算法的小区维修任务的建模与求解.doc

《数学建模论文基于遗传算法的小区维修任务的建模与求解.doc》由会员分享，可在线阅读，更多相关《数学建模论文基于遗传算法的小区维修任务的建模与求解.doc（15页珍藏版）》请在三一办公上搜索。

1、基于遗传算法的小区维修任务的建模与求解摘要本文研究小区维修任务安排的问题,考虑到小区的面积,大门朝向,及报修客户要求维修时间限制等约束条件,建立小区维修任务安排的优化模型,力求完成最多的任务.同时采用遗传算法,利用C语言编程,对模型进行了求解,并制定了详细的行走路线及维修计划,以此来帮助小区热水器维修商制定维修计划.对于问题一：小区的维修时间由小区的报修客户的数目和每个报修客户平均的维修时间来决定.保修客户随机分布在小区内,我们采用均匀分布的模型对小区的报修客户进行计算,结果为: ;而每个维修事项的时间我们近似采用指数衰减模型,得到每个报修客户的平均时间为16分钟,进一步总时间为: 对于问题二

2、：在实际数据的基础上，对经典的TSP问题进行改进，建立了一个优化的模型。通过C语言进行编程,逐个(1个,2个,，n个)踢出小区，然后枚举出全部情况，再利用遗传算法求出踢出小区时对应的最优路线，然后综合考虑，找到一个最优的路线，最优行走路线是：0-8-7-6-5-2-4-10-0，任务总时间为525分钟, 行走路径为:30KM,总时间为:597分钟 对于问题三：与问题二相比,报修客户有了维修时间限制,在问题二模型的基础上,将小区的维修任务分在三个时间段(上午,中午,下午),再分别对各个时间段的任务利用问题二的模型进行遍历,找到各个时间段的最佳路线,最后综合整理,找出整体最优方案.对于问题四:采取

3、分块法估计最短路径，然后利用整体最短路径与估计的最短路径对比，可得出维修人数关系不等式，求出最佳人数。对于问题五:假设至少需要维修员个,结合问题中的条件限制,列出几个不等式,找出目标函数,利用线性规划模型进行求解.关键字 小区维修优化模型 遗传算法 枚举法 TSP 线性规划 均匀分布 指数模型一、 问题重述某个热水器维修站承接多个品牌的热水器维修任务，负责附图1所示地区的维修事项。该地区共有70个不同的小区，为简单起见，假设每个小区都是长方形区域，边长也仅有两种规格：2000米、1000米，如小区1是边长1000米的正方形区域；小区3是2000米1000米的长方形区域；小区9是边长为2000米

4、的正方形区域。也假设每个小区的入口仅有一个，均位于小区区域上边的中点处。维修站位于65号小区的左上角。维修员的出行方式为电瓶车，平均速度为25公里/小时。维修站接待保修、维修员上门维修的流程如下：保修电话记录每个报修信息，生成任务清单。每个维修员早8：00到维修站领取其所负责区域的维修单，下午6：00之前必须将当天已经完成的清单与未完成的清单交到维修站。热水器的报修事项相对稳定，假设一共有A、B、C、D、E、F、G、H八类，各类事项的平均维修时间数据如下表。事项ABCDEFGH维修时（分钟）1020153020153520请按照所给信息，建立数学模型，回答下列问题。 （1）假设每个小区的报修客

5、户住处随机分布在小区内。建立模型说明在一个规格a 千米b千米小区内维修所需总时间与小区大小、报修项目之间的关系。（2） 假设维修员负责1-小区16的所有任务。某天接到的报修单见附表2。该维修员当如何安排，使得一天内完成尽可能多的维修任务。（3） 客户在报修时会对维修人员时间上有要求，假设可能的时间要求分为三个时间阶段:上午（8：0011：00）、午饭时间（11：0013：00）、下午时间（13：0018：00）。在上一题中，每项报修要求时间见附表3。该维修员应当如何安排，使得一天内能完成最多的任务（维修人员的午饭时间可以在11：0013：00内灵活安排，时间约为15分钟）。（4）假设维修站现在

6、仍没有完成的维修任务如附表4。按照当前任务，维修站至少需要几名维修员，能够使得在一天内完成所有的修理工作。（5） 维修站承诺所有报修事项能在3天内上门修理。假设今天是2012年5月日，维修站现在仍没有完成的维修任务以及报修时间如附表5。按照当前任务，维修站至少需要几名维修员，能够在承诺的时间内完成所有修理工作。二、问题分析问题一的分析:小区内维修总时间由小区内报修的客户个数和每个报修客户的维修时间有关，二者相乘即为总时间。求小区内报修的客户个数方法：由题目中的假设知： 每个小区的报修客户住处随机分布在小区内，我们采用二维的均匀分布，求出小区内报修的客户个数的期望。求每个报修客户的维修时间的方法

7、：由于维修故障所需的知识有难易之分，故障出现的频率有高低之别，一般说来，简单的故障发生的频率高，越复杂故障发生的频率就越低。文献1表明，故障发生的概率密度与故障维修的难易程度近似服从指数分布。而修理工时与故障的难易程度呈线性关系，因此为计算简便，可设某故障出现的概率其中，为正常数，x为故障的维修难易程度，即为维修时间。代入各个事项的维修时间，即可求出，然后可进一步求出每个报修客户需要维修的期望时间。报修客户数与每个报修客户的维修时间进行乘积，即可得出总的维修时间和小区面积与报修项目之间的关系。问题二的分析: 维修任务量的标准：题目要求求解一天内完成尽可能多的维修任务，怎样才是尽可能多的维修任务

8、呢？本文认为除了花费在最优路径上的时间外，其余时间全部用在执行维修任务上，这个时间是指切切实实花费在维修项目上的时间，也就是说我们认为不是完成的项目个数越多维修量就越多，而是除了不可避免的尽可能短的路程时间外，其余时间全部用在维修项目上，这个时间越多，维修任务完成的也就越多，也就是时间利用率最高的完成的维修任务越多。这就是本文评定维修任务多少的指标。首先，由附表2中1-16个小区的报销清单可知，维修完所有任务所需总时间为875分钟，而一个维修员一天的工作总时间为10个小时，也就是600分钟，这两个时间的对比可知，维修员一天是不可能完成这16个小区的维修任务的，只能在规定的时间内完成尽可能多的维

9、修任务，做到时间利用率最高。通过编程，我们用排列组合方式分别踢出1个，2个，n个小区，对应穷举出剩下的小区，用遗传算法进行最佳遍历，找出一个最佳行走路径，使最佳行走路径的总时间满足下式 ： 其中：T1为实际维修项目花费的总时间， T2为从维修站出发到回到维修站，其中最佳行程上花费的总时间。实践中发现，满足上述条件的成立情况有许多种，只要找到T1最大的一个遍历，即花费在维修任务上时间最多，路程时间最短的一个遍历，就是完成维修任务最多的一个遍历。问题三的分析:与问题二相比,维修任务时间有限制,项目维修时间分别限制为上午、上午或中午、上午或下午、中午、中午或下午、下午、全天。由计算可知，上午的工作时

10、间为180分钟，中午为105分钟，下午为300分钟。上午维修任务时间为225分钟，中午为190分钟，下午为105分钟 。通过对比可知，在上午和中午的规定时间内，其限制段内的任务是不可能完成的，只能尽可能多的完成。而在下午的时间段内除了限定的任务外，其时间是有余量的，所以应尽可能将可以在上午或下午、中午或下午、全天的时间段内的任务放在下午进行，以提高时间利用率。所以我们先对有弹性的时间段下午进行求解，用问题二的模型进行最优路径进行遍历，得出最优方案后，将剩余的维修任务归纳到相应的上午和中午中，例如对于中午时间段求解时，我们将上午或中午，剩余的中午或下午，剩余的全天，中午这些的时间段内的任务放在中

11、午，再用问题二模型分别对其进行遍历，得出最优维修方案。最后将上午、中午、下午的最优方案综合起来，既得出一天的最优方案，也就是完成任务最多的方案。问题四的分析:对于问题四每个人一天的工作时间一定，工作时间由实际维修时间和花在路上的时间组成。如果路上时间用的少，则有效时间多，每个人完成任务就多，这样总任务需要的人数最少。这样问题又转化为求最短路径问题。但是如果求70个小区最短路径那么计算量太大，所以分区进行，1-16 ,17-31,32-45,46-59,60-70分别为一个区。利用遗传算法求解出1-16的最短路径，由于这五个区面积相同，小区分布也相似，所以为了计算方便就取这个路径为5个区的平均最

12、短路径，则总的最短路径为,总时间为，但是这只是满足局部路径最优，整体不一定最优。所以假设总体最短路径为 则,所以整体最优的总时间. 所以利用公式： 其中N为所需要的维修人数 为第i个小区的项目时间 为花费在路上的时间 则 所以 所以根据上式即可求解出至少需要多少维修人员问题五的分析:由问题四可知,可以求出一个维修员一天最多维修任务的时间,假设至少需要维修员为个,5月4日必须做完5月1日的任务,然后再考虑做5月2日的,5月5日必须先做完5月2日的再做5月3日的,这样依次递推,可以列出列出规划方程及目标函数,利用线性规划求解,找出最小的即可.三、模型假设与约定1、假设维修工沿着两个小区之间的直线行

13、走2、假设维修工从一个小区到另外一个小区时走最近的路线3、假设维修工完成一个小区的所有维修任务后才去另外的小区进行维修4、假设维修员的电瓶车不出故障，行走正常。四、符号说明及名词定义（0，1,2，70）：0表示维修站，1-70表示小区a ：小区的长度b ：小区的宽度T1：实际维修项目花费的总时间，T2：从维修站出发到回到维修站，最佳行程上花费的总时间。S：1-70个小区的总面积N： 1-70小区的总人数 ：为遗传种群中的第个个体M1、M2、M3: 分别为5月1日至5月3日每天的维修时间五、模型建立与求解5.1、模型一:均匀分布模型5.1.1、模型的建立假设:1-70个小区的总面积为S,1-70

14、小区的总人数为NS和N可以看做常量, 由小区的资料可以查到，所以一个面积为小区的人数为: 题目中已经假设每个小区的报修客户住处随机分布在小区内，所以一个小区报修客户可用二维的均匀分布表示，其密度函数为： 0 ， 其他参考资料【2】知： 0 ， 其他的充要条件是X,Y相互独立且XU(a,b) , YU(c,d)由概率论知识知可知，关于小区内位置的期望为=5.2、模型二:指数衰减模型5.2.1、模型的建立 热水器维修有八类事项,不同的事项需要的维修时间不同,参考资料1: 由于维修故障所需的知识有难易之分，故障出现的频率有高低之别，因此某故障发生的频率和难易程度可以用图1来表示。点的横坐标的值表示故

15、障维修所需知识的难易程度，难度低的知识靠近原点，难度高的知识远离原点；点的纵坐标的值表示故障发生的概率。一般说来，简单的故障发生的频率高，越复杂故障发生的频率就越低。文献1表明，故障发生的概率密度与故障维修的难易程度近似服从指数分布。而修理工时与故障的难易程度呈线性关系，因此为计算简便，可设某故障出现的概率其中，为正常数，x为故障的维修难易程度，即为维修时间。由 (为维修不同的事项所需要的时间)即:可求得=所以每个报修客户平均需要维修时间为:5.3、模型三:基于遗传算法的TSP模型5.3.1 模型的建立5.3.1.1 TSP问题描述TSP即是旅行商问题，重要在找出最小权Hamilton圈,称这

16、种圈为最优圈.设,则对于所有适合的和,可以得到一个新的Hamilton圈. ,它是由C中删去边和添加和得到的.如对于某一对和,有则圈将是圈C的一个改进.在接连进行上述一系列修改之后,最后得到一个圈不能再用此方法改进了.这个最后的圈几乎可以肯定不是最优的.但有理由认为他是比较好的. 5.3.1.2 遗传算法的描述遗传算法是一种全局寻优搜索算法,它首先对问题的可行解进行编码,组成染色体,然后通过模拟自然界的进化过程,对初始种群中的染色体进行选择、交叉和变异,通过一代代进化来找出最优适应值的染色体来解决问题. 它具有很强的全局搜索能力和较强的自适应性,适合解决连续变量函数优化问题和离散变量的优化组合

17、问题是否算法开始产生初始种群编码初始化随机数发生器满足终止条件？是选择交叉变异确定最优解解码输出最优解算法结束 图二 遗传算法流程图(1)编码本文以要报修的小区作为遗传算法中的个体，采用实数矩阵形式进行编码。其具体形式为其中： 为遗传种群中的第个个体为编码矩阵中的第行第列元素，含义为小区与小区之间的最短距离(2)初始化种群:产生一个初始种群其中: R为n小区间的一个随机路径为小区号5.3.1.3 利用遗传算法求解TSP解决问题二基于问题二的模型,由于16个小区的任务不能全部完成,所以不能完全用经典的TSP进行求解,这里进行改进:逐个(1个,2个,，n个)踢出小区,枚举出剩下的小区，利用遗传算法

18、求出剩下小区的最佳路径，求出最佳路径下的时间满足：其中： T1为实际维修项目花费的总时间， T2为从维修站出发到回到维修站，最佳行程上花费的总时间。满足上述条件的成立情况有许多种，只要找到T1最大的一个遍历，即维修项目时间最多路程时间最少的一个遍历，就是完成维修任务最多的一个遍历。5.4 线性规划模型线性规划模型的一般形式矩阵形式其中：为决策向量，为目标函数的系数向量，为常数向量，为系数矩阵。六、模型求解61 模型的求解6.1.1 问题一模型的求解 6.1.1.1由均匀分布模型得出报修客户的期望值：=6.1.1.2 由指数衰减模型得出每个报修客户需要维修的时间的期望值:通过MATLAB计算 6

19、.1.1.3 问题一关系的求解:报修客户数与每个报修客户的维修时间进行乘积，即可得出总的维修时间和小区面积与报修项目之间的关系,即: 6.1.2 问题二模型的求解本模型求解通过C语言编程实现，使用软件为Microsoft Visual Studio 2010程序框图如下：踢出n个小区，排列组合出所有情况计算踢出的小区的项目时间和sumsumsumnsum275 ?用遗传算法求解最短路径计算出维修项目时间与花费在路上的时间之和timetime=600?打印结果，且n=sum所有情况是否都遍历完 n=n+1NOYESNOYESNOYES 图三 模型二程序框图 对于框图中的 275sum275 是为

20、了满足时间小于600分钟。因为维修任务总时间为875分钟,而一天的工作时间为600分钟，所以至少要踢出275分钟的维修任务时间。sumn 是为了满足维修任务时间最多，因为维修时间为875sum ,sum 越大维修时间越少。而这里的n是每次踢出小区后满足要求的sum,sumn就是说下一个方案只有满足这个要求时才能得出比已经满足要求的方案的维修任务时间多。如果不满足这个要求则方案不会比已经满足要求的方案好，所以不遍历路径了。经运行程序发现，当踢出小区个数为1,2,3，时,踢出任务时间小于275分钟，不符合条件；当踢出4个小区时，踢出任务时间已大于275分钟，但不满足T1+T2600分钟的工作时间.

21、当踢出小区个数大于9时,踢出的最少项目时间已经大于上述框图的sum了,所以不是最优解,所以,下表没列出通过运行程序,整理出踢出不同小区 满足总时间小于600分钟且维修任务时间最多的数据:求解结果如下表：踢出小区的个数维修任务时间(分钟)最佳路径有效时间利用率55150-1-2-3-4-5-6-7-8-9-10-11-085%65150-10-12-11-9-4-3-2-5-6-7-085%75150-8-7-6-2-3-4-9-11-12-085%85200-10-12-11-4-2-6-7-8-086.7%952508-7-6-5-2-4-10-087.5%从上表数据可知:选出维修任务总时间

22、最多的是踢出9个小区,分别为: 1 3 9 11 13 14 15 16,任务总时间为525分钟, 最短路径为:30KM,总时间为:597分钟,最佳路径为: 08-7-6-5-2-4-10-0 由上表可以看出:踢出5,6,7,8,9个小区时最优的任务总时间相差不大,但是联系实际情况,跨区域少的对于维修员来说比较方便.6.1.2 问题三的求解问题三的求解运用了问题二的模型，都是在规定的时间内找出最优化方案以求完成尽可能多的任务量，问题三由于维修任务有时间段限制，所以分为三个时间段进行优化，再将优化方案综合即可。考虑到问题二的算法求取的最短路径是一个H圈，但是维修人员上午从维修站出发，修完上午的任

23、务不可能又回来。所以遍历最短路径时，我们踢出维修站，只是在小区中进行遍历，但是从维修站到小区是需要时间的，所以我们为了保证维修人员一定能到达小区，我们留出30分钟（这里的30 分钟我们是选取从维修站到最远的小区所用的时间），就相当于维修人员上午的工作时间减少30分钟，下午回来也类似的减去30分钟。中午需要吃饭，也相当于从维修人员中午的工作时间中减去15分钟。求解结果如下：时间段维修任务时间（分钟）最佳路径有效时间利用率上午12010-13-14-1080% 中午905-6-7-585.7%下午2309-8-4-6-11-12-985.2%这里的有效时间利用率是指最佳路径上的有效利用时间，不包括

24、来和回去这段路程有效时间利用率计算如下：上午：120/(180-30) 这里30分钟时是保证早上维修人员能到到达第一个维修站中午：90/(120-15) 这里15分钟是吃饭用的下午：230/(300-30) 这里30分钟时是保证早上维修人员能到到达回到维修站分析比较三者的有效时间利用率发现早上的利用率较低，这是因为早上的路径是最后遍历的，前面两个遍历完后，剩下的小区分布的不均匀了，所以这样遍历得到的利用率没有前面两个高。 得到的整体利用率（120+90+230)/600=73.4%）比较第二题（87.5%）低了，这是符合实际的。 由于每个路径都是一个圆圈，所以可以任意选择起点，每个路径都可以任

25、意选择起点，然后回到起点。所以早上出发到达10小区，然后回到10小区，再到6小区。由于一开始留给了上午从维修站到10小区的时间为30分钟，而维修站到10小区大概用时15分钟，还有15分钟从10小区到6小区。这段路程可以完成。所以中午从6小区开始，完成后回到6小区，下午从6小区开始，完成后回到6小区，再回到维修站。由于一开始留给下午回来的时间是30分钟，所以可以回来的。6.1.4 问题四的求解对1-16小区利用遗传算法进行遍历，得到一个最佳路径为： 1-5-6-8-9-11-15-16-14-13-12-10-4-3-2-1最短路径为33km， 所以，1-70小区的遍历路径可近似为： 1-70小

26、区遍历的时间为： 小区1-70的任务总时间为： 所以 求 取 由于人数取整，所以 由于人数取整，所以 所以： 所以维修人数至少为：8所以至少需要8名维修员，才能够使得在一天内完成所有的修理工作6.1.5 问题五的求解假设一个维修员一天最多完成的维修任务的时间为,则,由问题四可知.其中: 为每个小区的维修时间 N 为问题四求解出的至少的人数假设: 为问题五需要的维修人员数, M1,M2,M3分别为5月1日到5月3日每天的维修时间则可得出下列方程: s.t. 求解得:,因为人数为整数,所以至少需要5个维修员, 能够在承诺的时间内完成所有修理工作。七、模型评价 对于问题二的模型,在求取最多的维修任务

27、时间时，采取排列组合的方式进行穷举，然后利用遗传算法求取最短路径，得出总时间满足条件的组合，然后寻找出维修时间最多的一组。该模型考略了所有的情况，得出的解具有普遍性。对于问题三的模型，采用分时间段的方法进行局部最佳方案的求解，在求解上午和下午的最加方案时，由于我们算法求取的最佳的路径是一个H圈，所以我们人为去除维修站只进行小区内的路径遍历，而估计了一个最大时间保证维修人员能够从维修站到达小区和回来，这样去到小区和回到维修站这段路程的时间有可能不是最优的。八、模型推广本文是针对小区维修热水器的任务安排,进行优化,找到最优路线建立了基于遗传算法的TSP模型,由结果可知,能达到很理想的效果,在如今的

28、小区维修任务中可以完全采用或者根据实际情况改进采用,当然,不仅限制于热水器的维修任务安排,本模型可以用于其他维修任务的优化安排,使小区维修效率提高一个很大的档次.九、参考文献1 王保峰， 吕克勤， 杨江平 ，信息化条件下装备维修力量优化配置模型研究，装备指挥技术学报 2008,19(6)：24-272 刘兆君, 二维均匀分布矩形区域面积的估计,大学数学,2007,23(4):651-8513 胡良剑，孙晓君，MATLAB数学实验，北京：高等教育出版社，20064 buaazhang, 遗传算法解决10城市TSP问题方案设计及程序源码, 5 biluowukai, 基于遗传算法的机组组合问题的建模与求解,