资源描述
巡巡检线路的排班路的排班20212021年年D D题讲评题讲评主讲人：北京工业大学主讲人：北京工业大学 薛毅薛毅 20212021全国数学建模讲评会全国数学建模讲评会云南、昆明云南、昆明20212021年年1111月月2525日日巡检线路的排班巡检线路的排班2021年年D题讲评题讲评 题目目 问题分析及分析及问题1的求解的求解 问题2的求解的求解 问题3的求解的求解 阅卷情况卷情况简述述1.题目 巡检线路的排班题目题目 巡检线路的排班巡检线路的排班 某化工厂有某化工厂有 26 26 个点需要进行巡检以保证正常生个点需要进行巡检以保证正常生产，各个点的巡检周期、巡检耗时、两点之间的连通产，各个点的巡检周期、巡检耗时、两点之间的连通关系及行走所需时间在附件中给出。关系及行走所需时间在附件中给出。每个点每次巡检需要一名工人，巡检工人的每个点每次巡检需要一名工人，巡检工人的巡检起始地点在巡检调度中心巡检起始地点在巡检调度中心XJ0022XJ0022，工人可以，工人可以按固定时间上班，也可以错时上班，在调度中心得到按固定时间上班，也可以错时上班，在调度中心得到巡检任务后开始巡检。现需要建立模型来安排巡检人巡检任务后开始巡检。现需要建立模型来安排巡检人数和巡检路线，使得所有点都能按要求完成巡检，并数和巡检路线，使得所有点都能按要求完成巡检，并且消耗的人力资源尽可能少，同时还应考虑每名工人且消耗的人力资源尽可能少，同时还应考虑每名工人在一时间段内如一周或一月等的工作量尽量平衡。在一时间段内如一周或一月等的工作量尽量平衡。表表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个人。当然，个人。当然，没有那糟糕，如果一个人能巡视没有那糟糕，如果一个人能巡视35个点的话，一个班也就是个点的话，一个班也就是 69 个人。个人。因此，只需要启发式算法就可能得到因此，只需要启发式算法就可能得到问题的计算结果问题的计算结果。问题分析问题分析巡检人员下限估计巡检人员下限估计2.1 巡检人员下限估计 为估计巡检人员数量的下限，先计算出旅行商问题所需要的时间包括为估计巡检人员数量的下限，先计算出旅行商问题所需要的时间包括路程时间和巡检耗时。对于只有路程时间和巡检耗时。对于只有2626个城市的旅行商问题，无论是精确计算，个城市的旅行商问题，无论是精确计算，还是近似计算都是不困难的。还是近似计算都是不困难的。可以考虑使用可以考虑使用LINGOLINGO程程序见序见11得到精确的计得到精确的计算结果见图算结果见图2 2，其中路，其中路程耗时程耗时6868分钟和检查耗时分钟和检查耗时6767分钟，共计分钟，共计135135分钟。分钟。图图2 26个点的个点的TSP线路图线路图 由于巡视点两次巡视的最小间隔由于巡视点两次巡视的最小间隔时间是时间是3535分钟，且分钟，且135/35=3.86135/35=3.86，因，因此，一个班至少需要此，一个班至少需要4 4名工人。从图名工人。从图2 2 TSPTSP图形和题目要求从图形和题目要求从2222号点号点开始巡视来看，只用开始巡视来看，只用4 4名工人巡视，名工人巡视，肯定是不够的，应考虑增加肯定是不够的，应考虑增加1 1名工人，名工人，一个班使用一个班使用5 5名工人。名工人。从上述计算过程来看，实际上，从上述计算过程来看，实际上，并不需要精确求解并不需要精确求解TSPTSP，只需近似计，只需近似计算，估计出一个下界即可。算，估计出一个下界即可。例如，可以采用手工计算，也可例如，可以采用手工计算，也可以采用某些启发式算法，如最近领域以采用某些启发式算法，如最近领域法、最近插入法、最远插入法、最廉法、最近插入法、最远插入法、最廉价插入法、任意插入法和交换两边改价插入法、任意插入法和交换两边改进方法等。进方法等。如果不打算自己手工编程，如果不打算自己手工编程，可以使用现成的软件，例如，可以使用现成的软件，例如，R R软件软件中的中的TSPTSP函数见函数见22就可以很好地就可以很好地解决这些问题，提供不同的参数，选解决这些问题，提供不同的参数，选择你喜欢的算法。择你喜欢的算法。问题分析问题分析巡检人员下限估计巡检人员下限估计 现知道每个班需要现知道每个班需要5 5名工人，所名工人，所以需要将巡视点划分成以需要将巡视点划分成5 5个区域，每个区域，每个区域最多包含个区域最多包含6 6个点，最少也要有个点，最少也要有4 4个点，其目的是保证每个区域的工作个点，其目的是保证每个区域的工作量巡视时间尽量平衡。量巡视时间尽量平衡。由于题目要求，每位工人均从由于题目要求，每位工人均从2222号点开始巡视，因此，距号点开始巡视，因此，距2222号点较近号点较近的点那么多安排一些，而距的点那么多安排一些，而距2222号较远号较远的的2.2 问题1的求解点那么少安排一些。为了完成这种需点那么少安排一些。为了完成这种需求的安排，需要计算从求的安排，需要计算从2222号点至其余号点至其余各点的最短路，这项工作可用各点的最短路，这项工作可用Dijkstra Dijkstra 戴克斯特拉算法完成。戴克斯特拉算法完成。当然，也不需要自己编程计算，当然，也不需要自己编程计算，直接调用直接调用R R软件的软件的shortest.paths()shortest.paths()函数和函数和get.shortest.paths()get.shortest.paths()函数函数见见22就可完成此问题，所绘图形就可完成此问题，所绘图形如图如图3 3所示。所示。问题分析问题分析 问题问题1 1的求解的求解问题分析问题分析 问题问题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 1的求解的求解图图4 巡检线路的分组情况，巡检线路的分组情况，5-TSP问题分析问题分析 问题问题1 1的求解的求解下面给出具体的巡视路线和巡视时间：下面给出具体的巡视路线和巡视时间：第第1 1组组2222、2020、1919、2 2、4 4和和2121号点号点的巡视周期是的巡视周期是2929分钟，而分钟，而2121号点的号点的周期间隔是周期间隔是8080分钟，可以两个分钟，可以两个3535分钟分钟巡视一次，所以此时巡视同期是巡视一次，所以此时巡视同期是2727分分钟。钟。第第2 2组组2323、2424、9 9、8 8、1717和和2525号点号点的巡视，最长周期是的巡视，最长周期是3232分钟、最短分钟、最短周期周期2828分钟分钟1717号点和号点和2525号点的时间号点的时间间隔为分别为间隔为分别为480480分钟和分钟和 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 1的求解的求解表表3 第第1组巡视的时间表局部组巡视的时间表局部问题分析问题分析 问题问题1 1的求解的求解表表4 第第2组巡视的时间表局部组巡视的时间表局部问题分析问题分析 问题问题1 1的求解的求解表表5 第第3组巡视的时间表局部组巡视的时间表局部问题分析问题分析 问题问题1 1的求解的求解表表6 第第4组巡视的时间表局部组巡视的时间表局部问题分析问题分析 问题问题1 1的求解的求解表表7 第第5组巡视的时间表局部组巡视的时间表局部问题分析问题分析 问题问题1 1的求解的求解3.问题2的求解问题问题2 2 休息时间休息时间3.1 休息时间 为了简化问题，先不用考虑为了简化问题，先不用考虑“每每巡视巡视2 2小时左右休息大约小时左右休息大约5 5到到1010分钟分钟这一要求。这一要求。因为在问题因为在问题1 1的求解过程中，的求解过程中，5 5名名工人在巡视过程中，屡次出现工人在巡视过程中，屡次出现5 5分钟分钟的空余时间，这些空余时间可作休息的空余时间，这些空余时间可作休息时间。时间。在问题在问题1的讨论中，每班需要的讨论中，每班需要5名名工人，考虑两次进餐时间工人，考虑两次进餐时间1小时，小时，就需要增加就需要增加5小时，如果再考虑进餐小时，如果再考虑进餐的衔接时间，需要增加的时间还不止的衔接时间，需要增加的时间还不止5小时，所以仅依赖于原来的小时，所以仅依赖于原来的5名工人名工人而挤出进餐时间几乎是不可能的。而挤出进餐时间几乎是不可能的。因此，需要增加因此，需要增加1名工人让他在名工人让他在其他工人进餐时，完成巡视工作。其他工人进餐时，完成巡视工作。3.2 进餐时间排班的方法是：排班的方法是：原来的排班时间不变；原来的排班时间不变；5 5名工人的进餐时间安排在名工人的进餐时间安排在1111时至时至1313时之间，和时之间，和1717时至时至1919时之间；时之间；进餐时间为进餐时间为3535分钟最小的时间间隔，进餐时的巡视工作由第分钟最小的时间间隔，进餐时的巡视工作由第6 6名机动名机动工人完成；工人完成；第第6 6名机动工人的进餐时间可安排在他不替班的非工作时间。名机动工人的进餐时间可安排在他不替班的非工作时间。表表8 8至表至表1212给出了局部排班的时间表白班和中班，图中的黄色局部是给出了局部排班的时间表白班和中班，图中的黄色局部是可用于吃饭的时间。可用于吃饭的时间。第第6 6名机动工人的巡视时间表，以及替换组的情况如表名机动工人的巡视时间表，以及替换组的情况如表1313所示。所示。问题问题2 2 进餐时间进餐时间表表8 第第1组巡视的时间表局部，包含进餐时间组巡视的时间表局部，包含进餐时间问题问题2 2 进餐时间进餐时间表表9 第第2组巡视的时间表局部，包含进餐时间组巡视的时间表局部，包含进餐时间问题问题2 2 进餐时间进餐时间表表10 第第3组巡视的时间表局部，包含进餐时间组巡视的时间表局部，包含进餐时间问题问题2 2 进餐时间进餐时间表表11 第第4组巡视的时间表局部，包含进餐时间组巡视的时间表局部，包含进餐时间问题问题2 2 进餐时间进餐时间表表12 第第5组巡视的时间表局部，包含进餐时间组巡视的时间表局部，包含进餐时间问题问题2 2 进餐时间进餐时间表表13 第第6组机动的巡视时间表组机动的巡视时间表问题问题2 2 进餐时间进餐时间4.问题3的求解4.1 上班时间 问题问题3是考虑错时上班能否更省是考虑错时上班能否更省人力。人力。由前面的分析巡视人员的下限由前面的分析巡视人员的下限和问题和问题1 1,知道人员的下限是每班知道人员的下限是每班4 4人，而固定时间上班那么需要每班人，而固定时间上班那么需要每班5 5人。那么，是否能省下这人。那么，是否能省下这1 1个人成为个人成为问题问题的关键。的关键。如果能省，应在哪个地方省；如如果能省，应在哪个地方省；如果不能省，这个问题也就没有讨论的果不能省，这个问题也就没有讨论的必要了。必要了。每个点的检查时间共计每个点的检查时间共计6767分钟分钟肯定是不能省，因此，要省也只能肯定是不能省，因此，要省也只能省下巡视中所花的路程时间。省下巡视中所花的路程时间。巡视全部点巡视全部点2626个点的最个点的最短路程这恰好是一个旅行商问题，由短路程这恰好是一个旅行商问题，由前面的计算，这个时间是前面的计算，这个时间是6868分钟。分钟。问题问题3 3 上班时间上班时间 那么巡视全部点的最短时间是那么巡视全部点的最短时间是135135分钟。而题目要求，要在规定的分钟。而题目要求，要在规定的时间间隔最短为时间间隔最短为3535分钟内完成各分钟内完成各点的巡视。点的巡视。这样，只能换一种排班方法，让这样，只能换一种排班方法，让每名巡视工人完成一轮每名巡视工人完成一轮2626个点的个点的巡视，而每名工人的上班时间向后错巡视，而每名工人的上班时间向后错3535分钟，即在前一位工人开始巡视的分钟，即在前一位工人开始巡视的3535分钟之后，再安排另一名工人巡视。分钟之后，再安排另一名工人巡视。对于巡视间隔要求大于对于巡视间隔要求大于35分钟的分钟的点，可以采用下面的方法处理：点，可以采用下面的方法处理：l无论哪一个点，一律在无论哪一个点，一律在35分钟巡分钟巡视一次，这样肯定满足题目的要视一次，这样肯定满足题目的要求；求；l在满足巡视时间间隔要求的情况在满足巡视时间间隔要求的情况下，可以不巡视，但要在相应点下，可以不巡视，但要在相应点处休息，休息的时间就是该点的处休息，休息的时间就是该点的巡视需要的时间。巡视需要的时间。问题问题3 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 3 上班时间上班时间表表14 错时上班的时间表局部错时上班的时间表局部问题问题3 3 上班时间上班时间4.2 换班时间 由于题目要求，上班或换班的地由于题目要求，上班或换班的地点只能是调度中心，也就是说，只能点只能是调度中心，也就是说，只能在完成一轮在完成一轮2626个点巡视后才能换个点巡视后才能换班。因此，每名工人的换班时间只能班。因此，每名工人的换班时间只能是是140140分钟的整数倍，选择适宜的时分钟的整数倍，选择适宜的时间点，工作间点，工作7 7个小时开始换班。个小时开始换班。例如，第一班工作的例如，第一班工作的4 4名工人上名工人上班的时间分别是班的时间分别是8:008:00、8:358:35、9:109: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 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 3 换班时间换班时间表表15 错时上班的换班时间表错时上班的换班时间表问题问题3 3 中间休息中间休息4.4 进餐时间 考虑进餐时间会使排班麻烦一些。考虑进餐时间会使排班麻烦一些。首先由于进餐时间增加了首先由于进餐时间增加了4 4个小时，个小时，所以，不可能在一个班内由所以，不可能在一个班内由4 4名工人名工人完成。与问题完成。与问题2 2一样，需要增加一样，需要增加1 1名机名机开工人，顶替工人吃饭时的巡视。开工人，顶替工人吃饭时的巡视。由于题目要求，换班只能在由于题目要求，换班只能在2222号号点完成，也就是说，吃饭的换班时间点完成，也就是说，吃饭的换班时间也只能在也只能在2222号点完成，也就是在完成号点完成，也就是在完成某一轮的巡视后，才可以考虑进餐。某一轮的巡视后，才可以考虑进餐。还以第一班工作时间为例，考虑还以第一班工作时间为例，考虑进餐时间的安排。进餐时间的安排。从从8:358:35开始工作的第开始工作的第2 2名工人，名工人，在在10:5010:50完成第一轮的巡视，如果他完成第一轮的巡视，如果他不进餐，将在不进餐，将在10:5510:55开始第二轮的巡开始第二轮的巡视，这时，可以考虑让他停止工作，视，这时，可以考虑让他停止工作，选择吃午饭，他的工作由机动第选择吃午饭，他的工作由机动第5 5名工人替代完成。名工人替代完成。问题问题3 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 3 进餐时间进餐时间 20:15 20:15，第，第4 4位工人开始工作，接位工人开始工作，接替第替第5 5位机动工人的工作。而机位机动工人的工作。而机开工人那么下班休息这时不用考虑开工人那么下班休息这时不用考虑他是否吃晚饭，因为到第二天的他是否吃晚饭，因为到第二天的10:5010:50才接替第才接替第1 1位工人的工作，让第位工人的工作，让第1 1位工人吃午饭。位工人吃午饭。这个过程较为复杂，详细排班请这个过程较为复杂，详细排班请见错时上班的换班时间表见错时上班的换班时间表,表表1616显示显示了了ExcelExcel表中排班和换班的局部表格。表中排班和换班的局部表格。表表16 增加吃饭时间的排班表增加吃饭时间的排班表问题问题3 3 进餐时间进餐时间续表续表16-2 增加吃饭时间的排班表增加吃饭时间的排班表续表续表16-1 增加吃饭时间的排班表增加吃饭时间的排班表问题问题3 3 进餐时间进餐时间5.阅卷情况简述阅卷情况阅卷情况 固定上班时间固定上班时间 本人参加了北京地区和全国的本人参加了北京地区和全国的D题阅卷，下面就阅卷中遇到的问题谈题阅卷，下面就阅卷中遇到的问题谈一谈本人一点感受。一谈本人一点感受。5.1 固定上班时间 问题问题1 1和问题和问题2 2要求：固定时间上要求：固定时间上班，并且由巡检调度中心班，并且由巡检调度中心2222号点号点开始巡检。开始巡检。在通常情况下，三班倒的工作时在通常情况下，三班倒的工作时间分别是间分别是8:00 16:00，16:00 24:00和和0:00 8:00。这一点绝大多数的队都注意到了，这一点绝大多数的队都注意到了，所以根本上都采用所以根本上都采用8点、下午点、下午4点和凌点和凌晨晨0点开始上班的模式。当然，如果点开始上班的模式。当然，如果你认为有必要，采用其他时间开始上你认为有必要，采用其他时间开始上班也是正确的，只要是固定时间上班班也是正确的，只要是固定时间上班就可以。就可以。但这个固定上班时间，是每个班但这个固定上班时间，是每个班组的固定上班时间，不是每个人的固组的固定上班时间，不是每个人的固定上班时间。定上班时间。例如，一个班有例如，一个班有5 5个人个人(5(5条巡视条巡视线路线路)，那么要求这，那么要求这5 5个人同时上班。个人同时上班。这也是为什么要求大家一定从这也是为什么要求大家一定从2222号点号点开始的原因，大家需要集中一下如开始的原因，大家需要集中一下如布置工作或其他要求。布置工作或其他要求。有很多队理解成每名工人固定时有很多队理解成每名工人固定时间上班，而上班时间是不同的，这样间上班，而上班时间是不同的，这样理解问题，巡检工作从理解问题，巡检工作从22号点开始就号点开始就无意义了，因为可以让无意义了，因为可以让22号点、号点、23号、号、1号点、号点、26号点和号点和11号点都是从号点都是从8点开点开始工作，而这些点开始上班的时间分始工作，而这些点开始上班的时间分别为别为8:00、7:59、7:52、7:50和和7:45，这种方法相当于去掉从，这种方法相当于去掉从22号点开始号点开始的要求，降低了题目的难度。事实上，的要求，降低了题目的难度。事实上，这种做法只需要这种做法只需要4个人就够了。个人就够了。阅卷情况阅卷情况 固定上班时间固定上班时间 还有一个小问题：每个班的巡检还有一个小问题：每个班的巡检工作是否能在工作是否能在8 8小时内结束并不要小时内结束并不要求一定在求一定在8 8小时内回到小时内回到2222号点，这号点，这个问题根本上没有学生讨论，但它应个问题根本上没有学生讨论，但它应该是问题潜在的要求，因为在交接班该是问题潜在的要求，因为在交接班时，应该简短地说明一下本班的巡检时，应该简短地说明一下本班的巡检情况。情况。当然，并不需要见面交流，用一当然，并不需要见面交流，用一下现代通讯工具是可以的。下现代通讯工具是可以的。题目明确要求，给出巡检人员的题目明确要求，给出巡检人员的巡检线路和巡检的时间表，但很多队巡检线路和巡检的时间表，但很多队只给出巡检线路图，并没有给出具体只给出巡检线路图，并没有给出具体的巡检点的时间表。的巡检点的时间表。由于没有巡检点的排班时间表，由于没有巡检点的排班时间表，因此无法判断该队的结果是否正确，因此无法判断该队的结果是否正确，是否满足巡检要求。本质上没有完成是否满足巡检要求。本质上没有完成题目要求，分数上也会打折扣的。题目要求，分数上也会打折扣的。5.2 巡检线路与时间表阅卷情况阅卷情况 巡检时间表巡检时间表5.3 休息时间与进餐时间 问题问题2要求：每巡检要求：每巡检2小时左右需小时左右需要休息一次，休息时间大约是要休息一次，休息时间大约是5到到10分钟。在中午分钟。在中午12时和下午时和下午6时左右需时左右需要进餐一次，进餐时间为要进餐一次，进餐时间为30分钟。分钟。实际上实际上,如果每名巡检人员的排如果每名巡检人员的排班时间较均匀，这里并不需要真的考班时间较均匀，这里并不需要真的考虑休息时间的安排，因为在巡检中有虑休息时间的安排，因为在巡检中有大量的大量的5分钟可以作为休息时间。分钟可以作为休息时间。进餐时间不是固定的，否那么，进餐时间不是固定的，否那么，大家都在中午大家都在中午1212时进餐，这样就需要时进餐，这样就需要再派其他的工人来顶替进餐时的空缺，再派其他的工人来顶替进餐时的空缺，需要的人数是原来的需要的人数是原来的2 2倍，这显然过倍，这显然过于浪费人力。于浪费人力。当进餐时间不固定时，只需要增当进餐时间不固定时，只需要增加一名工人就够了，这名工人的工作加一名工人就够了，这名工人的工作是接替中午和晚上需要进餐的工人，是接替中午和晚上需要进餐的工人，这里的重点是具体的替班时间表。这里的重点是具体的替班时间表。阅卷情况阅卷情况 休息与进餐时间休息与进餐时间5.4 错时上班的讨论 问题问题3 3是讨论错时上班是否更节是讨论错时上班是否更节省人力，如果不能更节省人力，这一省人力，如果不能更节省人力，这一问也就没有讨论的必要。有的队，讨问也就没有讨论的必要。有的队，讨论了半天还是不能更省人力。可以猜论了半天还是不能更省人力。可以猜测，该队应该没有完成题目的要求。测，该队应该没有完成题目的要求。实际上，更省人力是这个问题的实际上，更省人力是这个问题的重点，需要分析在哪些地方可以更省重点，需要分析在哪些地方可以更省人力。人力。巡检时间肯定是不能省的，要省巡检时间肯定是不能省的，要省也只能是巡检路线，尽量少走重复路也只能是巡检路线，尽量少走重复路线。这自然会想到旅行商问题。但我线。这自然会想到旅行商问题。但我们发现，很多专科学校没有培训过图们发现，很多专科学校没有培训过图论方面的相关知识。论方面的相关知识。经过验算经过验算,旅行商问题的解是旅行商问题的解是135分钟，巡检点的最小间隔时间是分钟，巡检点的最小间隔时间是35分分钟，因此，需要钟，因此，需要4名工人就可以能完名工人就可以能完成工作。成工作。阅卷情况阅卷情况 错时上班时间错时上班时间 排班方法有点像列车时刻表，每排班方法有点像列车时刻表，每隔隔3535分钟发一趟车。分钟发一趟车。这种处理方法大多数队已经注意这种处理方法大多数队已经注意到了，但很多队没有给出具体的时间到了，但很多队没有给出具体的时间表。也许学生已没有足够的答题时间表。也许学生已没有足够的答题时间了，也许根本就不知道如何计算。了，也许根本就不知道如何计算。问题问题3 3的难度是增加进餐时间，的难度是增加进餐时间，大多数队根本上都没有给出这一问题大多数队根本上都没有给出这一问题的讨论。的讨论。我们很多的队希望给出一个我们很多的队希望给出一个“高高大上的模型，然后再用软件求解大上的模型，然后再用软件求解(如如LINGO)LINGO)，但由于，但由于“高大上的模高大上的模型过于复杂，无法求解或求解困难型过于复杂，无法求解或求解困难，这只能再借助于手工求解。，这只能再借助于手工求解。这样，这个模型实际上是没有用这样，这个模型实际上是没有用的，不如将精力放在问题的分析上，的，不如将精力放在问题的分析上，如采用如采用“接地气的启发式算法接地气的启发式算法 。5.5 关于模型阅卷情况阅卷情况 错时上班时间错时上班时间5.6 能否更省人力 有的队想出了更省人力的方法，有的队想出了更省人力的方法，例如，将进餐时间安排在工作时间之例如，将进餐时间安排在工作时间之外。例如，对于固定上班的工人来说，外。例如，对于固定上班的工人来说，将三班的工作时间安排为将三班的工作时间安排为3:3011:30、11:3019:30、19:303:30(次日次日)。第一班的工人下班后进餐，第二班第一班的工人下班后进餐，第二班的工人上班前吃午饭下班后吃晚饭，的工人上班前吃午饭下班后吃晚饭，第三班的工人在上班前吃晚饭，这样第三班的工人在上班前吃晚饭，这样就不用考虑他们进餐时，不需要另外就不用考虑他们进餐时，不需要另外的人员替换他们，从而更省人力。的人员替换他们，从而更省人力。有的队确实是这样做的只是时有的队确实是这样做的只是时间略有不同，对于题目要求来说，间略有不同，对于题目要求来说，这种方法无可厚非，但在实际操作中这种方法无可厚非，但在实际操作中会产生新的问题会产生新的问题是否要吃早饭。是否要吃早饭。如果能将吃早饭的问题解决，这如果能将吃早饭的问题解决，这种结果无疑是最好的。种结果无疑是最好的。阅卷情况阅卷情况 更省人力更省人力6.结论 这个问题看似复杂，如使用这个问题看似复杂，如使用TSPTSP模型、模型、VRP VRP 模型模型,甚至是甚至是 m-TSP m-TSP 模型或模型或VRPTW VRPTW 模型，但由于需要处理的点数较少，可以运用最短路算法，结合启发模型，但由于需要处理的点数较少，可以运用最短路算法，结合启发式方法得到问题的计算结果：式方法得到问题的计算结果：固定上班时间，每班需要固定上班时间，每班需要5 5人，一天共需要人，一天共需要1515人；人；考虑进餐时间，增加一名机开工人作为替补，一天需要考虑进餐时间，增加一名机开工人作为替补，一天需要1616人；人；如果采用错时上班，每班需要如果采用错时上班，每班需要4 4人，一天共人，一天共1212人；人；如再考虑进餐时间，再增加一人，每天需要如再考虑进餐时间，再增加一人，每天需要1313人。人。参考文献参考文献1 谢谢金星，薛毅金星，薛毅优优化建模与化建模与LINDO/LINGO软软件北京：件北京：清清华华大学出版社，大学出版社，2005.72薛毅数学建模基于北京：机械工薛毅数学建模基于北京：机械工业业出版社，出版社，2021.7谢 谢!
展开阅读全文