Ce travail porte sur la résolution exacte d'un problème d'optimisation combinatoire multi-objectif. Nous cherchons d'une part à confirmer l'efficacité de l'algorithme dit en deux phases, et d'autre part à poser une généralisation des procédures de séparation et évaluation, populaires dans le cadre mono-objectif mais presque absentes en multi-objectif. Notre étude s'appuie sur le problème multi-objectif de sac à dos unidimensionnel en variables binaires. Ce dernier est un classique de l'optimisation combinatoire, présent comme sous problème dans de nombreux problèmes d'optimisation. La première partie de nos travaux porte sur un pré-traitement permettant de réduire la taille d'instances de ce problème. Nous mettons en évidence plusieurs propriétés permettant de déterminer a priori une partie de la structure de toutes les solutions efficaces. Nous nous attachons ensuite à décrire une procédure performante de type deux phases pour ce problème, tout d'abord dans le cas bi-objectif. Nous étendons ensuite cette procédure pour des instances ayant trois objectifs ou plus. Les résultats obtenus sont comparés aux meilleurs algorithmes existants pour ce problème et confirment l'efficacité de l'approche en deux phases. La dernière partie de notre travail concerne la généralisation au cas multi-objectif d'une procédure de séparation et évaluation. Nous identifions plusieurs difficultés auxquelles nous répondons en proposant deux nouvelles procédures. Les expérimentations numériques indiquent que ces dernières permettent de résoudre des instances en des temps raisonnables, bien qu'elles n'atteignent pas les performances d'une procédure de type deux phases.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00488215 |
| Date | 11 May 2010 |
| Creators | Jorge, Julien |
| Publisher | Université de Nantes |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0025 seconds