基于旅行商路径与任务指派的风力发电设备检修问题研究

邓 佳，谭代伦

风能是一种具有无污染、分布广泛、可循环利用等优点的可再生资源［1］，风能发电在我国发电系统的占比呈逐年上升趋势［2］.其中，维护风力发电设备正常运行、保持较高的日均发电效率［3−4］，是风力发电运营公司日常需要解决的重要问题.

当风力发电设备数量较多时，电力运营公司不得不组织一定数量的检修小组，依靠合适的运输工具将检修小组送达故障设备处完成检修任务.对一批待检修的风机故障任务，是否能及时有效地完成，对公司降低成本、提高效益具有重要作用.为此，在风力发电设备的故障检修过程中，存在着运筹学领域中的优化问题，对其进行研究，对电力公司的高效运营和维修具有较强的理论与实践意义.

该类问题不仅包含了沿某种路径完成维修小组的运送，还包括了根据人员特性和故障需求进行合理的任务指派，前者更具有TSP问题［5］的特征，后者则比较符合运筹学中的AP 问题的特征［6］，因此它属于这两类基本运筹学问题复合而成的组合优化问题.由于设备数量多、场地面积大，这类复合型问题尤为突出，在其他领域也有类似情况.

对此，国内外学者展开了相关研究.在国外，TANG 等［7］于2007 年利用禁忌搜索算法求解了一类带时间依赖的计划调度问题.BAYS等［8−9］利用运筹学知识研究了一艘母舰携带一定数量的、带有不同特定任务的无人小艇在某一片海域进行施放或回收作业问题.RASHIDNEJAD 等［10］研究了将维护调度与车辆路由相结合问题并利用遗传算法求解.MOSAYEBI 等［11］提出了带工作时间的TSP 问题，给出了数学模型并设计了启发式搜索算法进行求解.目前，国内对该类问题的研究还较少.陈峰［12］研究了运筹学在整车物流智能调度决策支持系统的应用.袁玮等［13］研究了运筹学在海上油田直升机智能航线规划中的应用.周忠彬等［14］研究了运输排程优化模型在海上批量伤员运送中的应用.

本文基于风力发电设备检修场景，研究基于TSP 路径与任务指派的MWPEP 问题，分析并建立数学模型，既拓宽了运筹学知识的应用，也对企业的经营管理具有较强的借鉴意义.

1 问题提出

在风力发电运营与管理的全过程，即使只考虑设备检修环节，需要考虑的因素也比较多，为此需要对问题作一些必要的简化，使问题具有基础性和代表性.

①只考虑有一辆运输工具的情形，它从固定的检修中心出发，装载上全部检修小组及物资后，沿一定路线依次经过每一个待检修的故障设备点，到达故障点后被指定的检修小组马上开始检修工作，运输工具则继续前往下一个故障点，完成全部运送任务后回到起点.对每一个故障点，过且只过一次，以保证不遗漏也不重复.合理地规划路线，将有利于尽早把检修人员送达现场.

②对于检修人员与故障设备，假设每一个设备点所出现的故障现象并不完全相同，成功检修故障所需的时间也因而不同；另外，不同检修人员对不同类别故障现象的检修水平也各有不同，相应的每个检修小组完成每一个故障设备的检修时间也不完全相同.任务的指派规则是每一个检修小组只承担一个故障点的检修任务，反之每一个故障点的检修任务只被一个检修小组完成.合理地进行故障检修任务的指派，将有利于尽早完成全部的检修任务.

综合考虑运送与任务指派，问题的总体目标是规划一条最优的运送路线和检修小组的最优指派，使得全部检修任务能尽早结束.其中，运输工具的行进速度视为匀速，检修小组对每一类故障现象的检修时间可经统计或测试获得.

基于以上问题描述，为完成风力发电设备的检修任务，需要综合运用基于TSP 问题的路径规划方法和AP 问题的任务指派方法，本文将其称为基于TSP 路径与任务指派的一类MWPEP 问题.

2 建立MWPEP 问题的数学模型

根据问题提出，MWPEP 问题的目标是要求尽早完成全部检修任务，即使整体完工时间最短.容易发现，对任意一个检修小组，它的检修任务完工时间由两个部分组成：一是运输工具从检修中心（即TSP 中0 号路径点）出发将此检修小组运送到达某个故障点所需的时间；二是到达故障点后检修小组完成该故障任务检修所花的时间.由于到达时间有先后，各个故障点检修任务的完工时间有所不同，因此要使整体完工时间最短，则需使所有检修小组的到达时间和检修时间之和中的最大者尽量小.其中，到达时间由按TSP 问题特征进行路径规划的结果所决定，检修时间由按AP 问题特征进行任务指派的结果所决定.

鉴于此，下面先给出必要的数学符号和变量，再基于TSP 问题和AP 问题分别从两个方面进行分析和建模.

2.1 符号与变量

不妨设共有n个故障点，依次记为1，2，…，n，检修中心记为0 号点，任意第i个点的坐标记为pi(xi，yi)，i=0，1，2，…，n，这里假设所有点均在一个平面内，而不考虑具体的山区或海上情形.运输工具以匀速行驶，速度记为V0.共有n个检修小组，任意第j个检修小组完成第i个故障检修任务的时间记为cij.

对所有路径节点（包括设备故障点和检修中心），设任意两点之间的距离为dij，按欧式距离公式计算，公式为：

式中：i，j=0，1，2，…，n.

经过该段路程dij所花的时间为：

2.2 基于TSP 路径与任务指派的建模

对MWPEP 问题，基于TSP 路径与任务指派进行建模，主要是指在TSP 行走路径基础上考虑任务指派所形成的设备检修时间的叠加.为此，不妨设任意一轮检修设备及人员运送形成的TSP 路径及任务指派的检修小组如下：

式中：v0为0 号检修中心，vi，ui∈{1，2，…，n}分别为不重复的任意一个设备故障点和任意一个检修小组.

因此，各检修小组被运送到设备故障点的到达时间和完成检修任务的完工时间可沿路径点依次计算，结果如表1 所示.

表1 基于TSP 路径与任务指派的变量构造

借鉴基于路径构建的TSP 问题的数学模型，记任意一条运送路径为V={v0，v1，…，vi，…，vj，…，vn}，对应检修小组的任意一个指派为U={u1，u2，…，ui，…，uj，…，un}，则MWPEP问题的数学模型（记为模型Ⅰ）可表示为：

上述模型的目标是使各个检修小组的完工时间最大最小化，它依赖于运送路径，也依赖于指派方案.此外由表1 可知，模型中运送到每一个路径节点的到达时间TVi与前一个节点的到达时间TVi−1形成累加关系，在模型中也可以由递推关系式表示为：

2.3 基于0-1 型决策变量的建模

TSP 问题的0−1 规划模型 和AP 问题的模型均基于0−1 型决策变量进行建模，其优点是比较容易刻画路径节点被唯一经过、维修任务与检修小组的唯一分配等对应关系，但这种对应关系无法体现出路径节点被经过的先后顺序，因此无法按表1 刻画出每一个节点的到达时间，相应的检修时间也无法累加进去.

基于此，除继续采用关于TSP 路径和任务指派的两种0−1 型决策变量外，还将运送到达任意一个节点的到达时间也作为一组决策变量，并对其进行约束.

为此，设TSP 的路径节点集为V={1，2，…，n}，待分配的任务集为U={1，2，…，n}.在节点集V中，0 为检修中心，是出发的起始点，不分配检修小组.问题的主要决策变量及定义如下：

Ti：运送到第i个故障点的到达时间.式中：i，j，k=1，2，…，n.

决策变量xij，yik仍然分别用于约束运送路径和任务指派关系的生成，结合变量Ti可表示检修任意第i个设备故障点处的完工时间为：

式中：cik为第k个检修小组对第i个设备故障点的检修时间.

根据AP 问题的基本约束，对于任意i，决策变量组{yi1，yi2，…，yin}必只有一个取值为1，因此式（1）就是任意第i个设备故障点处的到达时间和检修时间之和，即第i点的完工时间.

于是，MWPEP 问题要使运送与检修总体完工时间最短的目标可以表示为：

下面对Ti构建必要的约束，运送到第j个设备故障点的两种情形如图1 所示.

图1 运送到达第j 点的两种情形

由图1（a）可知，当起点从0 号点出发时，必有

类似地，当最终从任意第i个设备故障点返回0 号起点时，必有

由图1（b）可知，当从任意第i点向第j点运送时，必有

综合TSP 问题、AP 问题的0−1 规划模型，以及式（1）～式（4），可建立MWPEP 问题基于0−1 型决策变量的数学模型（记为模型Ⅱ）如下：

3 MWPEP 问题算例与模型分析

前面已经建立了MWPEP 问题的两个数学模型，其中，模型Ⅰ的建模过程简单直观，可以通过列举一个方案，描述清楚模型Ⅰ的可行解和目标函数值的形成过程.而对模型Ⅱ直接构建可行解，其目标函数值计算过程与模型Ⅰ相似，在此不再对模型Ⅱ进行举例计算.在模型Ⅱ中，为刻画到达节点的先后顺序，构造了一组运送到第i个故障点的到达时间作为决策变量，下面对模型Ⅱ中构造的决策变量做详细分析.

3.1 MWPEP 问题算例

现设需要维修的设备故障点有5 个，编号为1，2，3，4，5，起点记为0.为简化计算，直接给出任意两点之间的运送时间，不再给出距离矩阵和速度.相应地，检修小组有5 个，编号记为A，B，C，D，E，给出任意设备故障点对应检修小组的检修时间，相关数据如表2 所示.

表2 MWPEP 问题算例的运送时间和检修时间数据

注：表2 中任意两路径点之间的运送时间即为模型Ⅰ中的矩阵T=(tij)，指派给任意路径点的检修小组所对应的检修时间即为模型Ⅰ中的矩阵C=(cik)，且表中时间数据的单位均为分.

3.2 基于算例对模型Ⅰ的分析

在模型Ⅰ中，首先规划了一条TSP 运送路径，然后在路径的基础上分配任务指派的检修小组.其中，运送到达每个路径点的时间与检修小组完成工作需要的检修时间之和，就是检修此路径点的完工时间.所有路径点的检修完工时间中最大值为最大完工时间，最大完工时间与运输返回起点时间中较大者，即为目标函数值.

假设一轮运送路径及任务指派的检修小组为：0 →2(D) →1(C) →4(A) →5(E)→3(B)→0 记为方案1，参照表1 的计算公式可得出方案1 任意路径点的到达时间、检修时间和完工时间，如表3 所示.

表3 方案1 对应的变量取值

为更直观理解表3 中数字的含义，绘制方案1 的运输路线、指派方案及相应的时间，如图2 所示.其中圆中数字为对应路径点，长方形中字母和数字分别代表分配给对应路径点的检修小组及检修时间，带箭头的线上数字为两相邻路径点的运输时间，圆形外面的数字为对应路径点的到达时间.

图2 方案1 的旅行路径和检修小组指派

从图2 可以看出，从起点到路径点3，需要依次经过路径点2，1，4，5，到达路径点3 的时间为41，此时检修小组B 在路径点3 执行检修任务，所需检修时间为11.所以，在路径点3的检修任务完工时间为到达路径点3 的时间与检修小组B 完成检修任务所需时间之和为52.同理，在路径点1，2，4，5 的检修完工时间分别为26，19，35，46.运输工具完成运送返回到起点花费的时间为51.所以，在这个方案中，所有路径点的检修完工时间和运输返回起点所需时间中最大值为52，则方案1 的函数值为52.

通过对模型Ⅰ进行举例说明，对MWPEP问题的决策变量和目标函数形成有了更清楚的认识.

3.3 基于算例对模型Ⅱ进行分析

在模型Ⅱ中，为了刻画到达路径点的顺序，特别使用了运送到达任意一个节点的到达时间Ti作为一组决策变量，并对Ti的取值范围进行约束，下面对方案1 中到达时间的约束作进一步分析，现设变量xij的取值如表4所示.

表4 MWPEP 问题方案1 对应变量xij 的取值

从表4 可以看出，当从0 号点出发到达第一个路径点为2 号路径点，此时

从起点出发到达除路径点2 的任意节点都会经过路径点2，则对除路径点2 的任意路径点满足Ti>T2，i≠2.所以，对除起点外任意路径点满足式（2），当且仅当i为从0 号点出发到达的第一个路径点时取等.

同理，返回0 号点有两种情况.返回0 号点前到达的最后一个路径点为3 号点，那么到达3 号点的时间为运送花费总时间与从i点到0 号点所需时间之差，即

对除3 号点的任意路径点，需要经过路径点3 才能返回起点，故Ti

综上，对除起点外任意路径点i的到达时间的取值范围满足8 ≤Ti≤41，i=1，2，3，4，5，即

经过路径点i到达路径点j有两种情况，第一种情况是从路径点i可直接到达路径点j，第二种情况是从路径点i需要经过若干个路径点才能到达路径点j.若j点为4 号点，i点为1 号点，则从1 号点可直接到达4 号点，满足

若i点为2 号点，从2 号点需要经过1 号点才能到达4 号点，此时T2=T1−t21

通过对模型Ⅱ到达时间变量的约束条件进行分析，对约束条件的构造过程更加容易理解.

4 结语

本文研究了风力发电设备检修场景内的一类设备检修问题.通过对问题做适当简化，给出了基于TSP 路径与任务指派的MWPEP 问题.同时以TSP 问题和AP 问题的数学模型为基础，一方面，在TSP 路径的基础上，把指派所形成的检修时间叠加，构造目标函数值，建立数学模型；另一方面，借鉴TSP 问题和AP 问题的0−1 规划模型，刻画到达每个节点时间作为一组决策变量，并限制其取值范围进行建模.MWPEP 问题的提出，扩宽了运筹学知识的应用，同时，MWPEP 问题数学模型的建立，为今后使用智能算法求解此类问题奠定了基础.