《2017全国大学生数学建模竞赛---D题解析课件》由会员分享，可在线阅读，更多相关《2017全国大学生数学建模竞赛---D题解析课件（47页珍藏版）》请在金锄头文库上搜索。
1、巡检线路的排班,2017年D题讲评,主讲人：北京工业大学 薛毅 Email: ,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, VRP
4、TW）。,如果这样考虑问题，这个问题将变得非常复杂。事实上，这个问题并没有这么复杂，因为它只有26个需要巡视的点，如果每个巡视点安排一个人的话，一个班至多是26个人。当然，没有那糟糕，如果一个人能巡视35个点的话，一个班也就是 69 个人。因此，只需要启发式算法就可能得到问题的计算结果。,问题分析巡检人员下限估计,2.1 巡检人员下限估计,为估计巡检人员数量的下限，先计算出旅行商问题所需要的时间（包括路程时间和巡检耗时）。对于只有26个城市的旅行商问题，无论是精确计算，还是近似计算都是不困难的。,可以考虑使用LINGO程序（见1）得到精确的计算结果（见图2），其中路程耗时68分钟和检查耗时67
5、分钟，共计135分钟。,图2 26个点的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.pat
7、hs()函数（见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所示。 这种分组方式是为了满足题目的要求： 在规定的巡视时间间隔内完成巡视； 每位工人的工作量尽量平衡，巡视时间即不能过长，也不能过短。,问题分析 问题
8、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号点）的巡视
9、，周期长度是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分钟的空
10、余时间，这些空余时间可作休息时间。,在问题1的讨论中，每班需要5名工人，考虑两次进餐时间（1小时），就需要增加5小时，如果再考虑进餐的衔接时间，需要增加的时间还不止5小时，所以仅依赖于原来的5名工人而挤出进餐时间几乎是不可能的。 因此，需要增加1名工人让他在其他工人进餐时，完成巡视工作。,3.2 进餐时间,排班的方法是： 原来的排班时间不变； 5名工人的进餐时间安排在11时至13时之间，和17时至19时之间； 进餐时间为35分钟（最小的时间间隔），进餐时的巡视工作由第6名（机动）工人完成； 第6名（机动）工人的进餐时间可安排在他不替班的非工作时间。 表8至表12给出了部分排班的时间表（白班和中
11、班），图中的黄色部分是可用于吃饭的时间。 第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是考虑错时上班能否更省人力。,由前面的分析（
12、巡视人员的下限和问题1）, 知道人员的下限是每班4人，而固定时间上班则需要每班5人。那么，是否能省下这1个人成为问题 的关键。,如果能省，应在哪个地方省；如果不能省，这个问题也就没有讨论的必要了。 每个点的检查时间（共计67分钟）肯定是不能省，因此，要省也只能省下巡视中所花的路程时间。 巡视全部点（26个点）的最短路程这恰好是一个旅行商问题，由前面的计算已知，这个时间是68分钟。,问题3 上班时间,那么巡视全部点的最短时间是135分钟。而题目要求，要在规定的时间间隔（最短为35分钟）内完成各点的巡视。 这样，只能换一种排班方法，让每名巡视工人完成一轮（26个点）的巡视，而每名工人的上班时间向后
13、错35分钟，即在前一位工人开始巡视的35分钟之后，再安排另一名工人巡视。,对于巡视间隔要求大于35分钟的点，可以采用下面的方法处理： 无论哪一个点，一律在35分钟巡视一次，这样肯定满足题目的要求； 在满足巡视时间间隔要求的情况下，可以不巡视，但要在相应点处休息，休息的时间就是该点的巡视需要的时间。,问题3 上班时间,因此，得到如下的排班方法：第1名工人在8:00开始巡视（上班或换班），第2名工人则在8:35开始巡视，第3名是9:10，第4名是9:45。而每位工人都走最优的旅行商路线。 注意到，每名巡视工人的间隔时间是35分钟，4名工人的间隔时间是140分钟，而一次26个点的旅行商问题的用时是1
14、35分钟。,如果第1名工人在第一轮巡视后，休息5分钟，那么他要在10:20开始第二轮的巡视，与第一轮巡视的第4名工人的巡视时间间隔正好相差35分钟。第2名工人第二轮巡视的开始时间是10:55，与第1名工人相差35分钟，以此类推。 由上述推导可知，4名工人足够满足巡视的要求，同时也达到了巡视人员要求的下界，是最优的。,问题3 上班时间,表14 错时上班的时间表（部分）,问题3 上班时间,4.2 换班时间,由于题目要求，上班或换班的地点只能是调度中心，也就是说，只能在完成一轮（26个点）巡视后才能换班。因此，每名工人的换班时间只能是140分钟的整数倍，选择合适的时间点，工作7个小时开始换班。 例如
15、，第一班工作的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、
16、 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 进餐
