基于ALNS-TS的大规模维修任务调度优化快速求解算法

中文题目：基于ALNS-TS的大规模维修任务调度优化快速求解算法

录用期刊/会议：化工学报（EI）

原文DOI：10.11949/0438-1157.20230883

原文链接：https://hgxb.cip.com.cn/CN/10.11949/0438-1157.20230883

作者列表：

1）高小永 中国石油大学（北京）信息科学与工程学院/人工智能学院 自动化系 教师

2）刘   顿 中国石油大学（北京）信息科学与工程学院/人工智能学院 控制科学与工程 硕23

3）檀朝东 中国石油大学（北京）信息科学与工程学院/人工智能学院 自动化系 教师

4）李菲菲 山东预见智能科技有限公司

摘要:

大规模维修任务的调度优化在实际生产过程中具有广泛的应用，例如煤层气井维修任务调度优化、修井作业调度和压裂作业调度等。该问题规模庞大且求解困难，是实时调度优化的难点和挑战。合理的大规模维修任务调度对于保障油气田平稳生产和降低成本具有重要意义。为了有效解决这一难题，提出了基于ALNS-TS的优化求解算法，并通过不同规模的案例验证了算法的有效性。实验结果显示，对于代表性的10个、50个和100个维修任务的案例，求解时间分别为0.03秒、8.33秒和74.32秒，都能在分钟级时间内给出合理的调度方案。随着问题规模增加，基于ALNS-TS的算法比传统算法更高效，并能找到目标函数值更低的更优解。

背景与动机:

石油和天然气的高效生产离不开多种昂贵设备，在持续的开发和生产过程中，必须及时维修故障设备以减少损失。传统的维修巡井方式是根据人工经验定期安排人员检查所有油气井口的设备运行状态，不论是否出现故障，维修人员必须按照规定的时间和任务逐个排查。这不仅造成了维修人员资源的极大浪费，且导致维修设备和工具的使用效率低下，使得油气生产成本大幅提高，不利于现场实时调度管理。因此，实现智能维修调度非常必要且急迫。

大规模维修调度优化问题是一个NP难问题。精确算法、启发式算法和元启发式算法都被广泛用于解决此类问题，如分支定界算法、遗传算法、模拟退火算法和蚁群算法等。当模型规模较小时，这些算法的效率较高，但随着模型规模逐渐增加，基于精确算法的求解器可能因内存不足而停止优化过程。启发式算法虽然能快速获得可行解，但由于缺乏全局搜索机制，难以保障解的质量。元启发式算法虽然适应性广泛，但通常存在易陷入局部最优、迭代寻优耗时高等问题。为了避免大规模的盲目搜索并提高调度方案的质量，本文提出以自适应大邻域搜索(Adaptive Large Neighborhood Search, ALNS)算法为基础，结合禁忌搜索(Tabu Search, TS)算法的混合启发式算法。

理论分析：

研究表明，自适应大邻域搜索算法具有更大、更多样化的邻域，可以探索解空间的大部分，但该算法在迭代后期可能会陷入局部最优解。融合禁忌搜索可以暂时降低解的质量，但同时增加解空间的多样性。为了提高搜索效率和精度，ALNS-TS算法融合了上述两种算法。本文提出了一种ALNS算法为基础、结合TS算法的混合启发式算法。该算法能够高效地解决问题，并具有较高的搜索效率和精度。图1展示了基于ALNS-TS的算法流程。

图1  ALNS-TS算法的流程

       首先是初始解的生成，通过贪心算法生成较高质量的初始解S0，以提高算法的搜索效率。接下来是生成新解的过程，通过轮盘赌算法基于破坏方法的权重集合ρ-与修复方法的权重集合ρ+ ，从破坏方法集合Ω-和修复方法集合Ω+中选出一对破坏方法与修复方法。利用破坏方法从当前解S中移除随机数量n个维修任务，组成移除列表R，并用Sc表示被破坏的解。然后，修复方法将移除列表R中的n个维修任务重新插入在被破坏的解Sc中，得到新解Snew。

       之后，禁忌搜索部分首先判断Snew是否满足禁忌准则，如果Snew在禁忌列表T中，直接进入下一次循环并更新禁忌表。如果Snew不在禁忌列表中，则进入下一步操作。算法接着判断Snew是否满足接受模拟退火的接受准则。如果满足，则将Snew加入到T中并更新当前解。然后，继续判断Snew是否优于历史最优解Sbest，若Snew优于Sbest，则更新历史最优解，否则，进入下一步操作。

       接下来是自适应调整部分，根据破坏方法和修复方法的表现对其进行评分，并更新相应的权重系数。最后是终止准则，本算法终止的两个准则分别是达到指定迭代次数或者在达到指定迭代次数之前找到可行解，如果在达到指定迭代次数后没有发现更优解也会终止程序。

实验结果及分析:

1 案例分析

为验证ALNS-TS算法在大规模维修调度问题中的有效性，本文提供了代表性的10、50和100个维修任务的案例，并求解使一名维修人员完成所分配维修任务的最优调度路线。通过对大量案例数据的总结分析，各个任务维修所需耗时得到了相对合理的经验值，并且在ALNS-TS算法中设定以下参数：（1）权重更新系数为0.7，（2）初始温度为问题规模的10倍，（3）降温速度为0.9，（4）禁忌长度为问题规模的10%。为确保最终收敛，最大迭代次数设置为500。所有案例均在Python平台上运行，并记录基于ALNS-TS算法的一次随机迭代结果。

(a) 10个维修任务案例的最优调度路线

(b) 10个维修任务案例的收敛曲线

(c) 50个维修任务案例的最优调度路线

(d) 50个维修任务案例的收敛曲线

（e）100个维修任务案例的最优调度路线

（f）100个维修任务案例的收敛曲线

图2 ALNS-TS算法求解不同规模案例的结果

如图2所示，在10个维修任务的案例中，使用ALNS-TS算法得出最优路线为[0,2,10,1,6,5,3,9,4,7,8,0]，收敛曲线显示在15次迭代（0.03秒）后达到最优值。在50个维修任务的案例中，最优路线为[0,10,50,17,43,33,42,47,2,29,24,36,34,45,18,30,14,28,44,27,5,22,7,37,12,8,15,19,48,26,41,35,1,4,11,49,32,38,6,3,20,23,39,21,25,13,16,9,46,31,40,0]，收敛曲线显示在83次迭代（8.33秒）后达到最优值。在100个维修任务的案例中，最优路线为[0,95,74,86,8,93,14,30,87,84,36,88,47,60,2,42,89,53,59,56,33,81,96,43,17,13,62,25,21,16,9,46,55,10,50,68,24,91,34,29,45,97,18,100,28,44,85,27,69,57,5,79,22,7,66,37,73,12,80,70,15,67,41,19,48,52,77,26,71,51,92,11,4,1,72,64,49,98,32,82,38,54,99,94,23,39,76,65,20,63,75,90,3,61,6,83,35,78,40,31,58,0]，收敛曲线显示在108次迭代（74.32秒）后达到最优值。

综上所述，经过优化的ALNS-TS算法在解决大规模维修调度问题上表现出较高的效率和准确性，算法得到的最优调度路线避免了路线交叉重叠。因此，该算法具有一定的优越性和有效性。

2 加入禁忌搜索前后对比分析

为了研究ALNS-TS算法在加入禁忌搜索后的性能提升效果，本文通过代表性的10、50和100个维修任务的案例，对比了本文算法（ALNS-TS）和自适应大邻域搜索（ALNS）算法的求解效果。

(a) 10个维修任务案例的调度结果对比

(b) 50个维修任务案例的调度结果对比

(c) 100个维修任务案例的调度结果对比

图3 ALNS-TS算法和ALNS算法求解不同规模案例的结果对比

图3表明了ALNS-TS算法在加入禁忌搜索后的性能提升效果。图中实线表示使用ALNS-TS算法求解的迭代曲线，虚线表示使用ALNS算法求解的迭代曲线。

针对10个维修任务的案例，ALNS-TS算法完成求解仅需6次迭代，而ALNS算法需要23次迭代。两种算法得到的求解方案目标函数值相同。结果显示，当案例规模较小时，ALNS-TS算法在更少的计算时间内达到了ALNS算法的计算效果。对于50个维修任务的案例，ALNS-TS算法完成求解需要108次迭代，而ALNS算法则需要167次迭代。此外，ALNS-TS算法得到的求解方案的目标函数值更低。对于100个维修任务的案例，ALNS-TS算法完成求解需要140次迭代，而ALNS算法则需要328次迭代。同样，ALNS-TS算法得到的求解方案的目标函数值更低。

综上所述，ALNS-TS算法在较大规模的案例中不仅在更少的迭代次数下获得了最优解，同时得到的最优解目标值更低。这表明ALNS-TS算法相比改进前的ALNS算法在性能上有一定提升，并且具有跳出局部最优和减少迭代寻优耗时的优势。

3 与精确算法对比分析

为了验证ALNS-TS算法的有效性和优越性，本文将使用传统精确算法和本文提出算法进行对比分析。传统精确算法选择分支定界算法，对于10个、14个、18个和20个维修任务的案例，求解结果如表1所示：

表1 10, 14, 18和20个任务案例的精确算法求解结果

表1显示，对于10、14、18和20个维修任务的案例，传统精确算法的求解时间分别为0.65秒、11.94秒、238.99秒和1685.91秒。然而，在30个维修任务的案例下，精确算法无法在给定的CPU时间内得到结果，这表明精确算法在处理大规模维修调度问题时效率低下。尽管精确算法在处理小规模案例时具有较高效率，并可获得问题的最优解，但随着案例规模的增加，节点的创建、剪枝和求解时间都呈指数级增长。因此，这些求解结果显示了大规模维修调度问题的复杂性，以及应用精确算法解决此类问题的低效性。

4 与其他启发式算法对比分析

为了证明本文提出的算法在解决大规模维修调度问题上的优越性，我们对多种经典的启发式算法和本文算法进行了对比分析，并应用它们求解不同规模的案例。研究表明，遗传算法 (Genetic Algorithm，GA)、模拟退火算法 (Simulated Annealing，SA) 和蚁群算法 (Ant Colony Optimization，ACO) 在调度优化领域广泛应用且效果优异，因此我们选择了这三种算法与本文算法进行对比。GA的参数设置如下：种群规模为50，染色体交叉概率为0.7，变异概率为0.005，初始染色体数量为50。SA的参数设置如下：初始温度为4000，最终温度为0，冷却系数为0.99。ACO的参数设置如下：蚂蚁数量为维修任务的数量，信息素常量为100，信息素因子为1，启发函数因子为2，信息素挥发因子为0.5。这三种算法各随机运行10次，并记录了平均计算时间和目标函数值作为对比指标。

图4 ALNS-TS算法与启发式算法的求解结果对比

根据图4的结果，对于10、30、60、80和100个维修任务的案例，ALNS-TS算法求解所需时间分别为0.03秒、2.89秒、14.34秒、40.37秒和74.32秒。SA求解所需时间分别为2.16秒、10.72秒、30.61秒、126.65秒和137.90秒。ACO求解所需时间分别为1.48秒、10.99秒、71.10秒、180.88秒和370.89秒。GA求解所需时间分别为3.39秒、12.33秒、92.42秒、299.93秒和409.12秒。此外，表2给出了各个算法求解方案的目标函数值，即完成所有维修任务的总时间。

针对10和30个维修任务的案例，传统算法得到的求解方案的质量不比本文提出算法差。然而，对于60、80和100个维修任务的案例，本文提出算法得到的求解方案质量更优。这些结果表明，在解决大规模维修调度问题时，启发式算法比精确算法更高效。并且，ALNS-TS算法比传统启发式算法更高效，并能搜索到目标函数值更低的更优解。

5 与Gurobi求解器对比分析

为了深入证明本文提出算法在解决大规模维修调度问题的优越性，本节运用Gurobi求解器和本文提出算法求解不同规模的案例来进行对比分析。针对不同规模的案例，使用Gurobi求解器随机运行了10次，并记录平均计算时间和目标函数值。

图5 ALNS-TS算法与Gurobi求解器的求解结果对比

根据图5的结果，对于10、30、60、80和100个维修任务的案例，ALNS-TS算法求解所需时间分别为0.03秒、2.89秒、14.34秒、40.37秒和74.32秒。SA求解所需时间分别为2.16秒、10.72秒、30.61秒、126.65秒和137.90秒。ACO求解所需时间分别为1.48秒、10.99秒、71.10秒、180.88秒和370.89秒。GA求解所需时间分别为3.39秒、12.33秒、92.42秒、299.93秒和409.12秒。此外，表2给出了各个算法求解方案的目标函数值，即完成所有维修任务的总时间。

针对10和30个维修任务的案例，传统算法得到的求解方案的质量不比本文提出算法差。然而，对于60、80和100个维修任务的案例，本文提出算法得到的求解方案质量更优。这些结果表明，在解决大规模维修调度问题时，启发式算法比精确算法更高效。并且，ALNS-TS算法比传统启发式算法更高效，并能搜索到目标函数值更低的更优解。

表2 求解方案的目标函数值对比

算法	10个任务的求解结果/min		20个任务的求解结果/min	30个任务的求解结果/min	60个任务的求解结果/min	80个任务的求解结果/min	100个任务的求解结果/min
精确算法		38.00	36.90	-	-	-	-
遗传算法		38.00	59.20	184.00	263.70	293.10	366.30
蚁群算法		38.00	45.50	108.80	234.30	264.30	309.60
模拟退火算法		38.00	49.90	153.40	285.00	324.20	447.80
Gurobi求解器		38.00	40.20	103.10	235.10	328.40	414.50
本文提出算法		38.00	42.70	101.20	191.10	243.00	283.50

结论:

（1）针对不同规模的维修调度案例，本文提出算法能够在分钟级别的时间内给出高质量的调度方案，实现了现场实时调度的基本要求。

（2）通过融入TS算法，本文提出算法相比ALNS算法，在解决大规模案例时具有更短的求解时间和更高的求解质量。因此，该算法不仅能够缩短迭代寻优的耗时，而且能够避免陷入局部最优解，为大规模维修调度案例找到更优的解决方案。

（3）与精确算法、其他启发式算法以及Gurobi求解器等传统算法相比，本文提出算法在小规模案例中的求解效果相似。然而，在处理大规模案例时，本文提出算法展现出更高的求解效率和求解精度。这表明该算法在解决大规模维修调度问题上具备明显的优势。

关于作者

高小永，博士生导师，石大学者，校青年拔尖人才，信息科学与工程学院/人工智能学院副院长，自动化专业及控制科学与工程学科建设负责人。北京自动化学会常务理事、中国自动化学会过程控制专业委员会委员、中国化工学会信息技术应用专业委员会委员、中国系统工程学会过程系统工程专业委员会委员。研究领域为复杂石油石化工业过程智能制造，主要方向有：机理与数据驱动的故障诊断、复杂工业过程建模与优化控制、工业过程计划与调度优化等。主持国家自然科学基金项目2项、北京市自然科学基金面上项目1项、校企联合项目10多项，发表SCI/EI等各类论文50多篇。

联系方式：x.gao@cup.edu.cn