Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Résumé

Dans plusieurs secteurs d'activité comme l'aéronautique, l'informatique, les télécommunications, l'environnement, le transport et autres, les décideurs sont confrontés à des problèmes de complexité grandissante. Il peut s'agir d'optimiser le trajet d'un véhicule, de minimiser des coûts de production, de supporter la prise de décision, d'améliorer les performances d'un circuit électronique ou encore d'ordonnancer les processus dans un système informatique. Dans de nombreux cas, le problème à résoudre peut s'exprimer comme un problème d'optimisation combinatoire qui est rarement uni-objectif. En effet, la plupart des problèmes d'optimisation combinatoire rencontrés dans la pratique nécessitent l'optimisation simultanée de plusieurs objectifs souvent contradictoires. C'est par exemple le cas pour le problème d'ordonnancement de voitures. Toutefois, malgré l'intérêt indéniable d'aborder les problèmes industriels d'un point de vue multi-objectifs, plusieurs auteurs ont noté, en recensant la littérature, que les chercheurs s'attardaient principalement à des contextes théoriques de base. En contexte multi-objectifs, l'utilisation de métaheuristiques s'avère souvent d'une grande utilité.

Parmi les métaheuristiques, les algorithmes évolutionnaires, et plus particulièrement les algorithmes génétiques, se sont distingués comme étant des techniques bien adaptées à la résolution de problèmes multi-objectifs notamment à cause de leur faculté à exploiter de vastes espaces de recherche et à générer des compromis multiples en une seule étape d'optimisation. Les algorithmes génétiques tentent de simuler le processus de sélection naturelle dans un environnement hostile lié au problème à résoudre en s'inspirant des théories de l'évolution proposées par Darwin et des méthodes de combinaison de gènes introduites par Mendel.

Dans cette thèse, nous proposons des approches de résolution efficaces basées sur des algorithmes évolutionnaires permettant de supporter la prise de décision pour des problèmes d'ordonnancement industriel multi-objectifs comme le problème d'ordonnancement de voitures. En particulier, nous présentons dans un premier temps deux nouveaux opérateurs de croisement pour le problème théorique d'ordonnancement de voitures. Nous mettons ainsi en évidence l'importance d'utiliser des opérateurs génétiques dédiés à la problématique étudiée et ce, même lorsque l'emploi d'opérateurs naturels est possible. Une fois cette étape réalisée, nous proposons deux schémas de coopération entre algorithmes évolutionnaires et méthodes exactes pour résoudre le problème théorique d'ordonnancement de voitures. Par la suite, nous abordons la résolution du problème industriel d'ordonnancement de voitures en proposant un algorithme génétique efficace qui permet de résoudre le problème de manière îexicographique. Finalement, nous abordons la problématique industrielle d'ordonnancement de voitures d'un point de vue intégralement multi-objectifs en développant un algorithme Pareto générique qui hybride des concepts issus des algorithmes génétiques avec des concepts issus de la métaphore immune. C'est, à notre connaissance, le premier travail de recherche qui considère la problématique industrielle d'ordonnancement de voitures en traitant les objectifs simultanément sans leur attribuer d'ordre ou de poids. En plus d'avoir produit d'excellents résultats sur le problème industriel d'ordonnancement de voitures, l'approche proposée s'est aussi montrée particulièrement efficace sur un benchmark classique en optimisation multi-objectifs (le problème de sac à dos multi-objectifs). Ces résultats mettent en évidence l'intérêt pratique de ce genre d'approches en contexte industriel.