一、问题的提出^[1]

工厂的安全可靠运行，要求巡检效率更高。某化工厂有26个点需要进行巡检以保证正常生产，每个点每次巡检需要一名工人，且巡检起始地点在巡检调度中心（XJ0022），工人可以按固定时间上班，也可以错时上班，在调度中心得到巡检任务后就开始巡检。建立模型来安排巡检人数和巡检路线，使得所有点都能按要求完成巡检，并且耗费的人力资源尽可能少，同时还应考虑每名工人在一时间段内（如一周或一月等）的工作量尽量平衡。（1）.用固定上班时间，不考虑巡检人员的休息时间，采用每天三班倒，每班工作8小时，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。（2）.如果巡检人员每巡检2小时左右需要休息一次，休息时间大约是5到10分钟，在中午12时和下午6时左右需要进餐一次，每次进餐时间为30分钟，仍采用每天三班倒，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。（3）.用错时上班，重新讨论问题1和问题2，试分析错时上班是否更节省人力。

二、问题的解决

2.1作出带权邻接矩阵，求出巡检调度中心（XJ0022）到各点的最短路径

由问题可知，在赋权网络图G(V,E,W)中共有26个点。其中V={v₁,v₂,v₃,…v_n}(n=26)表示图G的26节点，E={e_ij}表示相关联的两点i,j的边集，W={w_ij}表示相关联的两点i,j间的权值。

定义0-1变量r_ij：

   其中相关联表示i,j两点之间有路径，不相关表示i,j之间没有路径。

根据赋权图写出邻接矩阵，利用MATLAB软件编写程序，得出该网络图G的最小生成树。

利用MATLAB软件对带权邻接矩阵^[2]进行编程计算，得到结果表1-1.即巡检调度中心（XJ0022）到各点的最短路径： 

                      表1-1巡检调度中心到各点的最短路径

2.2问题一

2.2.1模型的建立与求解

根据问题一的分析，在巡检人员尽可能少和每人巡检时间尽可能均衡的前提下，为减少过多重复的路线以交叉点作为分区的界限，这样可以建立多目标线性规划模型：

（1）巡检的总时间最短：

（2）每人巡检时间尽量均衡合理为使每个人工作时间均衡，我们引入了均衡度。它表示最大时间和最小时间的差值与最大时间的比值^[3]

约束条件为均衡度a<0.15。

其中c_i表示第i个人的巡检时间，a为均衡度。

根据最短路径以及满足巡检周期、工作时间均衡等条件，建立多目标规划模型得到，由巡检总时间最少，结合各巡检点的巡检周期得到5个区域的巡检路线分别为：

表2-1  巡检路线表

五个人所巡检的总时间为：

此时由五人所巡检的时间c_i得巡检时间均衡度：

因为a=0.28>0.15,均衡度不好，需要对分区进行修正。

通过上述结果发现第一个人所巡检的时间比较长，而第五个人所巡检的时间比较短，考虑将分区1中离分区4较近但距5较远的1个点划分到第4分区中，并将分区3的点18划分到第五区，所得的巡检路线如下表2-2：

表2-2  巡检路线表

则五人所巡检的总时间为：

此分区下的均衡度：

由a<0.15可知：此种情况下的分区较为合理，是最终的巡检路线。

2.3问题二

2.3.1模型的建立

结合问题一，通过问题二分析需要满足休息和吃饭的时间，建立多目标线性规划模型：

(1)巡视检总时间最短：

（2）巡检时间尽量均衡： 

（3）耗费人力资源最少且完成巡检任务   

约束条件：1.每巡检两小时后休息5-10分钟，每人有30分钟的吃饭时间；

          2. a<0.15.

2.3.2模型求解

根据问题二的约束条件，我们假设固定三班上班时间分为两种情况：

第一种：4:00-12:00,12:00-20:00,20:00-4:00；

第二种：0:00-8:00，8:00-16:00，16:00-24:00；

第一种情况：

早上第一班4:00-12:00，午餐时间为12点，所以选择下班之后去进餐，对于第二班从12:00-20:00的情况，需要在下午6点的时候进行进餐，选择轮流吃饭，因此需要多加一个人替补；此时需要6人进行第二班巡检；对于第三班20:00-4:00期间，不需进餐，与问题一相同。

第一班和第三班的分配安排与第一问一样（如下表3-1）：

表3-1  巡检路线表

则五人所巡检的总时间为：

此分区下的均衡度：

由a<0.15可知：此种情况下的分区较为合理。

对于第五个人巡检完一轮需要31钟，而2小时休息一次5-10分钟，休息是不够的，但按最小周期35分钟计算，也可以巡检完三轮，其中点5的周期为720分钟，即12小时。所以对于从第二轮开始也就不用对点5进行巡检。

对于第二个人需要进餐时间30分钟，考虑将其五人转化成六人，巡检路线安排如下表3-2：

表3-2  巡检路线安排表

让6个人轮流去吃饭，第一个人先去吃饭，剩余5人继续巡检。所以在18点时将六人巡检转化为五人巡检，这样3班最终需要5+6+5=16人。

很显然，这样不太合理，当第5个人去吃饭的时候已经到了20点，对巡检员安排的不公平，于是改进得到第二种情况。

第二种情况：

根据题意，早上第一班0:00-8:00，对于第二班8:00-16:00的情况，因为午餐时间为12点，所以选择进行轮流进餐，多加一个人进行替补。对于第三班16:00-24:00期间，在18点也需要轮流进餐，与第二班相同也需要6个人进行第三班巡检。

综上所述，这样每天3班最终需要5+6+6=17人。

2.4问题三

2.4.1错时上班与问题一模型的比较

2.4.1.1模型的建立

通过对问题三的分析，结合问题一求解讨论，不考虑巡检人员休息和就餐的前提下，为了使巡检员最少，采用环状巡检。 

目标： 巡检员人数最少，且完成巡检任务

 约束： 每个人的工作量尽量均衡，其中m是表示需要的巡检人数。

模型一：

即第一个人从巡检中心22点开始巡检，一直走到最后回到起始点，当第一个人出发35分钟后第二个人立即上班继续从巡检中心22点开始巡检，后面依此类推。另外需要一个人专门进行巡检一个环形圈。

巡检路径安排如下：

22-23-24-9-25-17-8-17-25-26-15-12-15-18-16-13-11-10-6-14-6-3-5-7-5-3-2-4-21-22

单人巡检路线：22-20-19-2-1-2-4-21-22

经过计算巡检完所有的点需要的时间总和为C=107+34=141（分钟）。因为巡检路线为两个环状，走了很多重复的路，因此考虑巡检路线为一个环状。由此改进到模型二：

即第一个人从巡检中心22点开始以图4-1箭头方向巡检，一直走到最后回到起始点，当第一个人出发35分钟后第二个人立即上班并与前一人巡检路线一样开始巡检；后面依此类推。经过分析，将巡检路线简化为一条环状路。

巡检路线如下：

22-23-24-9—25—17-8-17-25-26-15-12-15-18-16-13-11-10-6-14-6-3-5-7-5-3-2-1-2-4-21-22-20-19-20-22

经过计算巡检完所有的点需要的时间总和为C=135（分钟）。经比较模型一、二总巡检时间，选择模型二进行巡检人员的巡检时间和巡检路线进行安排。

2.4.1.2模型的求解

巡检完一圈所需135分钟，而其中的点大多周期都在35分钟，于是我们需要在第一个人刚好出发35分钟的时候，再来另一个人继续从巡检中心22点朝着第一人巡检的方向巡检。那么巡检完一轮需要的最少人数为

经过与问题一进行比较，发现此时每班巡检所需要的人数由原来的5人变为4人。

每天巡检的总人数由原来的15人降为12人。从人力资源来看，错时上班更节省人力。

2.4.2错时上班与问题二模型的比较

2.4.2.1模型的建立与求解

结合问题二的求解，及错时上班人员不休息和就餐时间的巡检路线的安排，再通过对问题三的分析我们可以建立多目标规划模型。

目标： 巡检人员最少，且完成巡检任务： 

    约束： 1.每个人的工作量尽量均衡；

2.每巡检两小时休息5-10分钟；每天12点和18点吃饭时间30分钟。

根据问题二可知:如果不考虑吃饭时间和休息时间，每班需要4人，但如果需要休息和吃饭4个人就不能满足要求。于是考虑增加一人，当第一个人巡检完所有的点回到巡检中心时一共用135分钟。假设每个人巡检到起始点（22）的时候进行休息。当到12点左右时，巡检了两圈，此时第一个人去吃饭，需要第5个人来接替他继续巡检。

对于0:00-8:00不需要吃饭，需要4个人巡检。

对于8:00-16:00,16:00-24:00,需要用30分钟进餐，每班5个人巡检。

每个巡检人员的巡检路线为：

22-23-24-9—25—17-8-17-25-26-15-12-15-18-16-13-11-10-6-14-6-3-5-7-5-3-2-1-2-4-21-22-20-19-20-22。

巡检人员巡检时间与巡检路线安排如下表4-2

表4-2  巡检时间表

注：前4个人依次推迟35分钟上班，第5个人比第一个人晚4个小时40分钟上班。

经过与问题二进行比较,发现此时第一班巡检人员4人，第二班和第三班巡检人员5人。每天巡检人员为14人。每天巡检的总人数由原来的17人降为14人。从人力资源来看，错时上班更节省人力。

参考文献： 

[1]2017年高教社杯全国大学生数学建模竞赛赛题D,http://www.mcm.edu.cn 2017-09-14 21:03 

[2]赵静 但琦主编，数学建模与数学实验[M],高等教育出版社2017.1 

[3]zhzofkzhz,灾情巡视路线模型，http://www.docin.com/p-586666472.html，2013.1.21  

[4]杨溪 王海龙 谭学平，灾情巡视路线网络模型门，甘肃高师学报，第4 卷

第2期(1999)

作者简介：刘学才（1963-），男，湖北广水人，湖北职业技术学院数学教授，研究方向:高等数学、应用数学及数学建模与数学实验。