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

2012年东华大学数学建模竞赛论文 赛题编号（B） （维修任务安排） 参赛队号：DHUMCM2012109 参赛队员： 马嘶鸣（信息科学与技术学院，自动化0901，090900317） 罗世操（信息科学与技术学院，自动化0902，090900424） 郑华科（信息科学与技术学院，电 气0901，090900316） 2012年5月21日 摘要 本文讨论了维修任务安排的优化问题，并总结出一些在这类图中求出最优回路的有效方法，即在有限的时间内如何使工作量最大化，在指定的工作量、工作时间的前提下如何使工作人员最少化的最优路径方案问题。 问题一：建立了单个小区维修总时间与小区大小a×b和报修项目之间的关系模型。采用古典概率模型和面积法求概率的方法，得出进入小区内完成k项维修任务之间的总的行走时间ti1，然后将各类维修事项时间乘以各自的数目就得出了小区内k项维修任务的维修时间ti2，相加即得出所需总时间模型ti= ti1+ ti2。 问题二：首先采用matlab计算各个小区及工作站之间最短曼哈顿距离矩阵D。由于典型的单旅行商模型（TSP）对路径进行修正，同时我们以每个小区所需总时间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名维修员。 关键字：曼哈顿距离 TSP mTSP 遗传算法 一、问题的重述 某个热水器维修站承接多个品牌的热水器维修任务，负责附图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