二0一七全国大学生数学建模竞赛解析演示文档.pptxVIP

. 巡检线路的排班 ——2017年D题讲评 主讲人：北京工业大学 薛毅 Email: xueyi@bjut.edu.cn 2017全国数学建模讲评会 云南、昆明 2017年11月25日 . 巡检线路的排班——2017年D题讲评 题目 问题分析及问题1的求解 问题2的求解 问题3的求解 阅卷情况简述 . 1. 题目 —— 巡检线路的排班 题目 —— 巡检线路的排班 某化工厂有 26 个点需要进行巡检以保证正常生产，各个点的巡检周期、巡检耗时、两点之间的连通关系及行走所需时间在附件中给出。 每个点每次巡检需要一名工人，巡检工人的巡检起始地点在巡检调度中心（XJ0022），工人可以按固定时间上班，也可以错时上班，在调度中心得到巡检任务后开始巡检。现需要建立模型来安排巡检人数和巡检路线，使得所有点都能按要求完成巡检，并且耗费的人力资源尽可能少，同时还应考虑每名工人在一时间段内（如一周或一月等）的工作量尽量平衡。 表1 Excel表中的基本信息 . 图1 Excel表中的连通图 题目 —— 巡检线路的排班 . 问题1.如果采用固定上班时间，不考虑巡检人员的休息时间，采用每天三班倒，每班工作8小时左右，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。 问题2. 如果巡检人员每巡检 2 小时左右需要休息一次，休息时间大约是 5 到 10 分钟，在中午12 时和下午 6 时左右需要进餐一次，每次进餐时间为 30 分钟，仍采用每天三班倒，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。 题目 —— 巡检线路的排班 问题3. 如果采用错时上班，重新讨论问题 1 和问题 2，试分析错时上班是否更节省人力。 . 2.问题分析与模型建立 问题分析与模型建立 这个问题说的复杂一点是旅行商问题（Traveling Salesman Problem, TSP），或者是多旅行商问题（m-TSP），更严格的说，是车辆路径问题（Vehicle Routing Problem, VRP），而且还是带有时间窗口的车辆路径问题（Vehicle Routing Problem with Time Windows, VRPTW）。 如果这样考虑问题，这个问题将变得非常复杂。事实上，这个问题并没有这么复杂，因为它只有26个需要巡视的点，如果每个巡视点安排一个人的话，一个班至多是26个人。当然，没有那糟糕，如果一个人能巡视3～5个点的话，一个班也就是 6～9 个人。因此，只需要启发式算法就可能得到问题的计算结果。 . 问题分析——巡检人员下限估计 2.1 巡检人员下限估计 为估计巡检人员数量的下限，先计算出旅行商问题所需要的时间（包括路程时间和巡检耗时）。对于只有26个城市的旅行商问题，无论是精确计算，还是近似计算都是不困难的。 可以考虑使用LINGO程序（见[1]）得到精确的计算结果（见图2），其中路程耗时68分钟和检查耗时67分钟，共计135分钟。 图2 26个点的TSP线路图 . 由于巡视点两次巡视的最小间隔时间是35分钟，且135/35=3.86，因此，一个班至少需要4名工人。从图2 （TSP图形）和题目要求（从22号点开始巡视）来看，只用4名工人巡视，肯定是不够的，应考虑增加1名工人，一个班使用5名工人。 从上述计算过程来看，实际上，并不需要精确求解TSP，只需近似计算，估计出一个下界即可。 例如，可以采用手工计算，也可以采用某些启发式算法，如最近领域法、最近插入法、最远插入法、最便宜插入法、任意插入法和交换两边改进方法等。 如果不打算自己手工编程，可以使用现成的软件，例如，R软件中的TSP函数（见[2]）就可以很好地解决这些问题，提供不同的参数，选择你喜欢的算法。 问题分析——巡检人员下限估计 . 现知道每个班需要5名工人，所以需要将巡视点划分成5个区域，每个区域最多包含6个点，最少也要有4个点，其目的是保证每个区域的工作量（巡视时间）尽量平衡。 由于题目要求，每位工人均从22号点开始巡视，因此，距22号点较近的点则多安排一些，而距22号较远的 2.2 问题1的求解 点则少安排一些。为了完成这种需求的安排，需要计算从22号点至其余各点的最短路，这项工作可用Dijkstra （戴克斯特拉）算法完成。 当然，也不需要自己编程计算，直接调用R软件的shortest.paths()函数和get.shortest.paths()函数（见[2]）就可完成此问题，所绘图形如图3所示。 问题分析 —— 问题1的求解 . 问题分析 —— 问题1的求解 图3 22号点至