基于NP问题的机巡计划编排研究

廖建东，陈 浩，柳亦钢

（广东电网有限责任公司机巡管理中心，广东 广州510000）

随着国民经济的快速发展，生活与工业用电量与日俱增，使得我国用电需求不断增加，电网的规模也随之越来越大。与此同时，电力巡检工作也遇到了前所未有的挑战。为了确保输电线路安全可靠，需定期对输电线路进行巡检。然而，输电线路分布区域广，监测成本高，现阶段状态评估技术在分析准确性和实施经济性上还有所欠缺，故目前大部分电网公司仍采取“人巡+机巡”协同的定期巡检的方式来维护输电线路[1]。但定期巡检存在人工成本高、效率低、工作计划安排不合理等现象；现有的机巡计划编排方式已逐渐无法满足未来的机巡作业管理需求。所以迫切需要构建一整套机巡计划智能编排方案，实现对机巡计划的高效编排。目前，中国南方电网公司已经建立了完善的机巡作业中心，实现了定期机巡计划的智能编排，极大缩减了编排的时间。

1 机巡作业调度方案设计流程

智能调度方案可以有效覆盖各条输电线路，且在规定期限内完成巡检工作。智能调度算法需要根据电网运维管控流程要求进行设计优化。例如，广东电网有限责任公司2019年版《输电线路运维策略及管控机制实施细则》[2]，输电线路运维管控工作流程包括：

（1）开展输电线路状态评价，确定健康度；

（2）开展输电线路重要性评估，确定重要度；

（3）根据输电线路风险矩阵，确定管控级别；

（4）制定输电线路运维管控策略，明确管控要求；

（5）制定工作计划，开展输电线路运维。

依据该工作流程，按照年度机巡计划设计调度算法，年度机巡计划调度方案设计流程如图1所示。考虑到机巡作业中心需要为广东省14个地市制定年度机巡计划，涉及的输电线路数量庞大、地域分布广，年度机巡计划本身也是多目标优化问题，属于“NP问题”[3]，求解过程复杂，算法时间复杂度高，直接对年度机巡计划进行求解可能会导致优化算法实时性较差等问题。鉴于目前南方电网实施的是集约化巡视方式（地市的机巡任务会被机巡队集中在一段时间内完成），因此可以将年度机巡计划自下而上分为两个层面来求解：

图1 年度机巡计划调度算法设计流程

（1）地市层面。机巡作业中心得到地市上报的机巡任务需求，即待巡线路的巡视方式、各杆塔位置、巡视路段长度等信息后，先对地市内的机巡任务进行规划，得到一个机巡队情况下，集约化执行对应机巡任务所需要的时间，作为省级层面优化的输入数据。

（2）省级层面。通过“地市层面”的规划，机巡作业中心可以将原来14个地市的分散机巡任务需求看作“14个大的机巡任务”，只需要考虑以合理的间隔和方式，将“14个大的机巡任务”优化到下一年度中不同的季度和月份中去，避免陷入到地市详细机巡任务的细节里面。

2 机巡作业调度算法设计内容

在一条输电线路中，由于空域环境和地理环境的限制，可能需要进行分段处理，比如在具备直升机飞行的路段，采用直升机精细化巡视和直升机通道巡视；在不具备直升机飞行但可以固定翼飞行的路段，采用固定翼通道巡视；在直升机与固定翼均不可用的路段，采用人工巡检为主，多旋翼无人机辅助，在特殊情况路段，可视情况放弃巡检。

为此，机巡作业中心在收到各地市供电局上报的“待巡线路需求模型”后，结合机巡作业资源能力模型，建立模型合理的安排机巡的任务执行序列，最大程度发挥出机巡资源的能力，规划出实现各地市年度巡视任务所需的巡视任务执行时间，包括直升机精细化巡视时间、固定翼通道巡视时间和直升机通道巡视时间，并将该规划结果保存到机巡调度优化规则模型，作为机巡作业中心制定年度计划的输入数据之一。

地市年度巡检时间规划问题是指利用现有的不同类型的机巡资源（无人机和直升机），对若干空间分散的输电线路布置区域，按照输电线路管控级别等要求确定日常巡维的调度计划，即在满足不同巡视任务需求、作业区域地理条件、任务时间窗、机巡作业种类、数量和性能等约束下，为机巡资源分配巡视任务和地面调度方案。如图2所示，机巡资源从基地出发，按照调度方案的任务执行流程，经地面调度抵达任务的起降场，依次完成各自的任务。每个电网巡视任务代表一个作业区域，包含不同等级的杆塔点和输电线通道。

图2 机巡作业调度示意图

地市年度巡检时间规划问题可归纳为有容量约束的路径规划问题，即机巡作业基地为各输电线路提供巡视作业服务，机巡作业基地的每种作业资源（直升机或无人机）都有巡视作业时间长度的限制，通过安排科学合理的作业资源巡视路线，使得一定数量的作业资源从机巡作业基地出发，完成巡视任务后返回机巡作业基地。

2.1 场景应用假设

结合机巡任务需求以及复杂的作业环境，调度算法研究基于以下假设：

（1）在作业过程中，作业质量不随调度方案发生变化。

（2）一个机队拥有一种机巡作业资源，比如直升机或固定翼无人机，若干工作人员，由车辆运载转移。

（3）机巡资源作业效率恒定且作业过程中无故障。

（4）机队每日可工作时长固定，一周为五个工作日，可开展机巡作业和空域管辖地面转移，其余时间为非作业时间。

（5）一个机队可以为多个输电线路提供巡视作业服务，但是每个待巡输电线路只能由单个机队完成巡视任务。

（6）只有一个机巡作业基地，且所有的作业资源均以机巡作业基地为起点，分配的所有巡视作业资源完成后返回机巡作业基地。

（7）各待巡输电线路附近具备提供机巡作业资源的后勤保障能力，包括直升机加油、无人机充电，提供巡视工作人员住宿等，规划中认为作业资源具有持续作业能力，不考虑作业资源维护或者故障、恶劣天气、道路拥堵等因素的影响。

（8）作业资源的类型单一。

（9）机巡作业基地和待巡输电线路的位置坐标已知。

（10）所有距离采用欧几里得距离表示。

2.2 方案模型设计

为了更加清晰准确的描述模型，对模型中使用的符号进行如下定义：

（1）R表示机巡资源集合，R={R1，R2，…，Rr}表示直升机资源或固定翼资源，注意模型中仅具有单一机巡作业资源。

（2）r表示机巡资源的数量，对机巡资源的描述主要包括位置、所携带传感器、直升机性能（巡视航程，使用后维护时间，巡视速度等）或固定翼无人机性能（巡视航程，使用后维护时间，巡视速度等）等，具体数据来自机巡作业资源能力。

（3）M为巡视任务集合，M={M1，M2，…，Mm}，m为该地区巡视任务的个数，对巡视任务的初始描述主要包括任务数据需求（精细化巡视、通道巡视）、巡视长度、输电线路位置和任务优先级等，具体数据来自待巡线路需求模型。

（4）机巡资源的巡视时间记为T={T1，T2，…，Tr}。

（5）机巡资源Rj执行巡视任务Mi预计所需时间为ti，j，假设机巡作业资源巡视速度固定，通过巡视方式以及巡视距离，即可确定巡视时间。

（6）机巡资源集合R的开始任务位置集合PR={Pj，j=1，2，…，r}，应均位于机巡作业基地。

（7）巡视任务集合M的完成任务位置合集PM={Pi，i=1，2，…，m}。

（8）任意两点之间的地面调度距离为dPi，Pj，地面转移时间记为tPi，Pj，其中Pi和Pj∈（PR∪PM）。若两个机巡任务之间无需通过地面，直接由固定翼无人机或者直升机飞行过去，则dPi，Pj表示机巡任务Pi和Pj之间的空中距离，tP，Pji表示直接通过空中转移的时间。

（9）机巡资源Rk从待巡线路Pi转移到Pj的状态变量xi,j,k，

（10）任务Mi执行的决策变量为yi,k，

（11）作业成本C ost={costw，costt}，其中costw为机巡队单位距离的使用成本，包含机具折旧、人工费用和动力费用等；costt为机巡队单位距离的转移成本，主要为车辆燃油消耗和驾驶员人工费用。

（12）机巡作业资源作业时长Q表示每个机巡作业资源在该次分配中应该承担的作业时长上限，Q估算如下：

其中，r表示各机巡作业资源应该尽可能平均的执行巡视任务。

基于以上的假设条件和参数定义，建立地市年度巡检时间规划问题的数学模型如下：

其中式（4）为目标函数，前二项为作业成本，最后一项为惩罚函数Pon，表征作业资源之间作业任务分配的不合理些，wi为权重；式（5）保证每次配送任务都以配送中心为起点和终点；式（6）保证每个待巡线路有且仅能被服务一次；式（7）保证每个机巡作业资源的巡视时长总和小于作业资源的的额定巡视时长；式（8）表示为待巡线路服务的集训数量总数小于机巡作业基地所拥有的作业资源总数；式（9）表示决策变量x、y，是0-1变量。

3 结束语

由于机巡作业变量的离散性，机巡计划调度问题是为实现各地市输电线路巡查需求而对共同使用的作业资源实行时间分配，是一个典型的组合优化问题。通过利用精确算法求解NP难问题，即使能得到最优解，也存在所需计算时间过长，难以直接应用。因此，可以采用近似算法，通过输入上述方案模型所需参数进行求解计算。基于智能优化的近似算法是基于一定的优化搜索机制，并具有全局优化性能的一类算法[4]。常见的算法有：模拟退火算法（SA）、遗传算法（GA）、蚁群算法（ACO）、路径重连算法（PR）、迭代局部收缩算法（ILS）、禁忌搜索算法（TS）、分散搜索算法（SS）、粒子群算法（PSO）等等。作为一种通用算法框架，智能化算法主要是针对具体问题对框架结构进行局部修改，具有较好的实践通用性，且能在较快地处理大规模数据的同时得到可接受的解，在工业实际问题组合优化求解方面具有一定优势。