巡检线路排班优化模型研究

陆春桃

【摘 要】文章利用双向带权连通图遍历方法、数学规划方法、Excel工具对巡检线路安排进行讨论，从省力、工作量平衡等方面着手，构建出合理的巡检线路安排的优化模型。首先以所需人数最少和所用时间尽量最少作为双目标函数，同时需要满足巡检点的巡检周期不超过35 min，构建出优化模型后再转化为双向带权连通遍历问题，用模型得出每条路线所需最少人数、一天需要巡检人员人数；然后用穷举法，安排出巡检路线和巡检时间安排表。考虑上休息时间和进餐时间因素，增设时间约束条件，应用同样的方法，得出问题二的巡检路线和巡检时间安排表；最后利用Excel工具进行数据处理，给出问题三在错时上班时是否省力的结论。

【关键词】巡检线路安排；数学规划方法；穷举法；优化模型

【中图分类号】O224 【文献标识码】A 【文章编号】1674-0688（2017）11-0035-04

1 问题提出

合理安排工人进行巡检，及时发现问题、及时维修是大型工厂安全生产、提高劳动效益的有效举措。结合这一实际，2017年“高教社杯”全国大学生数学建模竞赛D题给出了巡检线路的排班问题。

某化工厂有26个点需要进行巡检以保证正常生产，题目给出了各个点的巡检周期、巡检耗时、两点之间的连通关系及行走所需时间。

现要求每个点每次巡检安排1名工人，每人均从巡检调度中心开始出发，分2种情况采取固定时间上班：一是每班工人不休息，二是每班工人每工作2 h可休息5～10 min，中午12時和下午6时左右有30 min的进餐时间；也可以错时上班，在调度中心得到巡检任务后开始巡检。现要求满足所有点都能按要求完成巡检，耗费的人力资源尽可能地少，每名工人在一段时间内（如1周或1个月等）的工作量尽量平衡3个条件来建立模型，进而确定巡检人数和巡检路线。

2 问题假设

（1）假设各个巡检人员的巡检路线是可以重复的。

（2）假设每个站点都可让巡检人员提前巡检。

（3）假设每个站点都排除意外因素的发生。

（4）假设问题一中，巡检工作人员的三班倒时间段为8：00-16：00；16：00-24：00；24：00-8：00。

（5）假设问题二中，巡检工作人员的三班倒时间段为12：00-18：00；18：00-2：00；2：00-10：00。

（6）假设问题三中，巡检工作人员的三班倒时间段为10：00-18：00；18：00-2：00；2：00-10：00。

（7）假设每个站点之间路程只有耗时的不同，并没有其他不同。

（8）假设如有一名巡检人员在某一段时间不够完成巡检工作的情况下，可以寻求临近的其他巡检人员帮忙。

（9）假设每个站点只需要1名巡检人员，其余的巡检人员可以路过该站点，但不需要停留巡检。

3 符号说明

符号及对应的意义见表1。

4 问题分析

本题属于优化模型问题，需要用数学规划方法对问题进行求解。

针对问题一，不考虑巡检人员的休息时间，采用每天三班倒，每班工作8 h左右的条件，我们可建立所需巡检人数最少的目标函数，同时确定约束条件，确立优化的规划模型。用Excel软件的数据处理分析功能对模型进行求解，得到巡检人员最少的人数，再用穷举法，按区域划分优先考虑回路的方式、折回的方式，根据题目所给的周期，选最少的时间按照连通图上点的顺序进行列举得出最佳路线，并根据路线安排巡检人员排班表。

在问题一的基础上，新增巡检人员每巡检2 h左右需要休息一次、在中午12时和下午6时左右需要进餐一次、每次进餐时间为30 min 3个约束条件。保持问题一中的模型不变，再加上这些约束条件后，可以得到新的模型，随后对模型进行求解，用同样的方法得出巡检人数、巡检线路排班表。

至于问题三，采用错时上班时间，在问题一、问题二模型的基础上，分别通过Excel软件的数据处理分析功能，得出化工厂最优化的巡检人员人数，以此说明是否节约人力。

5 模型的建立和求解

5.1 问题一

5.1.1 确立模型

根据题意：固定上班时间，不考虑巡检人员的休息时间，每天三班倒，每班工作尽量满足8 h，而且每个巡检点的实际巡检周期都小于或等于所需巡检周期。设Xi为巡检所需最少人数，Ti为第i个巡检点的巡检周期，li为巡检耗时时间（i=1，2，…，26），kj为路程间的耗时（j=1，2，…，31），建立巡检人数最少的目标函数：

min∑Xi=li+kj（模型I）

min■|ti-480|（i=1，2，3，4，5，…，n）

s.t

Ti≤Ti≤35，（i=1，3，4，6，8，9，11，12，14，15，16，18，19，20，22，23，24，26）；Ti≤80，（i=7，13，21）；Ti≤120，（i=10，25）；T2≤50；T17≤480；T5≤72；

5.1.2 确定人数

通过Excel软件对模型I进行数据处理分析，得到Xi=5。

结论：我们可以知道每班需要5名巡检人员，每天采用三班倒，需要15名巡检人员。

5.1.3 确定路线

因为最优解法在一般条件无法利用软件求出，所以我们得出以上最优解法后，需要使用穷举法，分区域划分优先考虑回路的方式，再安排折回的方式选出以下5条路线：①22→20→19→2→4→21→22；②23→24→9→25→26→23；③7→5→3→1→14→8→3；④17→6→10→12→6；⑤15→18→16→13→11→15。

5.1.4 安排时间

根据上述运算结果，假设巡检工作人员的三班倒时间段为8：00-16：00；16：00-24：00；24：00-8：00。

按每一班的时间表进行数据整理，由此我们得出三班倒的巡检时间安排表见表1，8：00-16：00的巡检时间表见表2。

我们知道巡检人员每天的工作时间为8 h，但是由于每条路线巡检耗时和路程耗时不同，存在细微的时间差，为了让每位巡检人员在上班时间段内的工作量尽量平衡，所以每个巡检人员每次上班的路线都实行轮换制来巡检以上5条路线。

5.2 问题二

考虑到增设条件：巡检人员每巡检2 h左右需要休息一次、休息时间为5～10 min、在中午12时和下午6时左右需要有30 min的进餐时间。

5.2.1 建立模型

假设三班倒的时间为2：00-10：00；10：00-18：00；18：00-2：00。为节省时间，假设每工作2 h的休息时间为5 min，两次进餐时间分别为巡检人员的上班前和下班后，先优化上班时间，使进餐时间分别在交接班处。综上所述，调整巡检人员的三班倒的时间为3：00-12：00，12：00-18：00，18：00-3：00，时长分别为9 h、6 h、9 h。

设Xi为巡检所需的最少人数；li为巡检耗时时间（i=1，2，…，26）；

kj为路程间的耗时时间（j=1，2，…，31）；Ti为第i个巡检点的巡检周期，建立目标函数：

min∑Xi=li+kj（模型II）

min■|A-360|（i=1，2，3，4，5，…，n）

（A为6 h的巡检耗时时间）

min■|B-540|（i=1，2，3，4，5，…，n）

（B为9 h巡检耗时时间）

s.t

Ti≤Ti≤35，（i=1，3，4，6，8，9，11，12，14，15，16，18，19，20，22，23，24，26）；Ti≤80，（i=7，13，21）；Ti≤120，（i=10，25）；T2≤50；T17≤480；T5≤72；

5.2.2 求出人数

通过Excel软件对模型II进行数据处理分析，得到Xi=5。

结论：9 h和6 h每班都需要5名巡检人员，所以一天需要15名巡检人员。

5.2.3 确定路线

由穷举法：分区域划分优先考虑回路的方式，再安排折回的方式，得出以下5条路线：①22→20→19→2→4→21→22；②23→24→9→25→26→23；③7→5→3→1→14→8→3；④17→6→10→12→6；⑤15→18→16→13→11→15。

5.2.4 安排时间

按每一班的时间表进行数据整理，由此我们得出三班倒的巡检时间安排表（见表3），下面给出12：00-18：00的巡检时间表。

因为巡检人员每天工作时间分别为6 h、9 h、9 h，并且每条路线巡检耗时和路程耗时不同，存在细微的时间差，所以为了确保在一个时间段内的工作量尽量平衡，要求每位巡检人员都要在6 h、9 h、9 h进行三班倒，因此可以考虑5天换一次班次，在这5天内每次上班的路线都需要轮流走这5条路线，走完5条路线就必须让巡检人员进行一次换班。

记5名巡检工人为a、b、c、d、e，5条线路用1、2、3、4、5标记，得出这5名工人轮换早班、中班、晚班的巡检线路表（见表4）。

5.3 问题三

5.3.1 问题一：错时上班

对于问题一，采用错时上班的时间，由于没有考虑休息时间，每人的巡检时间都为8 h，只是上班时间不同步。因此用同样的办法可以知道问题三中错时上班每班需要5名巡检人员，一天需要15名巡检人员，已经达到最优化，所以错时上班并没有起到节省人力资源的作用。

5.3.2 问题二：错时上班

对于问题二，采用错时上班的时间，考虑到中午12点、下午18点左右巡检人员需要进餐，针对问题二中10：00-18：00这一班，午餐时间5名巡检人员轮流去吃午餐（共花费30 min），若不考虑换路线，则每条路线安排2名巡检人员，10名巡检人员可以确保各个站点的巡检；若考虑换线路，则需要增加2名工人进行替换，这班共安排7名巡检人员。其余两班并没有进餐时间的影响，每班各有5名巡检人员，所以一天需要17～20名巡检人员，因此错时上班时间并没有起到节省人力的作用。

6 模型评价与分析

本文应用穷举法将复杂的数据进行处理，采用Excel工具产生巡检人员的排班表，并且联系实际生产，可以运用到生产中的各种排班问题上，实现巡检路线的最优化。但本模型的计算机自动化程度不高，没有能够编写程序实现全自动化排序。此外，安排的时间表具有一定的偶然性，普遍性不强。

参 考 文 献

[1]姜启源，谢金星，叶俊.数学模型[M].第3版.北京：高等教育出版社，2003.

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

[3]佚名.排班问题的最优数学规划[EB/OL].https：//wenku.

baidu.com/view/ab88b7834431b90d6d85c721.html？qq-

pf-to=pcqq.discussion，2015-08-21.

[4]佚名.基于線性规划的护士排班优化问题[EB/OL].http：//www.nexoncn.com/read/51fc68bb0a70fc16056d

7633.html，2011-07-15.

[责任编辑：钟声贤]