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

Sophie Jacquin 1, * Laetitia Jourdan 2 El-Ghazali Talbi 1
* Auteur correspondant
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Résumé :

Le 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

 

Type de document :
Communication dans un congrès
ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Feb 2014, Bordeaux, France
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-00946437
Contributeur : Martine Courbin-Coulaud <>
Soumis le : jeudi 13 février 2014 - 16:07:31
Dernière modification le : samedi 16 janvier 2016 - 01:09:10

Identifiants

  • HAL Id : hal-00946437, version 1

Citation

Sophie Jacquin, Laetitia Jourdan, El-Ghazali Talbi. Une metaheuristique basée sur la programmation dynamique pour l'UCP. ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Feb 2014, Bordeaux, France. 〈hal-00946437〉

Partager

Métriques

Consultations de la notice

437