Matheuristics to optimize refueling and maintenance planning of nuclear power plants
Tóm tắt
Planning the maintenance of nuclear power plants is a complex optimization problem, involving a joint optimization of maintenance dates, fuel constraints and power production decisions. This paper investigates Mixed Integer Linear Programming (MILP) matheuristics for this problem, to tackle large size instances used in operations with a time scope of 5 years, and few restrictions with time window constraints for the latest maintenance operations. Several constructive matheuristics and a Variable Neighborhood Descent local search are designed. The matheuristics are shown to be accurately effective for medium and large size instances. The matheuristics give also results on the design of MILP formulations and neighborhoods for the problem. Contributions for the operational applications are also discussed. It is shown that the restriction of time windows, which was used to ease computations, induces large over-costs and that this restriction is not required anymore with the capabilities of matheuristics or local searches to solve such size of instances. Our matheuristics can be extended to a bi-objective optimization extension with stability costs, for the monthly re-optimization of the maintenance planning in the real-life application.
Tài liệu tham khảo
Adamo, T., et al.: MIP neighborhood synthesis through semantic feature extraction and automatic algorithm configuration. Comput. OR 83, 106–119 (2017)
Anghinolfi, D., Gambardella, L., et al.: A matheuristic algorithm for a large-scale energy management problem. Lect. Notes Comput. Sci. 7116, 173–181 (2012)
Barty, K., Bonnans, J., Pfeiffer, L.: Sensitivity analysis for the outages of nuclear power plants. Energy Syst. 5(2), 371–406 (2014)
Benoist, T., Estellon, B., Gardi, F., Megel, R., Nouioua, K.: Localsolver 1. x: a black-box local-search solver for 0-1 programming. 4OR 9(3), 299–316 (2011)
Bertacco, L., Fischetti, M., Lodi, A.: A feasibility pump heuristic for general mixed-integer problems. Discr. Optim. 4(1), 63–76 (2007)
Blum, C., Pedro, P., López-Ibáñez, M., Lozano, J.: Construct, merge, solve and adapt a new general algorithm for combinatorial optimization. Comput. OR 68, 75–88 (2016)
Brandt, F.: Solving a Large-scale Energy Management Problem with Varied Constraints. Master’s thesis, Karlsruhe Institute of Technology (2010)
Brandt, F., et al.: A constraint programming-based approach to a large-scale energy management problem with varied constraints. J. Sched. 16(6), 629–648 (2013)
Danna, E., Rothberg, E., Le Pape, C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102, 71–90 (2005)
Dell’Amico, M., Diaz, J.: Constructive heuristics and local search for a large-scale energy management problem. EURO Conference, Liboa (2010). http://www.roadef.org/challenge/2010/files/talks/S04%20-%20Diaz%20Diaz.pdf. Accessed 13 May 2020
Dopazo, J., Merrill, H.: Optimal generator maintenance scheduling using integer programming. IEEE Trans. Power Appar. Syst. 94(5), 1537–1545 (1975)
Dubost, L., Gonzalez, R., Lemaréchal, C.: A primal-proximal heuristic applied to the French unit-commitment problem. Math. Program. 104(1), 129–151 (2005)
Dupin, N.: Modélisation et résolution de grands Problèmes Stochastiques Combinatoires: Application à la gestion de Production d’électricité. Ph.D. thesis, Lille 1 (2015)
Dupin, N.: Tighter MIP formulations of the discretised unit commitment problem with min-stop ramping constraints. EURO J. Comput. Optim. 5(1–2), 149–176 (2017)
Dupin, N., Talbi, E.: Multi-objective robust scheduling to maintain French nuclear power plants. In: META 2016, The 6th International Conference on Metaheuristics and Nature Inspired Computing, Marrakech, pp. 1–10 (2016a)
Dupin, N., Talbi, E-G.: Dual heuristics and new lower bounds for the challenge EURO/ROADEF 2010. In: Matheuristics 2016, 6th International Workshop on Model-Based Metaheuristics, pp. 60–71 (2016b)
Dupin, N., Talbi, E-G.: Matheuristics for the discrete unit commitment problem with min-stop ramping constraints. In: Matheuristics 2016, 6th International Workshop on Model-Based Metaheuristics, pp. 72–81 (2016c)
Dupin, N., Talbi, E.-G.: Machine learning-guided dual heuristics and new lower bounds for the refueling and maintenance planning problem of nuclear power plants. Algorithms 13(8), 185 (2020a). https://doi.org/10.3390/a13080185
Dupin, N., Talbi, E.: Parallel matheuristics for the discrete unit commitment problem with min-stop ramping constraints. Int. Trans. Oper. Res. 27(1), 219–244 (2020b)
Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1–3), 23–47 (2003)
Fourcade, F., et al.: Optimizing nuclear power plant refueling with mixed-integer programming. Eur. J. Oper. Res. 97(2), 269–280 (1997)
Gardi, F., Nouioua, K.: Local search for mixed-integer nonlinear optimization: a methodology and an application. Lect. Notes Comput. Sci. 6622, 167–178 (2011)
Gavranović, H., Buljubasić, M.: A hybrid approach combining local search and constraint programming for a large scale energy management problem. RAIRO Oper. Res. 47(4), 481–500 (2013)
Godskesen, S., Jensen, T., Kjeldsen, N., Larsen, R.: Solving a real-life, large-scale energy management problem. J. Sched. 16(6), 567–583 (2013)
Gorge, A., Lisser, A., Zorgati, R.: Stochastic nuclear outages semidefinite relaxations. Comput. Manag. Sci. 9(3), 363–379 (2012)
Griset, R.: Méthodes pour la résolution efficace de très grands problèmes combinatoires stochastiques. Application à un problème industriel d’EDF: Application à un problème industriel d’EDF. Ph.D. thesis, Université Bordeaux (2018)
Guzelsoy, M., Nemhauser, G., Savelsbergh, M.: Restrict-and-relax search for 0–1 mixed-integer programs. EURO J. Comput. Optim. 1(1–2), 201–218 (2013)
Joncour, C.: Problèmes de placement 2D et application à l’ordonnancement: modélisation par la théorie des graphes et approches de programmation mathématique. Ph.D. thesis, Université Bordeaux, pp. 147-166 (2010)
Jost, V., Savourey, D.: A 0–1 integer linear programming approach to schedule outages of nuclear power plants. J. Sched. 16(6), 551–566 (2013)
Khemmoudj, M.: Modélisation et résolution de systèmes de contraintes : application au problème de placement des arrêts et de la production des réacteurs nucléaires d’EDF. Ph.D. thesis, Paris 13 (2007)
Larrain, H., et al.: A variable MIP neighborhood descent algorithm for managing inventory and distribution of cash in automated teller machines. Comput. OR 85, 22–31 (2017)
Laumanns, M., Thiele, L., Zitzler, E.: An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. Eur. J. Oper. Res. 169(3), 932–942 (2006)
Lusby, R., Muller, L., Petersen, B.: A solution approach based on Benders decomposition for the preventive maintenance scheduling problem of a stochastic large-scale energy system. J. Sched. 16(6), 605–628 (2013)
Maniezzo, V., Stützle, T., Voss, S. (eds.): Matheuristics: Hybridizing Metaheuristics and Mathematical Programming, Volume 10 of Annals of Information Systems. Springer, New York (2010)
Mladenović, N., Hansen, P., Urozević, D.: Variable neighborhood search and local branching. Comput. OR 33(10), 3034–3045 (2006)
Peekstok, J., Kuipers, E.: Roadef/Euro 2010 Challenge. Be Improved Tech Report (2010)
Pira, C., et al.: Column generation for an electricity production planning problem with stochastic outage durations. In: PGMO-COPI, Conference on Optimization and Practices in Industry, pp. 1–5 (2014)
Porcheron, M., et al.: Challenge ROADEF/EURO 2010: A Large-scale Energy Management Problem with Varied Constraints. EDF R&D Technical Report (2010)
Rajan, D., Takriti, S.: Min-Up/Down Polytopes of the Unit Commitment Problem with Start-Up Costs. Technical report, IBM Research Report (2005)
Renaud, A.: Daily generation management at electricité de France: from planning towards real time. IEEE Trans. Autom. Control 38(7), 1080–1093 (1993)
Rozenknopf, A., et al.: Solving the electricity production planning problem by a column generation based heuristic. J. Sched. 16(6), 585–604 (2013)
Taillard, É, Voss, S.: POPMUSIC-Partial optimization metaheuristic under special intensification conditions. In: Essays and Surveys in Metaheuristics, pp. 613–629. Springer (2002)