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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abirami, M., Ganesan, S., Subramanian, S., Anandhakumar, R.: Source and transmission line maintenance outage scheduling in a power system using teaching learning based optimization algorithm. Appl. Soft Comput. 21, 72–83 (2014). https://doi.org/10.1016/j.asoc.2014.03.015
Artigues, C., Bourreau, E., Jost, V., Kedad-Sidhoum, S., Ramond, F.: Trains do not vanish: the ROADEF/EURO challenge 2014. Ann. Oper. Res. 271(2), 1091–1105 (2018). https://doi.org/10.1007/s10479-018-3066-x
Back, T., Fogel, D.B., Michalewicz, Z.: Handbook of Evolutionary Computation, 1st edn. IOP Publishing Ltd. (1997)
Ben Hamida, S., Schoenauer, M.: An adaptive algorithm for constrained optimization problems. In: International Conference on Parallel Problem Solving from Nature, pp. 529–538 (2000). Springer
Borůvka, O.: O jistém problému minimálním. Práce Moravské pírodovědecké společnosti II I(3), 37–58 (1926)
Burke, E.K., Smith, A.J.: Hybrid evolutionary techniques for the maintenance scheduling problem. IEEE Trans. Power Syst. 15(1), 122–128 (2000). https://doi.org/10.1109/59.852110
Da Silva, E.L., Schilling, M.T., Rafael, M.C.: Generation maintenance scheduling considering transmission constraints. IEEE Trans. Power Syst. 15(2), 838–843 (2000). https://doi.org/10.1109/59.867182
Duarte, A., Sánchez-Oro, J., Mladenović, N., Todosijević, R.: In: Martí, R., Pardalos, P.M., Resende, M.G.C. (eds.) Variable Neighborhood Descent, pp. 341–367. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-07124-4_9
El-Sharkh, M.Y.: Clonal selection algorithm for power generators maintenance scheduling. Int. J. Electr. Power Energy Syst. 57, 73–78 (2014). https://doi.org/10.1016/j.ijepes.2013.11.051
Feng, C., Wang, X., Li, F.: Optimal maintenance scheduling of power producers considering unexpected unit failure. IET Gener. Transm. Distrib. 3(5), 460–471 (2009). https://doi.org/10.1049/iet-gtd.2008.0427
Froger, A., Gendreau, M., Mendoza, J.E., Pinson, É., Rousseau, L.M.: Maintenance scheduling in the electricity industry: a literature review. Eur. J. Oper. Res. 251(3), 695–706 (2016). https://doi.org/10.1016/j.ejor.2015.08.045
Geetha, T., Swarup, K.S.: Coordinated preventive maintenance scheduling of GENCO and TRANSCO in restructured power systems. Int. J. Electr. Power Energy Syst. 31(10), 626–638 (2009). https://doi.org/10.1016/j.ijepes.2009.06.006
He, L., Liu, X., Laporte, G., Chen, Y., Chen, Y.: An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Comput. Oper. Res. 100, 12–25 (2018). https://doi.org/10.1016/j.cor.2018.06.020
Huang, S.J.: Generator maintenance scheduling: a fuzzy system approach with genetic enhancement. Electr. Power Syst. Res. 41(3), 233–239 (1997). https://doi.org/10.1016/s0378-7796(96)01194-7
Joines, J.A., Houck, C.R., et al.: On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with Ga’s. In: International Conference on Evolutionary Computation, pp. 579–584 (1994)
Khalid, W., Soleymani, I., Mortensen, N.H., Sigsgaard, K.V.: Ai-based maintenance scheduling for offshore oil and gas platforms. In: 2021 Annual Reliability and Maintainability Symposium (RAMS), pp. 1–6 (2021). https://doi.org/10.1109/RAMS48097.2021.9605794
Kovacs, A.A., Parragh, S.N., Doerner, K.F., Hartl, R.F.: Adaptive large neighborhood search for service technician routing and scheduling problems. J. Sched. 15(5), 579–600 (2012). https://doi.org/10.1007/s10951-011-0246-9
López-Ibáñez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Birattari, M., Stützle, T.: The irace package: iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3, 43–58 (2016). https://doi.org/10.1016/j.orp.2016.09.002
Lu, C., Wang, J., Sun, P.: Short-term transmission maintenance scheduling based on the benders decomposition. In: APPEEC 2012 (2012). https://doi.org/10.1109/APPEEC.2012.6307696
Lv, C., Wang, J., You, S., Zhang, Z.: Short-term transmission maintenance scheduling based on the Benders decomposition. Int. Trans. Electric. Energy Syst. 25(4), 697–712 (2015). https://doi.org/10.1002/etep.1867
Michel, L., Hentenryck, P.V.: In: Martí, R., Pardalos, P.M., Resende, M.G.C. (eds.) Constraint-Based Local Search, pp. 223–260. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-07124-4_7
Mollahassani-Pour, M., Abdollahi, A., Rashidinejad, M.: Application of a novel cost reduction index to preventive maintenance scheduling. Int. J. Electr. Power Energy Syst. 56, 235–240 (2014). https://doi.org/10.1016/j.ijepes.2013.11.026
Moro, L.M., Ramos, A.: Goal programming approach to maintenance scheduling of generating units in large scale power systems. IEEE Trans. Power Syst. 14(3), 1021–1028 (1999). https://doi.org/10.1109/59.780915
Pandžić, H., Conejo, A.J., Kuzle, I., Caro, E.: Yearly maintenance scheduling of transmission lines within a market environment. IEEE Trans. Power Syst. 27(1), 407–415 (2012). https://doi.org/10.1109/TPWRS.2011.2159743
Pisinger, D., Ropke, S.: Large neighborhood search. In: Handbook of Metaeuristics, pp. 399–419. Springer, Cham (2010). https://doi.org/10.1007/978-1-4419-1665-5_13
Reihani, E., Sarikhani, A., Davodi, M., Davodi, M.: Reliability based generator maintenance scheduling using hybrid evolutionary approach. Int. J. Electr. Power Energy Syst. 42(1), 434–439 (2012). https://doi.org/10.1016/j.ijepes.2012.04.018
Rifai, A.P., Nguyen, H.-T., Dawal, S.Z.M.: Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling. Appl. Soft Comput. 40, 42–57 (2016). https://doi.org/10.1016/j.asoc.2015.11.034
ROADEF: Challenge ROADEF/EURO 2020: Maintenance planning Problem (2020). https://www.roadef.org/challenge/2020/en/
Ropke, S., Pisinger, D.: An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp. Sci. 40(4), 455–472 (2006). https://doi.org/10.1287/trsc.1050.0135
Ruiz, M., Tournebise, P., Panciatici, P.: ROADEF Challenge RTE: Grid Operation-Based Outage Maintenance Planning. Technical report, RTE (2020)
Salinas San Martin, L., Yang, J., Liu, Y.: Hybrid NSGA III/dual simplex approach to generation and transmission maintenance scheduling. Int. J. Electric. Power Energy Syst. 135, 10 (2022). https://doi.org/10.1016/j.ijepes.2021.107498
Saraiva, J.T., Pereira, M.L., Mendes, V.T., Sousa, J.C.: A simulated annealing based approach to solve the generator maintenance scheduling problem. Electr. Power Syst. Res. 81(7), 1283–1291 (2011). https://doi.org/10.1016/j.epsr.2011.01.013
Schlünz, E.B., Van Vuuren, J.H.: An investigation into the effectiveness of simulated annealing as a solution approach for the generator maintenance scheduling problem. Int. J. Electr. Power Energy Syst. 53(1), 166–174 (2013). https://doi.org/10.1016/j.ijepes.2013.04.010
Shahidehpour, M., Marwali, M.: Maintenance Scheduling in Restructured Power Systems. Springer, New York (2000). https://doi.org/10.1007/978-1-4615-4473-9
Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: International Conference on Principles and Practice of Constraint Programming, pp. 417–431. Springer (1998)
Smith, S.L., Imeson, F.: GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem. Comput. Oper. Res. (2017). https://doi.org/10.1016/j.cor.2017.05.010
Suresh, K., Kumarappan, N.: Hybrid improved binary particle swarm optimization approach for generation maintenance scheduling problem. Swarm Evol. Comput. 9, 69–89 (2013). https://doi.org/10.1016/j.swevo.2012.11.003
Than Kyi, M., Maw, S.S., Naing, L.L.: Mathematical estimation for maximum flow in electricity distribution network by Ford–Fulkerson iteration algorithm. Int. J. Sci. Res. 9(8), 9229 (2019). https://doi.org/10.29322/ijsrp.9.08.2019.p9229
Volkanovski, A., Mavko, B., Boševski, T., Čauševski, A., Čepin, M.: Genetic algorithm optimisation of the maintenance scheduling of generating units in a power system. Reliab. Eng. Syst. Saf. 93(6), 779–789 (2008). https://doi.org/10.1016/j.ress.2007.03.027
Wang, Y., Zhong, H., Xia, Q., Kirschen, D.S., Kang, C.: An approach for integrated generation and transmission maintenance scheduling considering N-1 contingencies. IEEE Trans. Power Syst. 31(3), 2225–2233 (2016). https://doi.org/10.1109/TPWRS.2015.2453115
Wen, M., Linde, E., Ropke, S., Mirchandani, P., Larsen, A.: An adaptive large neighborhood search heuristic for the electric vehicle scheduling problem. Comput. Oper. Res. 76, 73–83 (2016). https://doi.org/10.1016/j.cor.2016.06.013
Woller, D., Kulich, M.: The ALNS metaheuristic for the maintenance scheduling problem. In: Proceedings of the 18th International Conference on Informatics in Control, Automation and Robotics, ICINCO 2021, pp. 156–164 (2021). https://doi.org/10.5220/0010552101560164
Acknowledgements
The work on this paper was supported by the Czech Science Foundation grant 23 - 05104S. The work of David Woller was also supported by the Grant Agency of the Czech Technical University in Prague, grant No. SGS23/122/OHK3/2T/13. Computational resources were supplied by the project “e-Infrastruktura CZ” (e-INFRA CZ LM2018140) supported by the Ministry of Education, Youth and Sports of the Czech Republic.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Woller, D., Rada, J. & Kulich, M. The ALNS metaheuristic for the transmission maintenance scheduling. J Heuristics 29, 349–382 (2023). https://doi.org/10.1007/s10732-023-09514-x
Received:
Revised:
Accepted:
Published:
Version of record:
Issue date:
DOI: https://doi.org/10.1007/s10732-023-09514-x
