全国大学生数学建模竞赛D题解析ppt课件

巡检线路的排班 2017年D题讲评 1 巡检线路的排班 2017年D题讲评 题目 问题分析及问题1的求解 问题2的求解 问题3的求解 阅卷情况简述 2 1 题目 巡检线路的排班 题目 巡检线路的排班 某化工厂有26个点需要进行巡检以保证正常生产 各个点的巡检周期 巡检耗时 两点之间的连通关系及行走所需时间在附件中给出 每个点每次巡检需要一名工人 巡检工人的巡检起始地点在巡检调度中心 XJ0022 工人可以按固定时间上班 也可以错时上班 在调度中心得到巡检任务后开始巡检 现需要建立模型来安排巡检人数和巡检路线 使得所有点都能按要求完成巡检 并且耗费的人力资源尽可能少 同时还应考虑每名工人在一时间段内 如一周或一月等 的工作量尽量平衡 表1Excel表中的基本信息 3 表2Excel表中的连通关系 图1Excel表中的连通图 题目 巡检线路的排班 4 问题1 如果采用固定上班时间 不考虑巡检人员的休息时间 采用每天三班倒 每班工作8小时左右 每班需要多少人 巡检线路如何安排 并给出巡检人员的巡检线路和巡检的时间表 问题2 如果巡检人员每巡检2小时左右需要休息一次 休息时间大约是5到10分钟 在中午12时和下午6时左右需要进餐一次 每次进餐时间为30分钟 仍采用每天三班倒 每班需要多少人 巡检线路如何安排 并给出巡检人员的巡检线路和巡检的时间表 题目 巡检线路的排班 问题3 如果采用错时上班 重新讨论问题1和问题2 试分析错时上班是否更节省人力 5 2 问题分析与模型建立 问题分析与模型建立 这个问题说的复杂一点是旅行商问题 TravelingSalesmanProblem TSP 或者是多旅行商问题 m TSP 更严格的说 是车辆路径问题 VehicleRoutingProblem VRP 而且还是带有时间窗口的车辆路径问题 VehicleRoutingProblemwithTimeWindows VRPTW 如果这样考虑问题 这个问题将变得非常复杂 事实上 这个问题并没有这么复杂 因为它只有26个需要巡视的点 如果每个巡视点安排一个人的话 一个班至多是26个人 当然 没有那糟糕 如果一个人能巡视3 5个点的话 一个班也就是6 9个人 因此 只需要启发式算法就可能得到问题的计算结果 6 问题分析 巡检人员下限估计 2 1巡检人员下限估计 为估计巡检人员数量的下限 先计算出旅行商问题所需要的时间 包括路程时间和巡检耗时 对于只有26个城市的旅行商问题 无论是精确计算 还是近似计算都是不困难的 可以考虑使用LINGO程序 见 1 得到精确的计算结果 见图2 其中路程耗时68分钟和检查耗时67分钟 共计135分钟 图226个点的TSP线路图 7 由于巡视点两次巡视的最小间隔时间是35分钟 且135 35 3 86 因此 一个班至少需要4名工人 从图2 TSP图形 和题目要求 从22号点开始巡视 来看 只用4名工人巡视 肯定是不够的 应考虑增加1名工人 一个班使用5名工人 从上述计算过程来看 实际上 并不需要精确求解TSP 只需近似计算 估计出一个下界即可 例如 可以采用手工计算 也可以采用某些启发式算法 如最近领域法 最近插入法 最远插入法 最便宜插入法 任意插入法和交换两边改进方法等 如果不打算自己手工编程 可以使用现成的软件 例如 R软件中的TSP函数 见 2 就可以很好地解决这些问题 提供不同的参数 选择你喜欢的算法 问题分析 巡检人员下限估计 8 现知道每个班需要5名工人 所以需要将巡视点划分成5个区域 每个区域最多包含6个点 最少也要有4个点 其目的是保证每个区域的工作量 巡视时间 尽量平衡 由于题目要求 每位工人均从22号点开始巡视 因此 距22号点较近的点则多安排一些 而距22号较远的 2 2问题1的求解 点则少安排一些 为了完成这种需求的安排 需要计算从22号点至其余各点的最短路 这项工作可用Dijkstra 戴克斯特拉 算法完成 当然 也不需要自己编程计算 直接调用R软件的shortest paths 函数和get shortest paths 函数 见 2 就可完成此问题 所绘图形如图3所示 问题分析 问题1的求解 9 问题分析 问题1的求解 图322号点至其余各点的最短路 10 从图3出发 作如下尝试 将22 20 19 2 4和21号点编为第一组 23 24 9 8 17和25号点编为第二组 1 3 6 14 5和7号点编为第三组 26 15 18和12号点编为第四组 11 13 16和10号点编为第五组 每一组都找出相应TSP的结果 具体分组和相应的TSP图形如图4所示 这种分组方式是为了满足题目的要求 在规定的巡视时间间隔内完成巡视 每位工人的工作量尽量平衡 巡视时间即不能过长 也不能过短 问题分析 问题1的求解 11 图4巡检线路的分组情况 5 TSP 问题分析 问题1的求解 12 下面给出具体的巡视路线和巡视时间 第1组 22 20 19 2 4和21号点 的巡视周期是29分钟 而21号点的周期间隔是80分钟 可以两个35分钟巡视一次 所以此时巡视同期是27分钟 第2组 23 24 9 8 17和25号点 的巡视 最长周期是32分钟 最短周期28分钟 17号点和25号点的时间间隔为分别为480分钟和 120分钟 第3组 1 3 6 14 5和7号点 的巡视 最长周期是32分钟 最短周期19分钟 5号点和7号点的时间间隔分别为720分钟和80分钟 第4组 26 15 18和12号点 的巡视 周期长度是28分钟 第5组 11 13 16和10号点 的巡视 周期长度是25分钟 问题分析 问题1的求解 13 表3第1组巡视的时间表 部分 问题分析 问题1的求解 14 表4第2组巡视的时间表 部分 问题分析 问题1的求解 15 表5第3组巡视的时间表 部分 问题分析 问题1的求解 16 表6第4组巡视的时间表 部分 问题分析 问题1的求解 17 表7第5组巡视的时间表 部分 问题分析 问题1的求解 18 3 问题2的求解 问题2 休息时间 3 1休息时间 为了简化问题 先不用考虑 每巡视2小时左右休息大约5到10分钟 这一要求 因为在问题1的求解过程中 5名工人在巡视过程中 多次出现5分钟的空余时间 这些空余时间可作休息时间 在问题1的讨论中 每班需要5名工人 考虑两次进餐时间 1小时 就需要增加5小时 如果再考虑进餐的衔接时间 需要增加的时间还不止5小时 所以仅依赖于原来的5名工人而挤出进餐时间几乎是不可能的 因此 需要增加1名工人让他在其他工人进餐时 完成巡视工作 3 2进餐时间 19 排班的方法是 原来的排班时间不变 5名工人的进餐时间安排在11时至13时之间 和17时至19时之间 进餐时间为35分钟 最小的时间间隔 进餐时的巡视工作由第6名 机动 工人完成 第6名 机动 工人的进餐时间可安排在他不替班的非工作时间 表8至表12给出了部分排班的时间表 白班和中班 图中的黄色部分是可用于吃饭的时间 第6名 机动 工人的巡视时间表 以及替换组的情况如表13所示 问题2 进餐时间 20 表8第1组巡视的时间表 部分 包含进餐时间 问题2 进餐时间 21 表9第2组巡视的时间表 部分 包含进餐时间 问题2 进餐时间 22