数学建模-DHUMCM2012-109-B.doc

2012年东华大学数学建模竞赛论文赛题编号（B）（维修任务安排）参赛队号：DHUMCM2012109参赛队员： 马嘶鸣（信息科学与技术学院，自动化0901，090900317） 罗世操（信息科学与技术学院，自动化0902，090900424） 郑华科（信息科学与技术学院，电 气0901，090900316） 2012年5月21日摘要本文讨论了维修任务安排的优化问题，并总结出一些在这类图中求出最优回路的有效方法，即在有限的时间内如何使工作量最大化，在指定的工作量、工作时间的前提下如何使工作人员最少化的最优路径方案问题。问题一：建立了单个小区维修总时间与小区大小ab和报修项目之间的关系模型。采用古典概率模型和面积法求概率的方法，得出进入小区内完成k项维修任务之间的总的行走时间ti1，然后将各类维修事项时间乘以各自的数目就得出了小区内k项维修任务的维修时间ti2，相加即得出所需总时间模型ti= ti1+ ti2。问题二：首先采用matlab计算各个小区及工作站之间最短曼哈顿距离矩阵D。由于典型的单旅行商模型（TSP）在建立Hamilton回路时，会遍历所有节点，而本题要求则是遍历尽可能多的小区节点，为此我们引入0-1决策变量对路径进行修正，同时我们以每个小区所需总时间ti和各小区间的最短路径时间为基础添加了时间约束条件，并最大工作量为目标建立算法，通过LINGO11.0求解得到最优维修路径，最优路线为：维修站小区10小区9小区4小区3小区1小区6小区5小区7小区8维修站，所需时间9.993200h，完成项目24项。问题三：考虑到大部分维修事项都有具体的时间要求，维修员在每个时间段内只能着眼于当前时间段内的最大工作量。故本问题在问题二模型的基础上，修改相应时间段的路径约束条件，出发点、回归点约束条件和时间约束条件，并修改相应时间段内的维修事项数量矩阵C，分别建立上午、中午、下午模型，在时间段交接的节点小区内，两个时间段的维修任务都做，减少了行走时间，通过LINGO求解得到最优维修路径，最优路线如下：上午：维修站小区8小区6小区2小区1，所需时间2.886633h，完成项目7项；中午：小区1小区5小区7；所需时间1.593267h，完成项目4项；下午：小区7小区8小区9小区11小区13小区16小区12维修站，所需时间4.706600h，完成项目11项。共完成项目22项。问题四：首先对维修员工初值进行预判。下限：计算所有维修任务总时间72.3h，至少要8人完成；上限：采用将mTSP问题转换为TSP问题的方法，利用问题二模型，修改相应约束条件，将所有工作任务先对第1人求最优解，然后依次将剩余工作任务对第2，3，人求最优解，直至无最优解，利用LINGO求解得到10人。确定维修员人数在8-10人。然后利用遗传算法和matlab编程，在给定初值中寻找最优路径，并确定最少维修员人数。至少需要10名维修员工。问题五：首先估计初值，所有维修任务所需时间120.4h，对3天取平均，每天至少需要5人。然后以问题四的遗传算法为基础，假设今天为5月第i天，先对第i-3天的所有维修任务以时间最少为目标进行优化，优化不成功则初值加1，重新开始；优化成功则计算出完成第i-3天所有工作任务最少维修时间，和第i天的剩余工作时间，再在第i天的剩余工作时间里，对第i-2天的所有维修任务以完成最多维修项目为目标进行优化，得到第i-2天的剩余工作量，然后天数i=i+1，重复上述过程，直到5月6日只对5月3日的剩余工作任务进行最少时间优化完成。若5月6日最终的优化时间很小，则维修员人数可能多余，对初值减1，重复上述过程；若5月6日最终的优化时间合理，即得到最优解。至少需要5名维修员。关键字：曼哈顿距离TSPmTSP遗传算法一、问题的重述某个热水器维修站承接多个品牌的热水器维修任务，负责附图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八类，各类事项的平均维修时间数据如下表。 事项 A B C D E F G H 维修时间（分钟） 10 20 15 30 20 15 35 20 请按照所给信息，建立数学模型，回答下列问题。 （1）假设每个小区的报修客户住处随机分布在小区内。建立模型说明在一个规格为a千米b千米小区内维修所需总时间与小区大小、报修项目之间的关系。 （2）假设维修员 Z 负责小区 1-小区 16 的所有维修任务。某天接到的报修单见附表 2。该维修员应当如何安排，使得一天内能完成尽可能多的维修任务。 （3）客户在报修时往往会对维修人员上门时间有要求，假设可能的时间要求分为三个时间段：上午（8：00-11：00）、午饭时间（11：00-13：00）、下午时间（13：00-18：00）。在上一题中，每项报修要求时间见附表 3。该维修员应当如何安排，使得一天内能完成最多的维修任务（维修人员的午饭时间可以在 11：00-13：00 内灵活安排，时间约为 15 分钟）。 （4）假设维修站现在仍没有完成的维修任务如附表 4。按照当前任务，维修站至少需要几名维修员，能够使得在 1天内完成所有修理工作。 （5）维修站承诺所有报修事项能在报修后 3 天内上门修理。假设今天是 2012 年 5 月 4 日，维修站现在仍没有完成的维修任务以及报修时间如附表 5。按照当前任务，维修站至少需要几名维修员，能够在承诺的时间内完成所有修理工作。二、基本假设（1）考虑到小区的布局图及现实中楼房的排布，设计维修员出行路线距离计算采用曼哈顿距离，即（个别位置需要修正）。（2）考虑到维修站一般临街，故维修站位于65号小区左上角的临街处。（3）每个小区的各类维修事项随机分布，不考虑楼层的影响。（4）考虑到现实情况，维修员每次进入1个小区便完成该小区的全部维修事项。三、符号说明四、问题分析及模型建立和求解4.1 问题一：分析：规格为a千米b千米的小区进出口朝向有4种，进一步可将进出口归纳为位于a千米所在边或位于b千米所在边。小区报修事项满足随机分布，两两维修事项之间的曼哈顿距离通过古典概率求取期望的办法求得距离的期望值以获得尽可能小的误差。故从进入小区i到维修完成所有维修事项再从小区i出来的总时间ti可分为行走时间ti1(与小区大小ab和报修项目数量有关)和维修时间ti2(与报修项目数量和各项目时间有关)，分别计算并相加即可。模型建立：各类项目维修所需时间矩阵第i个小区各类维修项目数量矩阵以每个小区入口为坐标原点，建立坐标，第i个小区中行走时间ti1：对ti1求取期望E(ti1)得：其中：第i个小区维修时间ti2：故第i个小区的总时间ti：近似为：4.2 问题二：分析：首先利用matlab计算维修站及各个小区之间的出入口相对曼哈顿距离矩阵D（存在不能直接利用的情况，需加以修正）：（见附表D）考虑维修员从维修站出发每进入一个小区就完成该小区的所有维修任务，但不会经过所有小区，由此引入两个决策变量，其数学含义：维修员从维修站出发并最终回到维修站，对于任意一点，有且仅有1条路从到，即满足；同时，对任意一点，从该点出发到的路也仅有1条，即满足条件。由于维修员从早上8：00工作到下午6：00，期间有10个小时，除了所到的每个小区维修的总时间，还需要考虑每个小区之间的行走时间。此外，这种TSP问题的前2个约束条件无法避免可能出现的TSP子圈问题，为了过滤这种情况，增加了“不含子圈”的约束条件，采用文献3介绍的方法，增加额外变量，并附加约束条件。目标是一天内尽可能完成多的维修项目，由此建立目标函数，便完成了问题二的模型分析。模型建立：其中：模型求解：根据问题二的模型，利用lingo11.0编程求得全局最优解，即为本题的维修任务安排。由于lingo软件中的变量值需从1开始，故程序中地点从i=1开始，到i=17结束，此外，还需要将目标函数取负，获得最小值，才能使程序正确运行，结果如下：路线所用时间完成数量维修站小区10小区9小区4小区3小区1小区6小区5小区7小区8维修站9.993200h24一天完成项目数量=24项。4.3问题三：分析：由于大部分维修事项都有具体的时间范围，维修员进行考虑时，优先考虑当前时间段的最大工作量。故建立模型时，列写出分阶段的优化模型，计算各阶段的维修项目数量矩阵，分别求解。上午模型中，由于维修员在进行完上午的维修工作后不返回维修站，在问题二的基础上我们修改约束条件如下：目标函数仍为尽可能完成多的维修任务，完成上午模型。假设上午维修员在L区结束，在完成上午的任务后，为了节省路程时间，维修员中午接着在L区开始维修，由于中午的维修项目矩阵中，可能有部分已经在上午完成，故中需要减去已经维修过的部分，新的维修数量矩阵为。修改上午模型的约束条件（1）、（2）为和（3）即可建立中午模型，修改后的约束条件为：目标函数不变，完成中午模型。假设中午维修员在P区结束，在完成中午的任务后，为了节省路程时间，维修员下午接着在P区开始维修，由于下午的维修项目数量矩阵中，可能有部分已经在上午、中午完成，故中需要减去已经维修过的部分，新的维修数量矩阵为。修改中午模型的约束条件（2）为和（3）即可建立中午模型，修改后的约束条件为：目标函数不变，即完成下午模型。模型建立：上午模型（维修员从维修站出发，不返回维修站）：中午模型（假设上午最后一站在小区L）：下午模型（假设上午最后一站在小区P）：模型求解：根据问题三的模型，利用lingo11.0编程分别求得全局最优解，即为本题的维修任务安排。结果如下：路线所用时间完成数量上午维修站小区8小区6小区2小区12.886633h7中午小区1小区5小区71.593267h4下午小区7小区8小区9小区11小区13小区16小区12维修站4.706600h11因此，全天完成维修项目=7+4+11=22项。4.4问题四：模型分析：由于维修项目数量和时间窗已知，要确定最少维修员工，首先需要对维修员工初值进行预判，然后进行最优化。这里维修员工初值的上下限采用如下办法确定：下限：计算所有维修任务总时间72.3h，因此至少要8人完成；上限：采用将mTSP问题转换为TSP问题的方法，利用上述模型，修改相应约束条件，将所有工作任务先对第1人求最优解，然后依次将剩余工作任务对第2，3，人求最优解，直至无最优解，利用LINGO求解得到10人。因此确定了需要的维修员在8-10人。然后利用遗传算法和matlab编程，为了简化程序，画图时采用坐标值形式，路径变为两点间的距离，在给定初值中寻找最优路径，并验证最少维修员人数。模型建立：第一步编码：点0表示维修站，假设m个维修工需要对70个小区进行修理，构造m个维修工的组成的mTSP的行走路径为一条染色体编码。为了表示，作适当简化，如0，1，8个小区，3个维修工构成的mTSP的一条染色体编码为：25739410186则三个维修工的路径分别为：0-2-5-7-3-00-4-00-1-8-6-0第二步选择适应度函数：在人数假定的情况下，优化的目标为最优路径，即最小化完成时间，选取适应度函数：。第三步进行选择：在计算完适应度后，采用按比例的适应度分配，利用比例于各个个体适应度的概率决定其子孙遗留。若某个个体i其适应值为，则其被选择的概率表示为，然后对各个染色体计算它们的累计概率，用轮盘法选择交配个体。第四步交叉变异：我们采用基于路径表示的匹配交叉法，在交叉完成后，采用交换变异。第五步进行解码：确定最终的染色体编码后，我们对其解码，并给出维修员路径图。模型求解：首先给出LINGO11.0逐次求解的个人的最优解。维修员路线所用时间完成任务数量完成小区数量1维修站363518176237484762维修站9.903333h27102维修站666768301428152725维修站9.989867h2593维修站2419873346395064维修站9.919567h2394维修站555643952维修站9.896400h2255维修站61215134维修站9.883167h2266维修站5831452954维修站9.933000h2157维修站635340412342维修站9.993000h2268维修站697059571165维修站9.966333h2069维修站512234384960维修站9.773100h18610维修站1632264420101312维修站9.426467h128从每个人的所用时间都在10h左右，上述解基本接近最优解，预判至多需要10人，然后采用matlab通过遗传算法进行验证，目标函数：， ，为维修员最大工作时间 当人数为9人时，无最优解；当人数为10人时，最优解如下：总的最小时间： global_min = 96.2178h；与LINGO迭代结果基本相符。4.5问题五：模型分析：由于维修站承诺3天内上门修理，假设今天是2012年5月4日，并给出了5月1日-5月3日的维修任务数量，要求在承诺时间内完成所有修理工作。具体来讲，5月4日可以处理1、2、3日报修任务，5日可以处理2、3日的报修任务，6日只能处理3日报修任务。我们以问题四的方法为基础，加入筛选条件，使其在5月4日完成5月1日的任务，并尽量完成较多的5月2日任务；5月5日完成5月2日的所有任务，并尽量完成较多的5月3日的任务；5月6日完成所有5月3日的任务。模型建立：以问题四中的遗传算法为模型，多次调用遗传算法模型，对每次优化结果进行判断，实现问题五的算法。其算法流程图如下：模型求解：利用matlab中程序实现上述算法，初值为5有最优解，进而得出至少需要5名维修员。第一天最小时间： global_min1 = 46.5867h；第二天最小时间： global_min2 = 45.9133h；第三天最小时间： global_min3 = 47.5933h；所有时间均满足优化条件，进而说明至少需要5名维修员。五、优缺点分析5.1模型的优点1、问题一在建立维修所需时间与小区大小、报修项目关系模型时，忠于题意，将各类事项随机分布，通过求取期望的办法，获得尽可能小的误差。此外，由于出入口位置的不同，而引入的决策变量 满足0-1分布，使小区内的行走时间更加体现了现实条件，也简化了后续的计算工作。2、各个小区的出入口之间的最短行走距离采用曼哈顿距离，但从小区的分布图中可以看出，存在不满足上述条件的情况（如小区5和小区6的距离），故本模型对距离矩阵D进行了修正，从而使优化模型更加准确。3、问题二、问题三都是基于TSP问题，通过对一般的模