Une metaheuristique basée sur la programmation dynamique pour l'UCP

International audienceLe problème d'affectation d'unités ou Unit Commitment Problem, est un problème NP-Complet très étudié dans la littérature. L'objectif de ce problème consiste à faire un choix stratégique sur l'état de marche/arrêt et les quantités d'énergie produites par un ensemble d'unités de production fonctionnant en parallèle. Cependant, cette production engendre des coûts financiers importants, il faut donc les minimiser tout en satisfaisant la demande et en respectant un ensemble de contraintes techniques. La programmation dynamique (PD) est une méthode d'optimisation qui permet de résoudre ce problème de façon exacte. Elle s'appuie sur une modélisation du problème comme une recherche d'un meilleur chemin dans un graphe d'états. Néanmoins le temps de calcul et l'espace mémoire nécessaires à l'application d'une telle méthode augmentent exponentiellement avec le nombre d'unités. Cela la rend inapplicable à la résolution de problèmes réels de grande taille. Nous proposons un algorithme génétique (AG) permettant de guider la recherche effectuée par la PD en manipulant directement des solution représentées sous forme de chemins du graphe d'états. Cette représentation des solutions constitue l'originalité et la contribution majeure de notre travail. Nous verrons en effet qu'elle permet d'obtenir de très bons résultats et apporte une amélioration importante par rapport aux algorithmes de la littérature utilisant une représentation plus classique. https://docs.google.com/file/d/0B90YRHhLCDA6dTF1aFF4a2N0Tnc/edit