全国大学生数学建模竞赛-D题解析-课件.pptx

1、巡检巡检线路的线路的排班排班20172017年年D D题题讲评讲评主讲人：北京工业大学主讲人：北京工业大学 薛毅薛毅 Email:20172017全国数学建模讲评全国数学建模讲评会会云南、昆明云南、昆明20172017年年11 11月月2525日日1ppt课件巡检巡检线路的线路的排班排班2017年年D题题讲评讲评 题目题目 问题问题分析及问题分析及问题1的求解的求解 问题问题2的求解的求解 问题问题3的求解的求解 阅卷阅卷情况简述情况简述2ppt课件1.题目 巡检线路的排班题目题目 巡检巡检线路的排班线路的排班 某某化工厂有化工厂有 26 个点需要进行巡检以保证正常生个点需要进行巡检以保证正常

2、生产，各个点的巡检周期、巡检耗时、两点产，各个点的巡检周期、巡检耗时、两点之间之间的连通的连通关系及行走所需时间在附件中给出关系及行走所需时间在附件中给出。每个每个点每次巡检需要一名工人，巡检工人的巡检点每次巡检需要一名工人，巡检工人的巡检起始地点在巡检调度中心（起始地点在巡检调度中心（XJ0022），），工人工人可以按固可以按固定时间上班，也可以错时上班，在调度中心得到巡检定时间上班，也可以错时上班，在调度中心得到巡检任务后开始巡检任务后开始巡检。现需要建立模型来安排巡检人数和。现需要建立模型来安排巡检人数和巡检路线，使得所有点都能按要求完成巡检，并且耗巡检路线，使得所有点都能按要求完成巡检

3、，并且耗费的人力资源尽可能少，同时还应考虑每名工人在一费的人力资源尽可能少，同时还应考虑每名工人在一时间段内（如一周或一月等）的工作量尽量平衡。时间段内（如一周或一月等）的工作量尽量平衡。表表1 Excel表中的基本信息表中的基本信息3ppt课件表表2 Excel表中的连通关系表中的连通关系图图1 Excel表中的连通图表中的连通图题目题目 巡检巡检线路的排班线路的排班4ppt课件问题问题1 1.如果如果采用固定上班时间，不考虑采用固定上班时间，不考虑巡检人员的休息时间，采用每天三巡检人员的休息时间，采用每天三班倒，每班班倒，每班工作工作8 8小时小时左右，每班需左右，每班需要多少人，巡检线路

4、如何安排，并要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的给出巡检人员的巡检线路和巡检的时间表。时间表。问题问题2.如果巡检人员每巡检如果巡检人员每巡检 2 小时小时左右需要休息一次，休息时间左右需要休息一次，休息时间大约是大约是 5 到到 10 分钟，在分钟，在中午中午12 时和下午时和下午 6 时左右需要进餐一时左右需要进餐一次，每次进餐时间为次，每次进餐时间为 30 分钟，分钟，仍采用每天三班倒，每班仍采用每天三班倒，每班需要需要多少多少人，巡检线路如何安排，人，巡检线路如何安排，并给出巡检人员的巡检线路和并给出巡检人员的巡检线路和巡检的时间表巡检的时间表。题目题目 巡检巡

5、检线路的排班线路的排班问题问题3.如果采用错时上班，重新讨论如果采用错时上班，重新讨论问题问题 1 和问题和问题 2，试分析错时上，试分析错时上班是否更节省人力。班是否更节省人力。5ppt课件2.问题分析与模型建立问题问题分析与模型建立分析与模型建立 这个这个问题说的复杂一点是旅行商问题说的复杂一点是旅行商问题（问题（Traveling Salesman Problem,TSP），或者是多），或者是多旅行商旅行商问题（问题（m-TSP），更严格的说，是车辆路径问），更严格的说，是车辆路径问题（题（Vehicle Routing Problem,VRP），），而且还是而且还是带有时间窗口的车辆路

6、径问带有时间窗口的车辆路径问题（题（Vehicle Routing Problem with Time Windows,VRPTW）。如果如果这样考虑问题，这个问题将这样考虑问题，这个问题将变得非常复杂变得非常复杂。事实上。事实上，这个问题并，这个问题并没有没有这么复杂，因为它只有这么复杂，因为它只有26个需要个需要巡视的点，如果每个巡视点巡视的点，如果每个巡视点安排一个安排一个人人的话，一个班至多是的话，一个班至多是26个人。当然，个人。当然，没有那糟糕，如果一个人能没有那糟糕，如果一个人能巡视巡视35个个点的话，一个班也就是点的话，一个班也就是 69 个人。个人。因此，只需要启发式算法就可

7、能得到因此，只需要启发式算法就可能得到问题问题的计算结果的计算结果。6ppt课件问题分析问题分析巡检人员下限估计巡检人员下限估计2.1 巡检人员下限估计 为为估计巡检人员数量的估计巡检人员数量的下限，先下限，先计算出旅行商问题所需要的时间（包括计算出旅行商问题所需要的时间（包括路程时间和巡检路程时间和巡检耗时）。对于耗时）。对于只有只有2626个城市的旅行商个城市的旅行商问题，无论问题，无论是精确是精确计算，计算，还是还是近似计算都是不困难近似计算都是不困难的。的。可以可以考虑使用考虑使用LINGOLINGO程程序（见序（见11）得到）得到精确的计精确的计算算结果（见图结果（见图2 2），其中

8、），其中路路程耗时程耗时6868分钟和检查耗时分钟和检查耗时6767分钟，共计分钟，共计135135分钟。分钟。图图2 26个点的个点的TSP线路图线路图7ppt课件 由于由于巡视点两次巡视的最小间隔巡视点两次巡视的最小间隔时间是时间是3535分钟，且分钟，且135/35=3.86135/35=3.86，因，因此，一此，一个班至少个班至少需要需要4 4名名工人。从图工人。从图2 2（TSPTSP图形）和图形）和题目题目要求（从要求（从2222号点号点开始开始巡视）来看，只用巡视）来看，只用4 4名工人名工人巡视，巡视，肯定肯定是不够是不够的，应的，应考虑增加考虑增加1 1名名工人，工人，一一个

9、个班使用班使用5 5名名工人。工人。从从上述计算过程上述计算过程来看，实际上，来看，实际上，并不并不需要精确求解需要精确求解TSPTSP，只需，只需近似近似计计算，估计出一个下界即可算，估计出一个下界即可。例如例如，可，可以以采用手工采用手工计算，也计算，也可可以采用某些以采用某些启发式算法，如最近启发式算法，如最近领域领域法、最近插入法、最远插入法、最便法、最近插入法、最远插入法、最便宜插入法、任意插入法和交换两边改宜插入法、任意插入法和交换两边改进方法进方法等。等。如果如果不打算自己手工不打算自己手工编程，可以编程，可以使用现成的使用现成的软件，例如，软件，例如，R软件中软件中的的TSP函

10、数（见函数（见2）就）就可以很好地解决可以很好地解决这些这些问题，提供问题，提供不同的不同的参数，选择参数，选择你你喜欢的喜欢的算法。算法。问题分析问题分析巡检人员下限估计巡检人员下限估计8ppt课件 现现知道每个班需要知道每个班需要5 5名名工人，所工人，所以以需要将巡视点划分成需要将巡视点划分成5 5个个区域，每区域，每个个区域最多包含区域最多包含6 6个个点，最少点，最少也要有也要有4 4个个点，其点，其目的是保证每个区域的目的是保证每个区域的工作工作量（巡视时间）尽量平衡。量（巡视时间）尽量平衡。由于由于题目题目要求，每要求，每位工人均从位工人均从2222号点开始号点开始巡视，因此，距

11、巡视，因此，距2222号点较近号点较近的点则多安排的点则多安排一些，而一些，而距距2222号较远号较远的的2.2 问题1的求解点则少安排一些。为了完成这种需求点则少安排一些。为了完成这种需求的安排，需要计算从的安排，需要计算从2222号点至其余号点至其余各各点点的最短路，这项工作可用的最短路，这项工作可用Dijkstra Dijkstra（戴克斯特拉）算法完成（戴克斯特拉）算法完成。当然，也当然，也不需要自己编程不需要自己编程计算，计算，直接直接调用调用R R软件软件的的shortest.pathsshortest.paths()()函数和函数和get.shortest.pathsget.sh

12、ortest.paths()()函数函数（见（见22）就）就可完成此可完成此问题，所问题，所绘图绘图形如形如图图3 3所示。所示。问题分析问题分析 问题问题1 1的求解的求解9ppt课件问题分析问题分析 问题问题1 1的求解的求解图图3 22号点至其余各点的最短路号点至其余各点的最短路10ppt课件 从图从图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号点编为第三号点编

13、为第三组；组；2626、1515、1818和和1212号点编为第四号点编为第四组；组；1111、1313、1616和和1010号点编为第五号点编为第五组。组。每每一组都找出相应一组都找出相应TSPTSP的的结果，结果，具具体分组和相应的体分组和相应的TSPTSP图形如图形如图图4 4所示。所示。这种这种分组方式是为了满足题目的分组方式是为了满足题目的要求：要求：在在规定的巡视时间间隔内完成规定的巡视时间间隔内完成巡视；巡视；每每位工人的工作量尽量位工人的工作量尽量平衡，巡视平衡，巡视时间即不能过时间即不能过长，也长，也不能过不能过短。短。问题分析问题分析 问题问题1 1的求解的求解11ppt课

14、件图图4 巡检线路的分组情况，巡检线路的分组情况，5-TSP问题分析问题分析 问题问题1 1的求解的求解12ppt课件下面给出具体的巡视路线和巡视下面给出具体的巡视路线和巡视时间：时间：第第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号号点）的巡视，最点）的巡视，最长周期

15、是长周期是3232分钟、分钟、最最短周期短周期2828分钟（分钟（1717号号点和点和2525号号点点的的时间间隔时间间隔为分别为为分别为480480分钟和分钟和 120120分钟）分钟）。第第3 3组（组（1 1、3 3、6 6、1414、5 5和和7 7号号点）点）的巡视，最的巡视，最长周期是长周期是3232分钟，最分钟，最短短周期周期1919分钟（分钟（5 5号号点和点和7 7号点号点的时间的时间间隔分别为间隔分别为720720分钟和分钟和8080分钟）。分钟）。第第4 4组（组（2626、1515、1818和和1212号号点）的点）的巡视，周期巡视，周期长度是长度是2828分钟。分钟。

16、第第5 5组（组（1111、1313、1616和和1010号号点）的点）的巡视，周期巡视，周期长度是长度是2525分钟。分钟。问题分析问题分析 问题问题1 1的求解的求解13ppt课件表表3 第第1组组巡视巡视的时间表（部分）的时间表（部分）问题分析问题分析 问题问题1 1的求解的求解14ppt课件表表4 第第2组组巡视巡视的时间表（部分）的时间表（部分）问题分析问题分析 问题问题1 1的求解的求解15ppt课件表表5 第第3组组巡视巡视的时间表（部分）的时间表（部分）问题分析问题分析 问题问题1 1的求解的求解16ppt课件表表6 第第4组组巡视巡视的时间表（部分）的时间表（部分）问题分析问

17、题分析 问题问题1 1的求解的求解17ppt课件表表7 第第5组组巡视巡视的时间表（部分）的时间表（部分）问题分析问题分析 问题问题1 1的求解的求解18ppt课件3.问题2的求解问题问题2 2 休息时间休息时间3.1 休息时间 为了为了简化简化问题，先问题，先不用考虑不用考虑“每每巡视巡视2 2小时左右休息小时左右休息大约大约5 5到到1010分钟分钟”这一这一要求。要求。因为因为在问题在问题1 1的求解过程的求解过程中，中，5 5名名工人在巡视过程工人在巡视过程中，多次中，多次出现出现5 5分钟分钟的空余的空余时间，这些时间，这些空余时间可作休息空余时间可作休息时间。时间。在在问题问题1的

18、讨论的讨论中，每中，每班需要班需要5名名工人，考虑工人，考虑两次进餐两次进餐时间（时间（1小时），小时），就就需要增加需要增加5小时，如果小时，如果再考虑进餐再考虑进餐的衔接的衔接时间，需要时间，需要增加的时间还不止增加的时间还不止5小时，所以小时，所以仅依赖于原来的仅依赖于原来的5名工人名工人而挤出而挤出进餐时间几乎是不可能进餐时间几乎是不可能的。的。因此，需要因此，需要增加增加1名名工人让工人让他在他在其他工人进餐其他工人进餐时，完成时，完成巡视巡视工作。工作。3.2 进餐时间19ppt课件排班的方法排班的方法是：是：原来原来的排班时间不变的排班时间不变；5 5名工人的进餐时间安排在名工人

19、的进餐时间安排在1111时至时至1313时时之间，和之间，和1717时至时至1919时之间时之间；进餐进餐时间为时间为3535分钟（最小分钟（最小的的时间间隔），进餐时间间隔），进餐时的巡视工作由时的巡视工作由第第6 6名（机名（机动）工人动）工人完成完成；第第6 6名（机动）工人的进餐时间可安排在他不替班的非工作时间名（机动）工人的进餐时间可安排在他不替班的非工作时间。表表8 8至表至表1212给给出了部分排班的出了部分排班的时间表（白班时间表（白班和和中班），图中班），图中的黄色部分是中的黄色部分是可用于吃饭的时间可用于吃饭的时间。第第6 6名（机动）工人名（机动）工人的巡视的巡视时间表，

20、以及时间表，以及替换组的情况替换组的情况如表如表1313所示所示。问题问题2 2 进餐时间进餐时间20ppt课件表表8 第第1组组巡视巡视的时间表（部分，包含进餐时间）的时间表（部分，包含进餐时间）问题问题2 2 进餐时间进餐时间21ppt课件表表9 第第2组组巡视巡视的时间表（部分，包含进餐时间）的时间表（部分，包含进餐时间）问题问题2 2 进餐时间进餐时间22ppt课件表表10 第第3组组巡视巡视的时间表（部分，包含进餐时间）的时间表（部分，包含进餐时间）问题问题2 2 进餐时间进餐时间23ppt课件表表11 第第4组组巡视巡视的时间表（部分，包含进餐时间）的时间表（部分，包含进餐时间）问

21、题问题2 2 进餐时间进餐时间24ppt课件表表12 第第5组组巡视巡视的时间表（部分，包含进餐时间）的时间表（部分，包含进餐时间）问题问题2 2 进餐时间进餐时间25ppt课件表表13 第第6组（机动）的组（机动）的巡视巡视时间表时间表问题问题2 2 进餐时间进餐时间26ppt课件4.问题3的求解4.1 上班时间 问题问题3 3是考虑错时上班能否更省是考虑错时上班能否更省人力。人力。由前面的分析（巡视人员的下限由前面的分析（巡视人员的下限和问题和问题1 1）,知道人员的下限是每班知道人员的下限是每班4 4人，而固定时间上班则需要每班人，而固定时间上班则需要每班5 5人。人。那么，是否能省下这

22、那么，是否能省下这1 1个人成为问题个人成为问题的关键。的关键。如果能省，应在哪个地方省；如如果能省，应在哪个地方省；如果不能省，这个问题也就没有讨论的果不能省，这个问题也就没有讨论的必要了。必要了。每个点的检查时间（共计每个点的检查时间（共计67分钟）分钟）肯定是不能省，因此，要省也只能省肯定是不能省，因此，要省也只能省下巡视中所花的路程时间。下巡视中所花的路程时间。巡视全部点（巡视全部点（26个点）的最短路个点）的最短路程这恰好是一个旅行商问题，由前面程这恰好是一个旅行商问题，由前面的计算已知，这个时间是的计算已知，这个时间是68分钟。分钟。问题问题3 3 上班时间上班时间27ppt课件

23、那么巡视全部点的最短时间是那么巡视全部点的最短时间是135135分钟。而题目要求，要在规定的分钟。而题目要求，要在规定的时间间隔（最短为时间间隔（最短为3535分钟）内完成各分钟）内完成各点的巡视。点的巡视。这样，只能换一种排班方法，让这样，只能换一种排班方法，让每名巡视工人完成一轮（每名巡视工人完成一轮（2626个点）的个点）的巡视，而每名工人的上班时间向后错巡视，而每名工人的上班时间向后错3535分钟，即在前一位工人开始巡视的分钟，即在前一位工人开始巡视的3535分钟之后，再安排另一名工人巡视。分钟之后，再安排另一名工人巡视。对于巡视间隔要求大于对于巡视间隔要求大于35分钟的分钟的点，可以

24、采用下面的方法处理：点，可以采用下面的方法处理：l无论哪一个点，一律在无论哪一个点，一律在35分钟巡分钟巡视一次，这样肯定满足题目的要视一次，这样肯定满足题目的要求；求；l在满足巡视时间间隔要求的情况在满足巡视时间间隔要求的情况下，可以不巡视，但要在相应点下，可以不巡视，但要在相应点处休息，休息的时间就是该点的处休息，休息的时间就是该点的巡视需要的时间。巡视需要的时间。问题问题3 3 上班时间上班时间28ppt课件 因此，得到如下的排班方法：第因此，得到如下的排班方法：第1名工人在名工人在8:00开始巡视（上班或换开始巡视（上班或换班），第班），第2名工人则在名工人则在8:35开始巡视，开始巡

25、视，第第3名是名是9:10，第，第4名是名是9:45。而每位。而每位工人都走最优的旅行商路线。工人都走最优的旅行商路线。注意到，每名巡视工人的间隔时注意到，每名巡视工人的间隔时间是间是35分钟，分钟，4名工人的间隔时间是名工人的间隔时间是140分钟，而一次分钟，而一次26个点的旅行商问个点的旅行商问题的用时是题的用时是135分钟。分钟。如果第如果第1名工人在第一轮巡视后，名工人在第一轮巡视后，休息休息5分钟，那么他要在分钟，那么他要在10:20开始第开始第二轮的巡视，与第一轮巡视的第二轮的巡视，与第一轮巡视的第4名名工人的巡视时间间隔正好相差工人的巡视时间间隔正好相差35分钟。分钟。第第2名工

26、人第二轮巡视的开始时间是名工人第二轮巡视的开始时间是10:55，与第，与第1名工人相差名工人相差35分钟，以分钟，以此类推。此类推。由上述推导可知，由上述推导可知，4名工人足够满名工人足够满足巡视的要求，同时也达到了巡视人足巡视的要求，同时也达到了巡视人员要求的下界，是最优的。员要求的下界，是最优的。问题问题3 3 上班时间上班时间29ppt课件表表14 错时上班的时间表（部分）错时上班的时间表（部分）问题问题3 3 上班时间上班时间30ppt课件4.2 换班时间 由于题目要求，上班或换班的地由于题目要求，上班或换班的地点只能是调度中心，也就是说，只能点只能是调度中心，也就是说，只能在完成一轮

27、（在完成一轮（2626个点）巡视后才能换个点）巡视后才能换班。因此，每名工人的换班时间只能班。因此，每名工人的换班时间只能是是140140分钟的整数倍，选择合适的时分钟的整数倍，选择合适的时间点，工作间点，工作7 7个小时开始换班。个小时开始换班。例如，第一班工作的例如，第一班工作的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

28、4名工人的换班时名工人的换班时间分别是间分别是22:0022:00、22:3522:35、23:1023:10和和23:4523:45。由于每天是由于每天是2424小时，而换班的时小时，而换班的时间是间是7 7小时，三班下来是小时，三班下来是2121小时，所小时，所以每天的换班时间比前一天提前以每天的换班时间比前一天提前3 3小小时。时。问题问题3 3 换班时间换班时间31ppt课件 也就是说，第一班的也就是说，第一班的4 4名工人在名工人在第二天的换班时间分别是第二天的换班时间分别是5:005:00、5:355:35、6:106:10和和6:456:45；第二班的；第二班的4 4名工人在第名

29、工人在第二天的换班时间分别是二天的换班时间分别是12:0012:00、12:3512:35、13:1013:10和和13:4513:45；第三班的；第三班的4 4名工人在名工人在第二天的换班时间分别是第二天的换班时间分别是19:0019:00、19:3519:35、20:1020:10和和20:4520:45。以后的各天以此类推，每天提早以后的各天以此类推，每天提早3 3个小时换班。个小时换班。一周一周7 7天，有天，有7 7个个2424小时，恰好有小时，恰好有8 8个个2121小时，所以这种换班方案一周小时，所以这种换班方案一周重复一次。具体换班方案如表重复一次。具体换班方案如表1515所示

30、。所示。4.3 中间休息 与问题与问题2 2相同，这里不用考虑每相同，这里不用考虑每2 2个小时左右休息个小时左右休息5 5分钟的问题，因为分钟的问题，因为这里面有太多的休息时间。例如，一这里面有太多的休息时间。例如，一轮巡视后，可休息轮巡视后，可休息5 5分钟。分钟。问题问题3 3 换班时间换班时间32ppt课件表表15 错时上班的换班时间表错时上班的换班时间表问题问题3 3 中间休息中间休息33ppt课件4.4 进餐时间 考虑进餐时间会使排班麻烦一些。考虑进餐时间会使排班麻烦一些。首先由于进餐时间增加了首先由于进餐时间增加了4 4个小时，个小时，所以，不可能在一个班内由所以，不可能在一个班

31、内由4 4名工人名工人完成。与问题完成。与问题2 2一样，需要增加一样，需要增加1 1名机名机动工人，顶替工人吃饭时的巡视。动工人，顶替工人吃饭时的巡视。由于题目要求，换班只能在由于题目要求，换班只能在2222号号点完成，也就是说，吃饭的换班时间点完成，也就是说，吃饭的换班时间也只能在也只能在2222号点完成，也就是在完成号点完成，也就是在完成某一轮的巡视后，才可以考虑进餐。某一轮的巡视后，才可以考虑进餐。还以第一班工作时间为例，考虑还以第一班工作时间为例，考虑进餐时间的安排。进餐时间的安排。从从8:358:35开始工作的第开始工作的第2 2名工人，名工人，在在10:5010:50完成第一轮的

32、巡视，如果他完成第一轮的巡视，如果他不进餐，将在不进餐，将在10:5510:55开始第二轮的巡开始第二轮的巡视，这时，可以考虑让他停止工作，视，这时，可以考虑让他停止工作，选择吃午饭，他的工作由机动（第选择吃午饭，他的工作由机动（第5 5名）工人替代完成。名）工人替代完成。问题问题3 3 进餐时间进餐时间34ppt课件 在在3030分钟后，让分钟后，让11:2511:25完成第一完成第一轮巡视的第轮巡视的第3 3名工人休息进餐，而第名工人休息进餐，而第2 2名工人来接替他，在名工人来接替他，在11:3011:30开始工作。开始工作。之后，第之后，第3 3名工作完成进餐后，名工作完成进餐后，接替

33、接替12:0512:05开始工作的第开始工作的第4 4名工人，让名工人，让第第4 4名工人吃午饭。名工人吃午饭。第第4 4名工人午饭后，在名工人午饭后，在12:4012:40接替接替第第1 1名工人的工作，第名工人的工作，第1 1名工人开始吃名工人开始吃午饭。午饭。第第1 1名工人在午饭后就不工作了，名工人在午饭后就不工作了，需要等到下午需要等到下午18:3018:30分，接替第分，接替第2 2名工名工人的工作，直到这个班工作结束。在人的工作，直到这个班工作结束。在这中间也不考虑他吃晚饭的时间，因这中间也不考虑他吃晚饭的时间，因为他可以在为他可以在18:3018:30以前吃完晚饭。以前吃完晚饭

34、。此时此时(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 进餐时间进餐时间35ppt课件 20:1520:15，第，第4 4位工人开始工作，接位工人开始工作，接替第替第5 5位（机动）工人的工作。而机位（机动）工人的工作。而机动工人则下班休息（这时不用考虑他动工人则下班休息（这时不用考虑他是否吃晚饭），因为到第二天的是否吃晚饭），因为到

35、第二天的10:5010:50才接替第才接替第1 1位工人的工作，让第位工人的工作，让第1 1位工人吃午饭。位工人吃午饭。这个过程较为复杂，详细排班请这个过程较为复杂，详细排班请见错时上班的换班时间表见错时上班的换班时间表,表表1616显示显示了了ExcelExcel表中排班和换班的部分表格。表中排班和换班的部分表格。表表16 增加吃饭时间的排班表增加吃饭时间的排班表问题问题3 3 进餐时间进餐时间36ppt课件续表续表16-2 增加吃饭时间的排班表增加吃饭时间的排班表续表续表16-1 增加吃饭时间的排班表增加吃饭时间的排班表问题问题3 3 进餐时间进餐时间37ppt课件5.阅卷情况简述阅卷情况

36、阅卷情况 固定上班时间固定上班时间 本人参加了北京地区和全国的本人参加了北京地区和全国的D D题阅卷，下面就阅卷中遇到的问题谈题阅卷，下面就阅卷中遇到的问题谈一谈本人一点感受。一谈本人一点感受。5.1 固定上班时间 问题问题1 1和问题和问题2 2要求：固定时间上要求：固定时间上班，并且由巡检调度中心（班，并且由巡检调度中心（2222号点）号点）开始巡检。开始巡检。在通常情况下，三班倒的工作时在通常情况下，三班倒的工作时间分别是间分别是8:00 16:00，16:00 24:00和和0:00 8:00。这一点绝大多数的队都注意到了，这一点绝大多数的队都注意到了，所以基本上都采用所以基本上都采用

37、8点、下午点、下午4点和凌点和凌晨晨0点开始上班的模式。当然，如果点开始上班的模式。当然，如果你认为有必要，采用其他时间开始上你认为有必要，采用其他时间开始上班也是正确的，只要是固定时间上班班也是正确的，只要是固定时间上班就可以。就可以。38ppt课件 但这个固定上班时间，是每个班但这个固定上班时间，是每个班组的固定上班时间，不是每个人的固组的固定上班时间，不是每个人的固定上班时间。定上班时间。例如，一个班有例如，一个班有5 5个人个人 (5(5条巡视条巡视线路线路)，则要求这，则要求这5 5个人同时上班。这个人同时上班。这也是为什么要求大家一定从也是为什么要求大家一定从2222号点开号点开始

38、的原因，大家需要集中一下（如布始的原因，大家需要集中一下（如布置工作或其他要求）。置工作或其他要求）。有很多队理解成每名工人固定时有很多队理解成每名工人固定时间上班，而上班时间是不同的，这样间上班，而上班时间是不同的，这样理解问题，巡检工作从理解问题，巡检工作从2222号点开始就号点开始就无意义了，因为可以让无意义了，因为可以让2222号点、号点、2323号、号、1 1号点、号点、2626号点和号点和1111号点都是从号点都是从8 8点开点开始工作，而这些点开始上班的时间分始工作，而这些点开始上班的时间分别为别为8:008:00、7:597:59、7:527:52、7:507:50和和7:45

39、7:45，这种方法相当于去掉从这种方法相当于去掉从2222号点开始的号点开始的要求，降低了题目的难度。事实上，要求，降低了题目的难度。事实上，这种做法只需要这种做法只需要4 4个人就够了。个人就够了。阅卷情况阅卷情况 固定上班时间固定上班时间39ppt课件 还有一个小问题：每个班的巡检还有一个小问题：每个班的巡检工作是否能在工作是否能在8 8小时内结束（并不要小时内结束（并不要求一定在求一定在8 8小时内回到小时内回到2222号点），这号点），这个问题基本上没有学生讨论，但它应个问题基本上没有学生讨论，但它应该是问题潜在的要求，因为在交接班该是问题潜在的要求，因为在交接班时，应该简短地说明一下

40、本班的巡检时，应该简短地说明一下本班的巡检情况。情况。当然，并不需要见面交流，用一当然，并不需要见面交流，用一下现代通讯工具是可以的。下现代通讯工具是可以的。题目明确要求，给出巡检人员的题目明确要求，给出巡检人员的巡检线路和巡检的时间表，但很多队巡检线路和巡检的时间表，但很多队只给出巡检线路图，并没有给出具体只给出巡检线路图，并没有给出具体的巡检点的时间表。的巡检点的时间表。由于没有巡检点的排班时间表，由于没有巡检点的排班时间表，因此无法判断该队的结果是否正确，因此无法判断该队的结果是否正确，是否满足巡检要求。本质上没有完成是否满足巡检要求。本质上没有完成题目要求，分数上也会打折扣的。题目要求

41、，分数上也会打折扣的。5.2 巡检线路与时间表阅卷情况阅卷情况 巡检时间表巡检时间表40ppt课件5.3 休息时间与进餐时间 问题问题2 2要求：每巡检要求：每巡检2 2小时左右需小时左右需要休息一次，休息时间大约是要休息一次，休息时间大约是5 5到到1010分钟。在中午分钟。在中午1212时和下午时和下午6 6时左右需时左右需要进餐一次，进餐时间为要进餐一次，进餐时间为3030分钟。分钟。实际上实际上,如果每名巡检人员的排如果每名巡检人员的排班时间较均匀，这里并不需要真的考班时间较均匀，这里并不需要真的考虑休息时间的安排，因为在巡检中有虑休息时间的安排，因为在巡检中有大量的大量的5 5分钟可

42、以作为休息时间。分钟可以作为休息时间。进餐时间不是固定的，否则，大进餐时间不是固定的，否则，大家都在中午家都在中午1212时进餐，这样就需要再时进餐，这样就需要再派其他的工人来顶替进餐时的空缺，派其他的工人来顶替进餐时的空缺，需要的人数是原来的需要的人数是原来的2 2倍，这显然过倍，这显然过于浪费人力。于浪费人力。当进餐时间不固定时，只需要增当进餐时间不固定时，只需要增加一名工人就够了，这名工人的工作加一名工人就够了，这名工人的工作是接替中午和晚上需要进餐的工人，是接替中午和晚上需要进餐的工人，这里的重点是具体的替班时间表。这里的重点是具体的替班时间表。阅卷情况阅卷情况 休息与进餐时间休息与进

43、餐时间41ppt课件5.4 错时上班的讨论 问题问题3 3是讨论错时上班是否更节是讨论错时上班是否更节省人力，如果不能更节省人力，这一省人力，如果不能更节省人力，这一问也就没有讨论的必要。有的队，讨问也就没有讨论的必要。有的队，讨论了半天还是不能更省人力。可以猜论了半天还是不能更省人力。可以猜想，该队应该没有完成题目的要求。想，该队应该没有完成题目的要求。实际上，更省人力是这个问题的实际上，更省人力是这个问题的重点，需要分析在哪些地方可以更省重点，需要分析在哪些地方可以更省人力。人力。巡检时间肯定是不能省的，要省巡检时间肯定是不能省的，要省也只能是巡检路线，尽量少走重复路也只能是巡检路线，尽量

44、少走重复路线。这自然会想到旅行商问题。但我线。这自然会想到旅行商问题。但我们发现，很多专科学校没有培训过图们发现，很多专科学校没有培训过图论方面的相关知识。论方面的相关知识。经过验算经过验算,旅行商问题的解是旅行商问题的解是135135分钟，巡检点的最小间隔时间是分钟，巡检点的最小间隔时间是3535分分钟，因此，需要钟，因此，需要4 4名工人就可以能完名工人就可以能完成工作。成工作。阅卷情况阅卷情况 错时上班时间错时上班时间42ppt课件 排班方法有点像列车时刻表，每排班方法有点像列车时刻表，每隔隔3535分钟发一趟车。分钟发一趟车。这种处理方法大多数队已经注意这种处理方法大多数队已经注意到了

45、，但很多队没有给出具体的时间到了，但很多队没有给出具体的时间表。也许学生已没有足够的答题时间表。也许学生已没有足够的答题时间了，也许根本就不知道如何计算。了，也许根本就不知道如何计算。问题问题3 3的难度是增加进餐时间，的难度是增加进餐时间，大多数队基本上都没有给出这一问题大多数队基本上都没有给出这一问题的讨论。的讨论。我们很多的队希望给出一个我们很多的队希望给出一个“高高大上大上”的模型，然后再用软件求解的模型，然后再用软件求解(如如LINGO)LINGO)，但由于，但由于“高大上高大上”的模的模型过于复杂，无法求解（或求解困型过于复杂，无法求解（或求解困难），这只能再借助于手工求解。难），

46、这只能再借助于手工求解。这样，这个模型实际上是没有用这样，这个模型实际上是没有用的，不如将精力放在问题的分析上，的，不如将精力放在问题的分析上，如采用如采用“接地气接地气”的启发式算法的启发式算法 。5.5 关于模型阅卷情况阅卷情况 错时上班时间错时上班时间43ppt课件5.6 能否更省人力 有的队想出了更省人力的方法，有的队想出了更省人力的方法，例如，将进餐时间安排在工作时间之例如，将进餐时间安排在工作时间之外。例如，对于固定上班的工人来说，外。例如，对于固定上班的工人来说，将三班的工作时间安排为将三班的工作时间安排为3:303:3011:3011:30、11:3019:3011:3019:

47、30、19:3019:303:30(3:30(次日次日)。第一班的工人下班后进餐，第二第一班的工人下班后进餐，第二班的工人上班前吃午饭下班后吃晚饭，班的工人上班前吃午饭下班后吃晚饭，第三班的工人在上班前吃晚饭，这样第三班的工人在上班前吃晚饭，这样就不用考虑他们进餐时，不需要另外就不用考虑他们进餐时，不需要另外的人员替换他们，从而更省人力。的人员替换他们，从而更省人力。有的队确实是这样做的（只是时有的队确实是这样做的（只是时间略有不同），对于题目要求来说，间略有不同），对于题目要求来说，这种方法无可厚非，但在实际操作中这种方法无可厚非，但在实际操作中会产生新的问题会产生新的问题是否要吃早饭。是否

48、要吃早饭。如果能将吃早饭的问题解决，这如果能将吃早饭的问题解决，这种结果无疑是最好的。种结果无疑是最好的。阅卷情况阅卷情况 更省人力更省人力44ppt课件6.结论 这个问题看似复杂，如使用这个问题看似复杂，如使用TSPTSP模型、模型、VRP VRP 模型模型,甚至是甚至是 m-TSP m-TSP 模型或模型或VRPTW VRPTW 模型，但由于需要处理的点数较少，可以运用最短路算法，结合启发模型，但由于需要处理的点数较少，可以运用最短路算法，结合启发式方法得到问题的计算结果：式方法得到问题的计算结果：l 固定上班时间，每班需要固定上班时间，每班需要5 5人，一天共需要人，一天共需要1515人

49、；人；l 考虑进餐时间，增加一名机动工人作为替补，一天需要考虑进餐时间，增加一名机动工人作为替补，一天需要1616人；人；l 如果采用错时上班，每班需要如果采用错时上班，每班需要4 4人，一天共人，一天共1212人；人；l 如再考虑进餐时间，再增加一人，每天需要如再考虑进餐时间，再增加一人，每天需要1313人。人。45ppt课件参考文献参考文献1 谢金星，薛毅优化建模与谢金星，薛毅优化建模与LINDO/LINGO软件北京：软件北京：清华大学出版社，清华大学出版社，2005.72薛毅数学建模基于北京：机械工业出版社，薛毅数学建模基于北京：机械工业出版社，2017.746ppt课件谢 谢!47ppt课件