搜索
巡检线路的排班——2017年D题讲评主讲人：北京工业大学薛毅Email:xueyi@bjut.edu.cn2017全国数学建模讲评会云南、昆明2017年11月25日巡检线路的排班——2017年D题讲评•题目•问题分析及问题1的求解•问题2的求解•问题3的求解•阅卷情况简述1.题目——巡检线路的排班题目——巡检线路的排班某化工厂有26个点需要进行巡检以保证正常生产，各个点的巡检周期、巡检耗时、两点之间的连通关系及行走所需时间在附件中给出。每个点每次巡检需要一名工人，巡检工人的巡检起始地点在巡检调度中心（XJ0022），工人可以按固定时间上班，也可以错时上班，在调度中心得到巡检任务后开始巡检。现需要建立模型来安排巡检人数和巡检路线，使得所有点都能按要求完成巡检，并且耗费的人力资源尽可能少，同时还应考虑每名工人在一时间段内（如一周或一月等）的工作量尽量平衡。表1Excel表中的基本信息表2Excel表中的连通关系图1Excel表中的连通图题目——巡检线路的排班问题1.如果采用固定上班时间，不考虑巡检人员的休息时间，采用每天三班倒，每班工作8小时左右，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。问题2.如果巡检人员每巡检2小时左右需要休息一次，休息时间大约是5到10分钟，在中午12时和下午6时左右需要进餐一次，每次进餐时间为30分钟，仍采用每天三班倒，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。题目——巡检线路的排班问题3.如果采用错时上班，重新讨论问题1和问题2，试分析错时上班是否更节省人力。2.问题分析与模型建立问题分析与模型建立这个问题说的复杂一点是旅行商问题（TravelingSalesmanProblem,TSP），或者是多旅行商问题（m-TSP），更严格的说，是车辆路径问题（VehicleRoutingProblem,VRP），而且还是带有时间窗口的车辆路径问题（VehicleRoutingProblemwithTimeWindows,VRPTW）。如果这样考虑问题，这个问题将变得非常复杂。事实上，这个问题并没有这么复杂，因为它只有26个需要巡视的点，如果每个巡视点安排一个人的话，一个班至多是26个人。当然，没有那糟糕，如果一个人能巡视3～5个点的话，一个班也就是6～9个人。因此，只需要启发式算法就可能得到问题的计算结果。问题分析——巡检人员下限估计2.1巡检人员下限估计为估计巡检人员数量的下限，先计算出旅行商问题所需要的时间（包括路程时间和巡检耗时）。对于只有26个城市的旅行商问题，无论是精确计算，还是近似计算都是不困难的。可以考虑使用LINGO程序（见[1]）得到精确的计算结果（见图2），其中路程耗时68分钟和检查耗时67分钟，共计135分钟。图226个点的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的求解图322号点至其余各点的最短路从图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的求解图4巡检线路的分组情况，5-TSP问题分析——问题1的求解下面给出具体的巡视路线和巡视时间：•第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的求解表3第1组巡视的时间表（部分）问题分析——问题1的求解表4第2组巡视的时间表（部分）问题分析——问题1的求解表5第3组巡视的时间表（部分）问题分析——问题1的求解表6第4组巡视的时间表（部分）问题分析——问题1的求解表7第5组巡视的时间表（部分）问题分析——问题1的求解3.问题2的求解问题2——休息时间3.1休息时间为了简化问题，先不用考虑“每巡视2小时左右休息大约5到10分钟”这一要求。因为在问题1的求解过程中，5名工人在巡视过程中，多次出现5分钟的空余时间，这些空余时间可作休息时间。在问题1的讨论中，每班需要5名工人，考虑两次进餐时间（1小时），就需要增加5小时，如果再考虑进餐的衔接时间，需要增加的时间还不止5小时，所以仅依赖于原来的5名工人而挤出进餐时间几乎是不可能的。因此，需要增加1名工人让他在其他工人进餐时，完成巡视工作。3.2进餐时间排班的方法是：•原来的排班时间不变；•5名工人的进餐时间安排在11时至13时之间，和17时至19时之间；•进餐时间为35分钟（最小的时间间隔），进餐时的巡视工作由第6名（机动）工人完成；•第6名（机动）工人的进餐时间可安排在他不替班的非工作时间。表8至表12给出了部分排班的时间表（白班和中班），图中的黄色部分是可用于吃饭的时间。第6名（机动）工人的巡视时间表，以及替换组的情况如表13所示。问题2——进餐时间表8第1组巡视的时间表（部分，包含进餐时间）问题2——进餐时间表9第2组巡视的时间表（部分，包含进餐时间）问题2——进餐时间表10第3组巡视的时间表（部分，包含进餐时间）问题2——进餐时间表11第4组巡视的时间表（部分，包含进餐时间）问题2——进餐时间表12第5组巡视的时间表（部分，包含进餐时间）问题2——进餐时间表13第6组（机动）的巡视时间表问题2——进餐时间4.问题3的求解4.1上班时间问题3是考虑错时上班能否更省人力。由前面的分析（巡视人员的下限和问题1）,知道人员的下限是每班4人，而固定时间上班则需要每班5人。那么，是否能省下这1个人成为问题的关键。如果能省，应在哪个地方省；如果不能省，这个问题也就没有讨论的必要了。每个点的检查时间（共计67分钟）肯定是不能省，因此，要省也只能省下巡视中所花的路程时间。巡视全部点（26个点）的最短路程这恰好是一个旅行商问题，由前面的计算已知，这个时间是68分钟。问题3——上班时间那么巡视全部点的最短时间是135分钟。而题目要求，要在规定的时间间隔（最短为35分钟）内完成各点的巡视。这样，只能换一种排班方法，让每名巡视工人完成一轮（26个点）的巡视，而每名工人的上班时间向后错35分钟，即在前一位工人开始巡视的35分钟之后，再安排另一名工人巡视。对于巡视间隔要求大于35分钟的点，可以采用下面的方法处理：无论哪一个点，一律在35分钟巡视一次，这样肯定满足题目的要求；在满足巡视时间间隔要求的情况下，可以不巡视，但要在相应点处休息，休息的时间就是该点的巡视需要的时间。问题3——上班时间因此，得到如下的排班方法：第1名工人在8:00开始巡视（上班或换班），第2名工人则在8:35开始巡视，第3名是9:10，第4名是9:45。而每位工人都走最优的旅行商路线。注意到，每名巡视工人的间隔时间是35分钟，4名工人的间隔时间是140分钟，而一次26个点的旅行商问题的用时是135分钟。如果第1名工人在第一轮巡视后，休息5分钟，那么他要在10:20开始第二轮的巡视，与第一轮巡视的第4名工人的巡视时间间隔正好相差35分钟。第2名工人第二轮巡视的开始时间是10:55，与第1名工人相差35分钟，以此类推。由上述推导可知，4名工人足够满足巡视的要求，同时也达到了巡视人员要求的下界，是最优的。问题3——上班时间表14错时上班的时间表（部分）问题3——上班时间4.2换班时间由于题目要求，上班或换班的地点只能是调度中心，也就是说，只能在完成一轮（26个点）巡视后才能换班。因此，每名工人的换班时间只能是140分钟的整数倍，选择合适的时间点，工作7个小时开始换班。例如，第一班工作的4名工人上班的时间分别是8:00、8:35、9:10和9:45，那么，第二班的4名工人的换班时间分别是15:00、15:35、16:10和16:45，第三班的4名工人的换班时间分别是22:00、22:35、23:10和23:45。由于每天是24小时，而换班的时间是7小时，三班下来是21小时，所以每天的换班时间比前一天提前3小时。问题3——换班时间也就是说，第一班的4名工人在第二天的换班时间分别是5:00、5:35、6:10和6:45；第二班的4名工人在第二天的换班时间分别是12:00、12:35、13:10和13:45；第三班的4名工人在第二天的换班时间分别是19:00、19:35、20:10和20:45。以后的各天以此类推，每天提早3个小时换班。一周7天，有7个24小时，恰好有8个21小时，所以这种换班方案一周重复一次。具体换班方案如表15所示。4.3中间休息与问题2相同，这里不用考虑每2个小时左右休息5分钟的问题，因为这里面有太多的休息时间。例如，一轮巡视后，可休息5分钟。问题3——换班时间表15错时上班的换班时间表问题3——中间休息4.4进餐时间考虑进餐时间会使排班麻烦一些。首先由于进餐时间增加了4个小时，所以，不可能在一个班内由4名工人完成。与问题2一样，需要增加1名机动工人，顶替工人吃饭时的巡视。由于题目要求，换班只能在22号点完成，也就是说，吃饭的换班时间也只能在22号点完成，也就是在完成某一轮的巡视后，才可以考虑进餐。还以第一班工作时间为例，考虑进餐时间的安排。从8:35开始工作的第2名工人，在10:50完成第一轮的巡视，如果他不进餐，将在10:55开始第二轮的巡视，这时，可以考虑让他停止工作，选择吃午饭，他的工作由机动（第5名）工人替代完成。问题3——进餐时间在30分钟后，让11:25完成第一轮巡视的第3名工人休息进餐，而第2名工人来接替他，在11:30开始工作。之后，第3名工作完成进餐后，接替12:05开始工作的第4名工人，让第4名工人吃午饭。第4名工人午饭后，在12:40接替第1名工人的工作，第1名工人开始吃午饭。第1名工人在午饭后就不工作了，需要等到下午