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