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

陈辉

(安徽商贸职业技术学院， 安徽芜湖214002)

引言

巡检线路的优化设计在电力设备维护、社区安全巡视和车间设备检测等生产和生活的各个环节都有着重要的应用[1-7]，近年来，结合无人机和智能化手持设备等现代化技术手段的使用，大批学者展开了相关领域的研究。郭国法等在巡检地点及巡检人员经过的路线上安装RFID阅读器，用于车间巡检人员的跟踪定位[8]；汤坚等提出了利用多旋翼无人机RTK差分定位技术等无人机航测系统技术，研发了面向电网巡检的无人机智能操作系统及控制终端[9]；胡万才介绍了一种基于计算机网络技术，实现对机务段设备的巡检管理[10]。新技术设备和检测方法不断引入的同时，路径优化方面的研究也在不断推进。熊鹏文等提出了一种基于改进概率地图法的电力线巡检飞行机器人路径规划方法[11]；柳长安等提出了一种适用于核电站巡检与应急机器人的有效局部路径优化方法[12]；还有部分学者将巡检业务抽象为VRP问题(车辆路径问题)进行求解，以总耗费时间和巡检车辆数量为优化目标，利用蚁群算法和遗传算法等智能算法得到最优巡检方案[13-16]。2017年全国大学生数学建模竞赛D题考察了某化工厂有26个点需要进行巡检以保证正常生产，每个点每次巡检需要一名工人，工人可以按固定时间上班，也可以错时上班[17]。本文提出在保证正常安全生产的前提下，这种巡检线路的优化问题与VRP问题并不等价，建立了确定巡检人数和优化巡检路线的数学模型，通过求解模型得到了车间生产安全巡检的完整解决方案，使得所有点都能按要求完成巡检，并且耗费的人力资源尽可能少，同时还应考虑每名工人在一时间段内的工作量尽量平衡。本文求解检路线设计和值班安排的方法、策略在边境线执行巡逻问题、医院病房护理巡视等场景下都可以直接应用。

1 问题分析

通常，某生产车间有若干个关键点需要进行巡检以保证正常生产，每个点每次巡检需要一名检测工人耗费一定的检测时间，而且每个点必须在一个确定的时间周期内重复检测。检测工人按三班倒上班，保障机器每天24小时不间断地安全运行，每天可以固定时间上班，也可以错时上班，在调度中心得到巡检任务后开始巡检。此时，需要安排巡检人数和巡检路线，使得所有点都能在每个巡检周期内得到检测，并且耗费的人力资源尽可能少，同时还应考虑每名工人在一时间段内(如一周或一月等)的工作量尽量平衡。

记集合V={Vi|i=1,2,…n}为巡检点。G(V,E)为巡检路线连通图，其中E⊂V×V为连通图的边。ti为检测第i个巡检点的耗时，zi为第i个巡检点的巡检周期，即巡检点Vi必须在小于等于zi的时间间隔内被检测一次，以保证正常生产安全。一个典型的26个巡检点任务采用每天三班倒，具体情况如图1所示，同时需要兼顾人力资源使用量、工作量的平衡、人员的休息和用餐以及错时上班等因素[17]。

为满足巡检任务要求，对应的路线规划和人员值班安排应满足如下条件。

(1)巡检点必须严格地满足全天24小时在巡检周期内得到检测，包括交接班过程。

(2)巡检人员在每班开始工作时在巡检调度中心领取任务，再到指定路线巡检，巡检过程中不需要再回到调度中心。

(3)工作时间包括赶往指定巡检路线的行走时间，上、下班时间以进入、离开调度中心为准。

(4)巡检人员如在巡检过程中发现巡检点出现异常，不需要回到调度中心汇报(可以通过无线通讯)，按既定路线继续巡检。

图1 巡检连通图

这种巡检线路排班的规划和车辆路径问题(Vehicle Routing Problem，VRP)有类似之处[18]，但并不完全相同。主要差别在于车辆路径问题是通过规划行车路线，由配送中心向各站点提供货物，使得客户的需求得到满足的同时，达到诸如路程最短、成本最小、耗费时间最少等目的[19]，问题求解的结果为单次行程的路径。巡检线路排班的规划还需要兼顾多次巡检圈次、各个班次的衔接问题，以及值班人员的休息和工作量平衡。这包含两方面的内容，路径的规划和人员值班的时间安排。

2 巡检路线的规划

巡检路线规划思路是将巡检联通图分解为若干TSP问题，每条TSP通路由一个值班人员巡检，这就要求每条通路上所有巡检点的巡检周期不能大于这个值班人员单次巡检的工作时间。通过0-1指派来安排某检测点由经过该点的哪位工作人员负责检测。

2.1 巡检路线分析

记巡检人员为RYi，i=1,2,…,m，

i=1,2,…,m，j=1,2,…,n

i=1,2,…,m，(Vq,Vh)⊂E

每个巡检人员安排的巡检任务时间为SJi，包括路程时间和所负责的检测点检测时间，则

(1)

其中，tj为检测第j个巡检点的耗时，dqh为从第q个巡检点到第h个巡检点所用的时间。

对于每一个指定的巡检人员RYi，通过Xiqh指定的边应该构成一个回路，这个回路上的每一点的出度和入度相同，

(Vj,Vh)⊂E，(Vk,Vj)⊂E

(2)

uij-uih+nixijh≤ni-1，(Vj,Vh)⊂E

(3)

其中，ni为人员i走过的路径长度。

2.2 巡检路线约束条件

巡检人员RYi路线上需要其检测站点的检测周期不能大于路线时间，否则无法及时检测：

SJiYij≤zjYij，i=1,2,…,m

j=1,2,…,n

(4)

其中，zj为第j个巡检点的巡检周期。

每一个检测站都需要有人员负责检修：

(5)

RYi负责检修的站点必须在其经过的路线上：

(Vj,Vh)⊂E

(6)

通过上述分析，在目标函数为每个巡检路线的工作时间尽量均衡情况下，由(1)式～(6)式得到巡检路线搜索模型，

min maxSJi

(7)

S.T.

i=1,2,…,m，(Vj,Vh)⊂E

(Vj,Vh)⊂E，(Vk,Vj)⊂E

uij-uih+nixijh≤ni-1，(Vj,Vh)⊂E

SJiYij≤zjYij，i=1,2,…,m，j=1,2,…,n

2.3 巡检路线求解

上述模型可以在Lingo中实现[20]。针对文献[17]中的问题，在使用计算机进行求解时，还可以根据实际情况进行手工干预。如可以将图1中的22→21→4→3→2→1→2→19→20→22指定给人员1，23→24→9→25→17→8→6→3→2→4→23指定给人员2等。经过若干次调试，可以得到巡检路线安排，如图2所示。具体参数见表1，表1中路线标示为阴影的部分代表经过该检测点而不进行检测。

图2 巡检路线示意图

表1 (单位：分钟)

路线223→24→9→25→17→8→6→3→2→4→23实际耗时时间31224321010201312304035周期3535341203550

路线325→17→8→6→10→12→15→26→25实际耗时时间0121320506220623035周期353535480

路线411→15→18→16→13→11实际耗时时间3722233252031周期3535353580

路线56→14→6→5→7→6→10→6实际耗时时间31310222240525032周期35353572080120

由表1可知，每班次安排5人即可完成所有26个检测点的巡检任务。在5条路线中，有两条路线的巡检时间刚好为35分钟，一条为34分钟，其余分别为32分钟和31分钟，由于所有的路程和巡检总时间为145分钟，这种路线安排效率较高。

3 巡检时间安排

3.1 固定上班时间巡检时间安排

如果采用每天三班倒按固定时间上班，所有工人严格执行8∶00早班开始从调度中心出发，赶赴各巡检路线开始值班。根据前文的分析，每班安排5人即可满足巡检要求。为使得耗费的人力资源尽可能少，需要选择每条巡检路线上距离调度中心处路径最短的起止点，让上一班次人员继续巡检(换班人员正在赶去的路上)产生的加班时间尽可能小。每个班次8小时，合计480分钟，每条路线巡检周期为35分钟，在固定上班情况下(不能提前上班)，每班工作人员必须巡检满14次直到接班人员达到指定位置。具体情况见表2。如巡检路线1，就近选择22检测点为路线起始点，490分钟后，检测完14次，在22∶00下班，加班时间为10分钟。此时，每次换班时，所有检测点提前了10分钟检测。

表2 固定上班时间巡检时间安排

注：有效工作时间去除了巡检过程中等待的时间。

3.2 固定上班时间轮班安排

不同线路工作人员的加班时间不同。为保证每个人员工作时间尽量均衡，需要在一定的周期(这里取一周7天)内安排在不同的路线上轮班，第一天如果在工作加班时间较长的路线4上巡检，第二天可以调换到工作时间较短的路线5上。因为按固定时间上班，三班倒的早、中、晚每班情形相同，只需按同一方案轮班。为给出优化的轮班方案，建立指派问题的优化模型。记

RYi，i=1,2,…,5为巡检人员。

DAYj，j=1,2,…,7为一周的各天。

Wk，k=1,2,…,5为5条不同的路线。

Tk，第k条路线上的工作时间，见表3。

则，每个人员在一周工作的时间总长为

(9)

每人每天安排且只能安排一条线路

(10)

每天每个线路上安排且只能安排一人

(11)

目标是使得SCi，i=1,2,…,5尽可能均匀。由(10)式和(11)式得到轮班安排优化模型：

minVar(SCi)

(12)

s.t.

计算所得的排班结果见表3。

表3 固定上班时间的人员路线分配表

如在周一1-5路线上安排编号分别为4、3、5、1、2的工作人员，其余类推，则人员一周的工作时间分别为3466分钟、3466分钟、3467分钟、3467分钟和3466分钟，因此每个人员工作时间得到了较大程度的均衡。每天平均工作时间为8.2524小时或8.2548小时。每天的早、中、晚班都可以类似安排。如果考虑均衡的是有效工作时间，可以类似得到人员一周的有效工作时间均衡为2963.78分钟、2978.00分钟、2945.06分钟、2982.38分钟和2967.14分钟。

3.3 错时上班时间巡检时间安排

按固定时间上班，下一班次接班人员不能提前上班，每个路线上的人员必须在一个班次内巡检完成14个周期，导致每条线路上的所有检测点在换班时被提前了10分钟检测。这种“浪费”是由于每个班次的上班时间8小时折合480分钟不能被35分钟整除导致的。计算出每天时长24小时和35分钟的最小公倍数为LCM(24×60,35)=10 080分钟，折合10 080/60=168小时，合计168/24=7天。这意味着，一周的时间段长度是路线巡检周期35分钟的整数倍，共计288个圈次。如果没有固定上班时间，可以事先在一周的时间段内固定这288个圈次的检测时间节点，按照错时上班，每个路线上的人员可以提前上班到达检测路线，严格按巡检时间节点到达巡检路线，这样可以避免提前10分钟检测造成的“浪费”。考虑到早、中、晚班次人员工作时间需要均衡，将这288个圈次安排在一周的时间内(表4)。

表4 错时上班每周班次巡检圈数安排

一周内每条路线在每个班次开始检测的时间见表5。

表5 错时上班每班次所有路线开始检测的时间

除去从调度中心走到各路线起始点的时间，得到各路线在各班次的提前上班时间。再根据各路线的实际工作时间，可以计算出各班次的下班时间(表6)。根据这种上下班安排，每周可以节约总的工作总量为35×6×5=1050分钟。

表6 错时上班每天不同班次所有路线上的人员上下班时间表(路线1)

4 结束语

本文主要解决了对工厂巡检点进行及时巡检的问题，同时兼顾人力资源使用量、工作量的平衡、人员的休息等因素。建立并求解路线搜索的数学模型，设计了巡检路线，每条路线的工作人员工作时长不超过巡检点的巡检周期。通过求解指派问题模型还解决了工作量均衡问题。最后指出，错时上班的关键作用在于，在三班倒换班交接时，可以错开各路线巡检周期的重叠，这是固定时间上班时无法避免的，同时计算了错时上班每周节约的工作总量。这些结果在边境线执行巡逻问题、医院病房护理巡视问题、通讯网络设施检测等场景下都有应用参考价值。

[1] 赵娟平.基于GPS的电力巡检系统[J].微计算机信息,2007,23(1):252-253.

[2] 毛丰江,李正中,路勇.基于RFID数据终端的智能化小区物业巡检系统[J].微计算机信息,2006(14):212-214.

[3] 顾海红.大型港口机械巡检周期的确定[J].水运工程,2007(8):52-55.

[4] 张国立.海底管道巡检船的设计和功能配置[J].中国造船,2016,57(1):54-60.

[5] 石远鹏,姜建军,郑德宇,等.输电线路巡检的路径规划与建模[J].应用科技,2011,38(11):18-21.

[6] 高振豪,苏贵影,李彦华,等.工作要素在装配线中分配与其平衡率的研究[J].四川理工学院学报:自然科学版,2017,30(6):89-92.

[7] 张民悦,连爱玲.修理设备可修且部件修复非新的温贮备可修系统[J].四川理工学院学报:自然科学版,2017,30(4):74-80.

[8] 郭国法,卢运栓,张开生.适用于车间巡检定位的改进RFID定位算法[J].实验室研究与探索,2016,35(12):29-33.

[9] 汤坚,杨骥,宫煦利.面向电网巡检的多旋翼无人机航测系统关键技术研究及应用[J].测绘通报,2017(5):67-70.

[10] 胡万才.设备智能巡检管理系统设计与应用[J].铁道机车车辆,2009,29(5):63-65.

[11] 熊鹏文,宋爱国,东辉.基于效率与安全机制的核电站巡检与应急机器人的局部路径优化方法[J].机器人,2015,37(2):196-203.

[12] 柳长安,刘春阳.电力线巡检飞行机器人路径规划方法[J].华中科技大学学报:自然科学版,2010(1):117-120.

[13] 刘志硕,申金升,关伟.车辆路径问题的混合蚁群算法设计与实现[J].管理科学学报,2007(3):15-22.

[14] 尹晓峰,杜艳萍.车辆路径问题的蚁群算法研究[J].太原科技大学学报,2005,26(4):279-283.

[15] 何冰,季建华,刘新平,等.基于遗传算法的城市输电网络巡视路径优化选择问题[J].计算机应用研究,2013,30(8):2276-2279.

[16] 李铭钧,甘团杰,赖奎,等.考虑杆塔风险概率的输电线路巡检路径优化方法[J].电网与清洁能源,2016,32(10):61-67.

[17] 全国大学生数学建模竞赛2017年赛题[DB/OL].http://mcm.blyun.com/front/detailTopic.

[18] DANTIZIG G,RINSER J.The truck dispatching problem[J].Management Science,1959,6(1):80-91.

[19] PAOLO T,DANIELE V.The vehicle routing problem[M].philadephia:Society for Industrial and Applied Mathematics,2002.

[20] 谢金星,薛毅.优化建模与LINDO LINGO软件[M].北京:清华大学出版社,2005.