The ALNS metaheuristic for the transmission maintenance scheduling

Abstract

ROADEF Challenge is an established international competition addressing challenging industrial problems of combinatorial optimization. It is organized by the French Operations Research and Decision Support Society (ROADEF) every 2 years since 1999. The most recent ROADEF challenge 2020 was co-organized by the French electricity transmission network operator, the RTE company. The competition problem addressed a novel variant of the transmission maintenance scheduling problem, distinctive in that it has multiple time-dependent properties, constraints, and a risk-based aggregate objective function. Therefore, the problem is more complex than the previous formulations, and the existing methods are not directly applicable. This paper presents a metaheuristic algorithm based on the adaptive large neighborhood search. The algorithm’s performance is based on a large bank of newly proposed problem-specific destroy and repair heuristics, an efficient local search engine, and a penalization mechanism for avoiding invalid solutions. The algorithm is compared with the best-known solutions from all competition phases and other methods submitted to the final phase. The result shows that the method yields consistent performance in all available datasets. The proposed algorithm finished 6th in the semifinal phase of the competition and 8–9th in the final phase. Finally, the effect of individual components and the algorithm’s behaviour are analyzed in detail.