对巡检线路的排班数学模型分析

李波　王妍婷

摘 要： 本文根据一个巡检线路的数据，用数学统计方法对线路评估并给出优化方案。用了最小生成树算法、整数线性规划建立了一系列数学规划模型，并用EXCEL和Mathematica、LINGO软件编程实现。

关键词： 最小生成树；最短路径；巡检线路

中图分类号： O242.1 文献标识码： A 文章编号： 2095-8153（2018）03-0073-04

0 引言

人力资源管理是一个企业进行人力资源分配的重要工作，合理地安排人力资源，能够为企业带来最大的经济效益、社会效益、环境效益。本文研究的是化工厂为满足不同条件的最优巡检人员调配方案问题，具体内容参看2017年全国大学生数学建模竞赛D题[1]。

结合本题附件中给出的具体要求及相关政策，建立模型，解决如下问题：

问题一：若满足巡检人员固定上班时间，每班需要巡检人员的数量，以及巡检线路的安排，并给出巡检的时间表。根据已有的各个点的巡检周期、巡检耗时、两点之间的连通关系及行走所需时间验证所建模型的合理性。

问题二：根据所建立的模型，分析如果巡检人员每巡检2小时左右需要休息一次，休息时间大约是5到10分钟，在中午12时和下午6时左右需要进餐一次，每次进餐时间为30分钟，仍采用每天三班倒轮班制，每班需要巡检人员的数量，巡检线路的安排，巡检人员的巡检线路和巡检的时间表。

问题三：根据问题一问题二所述，若满足巡检人员错时上班，重新验证问题一问题二，试分析错时上班是否更节省人力，是否更具有合理性。

1 模型假设

模型假设

（1）假设巡检人员在某一个时段一起开始上班，在某一个时段结束时一起下班。

（2）假设固定上班时间为早上8：00，每个巡检人员必须每天连续工作8小时，并且工作时间段稳定。

（3）假设不考虑上下班巡检人员交接班、中途吃饭和休息等时间。

（4）排除人员因生病、请假等不能正常工作的情况，排除天气对巡检的影响。

2 模型建立与求解

2.1 问题一的模型建立及求解

为估计巡检人员数量的下限，使用LINGO程序得到精确的计算结果[2]，其中路程耗时68分钟和检查耗时67分钟，共计135分钟。巡视点两次巡视的最小间隔时间是35分钟，且135/35=3.86，因此，一个班至少需要4名工人。根据题目要求来看，只用4名工人巡视，肯定是不够的，应考虑增加1名工人，一个班使用5名工人。现知道每个班需要5名工人，所以需要将巡视点划分成5个区域，每个区域最多包含6个点，最少也要有4个点，其目的是保证每个区域的工作量（巡视时间）尽量平衡。

由于题目要求，每位工人均从22号点开始巡视。因此，距22号点较近的点则多安排一些，而距22号较远的点则少安排一些。为了完成这种需求的安排，需要计算从22号点至其余各点的最短路，这项工作可用Dijkstra （戴克斯特拉）算法完成。

从图1出发，作如下尝试，将 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的结果，这种分组方式是为了满足题目的要求，在规定的巡视时间间隔内完成巡视；每位工人的工作量尽量平衡，巡视时间既不能过长，也不能过短。

下面给出具体的巡视路线和巡视时间：

第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号点）的巡视，周期长度是28分钟。

第5组（11、13、16和10号点）的巡视，周期长度是25分钟。

2.2 问题二的模型建立及求解

2.2.1 休息时间

为了简化问题，先不用考虑“每巡视2小时左右休息大约5到10分钟”这一要求。因为在问题1的求解过程中，5名工人在巡视过程中，多次出现5分钟的空余时间，这些空余时间可作休息时间。

2.2.2 进餐时间

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

排班的方法是： 原来的排班时间不变；

5名工人的进餐时间安排在11时至13时之间，和17时至19时之间；进餐时间为35分钟（最小的时间间隔），进餐时的巡视工作由第6名（机动）工人完成；第6名（机动）工人的进餐时间可安排在他不替班的非工作时间。

2.3 问题三模型建立及问题求解

问题3是考虑错时上班能否更省人力。

由前面的分析（巡视人员的下限和问题1），知道人员的下限是每班4人，而固定时间上班则需要每班5人。每个点的检查时间（共计67分钟）肯定是不能省，因此，要省也只能省下巡视中所花的路程时间。巡视全部点（26个点）的最短路程这恰好是一个旅行商问题，由前面的计算已知，这个时间是68分钟。那么巡视全部点的最短时间是135分钟。而题目要求，要在规定的时间间隔（最短为35分钟）内完成各点的巡视。这样，只能换一种排班方法，让每名巡视工人完成一轮（26个点）的巡视，而每名工人的上班时间向后错35分钟，即在前一位工人开始巡视的35分钟之后，再安排另一名工人巡视。对于巡视间隔要求大于35分钟的点，可以采用下面的方法处理：无论哪一个点，一律在35分钟巡视一次，这样肯定满足题目的要求。在满足巡视时间间隔要求的情况下，可以不巡视，但要在相应点处休息，休息的时间就是该点的巡视需要的时间。因此，得到如下的排班方法：第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名工人足够满足巡视的要求，同时也达到了巡视人员要求的下界，是最优的。

进餐时间会使排班麻烦一些。首先由于进餐时间增加了4个小时，所以，不可能在一个班内由4名工人完成。与问题2一样，需要增加1名机动工人，顶替工人吃饭时的巡视。由于题目要求，换班只能在22号点完成，也就是说，吃饭的换班时间也只能在22号点完成，也就是在完成某一轮的巡视后，才可以考虑进餐。给出部分表格。

3 模型评价

本题用运用最短路算法，kruskal算法、哈密爾顿图来计算分区路线的均衡性，得到相应的时间均衡度，从使用时间的长短均衡度来看，分为这四个区域均衡性比较好，能保证所有的巡检点在较短的时间内完成巡检，而且每个区域巡检一个周期所使用的时间相差较小，从而最大限度地避免了一个每个区域巡检的时间不均衡。

[参考文献]

[1]全国大学生数学建模竞赛组委会.2017高教社杯全国大学生数学建模竞赛（CUMCM）题目D题[EB/OL].[2017-09-14].http：//www.mcm.edu.cn/.

[2]谢金星，薛 毅.优化建模与LINDO/LINGO软件.北京： 清华大学出版社，2005：7.