Mixed-integer Programming Models for Maintenance Scheduling in Power Transmission Systems

Les systèmes de transport d’énergie électrique jouent un rôle fondamental, car ils constituent la connexion physique entre les centrales de production d’électricité et les systèmes de distribution aux consommateurs. Les systèmes de transport sont constitués de divers types d’équipements interconnectés, tels que des transformateurs et des lignes de transmission, qui sont constamment exposés à des pannes. Les pannes d’équipements peuvent entraîner des coupures d’alimentation, réduire la fiabilité du réseau, provoquer des accidents et détériorer la qualité de l’énergie fournie. Une défaillance de l’approvisionnement d’énergie aux clients peut entraîner des pertes financières pour les clients et pour les compagnies d’électricité qui exploitent le réseau de transport. En conséquence, ces sociétés planifient méticuleusement l’entretien de leurs actifs, assurant un fonctionnement sûr et continu du réseau. Les gestionnaires de réseau de transport d’électricité désignent les meilleurs moments pour retirer chaque équipement du réseau de transport d’électricité pour sa réparation préventive et sa maintenance. Cependant, pour que ces périodes soient décidées et qu’un calendrier soit établi, plusieurs conditions déterminées par l’opérateur doivent être remplies. Par exemple, le flux de puissance du réseau et ses limites de fonctionnement sécuritaire doivent être respectés ainsi que les outils pour effectuer les tâches doivent être disponibles. Lorsque cet ensemble de contraintes est satisfait simultanément, un groupe de solutions réalisables et viables pour la planification de la maintenance est obtenu. Afin de mettre en oeuvre cette procédure d’optimisation, il est nécessaire d’utiliser une fonction objectif et par conséquent définir une solution optimale parmi les solutions réalisables. Ce problème d’optimisation, abordé dans cette dissertation, est décrit dans la littérature comme le problème de planification de la maintenance dans les systèmes de transport d’énergie (TMS). Cette étude sur la planification de la maintenance a été élaborée sur la base des intérêts et du contexte d’une grande compagnie d’électricité canadienne. La résolution du problème TMS annuel est la première phase. Dans un premier temps, le programme linéaire mixte (MILP) a été formulé en maximisant à la fois la préférence d’entretien de la ligne de transport pour certaines semaines et l’énergie fournie aux consommateurs en cas de panne de la ligne de transport. Les contraintes mathématiques ne permettent pas non plus la division du réseau ou une isolation de bus. Les principales raisons à l’appui de cette formulation sont le développement et la validation d’une approche plus globale pour maintenir le réseau connecté et prendre en compte l’occurrence de pannes inattendues et d’événements de maintenance corrective. Le modèle proposé est basé sur le problème de planification d’unités de production et par un test de connectivité basé sur un problème de flux. Afin de résoudre ce grand modèle mathématique plus rapidement, un algorithme de décomposition a été proposé, évitant ainsi aux solveurs standard le travail difficile de la résolution directe du modèle. Dans un deuxième temps, le problème TMS court terme est résolu à partir de l’ordonnancement annuel obtenu à l’étape précédente. Ce modèle indique les meilleures heures pour que chaque tâche de maintenance ait lieu dans les semaines déjà préétablies par le TMS annuel, tout en minimisant les coûts de maintenance en ligne, production d’énergie et émissions de CO2. La justification principale du développement de ce modèle est de voir si le fait d’autoriser l’utilisation des heures supplémentaires est économiquement moins cher pour l’entreprise d’électricité que de l’interdire. De plus, deux méthodes ont été proposées pour le traitement des données d’entrée provenant du modèle à long terme afin qu’elles puissent être utilisées de manière efficace dans le modèle à court terme. En partant du modèle MILP proposé dans la première étape et en tenant compte de la nature stochastique des modèles de maintenance étudiés, enfin, dans un troisième temps, nous abordons le problème annuel TMS qui considère l’incertitude sur la durée des tâches de maintenance. La raison de cette étude est d’obtenir un calendrier insensible aux éventuels retards dans la durée de la maintenance, considérant que ces valeurs ne sont pas connues avec précision au moment de la planification et qu’il existe plusieurs scénarios plausibles. La résolution directe de ce grand MILP stochastique par des solveurs standard étant difficile, nous proposons donc un nouvel algorithme de décomposition. Ainsi, pour traiter l’ordonnancement de la maintenance dans les systèmes de transmission de puissance, plusieurs modèles mathématiques et informatiques ont été fournis. En raison des caractéristiques du problème, tous les modèles proposés sont formulés sous forme de programmes linéaires entiers mixtes et, les modèles à long terme sont capables de déterminer les semaines au cours desquelles les tâches de maintenance ont lieu pour chaque ligne et ensuite le modèle à court terme établit les meilleures heures pour ces tâches.

Abstract

Electrical power transmission systems have a fundamental role as they are the physical connection between power generation stations and consumer distribution systems. Transmission systems consist of various types of interconnected equipment, such as transformers and transmission lines, which are constantly exposed to failures. Equipment failures can lead to power supply interruption, reduce network reliability, cause accidents, and deteriorate the quality of the energy supplied. A failure in the supply of energy to customers can lead to financial losses for customers and for the utilities that operate the transmission network. As a result, the utilities meticulously schedule the maintenance of their assets, ensuring a safe and continuous operation of the network. Utilities designate the best times to extract each piece of equipment from the power transmission grids for preventive repair and maintenance. However, for these periods to be decided and a calendar to be settled, several conditions determined by the utility must be met. For example, the power flow of the network and its limits of safe operation must be respected as well as the tools to perform the tasks must be available. When this set of constraints are simultaneously met, a group of feasible and viable solutions for the maintenance scheduling is obtained. In order to implement this optimization procedure it is necessary to use an objective function and thus define an optimal solution among the feasible solutions; in short this is the Transmission Maintenance Scheduling (TMS) problem. Based on the interests and context of a large Canadian utility, this study on maintenance scheduling was developed. Solving the annual TMS problem is the primary phase. First, a Mixed-Integer Linear Programming (MILP) model is formulated maximizing at the same time the transmission line maintenance preference for certain weeks and the energy supplied to consumers in the event of a transmission line failure. The mathematical constraints also do not allow for network splitting or bus isolation. The main reasons supporting this formulation are the development and validation of a more comprehensive approach to keep the network connected and to consider the occurrence of unexpected fails and corrective maintenance events. The proposed model is inspired by the unit commitment problem and by a connectivity test based on a flow problem. To solve this large mathematical model more quickly, a decomposition algorithm is proposed, thus avoiding for off-the-shelf solvers the challenging work of direct model resolution. In a second moment, the short-term TMS problem is solved starting from the annual scheduling obtained in the previous stage. This model points out the best hours for each maintenance task to take place within the weeks already pre-established by the annual TMS, while minimizing the costs of: line maintenance, power generation, and CO2 emissions. The main justification for developing this model is to analyze whether authorizing the use of overtime hours is economically cheaper for the utility than prohibiting it from occurring. In addition, two methods are proposed for the treatment of input data coming from the long-term model so that they can be used in the short-term model in an efficient way. Starting from the MILP model proposed in the first stage and taking into account the stochastic nature of the maintenance models studied, finally, in a third moment, the annual TMS problem that considers the uncertainty in the duration of the maintenance tasks is solved. The reason for this study is to obtain a schedule that is insensitive to possible delays in maintenance duration, considering that these values are not known exactly at planning time and that there are some plausible scenarios. The direct resolution of this large stochastic extensive MILP by off-the-shelf solvers is difficult, so a decomposition algorithm is proposed. Thus, mathematical and computational models are provided to deal with the maintenance schedule of power transmission systems. Due to the characteristics of the problem, all proposed models are formulated as mixed integer linear programs, and as a consolidation, the long-term models are able to determine the weeks in which maintenance tasks occur for each line, and then the short-term model establishes the best hours for these jobs.