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

doi:10.11949/0438-1157.20230883

摘要/Abstract

摘要：

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

关键词: 自适应大邻域搜索, 禁忌搜索, 维修调度, 算法, 优化, 系统工程

Abstract:

The scheduling optimization of large-scale maintenance tasks has extensive applications in practical production processes such as optimizing maintenance scheduling for coal bed methane wells, well repair operations scheduling, and fracturing operations scheduling. This problem is large-scale and difficult to solve, which is a difficulty and challenge for real-time scheduling optimization. A well-designed schedule for large-scale maintenance tasks is of significant importance for ensuring smooth production and reducing costs in oil and gas fields. To effectively address this issue, an optimization algorithm based on ALNS-TS has been proposed, and its effectiveness has been verified through cases of different scales. The experimental results demonstrate that the solving time for representative cases with 10, 50 and 100 maintenance tasks is 0.03, 8.33, and 74.32 s, respectively, providing reasonable scheduling solutions within minutes. As the problem scale increases, the ALNS-TS based algorithm outperforms traditional algorithms in efficiency and is capable of finding lower objective function values and optimal solutions.

Key words: adaptive large neighborhood search, tabu search, maintenance scheduling, algorithm, optimization, systems engineering

中图分类号:

TP 29

高小永, 刘顿, 檀朝东, 李菲菲. 基于ALNS-TS的大规模维修任务调度优化快速求解算法[J]. 化工学报, 2023, 74(11): 4645-4655.

Xiaoyong GAO, Dun LIU, Chaodong TAN, Feifei LI. ALNS-TS based fast optimization algorithm for large-scale maintenance task scheduling[J]. CIESC Journal, 2023, 74(11): 4645-4655.

图/表 9

图1 维修人员的工作流程

Fig.1 The workflow of the maintenance personnel

图2 ALNS-TS算法的流程

Fig. 2 Flow chart of the ALNS-TS algorithm

表1 分数调整参数

Table 1 Score adjustment parameter

分数	描述
$θ 1$	经过破坏并修复后，算法得到了新的全局最优解
$θ 2$	经过破坏并修复后，尚未接受过的解中有比当前解更优的解存在
$θ 3$	经过破坏并修复后，尚未接受过的劣解中有比当前解更差但满足接受准则的解存在
$θ 4$	经过破坏并修复后，尚未接受过的劣解中有比当前解更差且不满足接受准则的解存在

表1 分数调整参数

Table 1 Score adjustment parameter

分数	描述
$θ 1$	经过破坏并修复后，算法得到了新的全局最优解
$θ 2$	经过破坏并修复后，尚未接受过的解中有比当前解更优的解存在
$θ 3$	经过破坏并修复后，尚未接受过的劣解中有比当前解更差但满足接受准则的解存在
$θ 4$	经过破坏并修复后，尚未接受过的劣解中有比当前解更差且不满足接受准则的解存在

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

Fig.3 The results of the ALNS-TS algorithm in solving cases of different scales

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

Fig.4 Comparison of the results of ALNS-TS algorithm and ALNS algorithm for solving cases of different scales

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

Table 2 Exact algorithmic solution results for 10， 14， 18 and 20 task cases

维修任务数量/个	创建的节点数/个	修剪的节点数/个	求解时间/s
10	223	109	0.65
14	6935	3464	11.94
18	73237	36610	238.99
20	406611	203282	1685.91

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

Fig.5 Comparison of results of ALNS-TS algorithm and heuristic algorithms

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

Table 3 Comparison of objective function values of the solution

算法	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

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

Fig.6 Comparison of results of the ALNS-TS algorithm and the Gurobi solver

参考文献 26

27	Qian W W, Chai J R, Xu Z G, et al. Differential evolution algorithm with multiple mutation strategies based on roulette wheel selection[J]. Applied Intelligence, 2018, 48(10): 3612-3629.
28	Ribeiro G M, Mauri G R, Lorena L A N. A simple and robust simulated annealing algorithm for scheduling workover rigs on onshore oil fields[J]. Computers & Industrial Engineering, 2011, 60(4): 519-526.
29	Katoch S, Chauhan S S, Kumar V. A review on genetic algorithm: past, present, and future[J]. Multimedia Tools and Applications, 2021, 80(5): 8091-8126.
30	Wang Z P, Tian J C, Feng K P. Optimal allocation of regional water resources based on simulated annealing particle swarm optimization algorithm[J]. Energy Reports, 2022, 8: 9119-9126.
31	Zhou X B, Ma H J, Gu J G, et al. Parameter adaptation-based ant colony optimization with dynamic hybrid mechanism[J]. Engineering Applications of Artificial Intelligence, 2022, 114: 105139.
32	Nau C, Sankaran P, McConky K. Comparison of parameter tuning strategies for team orienteering problem (TOP) solved with Gurobi[J]. IIE Annual Conference. Proceedings, 2022.
1	夔国凤, 赵越, 谢毅, 等. 多紧急等级复杂维修任务即时调度优化与应用[J]. 化工进展, 2021, 40(11): 6035-6043.
	Kui G F, Zhao Y, Xie Y, et al. Method and application of complex maintenance tasks just-in-time scheduling optimization considering multiple emergency levels[J]. Chemical Industry and Engineering Progress, 2021, 40(11): 6035-6043.
2	Bertsimas D, Tsitsiklis J. Simulated annealing[J]. Statistical Science, 1993, 8(1): 10-15.
3	Fu Y P, Hou Y S, Wang Z F, et al. Distributed scheduling problems in intelligent manufacturing systems[J]. Tsinghua Science and Technology, 2021, 26(5): 625-645.
4	Sahnehsaraei M A, Mahmoodabadi M, Taherkhorsandi M, et al. A hybrid global optimization algorithm: particle swarm optimization in association with a genetic algorithm[J]. Complex System Modelling and Control Through Intelligent Soft Computations, 2015: 45-86.
5	Golpîra H, Tirkolaee E B. Stable maintenance tasks scheduling: a bi-objective robust optimization model[J]. Computers & Industrial Engineering, 2019, 137: 106007.
6	Achkar V G, Cafaro V G, Méndez C A, et al. Discrete-time MILP formulation for the optimal scheduling of maintenance tasks on oil and gas production assets[J]. Industrial & Engineering Chemistry Research, 2019, 58(19): 8231-8245.
7	Xu Y J, Han X S, Yang M, et al. Condition-based midterm maintenance scheduling with rescheduling strategy[J]. International Journal of Electrical Power & Energy Systems, 2020, 118: 105796.
8	Mira L, Andrade A R, Gomes M C. Maintenance scheduling within rolling stock planning in railway operations under uncertain maintenance durations[J]. Journal of Rail Transport Planning & Management, 2020, 14: 100177.
9	Santos I M, Hamacher S, Oliveira F. A data-driven optimization model for the workover rig scheduling problem: case study in an oil company[J]. Computers & Chemical Engineering, 2023, 170: 108088.
10	Villagra A, Pandolfi D, Leguizamón G. Handling constraints with an evolutionary tool for scheduling oil wells maintenance visits[J]. Engineering Optimization, 2013, 45(8): 963-981.
11	黄义松, 赵德勇, 李明雨. 基于遗传算法的虚兵火力协同任务规划[J]. 信息系统工程, 2023(3): 77-80.
	Huang Y S, Zhao D Y, Li M Y. Virtual firepower collaborative task planning based on genetic algorithm[J]. China CIO News, 2023(3): 77-80.
12	Tozzo E, Costa A, Lins I. A hybrid multi-objective genetic algorithm for scheduling heterogeneous workover rigs on onshore oil fields[J]. Journal of Petroleum Science and Engineering, 2020, 195: 107935.
13	Naseri H, Golroo A, Shokoohi M, et al. Sustainable pavement maintenance and rehabilitation planning using the marine predator optimization algorithm[J]. Structure and Infrastructure Engineering, 2022: 1-13.
14	Ribeiro G M, Laporte G, Mauri G R. A comparison of three metaheuristics for the workover rig routing problem[J]. European Journal of Operational Research, 2012, 220(1): 28-36.
15	Gao X Y, Peng D, Kui G F, et al. Reinforcement learning based optimization algorithm for maintenance tasks scheduling in coalbed methane gas field[J]. Computers & Chemical Engineering, 2023, 170: 108131.
16	Pisinger D, Ropke S. A general heuristic for vehicle routing problems[J]. Computers & Operations Research, 2007, 34(8): 2403-2435.
17	徐倩, 熊俊, 杨珍花, 等. 基于自适应大邻域搜索算法的外卖配送车辆路径优化[J]. 工业工程与管理, 2021, 26(3): 115-122.
	Xu Q, Xiong J, Yang Z H, et al. Route optimization of takeout delivery vehicles based on adaptive large neighborhood search algorithm[J]. Industrial Engineering and Management, 2021, 26(3): 115-122.
18	南丽君, 陈彦如, 张宗成. 改进的自适应大规模邻域搜索算法求解动态需求的混合车辆路径问题[J]. 计算机应用研究, 2021, 38(10): 2926-2934.
	Nan L J, Chen Y R, Zhang Z C. Improved adaptive large-scale neighborhood search algorithm for solving dynamic demand hybrid vehicle routing problem[J]. Application Research of Computers, 2021, 38(10): 2926-2934.
19	李晓辉, 李沛帆, 于振宁, 等. 自适应大邻域搜索算法在无人机物流路径规划问题中的应用[J]. 计算机系统应用, 2021, 30(11): 260-265.
	Li X H, Li P F, Yu Z N, et al. Adaptive large neighborhood search algorithm in planning of UAV logistics route[J]. Computer Systems & Applications, 2021, 30(11): 260-265.
20	Alinaghian M, Shokouhi N. Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search[J]. Omega, 2018, 76: 85-99.
21	Chen C, Demir E, Huang Y. An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots[J]. European Journal of Operational Research, 2021, 294(3): 1164-1180.
22	Glover F, Laguna M. Tabu Search[M]. New York: Springer US, 1998.
23	符卓, 刘文, 邱萌. 带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J]. 中国管理科学, 2017, 25(5): 78-86.
	Fu Z, Liu W, Qiu M. A tabu search algorithm for the vehicle routing problem with soft time windows and split deliveries by order[J]. Chinese Journal of Management Science, 2017, 25(5): 78-86.
24	Mahmud S, Abbasi A, Chakrabortty R K, et al. Multi-operator communication based differential evolution with sequential Tabu Search approach for job shop scheduling problems[J]. Applied Soft Computing, 2021, 108: 107470.
25	白雪骢, 朱焱. 一种基于禁忌搜索算法的流程挖掘方法[J]. 计算机科学, 2016, 43(4): 214-218, 240.
	Bai X C, Zhu Y. Process mining approach based on tabu search algorithm[J]. Computer Science, 2016, 43(4): 214-218, 240.
26	Shaw P. Using constraint programming and local search methods to solve vehicle routing problems[M]//Maher M, Puget J F. Principles and Practice of Constraint Programming-CP98. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998: 417-431.

[1]	杨欣, 王文, 徐凯, 马凡华. 高压氢气加注过程中温度特征仿真分析[J]. 化工学报, 2023, 74(S1): 280-286.
[2]	陈哲文, 魏俊杰, 张玉明. 超临界水煤气化耦合SOFC发电系统集成及其能量转化机制[J]. 化工学报, 2023, 74(9): 3888-3902.
[3]	曹跃, 余冲, 李智, 杨明磊. 工业数据驱动的加氢裂化装置多工况切换过渡状态检测[J]. 化工学报, 2023, 74(9): 3841-3854.
[4]	齐聪, 丁子, 余杰, 汤茂清, 梁林. 基于选择吸收纳米薄膜的太阳能温差发电特性研究[J]. 化工学报, 2023, 74(9): 3921-3930.
[5]	何松, 刘乔迈, 谢广烁, 王斯民, 肖娟. 高浓度水煤浆管道气膜减阻两相流模拟及代理辅助优化[J]. 化工学报, 2023, 74(9): 3766-3774.
[6]	邢雷, 苗春雨, 蒋明虎, 赵立新, 李新亚. 井下微型气液旋流分离器优化设计与性能分析[J]. 化工学报, 2023, 74(8): 3394-3406.
[7]	张曼铮, 肖猛, 闫沛伟, 苗政, 徐进良, 纪献兵. 危废焚烧处理耦合有机朗肯循环系统工质筛选与热力学优化[J]. 化工学报, 2023, 74(8): 3502-3512.
[8]	诸程瑛, 王振雷. 基于改进深度强化学习的乙烯裂解炉操作优化[J]. 化工学报, 2023, 74(8): 3429-3437.
[9]	尹刚, 李伊惠, 何飞, 曹文琦, 王民, 颜非亚, 向禹, 卢剑, 罗斌, 卢润廷. 基于KPCA和SVM的铝电解槽漏槽事故预警方法[J]. 化工学报, 2023, 74(8): 3419-3428.
[10]	陈国泽, 卫东, 郭倩, 向志平. 负载跟踪状态下的铝空气电池堆最优功率点优化方法[J]. 化工学报, 2023, 74(8): 3533-3542.
[11]	刘文竹, 云和明, 王宝雪, 胡明哲, 仲崇龙. 基于场协同和耗散的微通道拓扑优化研究[J]. 化工学报, 2023, 74(8): 3329-3341.
[12]	吴文涛, 褚良永, 张玲洁, 谭伟民, 沈丽明, 暴宁钟. 腰果酚生物基自愈合微胶囊的高效制备工艺研究[J]. 化工学报, 2023, 74(7): 3103-3115.
[13]	汤晓玲, 王嘉瑞, 朱玄烨, 郑仁朝. 基于Pickering乳液的卤醇脱卤酶催化合成手性环氧氯丙烷[J]. 化工学报, 2023, 74(7): 2926-2934.
[14]	文兆伦, 李沛睿, 张忠林, 杜晓, 侯起旺, 刘叶刚, 郝晓刚, 官国清. 基于自热再生的隔壁塔深冷空分工艺设计及优化[J]. 化工学报, 2023, 74(7): 2988-2998.
[15]	江锦波, 彭新, 许文烜, 门日秀, 刘畅, 彭旭东. 泵出型螺旋槽油气密封泄漏特性及参数影响研究[J]. 化工学报, 2023, 74(6): 2538-2554.