资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2017/11/13,#,巡检,线路的,排班,2021年D题讲评,主讲人：北京工业大学 薛毅,2021全国数学建模讲评会,云南、昆明,2021年11月25日,巡检线路的排班2021年D题讲评,题目,问题,分析及问题,1,的求解,问题,2,的求解,问题,3,的求解,阅卷,情况简述,1.,题目,巡检,线路的排班,题目,巡检,线路的排班,某化工厂有 26 个点需要进展巡检以保证正常生产，各个点的巡检周期、巡检耗时、两点之间的连通关系及行走所需时间在附件中给出。,每个点每次巡检需要一名工人，巡检工人的巡检起始地点在巡检调度中心XJ0022，工人可以按固定时间上班，也可以错时上班，在调度中心得到巡检任务后开场巡检。现需要建立模型来安排巡检人数和巡检路线，使得所有点都能按要求完成巡检，并且消耗的人力资源尽可能少，同时还应考虑每名工人在一时间段内如一周或一月等的工作量尽量平衡。,表1 Excel表中的根本信息,表,2,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,号点至其余各点的最短路,从图,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名工人在午饭后就不工作了，需要等到下午18:30分，接替第2名工人的工作，直到这个班工作完毕。在这中间也不考虑他吃晚饭的时间，因为他可以在18:30以前吃完晚饭。,此时(18:30)，第2名工人在吃晚饭，饭后(19:05)他接替第3位工人的工作。,19:05，第3名工人在吃晚饭，19:40接替第4位工人的工作。,问题,3,进餐时间,20:15，第4位工人开场工作，接替第5位机动工人的工作。而机开工人那么下班休息这时不用考虑他是否吃晚饭，因为到第二天的10:50才接替第1位工人的工作，让第1位工人吃午饭。,这个过程较为复杂，详细排班请见错时上班的换班时间表, 表16显示了Excel表中排班和换班的局部表格。,表,16,增加吃饭时间的排班表,问题,3,进餐时间,续表,16-2,增加吃饭时间的排班表,续表,16-1,增加吃饭时间的排班表,问题,3,进餐时间,5.,阅卷情况简述,阅卷情况,固定上班时间,本人参加了北京地区和全国的,D,题阅卷，下面就阅卷中遇到的问题谈一谈本人一点感受。,5.1,固定上班时间,问题1和问题2要求：固定时间上班，并且由巡检调度中心22号点开场巡检。,在通常情况下，三班倒的工作时间分别是8:00 16:00，16:00 24:00和0:00 8:00。,这一点绝大多数的队都注意到了，所以根本上都采用8点、下午4点和凌晨0点开场上班的模式。当然，如果你认为有必要，采用其他时间开场上班也是正确的，只要是固定时间上班就可以。,但这个固定上班时间，是每个班组的固定上班时间，不是每个人的固定上班时间。,例如，一个班有5个人 (5条巡视线路)，那么要求这5个人同时上班。这也是为什么要求大家一定从22号点开场的原因，大家需要集中一下如布置工作或其他要求。,有很多队理解成每名工人固定时,间上班，而上班时间是不同的，这样理解问题，巡检工作从22号点开场就无意义了，因为可以让22号点、23号、1号点、26号点和11号点都是从8点开场工作，而这些点开场上班的时间分别为8:00、7:59、7:52、7:50和7:45，这种方法相当于去掉从22号点开场的要求，降低了题目的难度。事实上，这种做法只需要4个人就够了。,阅卷情况,固定上班时间,还有一个小问题：每个班的巡检工作是否能在8小时内完毕并不要求一定在8小时内回到22号点，这个问题根本上没有学生讨论，但它应该是问题潜在的要求，因为在交接班时，应该简短地说明一下本班的巡检情况。,当然，并不需要见面交流，用一下现代通讯工具是可以的。,题目明确要求，给出巡检人员的巡检线路和巡检的时间表，但很多队只给出巡检线路图，并没有给出具体的巡检点的时间表。,由于没有巡检点的排班时间表，因此无法判断该队的结果是否正确，是否满足巡检要求。本质上没有完成题目要求，分数上也会打折扣的。,5.2,巡检线路与时间表,阅卷情况,巡检时间表,5.3,休息时间与进餐时间,问题,2,要求：每巡检,2,小时左右需要休息一次，休息时间大约是,5,到,10,分钟。在中午,12,时和下午,6,时左右需要进餐一次，进餐时间为,30,分钟。,实际上,如果每名巡检人员的排班时间较均匀，这里并不需要真的考虑休息时间的安排，因为在巡检中有大量的,5,分钟可以作为休息时间。,进餐时间不是固定的，否那么，大家都在中午12时进餐，这样就需要再派其他的工人来顶替进餐时的空缺，需要的人数是原来的2倍，这显然过于浪费人力。,当进餐时间不固定时，只需要增加一名工人就够了，这名工人的工作是接替中午和晚上需要进餐的工人，这里的重点是具体的替班时间表。,阅卷情况,休息与进餐时间,5.4,错时上班的讨论,问题3是讨论错时上班是否更节省人力，如果不能更节省人力，这一问也就没有讨论的必要。有的队，讨论了半天还是不能更省人力。可以猜测，该队应该没有完成题目的要求。,实际上，更省人力是这个问题的重点，需要分析在哪些地方可以更省人力。,巡检时间肯定是不能省的，要省也只能是巡检路线，尽量少走重复路线。这自然会想到旅行商问题。但我,们发现，很多专科学校没有培训过图论方面的相关知识。,经过验算,旅行商问题的解是,135,分钟，巡检点的最小间隔时间是,35,分钟，因此，需要,4,名工人就可以能完成工作。,阅卷情况,错时上班时间,排班方法有点像列车时刻表，每隔35分钟发一趟车。,这种处理方法大多数队已经注意到了，但很多队没有给出具体的时间表。也许学生已没有足够的答题时间了，也许根本就不知道如何计算。,问题3的难度是增加进餐时间，大多数队根本上都没有给出这一问题的讨论。,我们很多的队希望给出一个“高大上的模型，然后再用软件求解(如LINGO)，但由于“高大上的模型过于复杂，无法求解或求解困难，这只能再借助于手工求解。,这样，这个模型实际上是没有用的，不如将精力放在问题的分析上，如采用“接地气的启发式算法 。,5.5,关于模型,阅卷情况,错时上班时间,5.6,能否更省人力,有的队想出了更省人力的方法，例如，将进餐时间安排在工作时间之外。例如，对于固定上班的工人来说，将三班的工作时间安排为,3:3011:30,、,11:3019:30,、,19:303:30 (,次日,),。,第一班的工人下班后进餐，第二班的工人上班前吃午饭下班后吃晚饭，,第三班的工人在上班前吃晚饭，这样就不用考虑他们进餐时，不需要另外的人员替换他们，从而更省人力。,有的队确实是这样做的只是时间略有不同，对于题目要求来说，这种方法无可厚非，但在实际操作中会产生新的问题是否要吃早饭。,如果能将吃早饭的问题解决，这种结果无疑是最好的。,阅卷情况,更省人力,6.,结论,这个问题看似复杂，如使用TSP模型、VRP 模型, 甚至是 m-TSP 模型或VRPTW 模型，但由于需要处理的点数较少，可以运用最短路算法，结合启发式方法得到问题的计算结果：,固定上班时间，每班需要5人，一天共需要15人；,考虑进餐时间，增加一名机开工人作为替补，一天需要16人；,如果采用错时上班，每班需要4人，一天共12人；,如再考虑进餐时间，再增加一人，每天需要13人。,参考文献,谢,谢,!,
展开阅读全文