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

巡检线路的排班;巡检线路的排班——2017年D题讲评;1. 题目 —— 巡检线路的排班;表2 Excel表中的连通关系;问题1.如果采用固定上班时间，不考虑巡检人员的休息时间，采用每天三班倒，每班工作8小时左右，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。;2.问题分析与模型建立;问题分析——巡检人员下限估计; 由于巡视点两次巡视的最小间隔时间是35分钟，且135/35=3.86，因此，一个班至少需要4名工人。从图2 （TSP图形）和题目要求（从22号点开始巡视）来看，只用4名工人巡视，肯定是不够的，应考虑增加1名工人，一个班使用5名工人。 从上述计算过程来看，实际上，并不需要精确求解TSP，只需近似计算，估计出一个下界即可。; 现知道每个班需要5名工人，所以需要将巡视点划分成5个区域，每个区域最多包含6个点，最少也要有4个点，其目的是保证每个区域的工作量（巡视时间）尽量平衡。 由于题目要求，每位工人均从22号点开始巡视，因此，距22号点较近的点则多安排一些，而距22号较远的;问题分析 —— 问题1的求解; 从图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号点编为第五组。;图4 巡检线路的分组情况，5-TSP;下面给出具体的巡视路线和巡视时间： 第1组（22、20、19、2、4和21号点）的巡视周期是29分钟，而21号点的周期间隔是80分钟，可以两个35分钟巡视一次，所以此时巡视同期是27分钟。 第2组（23、24、9、8、17和25号点）的巡视，最长周期是32分钟、最短周期28分钟（17号点和25号点的时间间隔为分别为480分钟和;表3 第1组巡视的时间表（部分）;表4 第2组巡视的时间表（部分）;表5 第3组巡视的时间表（部分）;表6 第4组巡视的时间表（部分）;表7 第5组巡视的时间表（部分）;3.问题2的求解;排班的方法是： 原来的排班时间不变； 5名工人的进餐时间安排在11时至13时之间，和17时至19时之间； 进餐时间为35分钟（最小的时间间隔），进餐时的巡视工作由第6名（机动）工人完成； 第6名（机动）工人的进餐时间可安排在他不替班的非工作时间。 表8至表12给出了部分排班的时间表（白班和中班），图中的黄色部分是可用于吃饭的时间。 第6名（机动）工人的巡视时间表，以及替换组的情况如表13所示。;表8 第1组巡视的时间表（部分，包含进餐时间）;表9 第2组巡视的时间表（部分，包含进餐时间）;表10 第3组巡视的时间表（部分，包含进餐时间）;表11 第4组巡视的时间表（部分，包含进餐时间）;表12 第5组巡视的时间表（部分，包含进餐时间）;表13 第6组（机动）的巡视时间表;4.问题3的求解; 那么巡视全部点的最短时间是135分钟。而题目要求，要在规定的时间间隔（最短为35分钟）内完成各点的巡视。 这样，只能换一种排班方法，让每名巡视工人完成一轮（26个点）的巡视，而每名工人的上班时间向后错35分钟，即在前一位工人开始巡视的35分钟之后，再安排另一名工人巡视。; 因此，得到如下的排班方法：第1名工人在8:00开始巡视（上班或换班），第2名工人则在8:35开始巡视，第3名是9:10，第4名是9:45。而每位工人都走最优的旅行商路线。 注意到，每名巡视工人的间隔时间是35分钟，4名工人的间隔时间是140分钟，而一次26个点的旅行商问题的用时是135分钟。;表14 错时上班的时间表（部分）;4.2 换班时间; 也就是说，第一班的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个小时换班。;表15 错时上班的换班时间表;4.4 进餐时间; 在30分钟后，让11:25完成第一轮巡视的第3名工人休息进餐，而第2名工人来接替他，在11:30开始工作。 之后，第3名工作完成进餐后，接替12:05开始工作的第4名工人，让第4名工人吃午饭。 第4名工人午饭后，在12:40接替第1名工人的工作，第1名工人开始吃午饭。; 20:15，第4位工人开始工作，接替第5位（机动）工人的工作。而机动工人则下班休息（这时不用考