2017全国大学生数学建模竞赛-D题解析.ppt

《2017全国大学生数学建模竞赛-D题解析.ppt》由会员分享，可在线阅读，更多相关《2017全国大学生数学建模竞赛-D题解析.ppt（47页珍藏版）》请在三一办公上搜索。

1、巡检线路的排班,2017年D题讲评,主讲人：北京工业大学 薛毅,2017全国数学建模讲评会云南、昆明2017年11月25日,巡检线路的排班2017年D题讲评,题目,问题分析及问题1的求解,问题2的求解,问题3的求解,阅卷情况简述,1.题目 巡检线路的排班,题目 巡检线路的排班,某化工厂有 26 个点需要进行巡检以保证正常生产，各个点的巡检周期、巡检耗时、两点之间的连通关系及行走所需时间在附件中给出。每个点每次巡检需要一名工人，巡检工人的巡检起始地点在巡检调度中心（XJ0022），工人可以按固定时间上班，也可以错时上班，在调度中心得到巡检任务后开始巡检。现需要建立模型来安排巡检人数和巡检路线，使

2、得所有点都能按要求完成巡检，并且耗费的人力资源尽可能少，同时还应考虑每名工人在一时间段内（如一周或一月等）的工作量尽量平衡。,表1 Excel表中的基本信息,表2 Excel表中的连通关系,图1 Excel表中的连通图,题目 巡检线路的排班,问题1.如果采用固定上班时间，不考虑巡检人员的休息时间，采用每天三班倒，每班工作8小时左右，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。,问题2.如果巡检人员每巡检 2 小时左右需要休息一次，休息时间大约是 5 到 10 分钟，在中午12 时和下午 6 时左右需要进餐一次，每次进餐时间为 30 分钟，仍采用每天三班倒，每班需要

3、多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。,题目 巡检线路的排班,问题3.如果采用错时上班，重新讨论问题 1 和问题 2，试分析错时上班是否更节省人力。,2.问题分析与模型建立,问题分析与模型建立,这个问题说的复杂一点是旅行商问题（Traveling Salesman Problem,TSP），或者是多旅行商问题（m-TSP），更严格的说，是车辆路径问题（Vehicle Routing Problem,VRP），而且还是带有时间窗口的车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）。,如果这样考虑问题，这个问

4、题将变得非常复杂。事实上，这个问题并没有这么复杂，因为它只有26个需要巡视的点，如果每个巡视点安排一个人的话，一个班至多是26个人。当然，没有那糟糕，如果一个人能巡视35个点的话，一个班也就是 69 个人。因此，只需要启发式算法就可能得到问题的计算结果。,问题分析巡检人员下限估计,2.1 巡检人员下限估计,为估计巡检人员数量的下限，先计算出旅行商问题所需要的时间（包括路程时间和巡检耗时）。对于只有26个城市的旅行商问题，无论是精确计算，还是近似计算都是不困难的。,可以考虑使用LINGO程序（见1）得到精确的计算结果（见图2），其中路程耗时68分钟和检查耗时67分钟，共计135分钟。,图2 26

5、个点的TSP线路图,由于巡视点两次巡视的最小间隔时间是35分钟，且135/35=3.86，因此，一个班至少需要4名工人。从图2（TSP图形）和题目要求（从22号点开始巡视）来看，只用4名工人巡视，肯定是不够的，应考虑增加1名工人，一个班使用5名工人。从上述计算过程来看，实际上，并不需要精确求解TSP，只需近似计算，估计出一个下界即可。,例如，可以采用手工计算，也可以采用某些启发式算法，如最近领域法、最近插入法、最远插入法、最便宜插入法、任意插入法和交换两边改进方法等。如果不打算自己手工编程，可以使用现成的软件，例如，R软件中的TSP函数（见2）就可以很好地解决这些问题，提供不同的参数，选择你喜

6、欢的算法。,问题分析巡检人员下限估计,现知道每个班需要5名工人，所以需要将巡视点划分成5个区域，每个区域最多包含6个点，最少也要有4个点，其目的是保证每个区域的工作量（巡视时间）尽量平衡。由于题目要求，每位工人均从22号点开始巡视，因此，距22号点较近的点则多安排一些，而距22号较远的,2.2 问题1的求解,点则少安排一些。为了完成这种需求的安排，需要计算从22号点至其余各点的最短路，这项工作可用Dijkstra（戴克斯特拉）算法完成。当然，也不需要自己编程计算，直接调用R软件的shortest.paths()函数和get.shortest.paths()函数（见2）就可完成此问题，所绘图形如

7、图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,问题分析 问题

8、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号点）的巡视，周期

9、长度是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名工人，考

10、虑两次进餐时间（1小时），就需要增加5小时，如果再考虑进餐的衔接时间，需要增加的时间还不止5小时，所以仅依赖于原来的5名工人而挤出进餐时间几乎是不可能的。因此，需要增加1名工人让他在其他工人进餐时，完成巡视工作。,3.2 进餐时间,排班的方法是：原来的排班时间不变；5名工人的进餐时间安排在11时至13时之间，和17时至19时之间；进餐时间为35分钟（最小的时间间隔），进餐时的巡视工作由第6名（机动）工人完成；第6名（机动）工人的进餐时间可安排在他不替班的非工作时间。表8至表12给出了部分排班的时间表（白班和中班），图中的黄色部分是可用于吃饭的时间。第6名（机动）工人的巡视时间表，以及替换组的情

11、况如表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人。那么，

12、是否能省下这1个人成为问题的关键。,如果能省，应在哪个地方省；如果不能省，这个问题也就没有讨论的必要了。每个点的检查时间（共计67分钟）肯定是不能省，因此，要省也只能省下巡视中所花的路程时间。巡视全部点（26个点）的最短路程这恰好是一个旅行商问题，由前面的计算已知，这个时间是68分钟。,问题3 上班时间,那么巡视全部点的最短时间是135分钟。而题目要求，要在规定的时间间隔（最短为35分钟）内完成各点的巡视。这样，只能换一种排班方法，让每名巡视工人完成一轮（26个点）的巡视，而每名工人的上班时间向后错35分钟，即在前一位工人开始巡视的35分钟之后，再安排另一名工人巡视。,对于巡视间隔要求大于35

13、分钟的点，可以采用下面的方法处理：无论哪一个点，一律在35分钟巡视一次，这样肯定满足题目的要求；在满足巡视时间间隔要求的情况下，可以不巡视，但要在相应点处休息，休息的时间就是该点的巡视需要的时间。,问题3 上班时间,因此，得到如下的排班方法：第1名工人在8:00开始巡视（上班或换班），第2名工人则在8:35开始巡视，第3名是9:10，第4名是9:45。而每位工人都走最优的旅行商路线。注意到，每名巡视工人的间隔时间是35分钟，4名工人的间隔时间是140分钟，而一次26个点的旅行商问题的用时是135分钟。,如果第1名工人在第一轮巡视后，休息5分钟，那么他要在10:20开始第二轮的巡视，与第一轮巡视

14、的第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、时间分别是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小时，恰好有

16、8个21小时，所以这种换班方案一周重复一次。具体换班方案如表15所示。,4.3 中间休息,与问题2相同，这里不用考虑每2个小时左右休息5分钟的问题，因为这里面有太多的休息时间。例如，一轮巡视后，可休息5分钟。,问题3 换班时间,表15 错时上班的换班时间表,问题3 中间休息,4.4 进餐时间,考虑进餐时间会使排班麻烦一些。首先由于进餐时间增加了4个小时，所以，不可能在一个班内由4名工人完成。与问题2一样，需要增加1名机动工人，顶替工人吃饭时的巡视。由于题目要求，换班只能在22号点完成，也就是说，吃饭的换班时间也只能在22号点完成，也就是在完成,某一轮的巡视后，才可以考虑进餐。还以第一班工作时间

17、为例，考虑进餐时间的安排。从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、中间也不考虑他吃晚饭的时间，因为他可以在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 增加吃饭时间的排班表,续表

19、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点开始上班的模式。当然，如果你认为有必要，采用其他时间开始上班也是正确的，只要是固定时间上班就可以。,但这个固定上班时间，是每个班组的固定上班时间，不是每个人的

20、固定上班时间。例如，一个班有5个人(5条巡视线路)，则要求这5个人同时上班。这也是为什么要求大家一定从22号点开始的原因，大家需要集中一下（如布置工作或其他要求）。有很多队理解成每名工人固定时,间上班，而上班时间是不同的，这样理解问题，巡检工作从22号点开始就无意义了，因为可以让22号点、23号、1号点、26号点和11号点都是从8点开始工作，而这些点开始上班的时间分别为8:00、7:59、7:52、7:50和7:45，这种方法相当于去掉从22号点开始的要求，降低了题目的难度。事实上，这种做法只需要4个人就够了。,阅卷情况 固定上班时间,还有一个小问题：每个班的巡检工作是否能在8小时内结束（并不

21、要求一定在8小时内回到22号点），这个问题基本上没有学生讨论，但它应该是问题潜在的要求，因为在交接班时，应该简短地说明一下本班的巡检情况。当然，并不需要见面交流，用一下现代通讯工具是可以的。,题目明确要求，给出巡检人员的巡检线路和巡检的时间表，但很多队只给出巡检线路图，并没有给出具体的巡检点的时间表。由于没有巡检点的排班时间表，因此无法判断该队的结果是否正确，是否满足巡检要求。本质上没有完成题目要求，分数上也会打折扣的。,5.2 巡检线路与时间表,阅卷情况 巡检时间表,5.3 休息时间与进餐时间,问题2要求：每巡检2小时左右需要休息一次，休息时间大约是5到10分钟。在中午12时和下午6时左右需

22、要进餐一次，进餐时间为30分钟。实际上,如果每名巡检人员的排班时间较均匀，这里并不需要真的考虑休息时间的安排，因为在巡检中有大量的5分钟可以作为休息时间。,进餐时间不是固定的，否则，大家都在中午12时进餐，这样就需要再派其他的工人来顶替进餐时的空缺，需要的人数是原来的2倍，这显然过于浪费人力。当进餐时间不固定时，只需要增加一名工人就够了，这名工人的工作是接替中午和晚上需要进餐的工人，这里的重点是具体的替班时间表。,阅卷情况 休息与进餐时间,5.4 错时上班的讨论,问题3是讨论错时上班是否更节省人力，如果不能更节省人力，这一问也就没有讨论的必要。有的队，讨论了半天还是不能更省人力。可以猜想，该队

23、应该没有完成题目的要求。实际上，更省人力是这个问题的重点，需要分析在哪些地方可以更省人力。,巡检时间肯定是不能省的，要省也只能是巡检路线，尽量少走重复路线。这自然会想到旅行商问题。但我们发现，很多专科学校没有培训过图论方面的相关知识。经过验算,旅行商问题的解是135分钟，巡检点的最小间隔时间是35分钟，因此，需要4名工人就可以能完成工作。,阅卷情况 错时上班时间,排班方法有点像列车时刻表，每隔35分钟发一趟车。这种处理方法大多数队已经注意到了，但很多队没有给出具体的时间表。也许学生已没有足够的答题时间了，也许根本就不知道如何计算。问题3的难度是增加进餐时间，大多数队基本上都没有给出这一问题的讨

24、论。,我们很多的队希望给出一个“高大上”的模型，然后再用软件求解(如LINGO)，但由于“高大上”的模型过于复杂，无法求解（或求解困难），这只能再借助于手工求解。这样，这个模型实际上是没有用的，不如将精力放在问题的分析上，如采用“接地气”的启发式算法。,5.5 关于模型,阅卷情况 错时上班时间,5.6 能否更省人力,有的队想出了更省人力的方法，例如，将进餐时间安排在工作时间之外。例如，对于固定上班的工人来说，将三班的工作时间安排为3:3011:30、11:3019:30、19:303:30(次日)。第一班的工人下班后进餐，第二班的工人上班前吃午饭下班后吃晚饭，,第三班的工人在上班前吃晚饭，这样

25、就不用考虑他们进餐时，不需要另外的人员替换他们，从而更省人力。有的队确实是这样做的（只是时间略有不同），对于题目要求来说，这种方法无可厚非，但在实际操作中会产生新的问题是否要吃早饭。如果能将吃早饭的问题解决，这种结果无疑是最好的。,阅卷情况 更省人力,6.结论,这个问题看似复杂，如使用TSP模型、VRP 模型,甚至是 m-TSP 模型或VRPTW 模型，但由于需要处理的点数较少，可以运用最短路算法，结合启发式方法得到问题的计算结果：固定上班时间，每班需要5人，一天共需要15人；考虑进餐时间，增加一名机动工人作为替补，一天需要16人；如果采用错时上班，每班需要4人，一天共12人；如再考虑进餐时间，再增加一人，每天需要13人。,参考文献,1 谢金星，薛毅优化建模与LINDO/LINGO软件北京：清华大学出版社，2005.72薛毅数学建模基于北京：机械工业出版社，2017.7,谢 谢!,