Les problèmes d'optimisation combinatoire faisant partie de la classe de problèmes NP-difficiles sont abordés et traités de nombreuses manières dans la littérature. Lorsqu'il s'agit de résoudre ces problèmes, les méta-heuristiques sont des algorithmes bien adaptés aux conditions de résolution rencontrées dans les domaines pratiques. Elles offrent un compromis intéressant entre la qualité des solutions et le temps nécessaire à leur obtention. C'est en partie pourquoi le domaine des méta-heuristiques a pris beaucoup d'ampleur depuis les dernières années. De nombreuses méthodes y ont été introduites, dont l'Optimisation par Colonie de Fourmis (OCF) (Ant Colony Optimization) qui est un algorithme dont le comportement est basé sur celui des fourmis réelles. Depuis son introduction au début des années '90, l'OCF s'est montrée efficace pour la résolution de nombreux problèmes.
Parmi les problèmes d'optimisation combinatoire, on retrouve le Problème d'Ordonnancement de Voitures (POV) (Car Sequencing Problem). Ce problème théorique présente une problématique qui est également rencontrée dans les usines de production automobile. Le POV consiste à déterminer, à l'aide d'un carnet de commandes définissant les options requises pour chaque voiture à assembler, l'ordre dans lequel produire ces véhicules afin de minimiser les dépassements de capacité des postes de la chaîne de montage. Les véhicules sont produits en séquences dont l'ordre ne peut être modifié une fois le processus enclenché. Certaines options, comme le toit ouvrant, la traction intégrale ou les freins anti-blocage, nécessitent un temps de traitement plus important. Ces différences dans les temps de traitement impliquent des contraintes de capacité pour les postes de la chaîne qui y sont associés. Si, à un moment dans la séquence, la demande pour une option dépasse la capacité du poste qui la traite, il y a retard sur la chaîne et des coûts supplémentaires sont impliqués. En raison de sa structure et de ses contraintes globales de séquencement, le POV représente un défi intéressant en optimisation.
Ce travail de recherche propose un nouvel algorithme d'OCF spécifiquement adapté pour la résolution du POV. Un algorithme tiré de la littérature et conçu pour le POV sert à la fois de base de comparaison et d'algorithme de départ pour la réalisation du projet. La démarche consiste à modifier cet algorithme de départ, étape par étape et de manière incrémentale, afin de le bonifier de certains éléments spécialisés pour résoudre le POV. Ces bonifications sont au nombre de trois : la première concerne les mécanismes d'apprentissage de l'algorithme, alors que les deux autres apportent une plus grande variation dans le comportement des fourmis.
Premièrement, la nature des contraintes du POV a inspiré une modification importante de la trace de phéromone. Cette trace est une mémoire collective à l'intérieur de laquelle est consignée l'apprentissage accumulé par la colonie. Un nouvel élément y est apporté afin de mieux l'adapter à la forme des contraintes du POV. Deuxièmement, des mécanismes permettant de diversifier la recherche de solutions sont proposés. Lorsqu'elle fait un choix, une fourmi cherche un compromis entre l'apprentissage et sa vision locale du problème. Les paramètres définissant l'importance relative de ces éléments sont ceux touchés par cette seconde modification. Finalement, un nouveau mode de construction des solutions est proposé. Une fourmi construit normalement sa solution de manière séquentielle, de la première position à la dernière. La bonification proposée permet à une fourmi de revenir sur des parties de solutions déjà fixées pour y insérer de nouveaux éléments.
Nous verrons que les trois éléments modifiés ou ajoutés à l'algorithme de départ contribuent à améliorer la performance générale. La nouvelle trace de phéromone permet d'identifier et d'encourager les motifs à répéter dans les solutions. Les variations des valeurs de paramètres aident à la diversification de la recherche dans l'espace de solutions et à mieux utiliser l'effort de calcul alloué. Quant au nouveau mode de construction, il se montre profitable dans certaines conditions et constitue une idée novatrice et généralisable pour traiter d'autres problèmes.
Les éléments proposés sont novateurs. Ce travail de recherche, loin de se prétendre exhaustif, apporte de nouveaux concepts avec un bon potentiel d'exploration. Les éléments présentés se sont montrés efficaces et pourraient aisément faire l'objet de travaux futurs pour en trouver des variantes encore plus intéressantes. Finalement, bien que le problème traité ici soit de nature théorique, les idées apportées sont transférables à la problématique industrielle pratique rencontrée par les fabricants automobiles.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QCU.578 |
| Date | January 2005 |
| Creators | Morin, Sara |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Detected Language | French |
| Type | Thèse ou mémoire de l'UQAC, NonPeerReviewed |
| Format | application/pdf |
| Relation | http://constellation.uqac.ca/578/ |
Page generated in 0.0045 seconds