基于遗传算法的小区维修任务的建模与求解

1基于遗传算法的小区维修任务的建模与求解摘要本文研究小区维修任务安排的问题,考虑到小区的面积,大门朝向,及报修客户要求维修时间限制等约束条件,建立小区维修任务安排的优化模型,力求完成最多的任务.同时采用遗传算法,利用C语言编程,对模型进行了求解,并制定了详细的行走路线及维修计划,以此来帮助小区热水器维修商制定维修计划.对于问题一：小区的维修时间由小区的报修客户的数目和每个报修客户平均的维修时间来决定.保修客户随机分布在小区内,我们采用均匀分布的模型对小区的报修客户进行计算,结果为:24SNab;而每个维修事项的时间我们近似采用指数衰减模型,得到每个报修客户的平均时间为16分钟,进一步总时间为:224164SNabSNab对于问题二：在实际数据的基础上，对经典的TSP问题进行改进，建立了一个优化的模型。通过C语言进行编程,逐个(1个,2个,……，n个)踢出小区，然后枚举出全部情况，再利用遗传算法求出踢出小区时对应的最优路线，然后综合考虑，找到一个最优的路线，最优行走路线是：0-8-7-6-5-2-4-10-0，任务总时间为525分钟,行走路径为:30KM,总时间为:597分钟对于问题三：与问题二相比,报修客户有了维修时间限制,在问题二模型的基础上,将小区的维修任务分在三个时间段(上午,中午,下午),再分别对各个时间段的任务利用问题二的模型进行遍历,找到各个时间段的最佳路线,最后综合整理,找出整体最优方案.对于问题四:采取分块法估计最短路径，然后利用整体最短路径与估计的最短路径对比，可得出维修人数关系不等式，求出最佳人数。对于问题五:假设至少需要维修员x个,结合问题中的条件限制,列出几个不等式,找出目标函数,利用线性规划模型进行求解.关键字小区维修优化模型遗传算法枚举法TSP线性规划均匀分布指数模型2一、问题重述某个热水器维修站承接多个品牌的热水器维修任务，负责附图1所示地区的维修事项。该地区共有70个不同的小区，为简单起见，假设每个小区都是长方形区域，边长也仅有两种规格：2000米、1000米，如小区1是边长1000米的正方形区域；小区3是2000米×1000米的长方形区域；小区9是边长为2000米的正方形区域。也假设每个小区的入口仅有一个，均位于小区区域上边的中点处。维修站位于65号小区的左上角。维修员的出行方式为电瓶车，平均速度为25公里/小时。维修站接待保修、维修员上门维修的流程如下：保修电话记录每个报修信息，生成任务清单。每个维修员早8：00到维修站领取其所负责区域的维修单，下午6：00之前必须将当天已经完成的清单与未完成的清单交到维修站。热水器的报修事项相对稳定，假设一共有A、B、C、D、E、F、G、H八类，各类事项的平均维修时间数据如下表。事项ABCDEFGH维修时（分钟）1020153020153520请按照所给信息，建立数学模型，回答下列问题。（1）假设每个小区的报修客户住处随机分布在小区内。建立模型说明在一个规格a千米b千米小区内维修所需总时间与小区大小、报修项目之间的关系。（2）假设维修员负责1---小区16的所有任务。某天接到的报修单见附表2。该维修员当如何安排，使得一天内完成尽可能多的维修任务。（3）客户在报修时会对维修人员时间上有要求，假设可能的时间要求分为三个时间阶段:上午（8：00—11：00）、午饭时间（11：00—13：00）、下午时间（13：00—18：00）。在上一题中，每项报修要求时间见附表3。该维修员应当如何安排，使得一天内能完成最多的任务（维修人员的午饭时间可以在11：00—13：00内灵活安排，时间约为15分钟）。（4）假设维修站现在仍没有完成的维修任务如附表4。按照当前任务，维修站至少需要几名维修员，能够使得在一天内完成所有的修理工作。（5）维修站承诺所有报修事项能在3天内上门修理。假设今天是2012年5月日，维修站现在仍没有完成的维修任务以及报修时间如附表5。按照当前任务，维修站至少需要几名维修员，能够在承诺的时间内完成所有修理工作。二、问题分析问题一的分析:小区内维修总时间由小区内报修的客户个数和每个报修客户的维修时间有关，二者相乘即为总时间。求小区内报修的客户个数方法：由题目中的假设知：每个小区的报修客户住处随机分布在小区内，我们采用二维的均匀分布，求出小区内报修的客户个数3的期望。求每个报修客户的维修时间的方法：由于维修故障所需的知识有难易之分，故障出现的频率有高低之别，一般说来，简单的故障发生的频率高，越复杂故障发生的频率就越低。文献[1]表明，故障发生的概率密度与故障维修的难易程度近似服从指数分布。而修理工时与故障的难易程度呈线性关系，因此为计算简便，可设某故障出现的概率)exp()(xxf其中，为正常数，x为故障的维修难易程度，即为维修时间。代入各个事项的维修时间，即可求出，然后可进一步求出每个报修客户需要维修的期望时间。报修客户数与每个报修客户的维修时间进行乘积，即可得出总的维修时间和小区面积与报修项目之间的关系。问题二的分析:维修任务量的标准：题目要求求解一天内完成尽可能多的维修任务，怎样才是尽可能多的维修任务呢？本文认为除了花费在最优路径上的时间外，其余时间全部用在执行维修任务上，这个时间是指切切实实花费在维修项目上的时间，也就是说我们认为不是完成的项目个数越多维修量就越多，而是除了不可避免的尽可能短的路程时间外，其余时间全部用在维修项目上，这个时间越多，维修任务完成的也就越多，也就是时间利用率最高的完成的维修任务越多。这就是本文评定维修任务多少的指标。首先，由附表2中1-16个小区的报销清单可知，维修完所有任务所需总时间为875分钟，而一个维修员一天的工作总时间为10个小时，也就是600分钟，这两个时间的对比可知，维修员一天是不可能完成这16个小区的维修任务的，只能在规定的时间内完成尽可能多的维修任务，做到时间利用率最高。通过编程，我们用排列组合方式分别踢出1个，2个，……，n个小区，对应穷举出剩下的小区，用遗传算法进行最佳遍历，找出一个最佳行走路径，使最佳行走路径的总时间满足下式：)(60021分钟TT其中：T1为实际维修项目花费的总时间，T2为从维修站出发到回到维修站，其中最佳行程上花费的总时间。实践中发现，满足上述条件的成立情况有许多种，只要找到T1最大的一个遍历，即花费在维修任务上时间最多，路程时间最短的一个遍历，就是完成维修任务最多的一个遍历。问题三的分析:与问题二相比,维修任务时间有限制,项目维修时间分别限制为上午、上午或中午、上午或下午、中午、中午或下午、下午、全天。由计算可知，上午的工作时间为180分钟，中午为105分钟，下午为300分钟。上午维修任务时间为225分钟，中午为190分钟，下午为105分钟。通过对比可知，在上午和中午的规定时间内，其限制段内的任务是不可能完成的，只能尽可能多的完成。而在下午的时间段内除了限定的任务外，其时间是有余量的，所以应尽可能将可以在上午或下午、中午或下午、全天的时间段内的任务放在下午进行，以提高时间利用率。所以我们先对有弹性的时间段下午进行求解，用问题二的模型进行最优路径进行4遍历，得出最优方案后，将剩余的维修任务归纳到相应的上午和中午中，例如对于中午时间段求解时，我们将上午或中午，剩余的中午或下午，剩余的全天，中午这些的时间段内的任务放在中午，再用问题二模型分别对其进行遍历，得出最优维修方案。最后将上午、中午、下午的最优方案综合起来，既得出一天的最优方案，也就是完成任务最多的方案。问题四的分析:对于问题四每个人一天的工作时间一定，工作时间由实际维修时间和花在路上的时间组成。如果路上时间用的少，则有效时间多，每个人完成任务就多，这样总任务需要的人数最少。这样问题又转化为求最短路径问题。但是如果求70个小区最短路径那么计算量太大，所以分区进行，1-16,17-31,32-45,46-59,60-70分别为一个区。利用遗传算法求解出1-16的最短路径s，由于这五个区面积相同，小区分布也相似，所以为了计算方便就取这个路径为5个区的平均最短路径，则总的最短路径为s5,总时间为T，但是这只是满足局部路径最优，整体不一定最优。所以假设总体最短路径为aS则sSa5,所以整体最优的总时间TTa.所以利用公式：7011600iiitTN其中N为所需要的维修人数it为第i个小区的项目时间1T为花费在路上的时间则70126001iiiTtN70116001iiitN7016001iiaiTtN所以21NNN所以根据上式即可求解出至少需要多少维修人员问题五的分析:由问题四可知,可以求出一个维修员一天最多维修任务的时间,假设至少需要维修员为x个,5月4日必须做完5月1日的任务,然后再考虑做5月2日的,5月5日必须先做完5月2日的再做5月3日的,这样依次递推,可以列出列出规划方程及目标函数,利用线性规划求解,找出最小的x即可.5三、模型假设与约定1、假设维修工沿着两个小区之间的直线行走2、假设维修工从一个小区到另外一个小区时走最近的路线3、假设维修工完成一个小区的所有维修任务后才去另外的小区进行维修4、假设维修员的电瓶车不出故障，行走正常。四、符号说明及名词定义i（0，1,2，……，70）：0表示维修站，1-70表示小区a：小区的长度b：小区的宽度T1：实际维修项目花费的总时间，T2：从维修站出发到回到维修站，最佳行程上花费的总时间。S：1-70个小区的总面积N：1-70小区的总人数kG：为遗传种群中的第k个个体M1、M2、M3:分别为5月1日至5月3日每天的维修时间五、模型建立与求解5.1、模型一:均匀分布模型5.1.1、模型的建立假设:1-70个小区的总面积为S,1-70小区的总人数为NS和N可以看做常量,由小区的资料可以查到，所以一个面积为ba小区的人数为:SNab题目中已经假设每个小区的报修客户住处随机分布在小区内，所以一个小区报修客户可用二维的均匀分布表示，其密度函数为：SNab1SNbySNax0,0),(yxf0，其他参考资料【2】知：6,))((1cdab,,dycbxa0，其他的充要条件是X,Y相互独立且X~U(a,b),Y~U(c,d)由概率论知识知可知，关于小区内位置的期望为dxdyyxfyxgyxE),(),(),(=)()(yExE=SNaxdxSNa01SNbydySNb01=24SNab5.2、模型二:指数衰减模型5.2.1、模型的建立热水器维修有八类事项,不同的事项需要的维修时间不同,参考资料[1]:由于维修故障所需的知识有难易之分，故障出现的频率有高低之别，因此某故障发生的频率和难易程度可以用图1来表示。点的横坐标的值表示故障维修所需知识的难易程度，难度低的知识靠近原点，难度高的知识远离原点；点的纵坐标的值表示故障发生的概率。一般说来，简单的故障发生的频率高，越复杂故障发生的频率就越低。文献[1]表明，故障发生的概率密度与故障维修的难易程度近似服从指数分布。),,,;,(~),(dcbayxfYX7而修理工时与故障的难易程度呈线性关系，因此为计算简便，可设某故障出现的概率)exp()(xxf其中，为正常数，x为故障的维修难易程度，即为维修时间。由1)(itf(it为维修不同的事项所需要的时间)即:1)20exp()35exp()15exp()20exp()30exp()15exp()20exp()10exp(可求得=1165.0所以每个报修客户平均需要维修时间为:)()(iitfttE16)]20exp(20)35exp(35)15exp(15)20exp(20)30exp(30)15exp(15)20exp(20)10exp(105.3、模型三:基于遗传算