Les problèmes d’optimisation combinatoire sont d’un grand intérêt à la fois pour le monde scientifique et le monde industriel. La communauté scientifique a oeuvré pour la simplification de certains problèmes issus du monde industriel vers des modèles d’optimisation combinatoire. Parmi ces problèmes, on peut trouver des problèmes appartenant à la famille du problème du sac à dos (knapsack). Dans cette thèse, nous considérons une variante du problème du sac à dos : le problème du sac à dos avec des contraintes disjonctives (Knapsack with Disjunctive Constraints). En raison de la difficulté de cette problématique, nous nous sommes intéressés au développement de méthodes heuristiques produisant des solutions de bonne qualité en un temps de calcul modéré. Nos travaux de recherche s’appuient sur le principe de la recherche par voisinage. Bien que cette façon de faire nous conduise vers des solutions approchées,leur utilisation ainsi que les résultats que nous avons obtenus restent intéressants tout en gardant un temps d’exécution raisonnable. Afin de résoudre des instances de grande taille pour la problématique étudiée, nous avons proposé des méthodes séquentielles et parallèles. Ces deux techniques de résolution sont basées sur la recherche par voisinage. Dans un premier temps, une première méthode de recherche par voisinage aléatoire a été proposée. Elle s’appuie sur la combinaison de deux procédures : une première procédure qui cherche à construire une série de solutions partielles et une deuxième procédure qui complète chacune des solutions partielles courantes par une exploration de son voisinage. Ensuite, une deuxième méthode adaptative a été mise en place. Elle s’appuie sur un système d’optimisation par colonie de fourmis pour simuler une recherche guidée et une procédure de descente pour explorer au mieux les solutions produites au cours du processus de recherche. Finalement, une troisième méthode a été élaborée dans le but de faire évoluer la performance des méthodes de recherche par voisinage. Dans cette partie de nos travaux de recherche, nous avons proposé une recherche par voisinage aléatoire parallèle. Nous nous appuyés sur l’exploration simultanée de différents (sous) espaces de recherche par différents processeurs, où chaque processeur adopte sa propre stratégie aléatoire pour construire ses propres voisinages en fonction de ses informations internes récoltées / Combinatorial optimization problems are of high interest both for the scientific world and for the industrial world. The research community has simplified many practical situations as combinatorial optimization problems. Among these problems, we can find some problems belonging to the knapsack family. This thesis considers a particular problem belonging to the knapsack family, known as the disjunctively constrained knapsack problem. Because of the difficulty of this problem, we are searching for approximate solution techniques with fast solution times for its large scale instances. A promising way to solve the disjunctively constrained knapsack problem is to consider some techniques based upon the principle of neighborhood search. Although such techniques produce approximate solution methods, they allow us to present fast algorithms that yield interesting solutions within a short average running time. In order to tackle large scale instances of the disjunctively constrained knapsack problem, we present sequential and parallel algorithms based upon neighborhood search techniques. The first algorithm can be viewed as a random neighborhood search method. This algorithm uses a combination of neighborhood search techniques in order to randomly explore a series of sub-solution spaces, where each subspace is characterized by a neighborhood of a local optimum. The second algorithm is an adaptive neighborhood search that guides the search process in the feasible solution space towards high quality solutions. This algorithm uses an ant colony optimization system to simulate the guided search. The third andlast algorithm is a parallel random neighborhood search method which exploits the parallelism for exploring simultaneously different sub-solution spaces by several processors. Each processor adopts its own random strategy to yield its own neighborhoods according to its internal information
| Identifer | oai:union.ndltd.org:theses.fr/2015AMIE0010 |
| Date | 15 June 2015 |
| Creators | Saleh, Sagvan Ali |
| Contributors | Amiens, Hifi, Mhand, Wu, Lei |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English, French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0021 seconds