Дисертації з теми "Heuristique de recherche tabou"
Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Heuristique de recherche tabou.
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 дисертацій для дослідження на тему "Heuristique de recherche tabou".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
1
Gómez-Villouta, Giglia. "Méthodes heuristiques pour le problème de placement sur bande en deux dimensions." Angers, 2010. http://www.theses.fr/2010ANGE0022.
Анотація:
Les problèmes de placement sont généralement NP-difficiles, ou NP-complets suivant l'objectif à atteindre. Il s'agit ici de positionner un ensemble d'objets dans un ou plusieurs “container(s)”, de dimensions données ou de hauteur infinie, en respectant des contraintes liées à certaines caractéristiques (poids, quantité, rotation, équilibre, découpe guillotine. . . ). Ces problèmes ont de nombreuses applications pratiques. Les stratégies de résolution les plus efficaces sont généralement les méthodes approchées, en particulier la recherche locale. Dans cette thèse, nous nous intéressons à un problème de placement particulier en deux dimensions (sans rotation possible des objets (rectangulaires) ni prise en compte de la contrainte guillotine) connu sous le nom de “strip packing” (SPP). L'objectif de ce problème est de minimiser la hauteur atteinte après placement (sans chevauchement) des objets. Nous avons développé deux approches “méta-heuristiques” incluant des composants novateurs reposant sur une connaissance approfondie du problème. La première est un algorithme génétique avec un nouveau croisement (très “visuel”) et une fonction d'évaluation hiérarchique. La seconde est une recherche tabou avec représentation “directe” (i. E. N'utilisant pas les habituelles permutations) dont les caractéristiques principales sont un voisinage consistant, une diversification reposant sur l'historique de la recherche et une fonction d'évaluation qui mesure la qualité de solutions éventuellement partielles. Les deux approches proposées, évaluées sur un jeux de test bien connu et très difficile, se sont révélées performantes comparées à d'autres stratégiesPacking problems are usually NP-hard, or NP-complete according to the objective. One has to locate a set of objects into one or more “container(s)”, with fix dimensions or of infinite height, while respecting constraints related to some characteristics (weight, quantity, rotation, stability, guillotine cuts. . . ). Themain interest of these problems are the numerous practical applications from various domains. The most effective solution strategies for these problems are usually approximate methods, local search in particular. In this thesis, we are interested in a particular two-dimensional packing problem (without rotation nor guillotine cuts) known as “strip packing” (SPP). The objective of this problem, after locating rectangular objects without overlap, is to minimize the height of the resulting packing. We developed two “meta-heuristic” approaches for the SPP, both including innovative components based on problem knowledge. The first one is a genetic algorithm with a new (highly “visual”) crossover and a hierarchical fitness function. The second one is a tabu search with “direct” representation (i. E. Not using the classical permutations) whose main characteristics are a consistent neighborhood, a “well-informed” diversification (based on the search history), and a fitness function able to evaluate possibly partial solutions. The two proposed approaches, assessed on a well-known and very difficult benchmark, show good performances compared with other strategies
2
Kuri, Josué. "Problèmes d'optimisation dans les réseaux optiques de transport avec des connexions planifiées." Paris, ENST, 2003. http://www.theses.fr/2003ENST0028.
Анотація:
Nous étudions des problèmes d'optimisation liés à l'ingénierie d'un réseau de transport optique (OTN). Nous proposons un modèle de trafic dynamique déterministe appelé Scheduled Lightpath Demand (SLDs). Une demande de connexion est representée par un quintuplet (s, d, n, a, o) où s et d représentent les noeuds source et destination, n représente le nombre de connexions requises et a/o sont les dates d'établissement et de fin des connexions. Le modèle décrit la distribution spatio-temporelle d'un ensemble de connexions et facilite l'utilisation de techniques d'optimisation combinatoire pour la résolution de problèmes d'optimisation réseau. Nous étudions 3 problèmes d'optimisation réseau impliquant ce modèle : le routage et l'affectation de longueurs d'onde, le routage et l'affectation de ressources de protection et le routage et l'agrégation dans un réseau avec deux niveaux de granularité de commutation. Des méta-heuristiques sont proposés pour le calcul de solutions approchéesWe investigate optimization problems arising in the engineering of an Optical Transport Network (OTN). We propose a dynamic deterministic traffic model called Scheduled Lightpath Demands (SLDs) in which a connection demand is represented by a tuple (s, d, n, a, o); s and d are the source and destination nodes, n is the number of requested connections and a/o are the set-up/tear-down dates of the connections. The model captures the time and space distribution of a set of demands and eases the use of combinatorial optimization techniques to solve network optimization problems. We address 3 OTN engineering problems involving SLDs: Routing and Wavelength Assignment, Diverse Routing and Spare Capacity Assignment, and Routing and Grooming in a multi-granularity switching network. We formulate the problems as optimization problems and propose meta-heuristic algorithms to compute approximate solutions. The algorithms provide solutions of good quality in reasonable computing time
3
Khemakhem, Mahdi. "Heuristiques pour un Problème de m-Tournées Sélectives." Phd thesis, Université de Valenciennes et du Hainaut-Cambresis, 2008. http://tel.archives-ouvertes.fr/tel-00440494.
Анотація:
Cette thèse aborde un problème de transport appelé le Problème de m-Tournées Sélectives (PmTS) ou ”Team Orienteering Problem” en anglais. Le PmTS consiste à construire m tournées pour une flotte de véhicules afin de desservir un sous-ensemble sélectionné de clients. Dans le PmTS un service est fourni à chaque client visité en contrepartie de quoi, un gain est récolté. La tournée de chaque véhicule part d'un dépôt, passe par un sous-ensemble de clients et revient en un autre sans dépasser la longueur maximale autorisée. Chaque client peut être desservi au plus une fois par un unique véhicule. L'objectif est de maximiser le gain total récolté. Le PmTS étant un problème NP-difficile, notre objectif de recherche a consisté à proposer des heuristiques basées sur le principe général de ”Cluster first - Route second”. Ces algorithmes sont prévus pour être intégrés dans un logiciel de planification des tournées de techniciens de maintenance.
4
Gomez-Villouta, Giglia. "Méthodes heuristiques pour le problème de placement sur bande en deux dimensions." Phd thesis, Université d'Angers, 2010. http://tel.archives-ouvertes.fr/tel-00575859.
Анотація:
Les problèmes de placement sont généralement NP-difficiles, ou NP-complets suivant l'objectif à atteindre. Il s'agit ici de positionner un ensemble d'objets dans un ou plusieurs “container(s)”, de dimensions données ou de hauteur infinie, en respectant des contraintes liées à certaines caractéristiques (poids, quantité, rotation, équilibre, découpe guillotine...). Ces problèmes ont de nombreuses applications pratiques. Les stratégies de résolution les plus efficaces sont généralement les méthodes approchées, en particulier la recherche locale. Dans cette thèse, nous nous intéressons à un problème de placement particulier en deux dimensions (sans rotation possible des objets (rectangulaires) ni prise en compte de la contrainte guillotine) connu sous le nom de “strip packing” (SPP). L'objectif de ce problème est de minimiser la hauteur atteinte après placement (sans chevauchement) des objets. Nous avons développé deux approches “méta-heuristiques” incluant des composants novateurs reposant sur une connaissance approfondie du problème. La première est un algorithme génétique avec un nouveau croisement (très “visuel”) et une fonction d'évaluation hiérarchique. La seconde est une recherche tabou avec représentation “directe” (i.e. n'utilisant pas les habituelles permutations) dont les caractéristiques principales sont un voisinage consistant, une diversification reposant sur l'historique de la recherche et une fonction d'évaluation qui mesure la qualité de solutions éventuellement partielles. Les deux approches proposées, évaluées sur un jeux de test bien connu et très difficile, se sont révélées performantes comparées à d'autres stratégies.
5
Sbihi, Abdelkader. "Les Méthodes Hybrides en Optimisation Combinatoire :Algorithmes Exacts et Heuristiques." Phd thesis, Université Panthéon-Sorbonne - Paris I, 2003. http://tel.archives-ouvertes.fr/tel-00012188.
Анотація:
La thèse se situe dans le domaine de l'optimisation combinatoire, en particulier celui de lamodélisation et de la résolution algorithmique. Dans cette thèse, nous étudions deux variantes
NP-difficiles de problèmes de type sac-à-dos. Plus précisément, nous traitons le problème de
la distribution équitable (le Knapsack Sharing Problem : KSP) et le problème du sac-à-dos
généralisé à choix multiple (le Multiple-choice Multidimensional Knapasck Problem : MMKP).
Dans la première partie de cette thèse, nous nous intéressons au développement d'algorithmes
approchés pour les deux variantes évoquées du problème de type sac-à-dos. La deuxième partie
traite essentiellement de la résolution exacte du problème du sac-à-dos généralisé à choix multiple.
L'approche exacte que nous proposons est de type séparation et évaluation s'appuyant
principalement sur : (i) le calcul des bornes inférieure et supérieure et (ii) l'utilisation de la
stratégie par le meilleur d'abord en développant des branches à double noeuds fils et frère.
La première partie porte sur l'étude et la résolution approchée des deux problèmes KSP et
MMKP. Concernant le problème de la distribution équitable, nous proposons dans un premier
temps, une première version de l'algorithme exploitant certaines caractéristiques de la
recherche tabou. Dans un deuxième temps, nous développons une deuxième version de l'algorithme dont l'idée principale consiste à tenter de combiner l'intensification de la recherche dans l'espace des solutions et la diversification de la solution obtenue. Nous soulignons la rapidité
de la première version et l'efficacité de la deuxième. Ensuite nous nous intéressons au problème
de sac-à-dos généralisé à choix multiple. Nous proposons deux heuristiques de recherche locale
itérative. Le premier algorithme s'appuie sur une “recherche guidée”. Le deuxième algorithme
est une recherche locale que nous appelons réactive avec stratégies de déblocage et de dégradtion améliorantes de la solution et basées sur l'inter-change local.
Dans la deuxième partie de cette thèse, nous proposons une méthode de résolution exacte de type séparation et évaluation pour le problème du sac-à-dos généralisé à choix multiple. D'une part, nous nous proposons la réduction du problème initial au problème auxiliaire MMKPaux qui n'est autre que le problème de sac-à-dos à choix multiple MCKP. Nous calculons une borne supérieure pour le MMKPaux et nous établissons le résultat théorique pour lequel une borne supérieure pour le MMKPaux est une borne supérieure pour le MMKP. D'autre part, nous proposons le calcul d'une borne supérieure ainsi qu'une borne inférieure de départ pour le problème étudié qui sont nécessaires pour la réduction de l'espace de recherche. L'étude expérimentale montre l'efficacité de la méthode proposée sur différents groupes d'instances de petite et moyenne taille.
Nous expliquons enfin pourquoi cet algorithme exact atteint ses limites de résolution, dˆues
principalement à la complexité intrinsèque du modèle étudié. D'autant la résolution dépend de
la taille et la densité des instances traitées.
6
Duvivier, David. "Étude de l'hybridation des méta-heuristiques, application à un problème d'ordonnancement de type jobshop." Phd thesis, Université du Littoral Côte d'Opale, 2000. http://tel.archives-ouvertes.fr/tel-00008729.
Анотація:
Dans ce mémoire, nous étudions les méthodes itératives de recherche dans le cadre de la résolution du problème d'ordonnancement de type jobshopPlus que les performances en elles-mêmes, nous nous intéressons tout particulièrement à la compréhension du fonctionnement des méthodes de résolution ainsi qu'à l'analyse de l'influence de la coopération de plusieurs méthodes de recherche sur la qualité des solutions engendrées.
Dans un premier temps, nous évaluons l'apport de critères secondaires intégrés dans la fonction coût. Nous utilisons des algorithmes itératifs de recherche pour étudier l'impact de l'intégration de ces critères sur le paysage adaptatif ainsi que sur la qualité des ordonnancements engendrés.
Nous proposons ensuite quelques améliorations du schéma d'application des opérateurs dans les algorithmes génétiques.
Finalement, nous étudions quelques modèles d'hybridation des méta-heuristiques basés sur la recherche tabou et les algorithmes évolutifs.
7
Mynard, Laurent. "Exploration locale oscillante heuristiquement ordonnée." Paris 6, 1998. http://www.theses.fr/1998PA066255.
Анотація:
Cette thèse présente un nouvel algorithme d'exploration par voisinage pour la résolution de problèmes d'optimisation combinatoire. Cet algorithme se nomme HOLSA, acronyme de Heuristic Oscillating Local Search Algorithm. Son originalité vient de l'utilisation de techniques issues de l'énumeration implicite au sein d'un schéma général d'exploration locale et de l'usage systématique d'une stratégie oscillante. L'énumération implicite, en particulier A*, a inspiré tout d'abord la méthode d'évaluation des éléments, qui permet d'inclure un aspect prédictif dans l'exploration, aspect en général ignoré des méthodes d'exploration locale. Ensuite, elle a influencé la méthode de mémorisation retenue, qui se démarque fortement de la mémoire flexible de la recherche tabou, processus de mémorisation le plus utilisé en exploration locale. HOLSA a été expérimenté pour la résolution du sac à dos multidimensionnel, en variables 0 - 1 ou en variables entières, sur une librairie de problèmes de la littérature comme sur des instances aléatoires. Mais son application n'est pas restreinte à un seul type de problèmes, et il fonctionne également pour des problèmes d'optimisation non linéaire. Les comparaisons avec les principaux algorithmes d'exploration locale et avec la méthode par évaluation et séparation (Branch and Bound) montrent que cette approche présente un intérêt et permet d'obtenir un rapport performant entre la qualité de la solution trouvée et le temps de résolution requis.
8
Zribi, Nozha. "Ordonnancement de job-shops flexibles sous contraintes de disponibilité des machines." Ecole Centrale de Lille, 2005. http://www.theses.fr/2005ECLI0012.
Анотація:
Mise en oeuvre de méthodologies pour la résolution du probléme de job-shop flexible sous contraintes de disponibilités des machines. La partie1 concerne le développement de nouvelles méthodes efficaces pour la résolution du FJSP par une approche par phases. Deux méthodes sont développées pour la résolution de l'affectation: une méthode exacte de type B&B et une méthode approchée, basée sur une heuristique permettant une bonne répartition des charges, suivie d'une recherche Tabou. Nous avons développé des bornes inférieures pour le makespan et pour la somme des retards puis introduit une approche intégrée basée sur les AG améliorant les approches existantes. La partie 2 concerne l'introduction de contraintes de disponibilité: dans le cas où les données concernant les tâches de maintenance sont fixées, nous avons traité le cas où les machines ont la même vitesse et proposé une heuristique basée sur des régies de priorité. Nous avons défini un critére approprié basé sur le calcul d'une borne inférieure du makespan en présence de contraintes de disponibilité. Une adaptation d'un AG est proposée pour résoudre le problème de séquencement s/c de disponibilité. Pour étudier la complexité des problèmes à deux jobs, nous avons généralisé l'approche géométrique temporisée pour tenir compte de la propriété de flexibililité et proposé un algorithme polynomial pour la résolution du problème à deux jobs. Une adaptation de l'approche intégrée et une borne inférieure sont développées pour le problème général. Nous avons traité ensuite le cas où les tâches de maintenance sont flexibles avec une fenêtre de temps allouée. Différentes heuristiques sont proposées et validées sur des benchmarks
9
Khanafer, Ali. "Algorithmes pour des problèmes de bin packing mono- et multi-objectif." Thesis, Lille 1, 2010. http://www.theses.fr/2010LIL10088/document.
Анотація:
Le problème de bin packing consiste à déterminer le nombre minimum de conteneurs (bins) nécessaires pour ranger un ensemble d’objets. Ce problème NP- complet fait depuis de nombreuses années l’objet de multiples travaux de recherche, théoriques et pratiques. On le retrouve entre autres dans l’industrie de découpe de tissu, de l’acier, de bois et de verre. La littérature sur le problème de bin packing est riche et les algorithmes et approches de résolution sont très diverses. Cependant, les solutions proposées par ces algorithmes peuvent ne pas être utiles quand on traite des problèmes industriels réels. Dans cette thèse, nous considérons plusieurs types de contraintes liées à des incompatibilités entre objets. Ces contraintes sont inspirées de celles rencontrées lors d’une collaboration industrielle. Le sujet de recherche de cette thèse porte sur la résolution d’une variété de problèmes de bin packing. Nous nous intéressons à des bornes inférieures et supérieures pour les trois problèmes suivants : un problème de bin packing avec conflits dans lequel des relations de compatibilité sont exprimées entre les couples d’objets ; un problème de bin packing bi-objectif dans lequel deux critères sont à minimiser, le nombre de bins utilisés et le nombre de couples en conflit placés dans le même bin ; un problème de bin packing avec objets fragiles dans lequel la somme des tailles des objets placés dans un bin ne dépasse la fragilité d’aucun de ces objetsThe bin packing problem consists in minimizing the number of containers (bins) needed to place a set of objects. This NP-complete problem has been, for many years, the subject of multiple theoretical and practical researches. It appears in many industrial applications such as cutting steel, wood and glass. The literature on the bin packing problem is rich and the algorithms and resolution approaches are also very are very diversified. However, solutions offered by these algorithms may not be useful when we deal with real industrial problems. In this thesis, we consider several types of constraints such as compatibility relations between objects. These constraints are issued from real life industrial applications. The research topic of this thesis focuses on solving a variety of bin packing problems. We are interested in lower and upper bounds for three problems: a bin packing problem with conflicts in which some compatibility relations exist between pairs of objects, a problem bi-objective bin packing in which two criteria are to minimize: the number of bins used and the number of conflicting couples of objects placed in the same bin, a problem of bin packing with fragile objects in which the sum of the sizes of objects placed in a bin does not exceed the fragility of any of these objects
10
Wilbaut, Christophe. "Heuristiques hybrides pour la résolution de problèmes en variables 0-1 mixtes." Phd thesis, Université de Valenciennes et du Hainaut-Cambresis, 2006. http://tel.archives-ouvertes.fr/tel-00409493.
Анотація:
Les problèmes d'optimisation en variables 0-1 mixtes permettent de modéliser de nombreux problèmes réels difficiles à résoudre. Cette thèse s'intéresse à la mise en oeuvre de méthodes de résolution hybrides pour obtenir des solutions de bonne qualité en des temps raisonnables pour ces problèmes. L'ensemble des algorithmes présentés dans cette thèse est testé sur le problème du sac-à-dos multidimensionnel. Il consiste à maximiser une fonction linéaire en respectant un ensemble de contraintes linéaires. Après une présentation de quelques concepts fondamentaux utilisés en recherche opérationnelle pour résoudre les problèmes d'optimisation, nous présentons dans le premier chapitre différents problèmes de la famille du sac-à-dos. Nous abordons dans le second chapitre un ensemble de méthodes efficaces existantes pour résoudre le problème du sac-à-dos multidimensionnel. Nous proposons dans le chapitre 3 une première méthode hybride qui combine la programmation dynamique et la recherche tabou au sein d'un processus dit d'intensification globale. Des concepts de réduction sont également intégrés dans la programmation dynamique de manière à essayer de réduire la taille du problème. La seconde approche décrite dans le chapitre 4 combine la recherche dispersée avec des éléments de la recherche tabou et des chemins reliants pour affiner la recherche. Une étude expérimentale est menée pour mesurer l'impact de différents composants de l'algorithme. Nous terminons dans le chapitre 5 par une méthode utilisant conjointement la relaxation en continu et la relaxation en nombres entiers mixtes pour résoudre efficacement les problèmes en variables 0-1. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes. La dernière approche permet d'améliorer quelques meilleures valeurs connues sur des instances existantes du problème du sac-à-dos multidimensionnel.
11
Malca, Franck. "Méthodes d'aide à la décision pour la gestion d'une flotte de véhicules en temps réel." Valenciennes, 2005. https://ged.uphf.fr/nuxeo/site/esupversions/ff6e9333-7852-4e06-b9b0-05d13b8c795d.
Анотація:
Cette thèse traite de la gestion d'une flotte de véhicules en temps réel. Les récentes améliorations dans les technologies de la communication et de l'information fournissent de nouveaux flots de données en temps réel qui conduisent au développement de nouvelles applications dans le domaine des transports. De nouvelles méthodes d'aide à la décision sont à développer afin d'assister le gestionnaire de la flotte dans sa tâche de planification des activités des véhicules. Le problème support de cette thèse est le problème de tournées de véhicules avec contraintes de ramassage et de livraison, de fenêtres de temps et une flotte de taille finie. Tout d'abord, nous proposons des heuristiques constructives ainsi qu'une approche basée sur la recherche tabou permettant d'optimiser la planification lorsque l'ensemble des demandes à affecter aux véhicules est connu a priori. La principale contribution réside en la définition de techniques d'extraction et d'exploitation d'informations permettant une réduction de l'espace de recherche, ce qui résulte en une diminution sensible de la durée de résolution. Lorsque certaines demandes parviennent au gestionnaire alors que les véhicules sont en route, une gestion en temps réel est nécessaire. Pour résoudre ce problème, nous capitalisons sur les méthodes définies pour le cas statique afin de définir une adaptation au contexte temps réel. Les travaux réalisés se sont inscrits dans le cadre du projet TESS (Transport ESpace et Société). Les méthodes définies ont été intégrées dans un moteur d'optimisation, inclus au sein d'un logiciel de gestion de la flotte développé en collaboration avec les partenaires du projet (le CNES et la société CGx)This thesis focuses on the real-time management of a fleet of vehicles. Recent improvements in communication and information technologies provide new data sets in real-time which lead to the development of new applications in transportation area. New decision-making methods are required to help the manager with the planning of the activities for all vehicles. This thesis addresses a pickup and delivery problem with time windows and a finite size fleet. First, we propose constructive heuristics and a tabu search approach to optimize the road planning when all requests to be assigned are known a priori. The main contribution consists of the extraction and the exploitation of informations to reduce the search space, which leads to cut computation times. In real-time, new demands occur while vehicles are in route. To manage the fleet in real-time, we capitalize on the methods defined for the static case to propose an adapted version. This research works were motivated by the TESS project (Transport ESpace et Société). Proposed methods were integrated in an optimization system, which has been included in a decision support system for the fleet management. This software was developped in collaboration with our partners (CNES and the CGx company)
12
Hail, Nourredine. "Méthodes algorithmiques pour les lignes de production avec des machines parallèles." Université Joseph Fourier (Grenoble), 1995. http://www.theses.fr/1995GRE10019.
Анотація:
Cette thèse présente un problème d'ordonnancement sur une ligne de production flexible. Dans une telle ligne, les postes de travail sont disposes séquentiellement, et chacun d'eux contient un certain nombre de machines parallèles identiques. Les pièces passent de poste en poste selon le même ordre et sont usinées par une des machines de chaque poste. Nos travaux portent sur l'étude de la minimisation de la date d'achèvement de la dernière pièce sur le dernier poste (makespan). Ce problème est np-difficile au sens fort. Nous étudions d'abord l'intérêt de ce type de ligne notamment en ce qui concerne la flexibilité, ensuite un état de l'art de ce domaine est présenté. Puis nous entamerons l'étude du flow shop flexible. Dans une première partie, nous proposons une borne inferieure pour le problème d'affectation (réduction à un seul poste). Ensuite nous développerons une heuristique pour ce cas particulier, en utilisant les algorithmes génétiques. Dans une seconde partie, nous présentons une heuristique pour un cas particulier du flow shop flexible à deux postes, puis on fera une étude théorique de sa performance. Nous proposons à la fin de cette thèse trois heuristiques pour le flow shop flexible, en utilisant trois méthodes différentes: l'amélioration locale, la méthode tabou et les algorithmes génétiques
13
Kammarti, Ryan. "Approches évolutionnistes pour la résolution du 1-PDPTW statique et dynamique." Ecole Centrale de Lille, 2006. https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/2006/50376-2006-Kammarti.pdf.
Анотація:
De nos jours, le transport de marchandise occupe une place importante dans la vie économique des sociétés modernes. Le problème de collecte et de distribution avec fenêtres de temps à un seul véhicule est un des problèmes les plus rencontrés. Ayant un ensemble de demandes à satisfaire, le véhicule doit transporter des biens de fournisseurs à leurs clients respectifs en respectant les fenêtres de temps et sa capacité. Dans ce travail, nous présentons un état de l’art du 1-PDPTW et nous proposons plusieurs approches évolutionnistes pour traiter ses deux cas : statique et dynamique. Nos approches utilisent principalement des algorithmes évolutionnistes basés sur l’utilisation d’opérateurs génétiques spéciaux conçus dans le but d’améliorer la qualité des solutions et de diminuer le temps de calcul. Elles sont aussi basées sur la Pareto optimalité pour fournir un ensemble de solutions viables. Quelques unes de nos approches utilisent des bornes inférieures de distance et de retard dans le but d’évaluer les résultats obtenus. Une recherche Tabou, constituant un étage d’hybridation, peut être appliquée pour l’amélioration des solutions obtenues par les algorithmes évolutionnistes. Enfin nous présentons quelques simulations et résultats élaborés à partir de benchmarks spécialement conçus pour le 1-PDPTW ainsi que d’autres provenant de la littératureNowadays, goods and people transportation take an important place in all societies daily life and business. The single pickup and delivery problem is one of the most faced problems. Having a set of request to satisfy the transportation vehicle will carry goods from providers to respective customers respecting their each time windows and its self-transportation capacity. In this work, we present a review of the scientific literature on the 1-PDPTW and we present some new approaches to resolve the static and the dynamic cases of this problem. Our approaches use mainly evolutionary algorithms based on the use of special genetic operators conceived in to improve the solutions quality and to decrease the computation time. They are also based on the use of the Pareto optimality approach to provide to the decision maker a set of good feasible solutions. Some of our approaches use distance end tardiness lower bounds to evaluate the obtained solutions. A hybridization stage, consisting on a special Tabu search, can be applied to improve the solutions given by the evolutionary algorithms. Finally, we present some simulations and results elaborated with benchmarks especially conceived for the 1-PDPTW and other benchmarks issued from the literature
14
Amrani-Benhalima, Faïza. "Problèmes de MIN-MAX en variables 0-1 : Algorithmes de résolution exacts et approchés." Valenciennes, 1997. https://ged.uphf.fr/nuxeo/site/esupversions/6fb2c7ce-df58-4bc6-bb55-a1a7c0529fcf.
Анотація:
Le problème de Minmax en variables continues ou en variables entières a toujours suscité un intérêt croissant d'une part, parce que son champs d'application est vaste. Que ce soit dans le domaine des mathématiques, l'allocation de ressource, l'économie, l'aéronautique et même des jeux. D'autres part, parce que les problèmes traités sont classés en théorie de la complexité comme NP-difficile même quand il s'agit d'un problème de Minmax en variables 0-1 sans contrainte et avec seulement deux objectifs. Cette thèse contribue à l'étude des problèmes en variables bivalentes. Elle propose la résolution exacte et approchée des problèmes de Minmax ou Maxmin en variables 0-1 qui consistent à minimiser un objectif exprimé sous la forme d'un minimum ou maximum de plusieurs fonctions linéaires et soumis à un ensemble de contraintes.
15
Cao, Xiaokang. "Le problème de renouvellement des équipements multi-période." Compiègne, 2011. http://www.theses.fr/2011COMP1920.
Анотація:
Cette thèse porte sur le problème de renouvellement des équipements multipériode (MPR pour Multi-Period Renewal equipment problem). Ce problème consiste à déterminer les dates de renouvellement d’un ensemble d’équipements sous des contraintes budgétaires sur un ensemble de périodes consécutives. La particularité de MPR est la possibilité de reporter le budget non utilisé d’une période aux périodes suivantes. Nous commençons par une étude de l’art. En particulier nous montrons les liens qui existent avec d’autres variantes du problème de sac-à-dos. Ensuite, nous proposons une étude approfondie de la complexité. Nous démontrons qu’un cas particulier du problème peut être résolu en temps polynomial via un modèle de flot de coût minimal et que deux autres cas peuvent être résolus en temps pseudopolynomial. Le problème lui-même est montré NP-difficile au sens fort lorsque le nombre de périodes est non-borné. Nous proposons deux heuristiques de type glouton ainsi que deux méthodes de recherche Tabou basées sur l’exploration de séquences correspondant à des priorités de renouvellement des items. Nous proposons une méthode de Branch-and-Bound pour résoudre le problème à l’optimalité. Cette méthode exacte est aussi basée sur l’énumération de séquences de priorité des items. Afin de tester nos méthodes, nous proposons plusieurs jeux de test. Pour évaluer les performances de nos méthodes, nous comparons nos résultats avec ceux obtenus par CPLEX 11 pour résoudre le MIP de MPRThis thesis looks at the Multi-Period Renewal equipment problem (MPR). It is inspired by a specific real-life situation where a set of hardware items is to be managed and their replacement dates determined, given a budget over a time horizon comprising a set of periods. The particularity of this problem is the possibility of carrying forward any unused budget from one period to the next. We begin with a state of art. Links with other knapsack problems cited in the literature are also established and studied. A complexity study of MPR via several special cases is then reported. In particular, it is established that one of the special cases can be solved in polynomial time via a minimum-cost flow model, and that two others can be solved in pseudo-polynomial time, while the problem itself is strongly NP-hard when the number of periods is unbounded. We propose two greedy heuristics and two Tabu search methods based on the exploration of sequences corresponding to the priorities of renewing items. We propose a Branch-and-Bound method in order to solve MPR to optimality. This method is also based on the enumeration of priority sequences of items. We propose several types of instances in order to test our methods. In order to evaluate the quality of our methods, we have compared with the results obtained with CPLEX 11 by solving the MIP of MPR
16
Karray, Asma. "Contribution à l’ordonnancement d’ateliers agroalimentaires utilisant des méthodes d’optimisation hybrides." Thesis, Ecole centrale de Lille, 2011. http://www.theses.fr/2011ECLI0024/document.
Анотація:
Nos travaux concernent la mise en œuvre de méthodologies pour la résolution de problèmes d’ordonnancement en industries agroalimentaires. Trois nouvelles approches basées sur les algorithmes génétiques, sont proposées pour la résolution de problèmes d’ordonnancement multi-objectifs : les algorithmes génétiques séquentiels (SGA), les algorithmes génétiques parallèles (PGA) et les algorithmes génétiques parallèles séquentiels (PSGA). Deux approches coopératives multi-objectifs en mode relais, SH_GA/TS et SH_GA/SA, hybridant toutes les deux des métaheuristiques de haut niveau, sont par la suite proposées. Un algorithme évolutionnaire et un algorithme de recherche locale sont, dans ce cas exécutés séquentiellementThe purpose of our works is the implementation of methodologies for the resolution of the agro-food industry scheduling problem. Three new approaches based on genetic algorithms are proposed to solve multi-objectives scheduling problems: sequential genetic algorithms (SGA), parallel genetic algorithms (PGA) and parallel sequential genetic algorithms (PSGA). Two high-level hybrid algorithms, SH_GA/TS et SH_GA/SA, are also proposed. The purpose in this hybridization is to benefit the exploration of the solution space by a population of individuals with the exploitation of solutions through a smart search of the local search algorithm
17
Hadj, Khalifa Ismahène. "Approches de modélisation et d'optimisation pour la conception d'un système interactif d'aide au déplacement dans un hypermarché." Phd thesis, Ecole Centrale de Lille, 2011. http://tel.archives-ouvertes.fr/tel-00605118.
Анотація:
Les travaux présentés dans cette thèse ont porté sur l'étude de faisabilité technique et logicielle du système i-GUIDE, système interactif de guidage des personnes dans les hypermarchés. Nous avons détaillé l'analyse fonctionnelle du besoin du système. Ensuite, nous avons étudié l'impact de l'intégration du système dans le magasin à travers le diagramme BPMN. Nous avons opté pour l'approche UML pour décrire les principales fonctionnalités de notre système ainsi que les objets nécessaires pour son bon fonctionnement. Une architecture du système i-GUIDE, basée sur la technologie RFID avec une application sous Android, a été présentée. Par ailleurs, nous avons proposé des approches d'optimisation de parcours dans un hypermarché basées sur la méthode de recherche tabou pour deux problèmes. Pour le premier problème, nous avons choisi le critère de la plus courte distance pour la détermination du chemin et pour le deuxième nous avons ajouté une contrainte de temps pour des articles en promotion. Avant de chercher le chemin le plus court à parcourir pour trouver les articles existants dans la liste de courses, nous avons proposé une méthode pour ladétermination des distances entre les articles de l'hypermarché pris deux à deux
18
Ahmad, Maqsood. "Mathematical models and methods based on metaheuristic approach for timetabling problem." Thesis, Clermont-Ferrand 2, 2013. http://www.theses.fr/2013CLF22393/document.
Анотація:
Résumé indisponibleIn this thesis we have concerned ourselves with university timetabling problems both course timetabling and examination timetabling problems. Most of the timetabling problems are computationally NP-complete problems, which means that the amount of computation required to find solutions increases exponentially with problem size. These are idiosyncratic nature problems, for example different universities have their own set of constraints, their own definition of good timetable, feasible timetable and their own choice about the use of constraint type (as a soft or hard constraint). Unfortunately, it is often the case that a problem solving approach which is successfully applied for one specific problem may not become suitable for others. This is a motivation, we propose a generalized problem which covers many constraints used in different universities or never used in literature. Many university timetabling problems are sub problems of this generalized problem. Our proposed algorithms can solve these sub problems easily, moreover constraints can be used according to the desire of user easily because these constraints can be used as reference to penalty attached with them as well. It means that give more penalty value to hard constraints than soft constraint. Thus more penalty value constraints are dealt as a hard constraint by algorithm. Our algorithms can also solve a problem in two phases with little modification, where in first phase hard constraints are solved. In this work we have preferred and used two phase technique to solve timetabling problems because by using this approach algorithms have broader search space in first phase to satisfy hard constraints while not considering soft constraints at all. Two types of algorithms are used in literature to solve university timetabling problem, exact algorithms and approximation algorithms. Exact algorithms are able to find optimal solution, however in university timetabling problems exact algorithms constitute brute-force style procedures. And because these problems have the exponential growth rates of the search spaces, thus these kinds of algorithms can be applied for small size problems. On the other side, approximation algorithms may construct optimal solution or not but they can produce good practically useable solutions. Thus due to these factors we have proposed approximation algorithms to solve university timetabling problem. We have proposed metaheuristic based techniques to solve timetabling problem, thus we have mostly discussed metaheuristic based algorithms such as evolutionary algorithms, simulated annealing, tabu search, ant colony optimization and honey bee algorithms. These algorithms have been used to solve many other combinatorial optimization problems other than timetabling problem by modifying a general purpose algorithmic framework. We also have presented a bibliography of linear integer programming techniques used to solve timetabling problem because we have formulated linear integer programming formulations for our course and examination timetabling problems. We have proposed two stage algorithms where hard constraints are satisfied in first phase and soft constraints in second phase. The main purpose to use this two stage technique is that in first phase hard constraints satisfaction can use more relax search space because in first phase it does not consider soft constraints. In second phase it tries to satisfy soft constraints when maintaining hard constraints satisfaction which are already done in first phase. (...)
19
Gomez, Urrutia Edwin David. "Optimisation intégrée des décisions en planification et ordonnancement dans une chaîne logistique." Thesis, Saint-Etienne, EMSE, 2014. http://www.theses.fr/2014EMSE0744/document.
Анотація:
Dans cette thèse, nous étudions l’optimisation des problèmes de planification et d’ordonnancement des flux, dans une stratégie d’intégration des décisions, pour planifier la chaîne logistique au niveau tactique avec prise en compte de contraintes opérationnelles. Le but de ce travail est de répondre au besoin de cohérence entre les décisions de planification et d’ordonnancement, qui sont souvent prises de manière séquentielle ne garantissant pas la faisabilité des plans de production. Nous proposons une approche intégrée pour résoudre des problèmes mono-niveau et multi-niveaux, dans des systèmes multi-produits et multi-ressources dans des ateliers de type job-shop.Les problèmes de planification avec contraintes de capacité et les problèmes d’ordonnancement dans des systèmes complexes sont des problèmes NP-difficiles. Intégrer les contraintes propres aux deux problèmes engendre un nouveau problème qui est d’autant plus complexe. Nous proposons une décomposition du problème intégré en un ensemble de sous-problèmes de planification avec séquence fixée, résolus par relaxation Lagrangienne. L’amélioration de la séquence est guidée par une recherche taboue. L’efficacité de l’approche intégrée, par rapport à un solveur commercial, a été prouvée en termes de qualité des solutions et d’effort de calcul. Pour les problèmes multi-niveaux, nous proposons une nouvelle formulation basée sur la notion d’échelon stock, ainsi que de nouveaux algorithmes et stratégies de lissage de la production, pour construire des plans de production respectant les contraintes de capacité détaillées et de nomenclatureIn this thesis, we study the optimization of flow planning and scheduling, within a strategy to integrate decisions for supply chain planning at tactical level, taking into account operational constraints. The goal of this work is to address the need for consistency between decisions arising from production planning and scheduling. These decisions are often taken in a sequential order, leading most of the time to unfeasible production plans. We propose an integrated approach to solve single-level and multi-level problems in multi-item multi-resource systems configured as job-shops.Both capacitated production planning and scheduling problems, in complex manufacturing systems, are NP-hard. Therefore, integrating constraints of both problems generates a new problem which is even more difficult to solve. We propose a decomposition of the integrated problem into a set of several sub-problems with fixed sequence, solved by Lagrangian Relaxation. The sequence improvement is guided by a Tabu Search. The efficiency of the integrated approach comparing to a standard solver is proved in terms of solution quality and computational effort. In case of multi-level problems, we propose a new mathematical model based on the concept of echelon stock, as well as new algorithms and smoothing strategies to build production plans respecting detailed capacity and bill-of-materials constraints
20
Baccouche, Mohamed. "Métaheuristiques hybrides d'optimisation d'atterrissage d'avions multipistes." Le Havre, 2007. http://www.theses.fr/2007LEHA0008.
Анотація:
Nous avons étudié dans cette thèse un problème complexe, mixte d'ordonnancement des avions et d'affectation des pistes, le problème d'atterrissage des avions. La complexité de ce problème d'optimisation résulte de son aspect combinatoire (taille de problème), de la forte interdépendance des fonctions (affectation et ordonnancement), des contraintes et des perturbations. Les capacités d'atterrissage des aéroports constituent de véritables goulots d'étranglement qui ne permettent pas de répondre à une augmentation du trafic aérien. Les plate-formes les plus importantes sont déjà au maximum de leur capacité et seule une optimisation accrue des séquences d'atterrissage permettra de faire face. Nous avons développé et testé différentes approches hybride basées sur des techniques métaheuristiques comme les algorithmes génétiques et la recherche taboue et des méthodes exactes. Nous avons comparé les différentes approches avec un large choix des paramètres, analysé la complexité de calcul et les performances et évalué les meilleures solutions trouvées. Nous avons utilisé la méthode des plans d'expériences pour optimiser le choix des paramètres des algorithmes développésWe studied in this thesis a complex problem, mixed aircraft scheduling and runway assignment, the Aircraft landing Problem. The complexity of this optimization problem is the result of its combinatorial aspects (problems size), of the strong interdependence between functions (assignment and scheduling), constraints and perturbations. Airport landing capacities constitute genuine bottlenecks, making it impossible to respond to an increase in air traffic. The largest airports are already operating at maximum capacity and only increased optimization of the landing sequences will make it possible to cope. We developed and tested different hybrid approaches based on metaheuristics techniques such as evolutionary algorithms and taboo search and on exact methods. We have compared different approaches with a large choice of parameters, analyzed computational complexity and performances and discussed the best values. We used the experience plans method in order to optimize the choice of parameters of developed algorithms
21
Hadj, Khalifa Ismahène. "Approches de modélisation et d’optimisation pour la conception d’un système interactif d’aide au déplacement dans un hypermarché." Thesis, Ecole centrale de Lille, 2011. http://www.theses.fr/2011ECLI0008/document.
Анотація:
Les travaux présentés dans cette thèse ont porté sur l’étude de faisabilité technique et logicielle du système i-GUIDE, système interactif de guidage des personnes dans les hypermarchés. Nous avons détaillé l’analyse fonctionnelle du besoin du système. Ensuite, nous avons étudié l’impact de l’intégration du système dans le magasin à travers le diagramme BPMN. Nous avons opté pour l’approche UML pour décrire les principales fonctionnalités de notre système ainsi que les objets nécessaires pour son bon fonctionnement. Une architecture du système i-GUIDE, basée sur la technologie RFID avec une application sous Android, a été présentée. Par ailleurs, nous avons proposé des approches d’optimisation de parcours dans un hypermarché basées sur la méthode de recherche tabou pour deux problèmes. Pour le premier problème, nous avons choisi le critère de la plus courte distance pour la détermination du chemin et pour le deuxième nous avons ajouté une contrainte de temps pour des articles en promotion. Avant de chercher le chemin le plus court à parcourir pour trouver les articles existants dans la liste de courses, nous avons proposé une méthode pour ladétermination des distances entre les articles de l’hypermarché pris deux à deuxThe present work focuses on the technical feasibility study of i-GUIDE system which is a real time indoor navigation system dedicated to assist persons inside hypermarkets. We detailed its functional analysis. Then, we studied the impact of integrating the system inside hypermarkets. We opted for an UML design to describe its main functionalities and objects required. We presented architecture of i-GUIDE system based on RFID technology with an Android application. Furthermore, we introduced optimization approaches based on tabu search to compute the route visiting items existing in a shopping list for two problems. The first one treats the shortest path to pick up items and the second one adds a time constraint for promotional items. Before computing the shortest path, we introduced a method to determine distance between each two items existing in the hypermarket
22
Kammoun, Mohamed Firas. "Conception et déploiement d'un algorithme pour l'optimisation des réseaux optiques." Mémoire, Université de Sherbrooke, 2010. http://savoirs.usherbrooke.ca/handle/11143/1638.
Анотація:
De nos jours, Internet devient de plus en plus répandue [i.e. répandu] ; la fibre optique est encore le support idéal pour cette technologie. Cependant, le développement des réseaux en fibre optique est très coûteux. Le but de ce projet est de mettre en place un algorithme d'optimisation des réseaux optiques qui vise la minimisation des coûts relatifs au déploiement et à l'exploitation de ces réseaux. L'algorithme est développé sous forme d'une librairie appelée OptimisationLib ; composée de quatre modules : de vérification, de correction, de calcul de coût et d'optimisation. Ces derniers collaborent ensemble pour donner une solution opérationnelle, avec un coût minimal à un réseau optique donné. La librairie ainsi développée est prête pour être intégrée dans le grand projet du groupe de recherche sur les réseaux de télécommunications appelé ONDE (optical Network Development Environment).
23
Palpant, Mireille. "Recherche exacte et approchée en optimisation combinatoire : schémas d'intégration et applications." Avignon, 2005. http://www.theses.fr/2005AVIG0138.
Анотація:
Le travail présenté dans ce mémoire est focalisé sur la résolution de problèmes d'optimisation combinatoire hautement difficiles par le biais de méthodes incomplètes intégrant des paradigmes issus de deux approches bien distinctes, à savoir recherche exacte et approchée. L'intérêt d'une telle coopération est de tirer parti des avantages complémentaires que peuvent apporter l'un et l'autre des composants : optimalité et déterminisme de la composante exacte, rapidité et côté moins systématique de la composante heuristique. A cet effet, deux méthodologies distinctes ont été abordées~:~d'une part l'intégration d'une procédure exaustive au sein d'une méthode de recherche de grands voisinages appelée LSSPER (Local Search (with) Sub-Problem Exact Resolution), d'une autre, l'utilisation d'un critère heuristique discrimant pour réduire la taille de l'espace de recherche exploré par une méthode complète dérivée de Resolution Search [Chvatal97]. Pour chacune de ces approches, une validation expérimentale a été réalisée sur divers problèmes académiques ou applicatifs (ordonnancement de projet sous contraintes de ressources, affectation de fréquences, coloration de graphes). Les résultats obtenus, s'ils ne sont pas toujours à la hauteur des meilleurs résultats pouvant être recensés dans la littérature, semblent à tout le moins exhiber l'intérêt de telles méthodologies et laissent entrevoir des perspectives de recherche aussi diverses que prometteuses
24
Boulanger, Célia. "Heuristiques basées sur la programmation mathématique pour des problèmes de localisation et de routage." Valenciennes, 2010. http://ged.univ-valenciennes.fr/nuxeo/site/esupversions/097f03a9-5364-4c57-afd3-697ff1edf975.
Анотація:
Les travaux de cette thèse portent sur la définition et la résolution de deux problèmes de transport dans le domaine de la recherche opérationnelle. Ces deux problèmes entrent dans le cadre des problèmes de tournées de véhicules et des problèmes de localisation. Le premier problème abordé est le problème de localisation et routage avec contraintes de capacités aux dépôts. Trois méthodes de résolution sont proposées pour résoudre ce problème. Les deux premières sont des heuristiques hybrides, combinant programmes linéaires et une recherche tabou. La troisième méthode est également une méthode approchée, elle est basée sur une approche par génération de colonnes. Ces trois contributions ont ensuite été implémentées afin de tester leur efficacité. Les résultats obtenus sont de bonne qualité, la meilleure méthode implémentée améliorant la majorité des trente instances testées. Le second problème abordé est un problème de voyageur de commerce bi-objectif adapté à un graphe particulier où seuls certains des sommets sont à visiter obligatoirement. Une méthode approchée a été développée pour résoudre ce problème bi-objectif. Afin d’évaluer les qualités des solutions obtenues par cette méthode, une méthode exacte a également été développéeThe aim of this PHD is the modelisation of two transportation problems of operationnal research. . These problems are routing problem and location problem. The first one studied is the location-routing problem with capacity constraints on facilities. Three methods are proposed to solve this problem. The two first are hybrid heuristics, mixing linear programs and a tabou search. The third method is based on a column generation method. These three contributions have been developped and tested to see their efficienty. We obtain good results, the best method giving most of the best results of the thirty instances. The second problem studied is a biobjectif travelling salesman problem on a particular graphe where some vertices have to be visited. A heuristic has been developed to solve this biobjective problem. To evaluate results obtained, an exacte method has been developed too
25
Danna, Emilie. "Intégration des techniques de recherche locale à la programmation linéaire en nombres entiers." Avignon, 2004. http://www.theses.fr/2004AVIG0132.
Анотація:
Cette thèse présente plusieurs algorithmes pour l'intégration des techniques de recherche locale à la programmation linéaire en nombres entiers (PLNE). Premièrement, nous introduisons un schéma de coopération entre recherche locale et génération de colonnes qui généralise le concept d'heuristiques pour le branch-and-cut au branch-and-price et nous l'appliquons avec succès au problème de tournées de véhicules avec fenêtres de temps. Deuxièmement, nous présentons une nouvelle heuristique pour les problèmes linéaires quelconques en nombres entiers : Relaxation Induced Neighborhood Search (RINS). Cette heuristique produit des solutions entières de qualité pour des modèles qu'il était très difficile de résoudre auparavant. Elle est maintenant implantée dans le logiciel ILOG CPLEX 9. RINS exploite les trois concepts fondamentaux de la recherche locale (voisinage, intensification et diversification) en les transposant à la programmation linéaire en nombres entiers. Cette heuristique est générique : elle peut être appliquée à n'importe quel modèle de PLNE, sans aucune connaissance préalable de sa structure. RINS nous permet de formaliser la notion d'algorithme "conceptuellement hybride". Ce paradigme de développement consiste à utiliser une seule technique de résolution et à intégrer dans ce cadre les concepts d'autres techniques plutôt qu'à faire coopérer des composants logiciels. Les performances de RINS et notre analyse des difficultés des algorithmes hybrides existants laissent à penser que cette classe d'algorithmes est prometteuse. Troisièmement, nous nous intéressons plus en détail au problème d'ordonnancement d'atelier avec coûts d'avance et de retard sur lequel RINS est particulièrement efficace. Nous proposons plusieurs améliorations et extensions du modèle disjonctif pour ce problème et une heuristique (MCORE: big-M COefficient REduction) qui pourrait être généralisée à d'autres modèles de structure similaire. MCORE est également un algorithme "conceptuellement hybride"We present several algorithms for integrating local search technique into mixed integer programming (MIP). We first introduce a cooperation scheme between local search and branch-and-price that generalizes the concept of branch-and-cut heuristics to branch-and-price and we apply it successfully to the vehicle routing problem with time windows. We then present a new MIP heuristic that we call Relaxation Induced Neighborhood Search (RINS). This heuristic finds good integer solutions on models that previously were very difficult to solve. It is now implemented in ILOG CPLEX 9. RINS exploits the three fundamental concepts of local search (neighborhood, intensification, and diversification) and transposes them to mixed integer programming. This heuristic is generic : it can be applied to any MIP model, with no other input than the model itself. RINS allows us to formalize the notion of "hybrid in spirit'' algorithms. This development paradigm consists in using only one optimization technique and integrating into its framework concepts of other resolution techniques instead of having several software components cooperate. RINS performances and our analysis of difficulties encountered by existing hybrid algorithms suggest that this class of algorithms is promising. We finally concentrate on the job-shop scheduling problem with earliness and tardiness costs on which RINS is particularly effective. We propose several improvements and extensions of the disjunctive model for this problem and a heuristic (MCORE : big-M COefficient REduction) that could be generalized to other MIP models of similar structure. MCORE is also a "hybrid in spirit'' algorithm
26
Tremblay, Bergeron. "L'empathie comme modèle de communication dans l'enseignement aux adultes, bune recherche heuristique." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape8/PQDD_0020/MQ48319.pdf.
27
Tremblay, Michèle B. "L'empathie comme modèle de communication dans l'enseignement aux adultes : une recherche heuristique /." Thèse, Chicoutimi : Université du Québec à Chicoutimi, 1999. http://theses.uqac.ca.
28
Leroy, Cassandre. "Élicitation incrémentale combinée à la recherche heuristique pour l'optimisation combinatoire multi-objectifs." Electronic Thesis or Diss., Sorbonne université, 2022. https://accesdistant.sorbonne-universite.fr/login?url=https://theses-intra.sorbonne-universite.fr/2022SORUS367.pdf.
Анотація:
Cette thèse s'intéresse à la résolution de problèmes de décision sur domaine combinatoire par des méthodes d'élicitation incrémentale des préférences basée le regret pour l'optimisation interactive. On se situe à l'intersection de la théorie de la décision, de la recherche opérationnelle et de l'intelligence artificielle, en théorie de la décision algorithmique. On suppose que les préférences du décideur peuvent être représentées par une fonction de scalarisation paramétrée (somme pondérée, OWA et intégrale de Choquet), mais que les paramètres (par exemple, le jeu de poids) ne sont pas connus au départ. L'apprentissage actif des paramètres est entremêlé à la résolution du problème dans le but d'apprendre seulement la part d'information sur ce paramètre qui est utile pour résoudre le problème donnée. L'originalité de ces travaux réside dans la conception de méthodes fondées sur la recherche heuristique couplée à l'élicitation incrémentale pour déterminer la meilleure solution du décideur. Nous proposons d'abord deux méthodes pour résoudre des problèmes d'optimisation combinatoire multi-objectifs avec des préférences imprécises, la première basée sur la recherche locale et la seconde sur un algorithme génétique. Nous proposons ensuite deux approches permettant l'élicitation d'une fonction d'ensemble linéaire, sous-modulaire et super-modulaire avec la construction d'un sous-ensemble indépendant optimal soumis à une contrainte de matroïde. La première approche est basée sur un algorithme glouton et l'autre sur la recherche locale. Afin de démontrer l'efficacité pratique de nos approches, nos algorithmes sont testés numériquement sur différents problèmes et évalués en termes de temps de calcul, de nombre de requêtes et d'erreur empiriqueThis thesis is concerned with solving combinatorial domain decision problems using incremental regret-based preference elicitation methods for interactive optimization. It is situated at the intersection of decision theory, operations research and artificial intelligence, in algorithmic decision theory. It is assumed that the decision maker's preferences can be represented by a parameterised scalarization function (weighted sum, OWA and Choquet integral), but the parameters (e.g. set of weights) are not known at the beginning. The active learning of the parameters is intertwined with the solution of the problem in order to learn only that part of the information about the parameter that is useful to solve the given problem. The originality of this work lies in the use of methods based on heuristic search coupled with incremental elicitation to determine the best solution for the decision maker. In first we propose two methods for solving multi-objective combinatorial optimisation problems with imprecise preferences, the first based on local search and the second on a genetic algorithm. We then propose two approaches for the elicitation of a linear, submodular and super-modular set function with the construction of an optimal independent subset subject to a matroid constraint. The first approach is based on a greedy algorithm and the other on local search. In order to demonstrate the practical effectiveness of our approaches, our algorithms are numerically tested on different problems and evaluated in terms of computation time, number of queries and empirical error
29
Chelouah, Rachid. "Adaptation aux problemes a variables continues de plusieurs metaheuristiques d'optimisation combinatoire : la methode tabou, les algorithmes genetiques et les methodes hybrides. application en controle non destructif." Cergy-Pontoise, 2000. http://www.theses.fr/2000CERG0108.
Анотація:
Les metaheuristiques - principalement le recuit simule, la methode de recherche tabou, les algorithmes genetiques - sont considerees comme des methodes efficaces pour la resolution de problemes d'optimisation combinatoires. Le travail presente dans le cadre de cette these consiste a adapter ces methodes en vue du traitement des fonctions a variables continues, a les reunir dans un meme environnement, afin de comparer leurs efficacites, et a les appliquer a plusieurs problemes relevant du controle non destructif par courants de foucault. Nous avons d'abord propose une strategie efficace de discretisation des variables, nous avons defini la notion de voisinage, et, pour chacune des methodes developpees, nous avons exploite deux concepts : la diversification et l'intensification. La diversification permet de bien couvrir l'espace des solutions, et de determiner les zones prometteuses. L'intensification permet d'approfondir la recherche dans chacune des zones prometteuses localisees. Nous avons d'abord developpe deux nouvelles methodes ; la premiere est inspiree de la methode de la recherche tabou, la seconde est une adaptation des algorithmes genetiques. Puis nous avons perfectionne un algorithme de recuit simule adapte aux problemes a variables continues. Afin d'accelerer la convergence de ces methodes pures, nous les avons couplees avec une methode de recherche locale. Nous avons, a cette fin, modifie les phases d'intensification, en utilisant la methode du polytope de nelder-mead, et nous avons ainsi obtenu trois methodes hybrides. Nous avons reuni toutes ces methodes dans un meme logiciel, que nous avons appele optim. Ce logiciel a ete developpe en programmation orientee objet, et implemente en c + +, puis en langage matlab. En collaboration avec le c. E. A. , nous avons applique les methodes developpees a l'optimisation de certaines fonctions utilisees pour la caracterisation de modeles d'inversion, en controle non destructif par courants de foucault.
30
Wu, Tingying. "Models and algorithms for two-echelon capacitated facility location problem with facility size selection." Thesis, Université Paris-Saclay (ComUE), 2015. http://www.theses.fr/2015SACLE029.
Анотація:
La localisation de sites est une des décisions stratégiques les plus importantes pour les entreprises dans le contexte de la mondialisation d'aujourd'hui. Les travaux existant dans la littérature traitant ce type de problèmes se concentrent principalement sur la détermination de l'emplacement des sites et des flux de produits provenant les sites localisés aux clients dans le but de minimiser le coût total de construction, de production et logistiques. Cependant, il est très important de bien choisir simultanément la capacité et la localisation des sites parce que la taille des sites a une grande influence sur ces coûts sur le long terme. La détermination de la location et de capacité des sites reste encore un problème ouvert.Dans cette thèse, nous étudions trois nouvelles variantes de problèmes de location de sites à deux échelons avec la sélection de taille (TECFLP). Les deux premières parties concentrent sur les TECFLPs avec sélection séparée de taille d’usines ou de dépôts. La troisième partie étudie le TECFLP avec sélection simultanée des tailles d’usines et de dépôts. Pour ces problèmes, trois modèles de programmation linéaire mixte sont proposés. Ensuite les approches basées sur la relaxation lagrangienne selon les caractéristiques de chaque problème sont développés. Pour améliorer les meilleures solutions proposées par les approches de relaxation lagrangienne, une méthode de recherche tabou, une méthode hybride de recherche tabou et à voisinage variable, une méthode hybride du recuit simulé et de la recherche tabou sont respectivement adaptées pour ces trois problèmes. Les algorithmes développés sont testés et évalués à travers 810 instances générées aléatoirement. Les résultats numériques montrent que nos méthodes sont capables de fournir des solutions de qualité avec un temps de calcul raisonnableFacility location is one of the most important strategic decisions for firms in globalization. Previous works on facility location in the literature mainly focus on determining the locations of facilities and the flows of products from facilities to customers with the goal of minimizing the sum of facility opening costs, production and logistic costs. However, it’s very important to determine at the same time the appropriate sizes for these facilities because they greatly affects these costs on the long term. Determining facility location and size is always an open problem.In this thesis, we study three new two-echelon capacitated facility location problems (TECFLP) with facility size selection. The two first parts of the wok focus on two-echelon facility location problems with plant and depot size selection, respectively. The third part concentrates on TECFLP considering simultaneously plant and depot size selection. For these problems, three corresponding mixed integer programming models are formulated and then Lagrangean relaxation approaches according to the problems’ characteristics are developed. To further improve the best solutions obtained by the Lagrangean Relaxation approaches, a tabu search, a hybrid variable neighborhood tabu search and a hybrid simulated annealing tabu search are adapted for the three problems respectively. The developed algorithms are tested and evaluated through 810 randomly generated instances. Computational results show ours algorithms can provide high quality solutions within a reasonable computation time
31
Fournier, David. "Metro regenerative braking energy : optimization through rescheduling : mathematical model and greedy heuristics compared to MILP and CMA-ES." Paris 7, 2014. http://www.theses.fr/2014PA077144.
Анотація:
The use of regenerative braking is a key factor to reduce the energy consumption of a metro line. In the case where no device can store the energy produced during braking, only the metros that are accelerating at the same time can benefit from it. Maximizing the power transfers between accelerating and braking metros thus provides a simple strategy to benefit from regenerative energy without any other hardware device. In this thesis, we use a mathematical timetable model to classify various metro energy optimization rescheduling problems studied in the literature and prove their NP-hardness by polynomial reductions of SAT. We then focus on the problem of minimizing the global energy consumption of a metro timetable by modifying the dwell times in stations. We present a greedy heuristic algorithm which aims at locally synchronizing braking metros along the timetable with accelerating metros in their time neighbourhood, using a non-linear approximation of energy transfers. On a benchmark of six small size timetables, we show that our greedy heuristics performs better than CPLEX using a MILP formulation of the problem, even when it is able to prove the optimality of a linear approximation of the objective function. We also show that it runs ten times faster than a state-of-the-art evolutionary algorithm, called the covariance matrix adaptation evolution strategy (CMA-ES), using the same non-linear objective function on these small size instances. On real data leading to 10000 decision variables on which both MILP and CMA-ES do not provide solutions, the dedicated algorithm of our thesis computes solutions with a reduction of energy consumption ranging from 5% to 9%The use of regenerative braking is a key factor to reduce the energy consumption of a metro line. In the case where no device can store the energy produced during braking, only the metros that are accelerating at the same time can benefit from it. Maximizing the power transfers between accelerating and braking metros thus provides a simple strategy to benefit from regenerative energy without any other hardware device. In this thesis, we use a mathematical timetable model to classify various metro energy optimization rescheduling problems studied in the literature and prove their NP-hardness by polynomial reductions of SAT. We then focus on the problem of minimizing the global energy consumption of a metro timetable by modifying the dwell times in stations. We present a greedy heuristic algorithm which aims at locally synchronizing braking metros along the timetable with accelerating metros in their time neighbourhood, using a non-linear approximation of energy transfers. On a benchmark of six small size timetables, we show that our greedy heuristics performs better than CPLEX using a MILP formulation of the problem, even when it is able to prove the optimality of a linear approximation of the objective function. We also show that it runs ten times faster than a state-of-the-art evolutionary algorithm, called the covariance matrix adaptation evolution strategy (CMA-ES), using the saure non-linear objective function on these small size instances. On real data leading to 10000 decision variables on which both MILP and CMA-ES do not provide solutions, the dedicated algorithm of our thesis computes solutions with a reduction of energy consumption ranging from 5% to 9%
32
Canon, Cyril. "Application des techniques de recherche opérationnelle à la planification de centres de contacts en milieu multicompétent." Tours, 2005. http://www.theses.fr/2005TOUR4039.
Анотація:
Le travail présenté dans cette thèse s’est déroulé dans le cadre d’une convention CIFRE entre le Laboratoire d’Informatique de l’Université François-Rabelais de Tours et la société Vitalicom. Ce travail porte sur la planification de personnel dans les centres d’appels (ou centres de contacts clients). La planification de personnel est devenue un enjeu économique très important, surtout dans les sociétés de services telles que les centres d’appels. En effet, la réactivité dans ce secteur est très importante, car il faut répondre au client dans des délais très courts. Toutefois, la planification de personnel dans un centre d’appels ne se résume pas à la création des horaires des employés. Le client envoie les prévisions d’appels au centre qui doit ensuite planifier le personnel afin de répondre à ces appels, tout en assurant une certaine qualité. Deux problèmes majeurs se profilent alors : -Déduire le nombre d’agents requis pour répondre aux appels, période par période. Ce problème est appelé dimensionnement. - Créer les horaires des agents sur un horizon d’une semaine. Ce problème est le Shift Design Problem. Le but de cette thèse est de résoudre ces problèmes de manière à obtenir un outil complet d’aide à la planification de personnel. La thèse est organisée de la façon suivante. Le chapitre 1 définit le contexte des centres d’appels. De nombreux aspects de cette industrie sont évoqués. Une méthode de planification en quatre phases est proposée. Elle sera suivie dans les chapitres suivants. Le chapitre 2 présente un état de l’art sur les deux problèmes majeurs traités dans cette thèse : le dimensionnement et la planification de personnel. Pour le problème de dimensionnement, les lois les plus usuelles sont données, ainsi que les formules de calcul de la qualité de service. Ensuite, des extensions du modèle de base sont données, avec leurs algorithmes respectifs. Pour le problème de planification de personnel, une notation des problèmes est proposée, inspirée de la notation à trois champs des problèmes d’ordonnancement. Ensuite, diverses méthodes de résolution de la littérature sont présentées, en expliquant pour chacune les inconvénients qui empêche d’appliquer cette méthode au problème qui nous concerne directement. Le chapitre 3 traite du dimensionnement des centres d’appels. Une modélisation déterministe est proposée et justifiée. Ensuite plusieurs méthodes de résolution sont proposées : un programme linéaire en nombre entiers, un programme par contraintes, des algorithmes de listes et des descentes locales. Des tests sont présentés et les méthodes de résolution sont comparées entre elles. Enfin, un moteur de simulation est présenté, ainsi que la simulation des résultats fournis par les algorithmes. Le chapitre 4 traite de la création des horaires des employés. Le problème est tout d’abord modélisé à l’aide de la PLNE et de la PPC. Ensuite deux méthodes heuristiques de résolution sont proposées : une méthode Tabou et une méthode de recherche sur de multiples voisinages, appelée Runner. Les méthodes sont testées et comparées. Enfin, le chapitre 5 traite de l’outil d’aide à la planification. Le problème de l’annualisation du temps de travail est d’abord traité. Un PLNE est mis en place pour résoudre ce problème. Ensuite, un outil de gestion de contraintes personnelles des employés est mis en place. Enfin, un exemple complet de planification est déroulé entièrementThe aim of a call center is to manage the contacts between their clients and their customers. Agents are not equivalent. Knowing the forecasted incoming calls for four weeks and knowing the data concerning the agents, the problem is to determine the detailed planning of the agents, for each week. Firstly the forecasted number of calls is used to determine for each eriod the number of agents needed to satisfy the required quality of service. Then knowing the constraints related tothe labor code, the number of working hours for each week per agent has tobe deterined. Then the shifts of all the agents plus the position of the breaks and the days-off, with respect of the loading curve, have to be determined. Finally, we have to assign the activities to agents. In case of unfeasibility, some constraints are added to the third phase, and the process iterates until a feasible solution is found. Heuristic approaches are proposed and tested on randomly generated instances
33
Abid, Mohamed Amine. "Étude des algorithmes de recuit simulé, de recherche tabou et génétique implémentés dans un système de construction d'horaires de cours universitaires." Mémoire, Université de Sherbrooke, 2008. http://savoirs.usherbrooke.ca/handle/11143/1478.
Анотація:
Dans ce travail on s'intéresse à la conception et au développement d'un système d'aide à la confection d'horaires. Le banc d'essai"Benchmark" utilisé est le problème d'horaires de cours dans une université basé sur l'inscription des étudiants aux cours"Post Enrolment based Course Timetabling", proposé en deuxième volet lors de la compétition internationale d'horaires en 2007"International Timetabling Competition". Le système d'aide à la confection d'horaires applique une approche heuristique basée sur la recherche locale stochastique. L'originalité du système consiste à implémenter les algorithmes de recuit simulé, recherche tabou et génétique, qui s'exécutent sur les mêmes énoncés des problèmes proposés par l'ITC et qui se partagent les mêmes structures de données et la majorité des modules de recherche locale. Ensuite une étude qualitative et quantitative de performance à produire des horaires de qualité comparable à ceux réalisés lors de la compétition est effectuée pour chaque algorithme implémenté.
34
Pessan, Cedric Néron Emmanuel. "Optimisation de changements de séries par ordonnancement des tâches de réglage." S. l. : S. n, 2008. http://theses.abes.fr/2008TOUR4026.
35
Vignier, Antony. "Contribution à la résolution des problèmes d'ordonnancement de type monogamme, multimachine (Flow-Shop Hybride)." Tours, 1997. http://www.theses.fr/1997TOUR4026.
Анотація:
Ce travail s'intéresse aux problèmes qui se posent dans les ateliers production en ligne et plus précisément sur ceux ou les gammes de fabrication de produits fabriqués sont identiques pour tous les produits (Flow-Shop). De plus, une opération de la gamme peut être réalisée par une ou plusieurs machines à chaque étage. L'atelier comporte K étages. En vue d'une plus grande efficacité d'intervention, une notation est proposée. L'état de l'art permet de mettre en évidence le peu de problèmes actuellement résolus et surtout l'ensemble de ceux qui restent à traiter des méthodes de résolution sont proposées pour résoudre différents problèmes prenant en compte des contraintes et de critères divers. Enfin, une plateforme d'aide à la construction progressive de procédures par séparation et évaluation et de tests (PCPSET) pour résoudre les problèmes de Flow-Shops Hybrides.
36
Galinho, Thierry. "Algorithme heuristique de placement pour l'ordonnancement : étude comparative et recherche d'expertise sur les stratégies de contrôle." Rouen, 1994. http://www.theses.fr/1994ROUES040.
Анотація:
Cette thèse présente l'étude des stratégies de contrôle utilisées par un algorithme heuristique de placement pour la résolution des problèmes d'ordonnancement d'ateliers de type job-shop. Dans ce type d'algorithme, la construction de l'ordonnancement est faite lot par lot et la prise en compte du lot suivant n'est possible qu'après le placement de toutes les opérations du lot précédent. Les stratégies interviennent à de nombreux niveaux dans l'algorithme utilisé par le module d'ordonnancement Fisias, tels que l'ordre de prise en compte des lots, le sens de jalonnement, le choix du poste permettant de traiter l'opération à insérer dans son plan de charge, le choix et la taille de la place sur le poste candidat, etc. Le choix des stratégies se fait une fois pour toutes en début de session, il conditionne de manière importante la qualité de la solution obtenue, vis-à-vis de critères tels que le retard cumulé, l'avance cumulée et le temps de cycle moyen. Cette étude comparative des stratégies a permis d'extraire l'expertise nécessaire à l'élaboration d'un système expert d'automatisation de la sélection de la stratégie appropriée aux objectifs. Ce système expert constitue l'un des deux modules du système stratège. L'autre module permet d'adapter la charge prévue (calculée par un module spécifique d'ordonnancement à capacité infinie) à la capacité réelle des centres de charge de l'atelier flexible
37
Deguet, Joris. "Intégration de l'émergence au sein des systèmes multi-agent : une étude appliquée à la recherche heuristique." Grenoble 1, 2008. http://www.theses.fr/2008GRE10051.
Анотація:
L'émergence et les systèmes multi-agent sont deux domaines aux problématiques proches. A travers l'étude de l'émergence dans le cadre des systèmes multi-agent, notre travail consiste à envisager leur principal point commun: la recherche d'un avantage collectif gagné grâce aux interactions entre les agents, quand le résultat global du système qui découle de l'exécution des agents est attribuable à l'interaction. Cette situation est souvent décrite comme celle d'un tout supérieur à la somme de ses parties. Une contribution de cette thèse est d'identifier des interactions dont l'impact peut être évalué à travers la comparaison de systèmes utilisant ou non ces interactions. Nous définissons de tels gains collectifs pour la résolution de problèmes par recherche heuristique dans un modèle d'agents hiérarchique. Ce travail inclut une modélisation multi-agent de ce type de recherche permettant de mettre en évidence des gains collectifs que nous appelons synergies. Trois synergies sont envisagées: la synergie entre des heuristiques travaillant sur le même problème, celle entre des problèmes proches et la synergie entre un utilisateur et le système de recherche artificiel. Ces possibilités de synergies sont à replacer dans le cadre de la discussion concernant l'émergence. Dans ce cadre, certaines populations d'heuristiques correspondent à l'idée de ``vrai composite'' qui désigne des systèmes composés dont le résultat est attribuable aux interactions entre composants et non à leur composition. L'interaction entre niveaux globaux et locaux s'envisage également naturellement à travers les niveaux induits par l'organisation hiérarchique de notre modèle. C'est en ce sens que le travail fourni contribue à l'étude de l'émergence: par l'étude des possibilités de définition offertes par un modèle multi-agentEmergence and multi-agent systems are two domains with share similar problems. Through the study of emergence in the context of multi-agent systems, this work is centred on their principal common point; the search for a collective advantage gained through the interaction among the agents, when the global result is due to interaction. This situation is often summarized by a whole that is more than the sum of its parts. One contribution of this thesis is identifying interactions whose impact can be evaluated through the side-by-side comparison of systems including these interactions or not. Such collective benefits are defined for problem-solving by a heuristic search with a hierarchical multi-agent model. This work includes a multi-agent model of that kind of search that identifies collective benefits, which are called synergies. Three kinds of synergies are considered: the synergy between heuristics searching the same problem, the one between similar problems, and the synergy between a human user and the artificial search system. These possible synergies are included in the discussion about emergence. In this framework, some heuristic populations match the idea of a ``true composite'' that is a composed system whose result is due to interactions between components and not to its composition. The interaction between local and global levels fits in the levels induced by the model's hierarchical organisation. This way, a contribution to the study of emergence is given, by the definition possibilities that a multi-agent model allows for emergence
38
Haïtami, Mehdi. "Optimisation multicouche des réseaux optiques wdm : heuristiques tabou pour la résolution à moindre coût du problème de groupage de routage et d’affectation de longueurs d’ondes." Thèse, Université de Sherbrooke, 2014. http://hdl.handle.net/11143/5985.
Анотація:
La fibre optique constitue le médium par excellence pour le transport d’information à haut débit. Elle forme l’épine dorsale de la majorité des réseaux optiques régionaux et métropolitains. La mise en œuvre à moindre coût de ce type de réseaux nécessite une planification rigoureuse des ressources pour satisfaire une demande de trafic de plus en plus exigeante en bande passante.
Le présent travail s’inscrit dans un cadre d’optimisation multicouche de réseaux optiques WDM. La principale contribution de cette thèse est de concevoir deux heuristiques Tabou, capable de résoudre le problème NP-complet de groupage, de routage et d’affectation de longueurs d’ondes GRWA (Grooming, Routing and Wavelength Assignment) dans un réseau optique WDM. La fonction objectif des heuristiques développées est de minimiser le coût de déploiement du réseau, autrement dit ses dépenses en capital (CAPEX), tout en maximisant son taux d’utilisation. Les contraintes réseaux à respecter sont celles du problème GRWA, augmenté des trois contraintes de la couche physique suivantes : le budget de puissance du signal optique, la quantité de dispersion chromatique qui s’y est accumulée et son rapport signal sur bruit optique (OSNR). Le coût du réseau est calculé en fonction de la quantité d’équipements optiques et optoélectroniques nécessaires pour satisfaire la demande de trafic. Les liens des réseaux optiques étudiés sont bidirectionnels composés de fibres optiques monomodes standard G-652 [1] opérant dans la fenêtre optique centrée autour de la longueur d’onde 1550 nm. Les nœuds sont équipés de plateformes multiservices (MSPP) supportant les protocoles SDH/SONET, GFP et LCAS/VCAT pour une gestion efficace de la bande passante. Le trafic considéré est statique de granularité multiple.
39
Bontoux, Boris. "Techniques hybrides de recherche exacte et appochée : application à des problèmes de transport." Avignon, 2008. http://www.theses.fr/2008AVIG0166.
Анотація:
Nous nous intéressons dans cette thèse aux possibilités d’hybridation entre les méthodes exactes et les méthodes heuristiques afin de pouvoir tirer avantage de chacune des deux approches : optimalité de la résolution exacte, caractère moins déterministe et rapidité de la composante heuristique. Dans l’objectif de résoudre des problèmes NPdifficiles de taille relativement importante tels que les problèmes de transports, nous nous intéressons dans les deux dernières parties de ce mémoire à la conception de méthodes incomplètes basées sur ces hybridations. Dans la première partie, nous allons nous intéresser aux méthodes de résolution par recherche arborescente. Nous introduisons une nouvelle approche pour la gestion des décisions de branchement, que nous appelons Dynamic Learning Search (DLS). Cette méthode définit de manière dynamique des règles de priorité pour la sélection des variables à chaque noeud et l’ordre des valeurs sur lesquelles brancher. Ces règles sont conçues dans une optique de généricité, de manière à pouvoir utiliser la méthode indépendamment du problème traité. Le principe général est de tenir compte par une technique d’apprentissage de l’impact qu’ont eu les décisions de branchement dans les parties déjà explorées de l’arbre. Nous évaluons l’efficacité de la méthode proposée sur deux problèmes classiques : un problème d’optimisation combinatoire et un problème à satisfaction de contraintes. La deuxième partie de ce mémoire traite des recherches à grand voisinage. Nous présentons un nouvel opérateur de voisinage, qui détermine par un algorithme de programmation dynamique la sous-séquence optimale d’un chemin dans un graphe. Nous montrons que cet opérateur est tout particulièrement destiné à des problèmes de tournées pour lesquels tous les noeuds ne nécessitent pas d’être visités. Nous appelons cette classe de problème les Problèmes de Tournées avec Couverture Partielle et présentons quelques problèmes faisant partie de cette classe. Les chapitres 3 et 4 montrent, à travers des tests expérimentaux conséquents, l’efficacité de l’opérateur que nous proposons en appliquant cette recherche à voisinage large sur deux problèmes, respectivement le Problème de l’Acheteur Itinérant (TPP) et le Problème de Voyageur de Commerce Généralisé (GTSP). Nous montrons alors que cet opérateur peut être combiné de manière efficace avec des métaheuristiques classiques, telles que des algorithmes génétiques ou des algorithmes d’Optimisation par Colonies de Fourmis. Enfin, la troisième partie présente des méthodes heuristiques basées sur un algorithme de Génération de Colonnes. Ces méthodes sont appliquées sur un problème complexe : le problème de Tournées de Véhicules avec Contraintes de Chargement à Deux Dimensions (2L-VRP). Nous montrons une partie des possibilités qu’il existe afin de modifier une méthode a priori exacte en une méthode heuristique et nous évaluons ces possibilités à l’aide de tests expérimentauxWe are interested in this thesis in the possibilities of hybridization between the exact methods and the methods heuristics to be able to take advantage of each of both approaches: optimality of the exact resolution, the less determinist character and the speed of the constituent heuristics. In the objective to resolve problems NP-hard of relatively important size such as the transportation problems, we are interested in the last two parts of this report in the conception of incomplete methods based on these hybridizations. In the first part, we are going to be interested in the methods of resolution by tree search. We introduce a new approach for the management of the decisions of connection, which we call Dynamic Learning Search ( DLS). This method defines in a dynamic way rules of priority for the selection of variables in every knot and the order of the values on which to connect. These rules are conceived in an optics of genericity, so as to be able to use the method independently of the treated problem. The general principle is to take into account by a technique of learning of the impact which had the decisions of connection in the parts already investigated in the tree. We estimate the efficiency of the method proposed on two classic problems: a combinatorial optimization problem and a constraints satisfaction problem. The second part of this report handles large neighborhood search. We present a new operator of neighborhood, who determines by an algorithm of dynamic programming the optimal sub-sequence of a road in a graph. We show that this operator is quite particularly intended for problems of tours for which all the vertices do not require to be visited. We call this class of problem the Problems of Tours with Partial Cover and present some problems being a part of this class. Chapters 3 and 4 show, through consequent experimental tests, the efficiency of the operator which we propose by applying this search to wide neighborhood on two problems, respectively the Traveling Purchaser Problem (TPP) and Generalized Traveling Salesman Problem ( GTSP). We show while this operator can be combined in a effective way with classic metaheuristics, such as genetic algorithms or algorithms of Ant Colony Optimization
40
Hamel, Johanne. "Création artistique et identité professionnelle: une étude heuristique." Thèse, Université de Sherbrooke, 2011. http://hdl.handle.net/11143/8290.
Анотація:
Cette recherche étudie l'effet de l'exploration de la création artistique sur l'identité professionnelle d'art-thérapeute, d'enseignante en art-thérapie et de psychologue avec une approche heuristique, c'est-à-dire en se plaçant au cœur de l'expérience sensible de la création. La question de recherche est la suivante : comment l'exploration de mon identité d'artiste à travers la création artistique modifiera-t-elle mon identité professionnelle? Cette recherche exploratoire vise à découvrir les processus et vécus présents lors de la création artistique, susceptibles de modifier l'identité professionnelle. La variante HSSI (Sela-Smith, 2002) de la méthode heuristique de recherche est utilisée. Nous retrouvons deux types de données : 11 productions artistiques et un Journal de processus créateur de 430 pages manuscrites. L'analyse des données comporte une analyse de la symbolique des œuvres artistiques, une analyse thématique du contenu du Journal de processus créateur, une analyse des étapes du processus créateur et une analyse de l'application de la méthode heuristique dans cette recherche. Les résultats obtenus concernent l'identité professionnelle d'art-thérapeute, celle d'enseignante en art-thérapie, celle de psychologue et celle d'artiste. Un intérêt secondaire de cette recherche est la formalisation de la méthode heuristique pour son application à l'art-thérapie.
41
T'Kindt, Vincent. "Etude des problèmes d'ordonnancement multicritères." Tours, 1999. http://www.theses.fr/1999TOUR4017.
Анотація:
En pratique, les problèmes d'ordonnancement nécessitent souvent la prise en compte de plusieurs critères pourtant ils ont fait l'objet de nombreuses études lorsqu'il s'agit d'optimiser un critère unique et beaucoup moins lorsqu'il s'agit de plusieurs critères. Plus généralement, les premiers travaux traitant de problèmes d'optimisation multicritères remontent au début des années 1970. La littérature dans ce domaine est très consquente. Pourtant aucun travail de synthèse faisant le lien entre les problèmes d'ordonnancement multicritères et les problèmes d'optimisation multicritères n'existe. Dans ce document nous proposons une démarche générale pour l'étude et la résolution des problèmes d'ordonnancement multicritères. Nous présentons dans un premier temps un état de l'art sur la théorie de l'optimisation multicritère mettant en évidence les principaux résultats et algorithmes du domaine. Nous présentons ensuite un état de l'art sur l'ordonnancement multicritère. A partir de ces deux études nous proposons une démarche générale. Nous nous intéressons également à la résolution de problèmes d'ordonnancement multicritères à partir de cette démarche. Trois problèmes d'ordonnancement multicritères à machines parallèles sont étudiés dont un est tiré du contexte de la production de bouteilles en verre. Nous proposons également des algorithmes exacts et heuristiques pour résoudre deux problèmes d'ordonnancemnt multicritères de type flowshop. Nous mettons également en évidence le fait qu'une heuristique multicritère pour résoudre un problème d'ordonnancement de type flowshop hybride monocritères est plus efficace que les heuristiques existantes. Nous terminons ce document par la présentation de l'outil de comparaison et l'élaboration d'algorithmes (projet OCEA).
42
Belmecheri, Farah. "Optimisation des tournées de véhicules en transport de type messagerie." Troyes, 2010. http://www.theses.fr/2010TROY0023.
Анотація:
Ce mémoire porte sur l’optimisation de tournées de véhicules d’un transporteur local TCP-Distribution. L’étude est sur le problème de tournées sur nœuds (VRP) et plus précisément sur le cas avec flotte hétérogène (Heterogeneous fleet), livraison et collecte (with Mixed Backhauls), et les fenêtres de temps (Time Windows), le problème est appelé HVRPMBTW. La littérature sur ce problème est quasi inexistante. Après une introduction générale sur les problèmes de transport et une description complète du problème traité, nous proposons des approches de résolutions. Un modèle mathématique est développé, c’est un modèle linéaire à variables réelles et binaires (PL mixte) qui est utilisé par une méthode exacte. Une première approche métaheuristique est proposée, elle est basée sur l’optimisation par colonies de fourmis (ACO) combinée à une efficace recherche locale. Cette méthode a montré son efficacité au HVRPMBTW. Une deuxième approche est développée, appelée optimisation par essaim particulaire (PSO) combinée à cette efficace recherche locale. Les nouveaux résultats obtenus améliorent les résultats précédents. La dernière partie de ce mémoire est dédiée à l’application industrielle. Les méthodes développées sont appliquées aux instances industrielles. Un Outil de Gestion des Performances est implémenté et accessible via une interface développée. Il a pour mission de calculer et d’analyser les indicateurs, et faire appel aux méthodes d’optimisationThis thesis focuses on the transportation problem of a local carrier TCP-Distribution. The study is on the node routing problem (VRP) and specifically to cases with Heterogeneous fleet (H), with Mixed Backhauls (MB), and Time Windows (TW), the problem is called HVRPMBTW. It is few studied in literature. After a general introduction to the transportation problems, and a complete description of the problem studied, we suggest several resolution approaches. A mathematical model is developed; it is a linear model with real and binary variables (mixed LP) which is used by an exact method. The first metaheuristic approach is proposed, it is based on an Ant Colony Optimization (ACO) combined with an efficient local search. This method has shown its effectiveness on HVRPMBTW. A second approach is developed, called a Particle Swarm Optimization (PSO) combined with the effective local search. The new results obtained improve the previous results. The last part of this thesis is dedicated to an industrial application. The methods developed are applied to the industrial cases. A Performance Management Tool is implemented and used with a graphic box developed. Its aim is to calculate and analyze the indicators, and to use the optimization methods
43
Reghioui, Hamzaoui Mohamed. "Problèmes de tournées de véhicules avec fenêtres horaires ou préemption des tâches." Troyes, 2008. http://www.theses.fr/2008TROY0018.
Анотація:
Dans ce mémoire, nous étudions les problèmes de tournées de véhicules sur nœuds et sur arcs qui sont les deux grands types de problèmes de tournées, rencontrés dans la majorité des applications de transport. Nous nous intéressons plus particulièrement aux cas avec fenêtres horaires ou préemption des tâches. Ce travail est décomposé en deux grandes parties. La première partie est consacrée aux problèmes de tournées sur nœuds et sur arcs avec fenêtres horaires (VRPTW pour Vehicle Routing Problem with Time Windows et CARPTW pour Capacitated Arc Routing Problem with Time Windows). Contrairement au VRPTW qui a fait l’objet d’une recherche intensive ces dix dernières années, peu de travaux ont porté sur le CARPTW. Dans cette partie de la thèse, nous proposons une méthode basée sur la métaheuristique GRASP couplée à une technique de reconnexion de chemins (path-relinking) pour le CARPTW et un algorithme mémétique pour le VRPTW. La deuxième partie de cette thèse porte sur les problèmes de tournées de véhicules sur nœuds et sur arcs avec préemption de la demande (SDVRP pour Split Delivery Vehicle Routing Problem et SDCARP pour Split Delivery Capacitated Arc Routing Problem). Vu que le SDCARP est un problème relativement nouveau, nous avons commencé par élaborer des modèles mathématiques. Nous avons ensuite proposé des bornes inférieures et supérieures. Les bornes inférieures sont obtenues par des méthodes de coupes, alors que les bornes supérieures sont déterminées par un algorithme mémétique avec gestion de la population et une nouvelle métaheuristique. L’algorithme mémétique a été aussi adapté au SDVRP, donnant lieu à des résultats très compétitifs avec ceux déjà publiésThis thesis studies the node and arc routing problems which are the two main types of routing problems encountered in most transportation applications. We focus particularly on the cases with time windows or split deliveries. This work is divided into two main parts. The first part is devoted to the node and arc routing problems with time windows (VRPTW for the Vehicle Routing Problem with Time Windows and CARPTW for the Capacitated Arc Routing Problem with Time Windows). Contrary to the VRPTW which has been the subject of intensive research over the past decade, few studies have considered the CARPTW. In this part of the thesis, we propose a method based on the metaheuristic GRASP combined with a path-relinking process for the CARPTW and a memetic algorithm for the VRPTW. The second part of the thesis focuses on the node and arc routing problems with split deliveries (SDVRP for the Split Delivery Vehicle Routing Problem and SDCARP for the Split Delivery Capacitated Arc Routing Problem). Since the SDCARP is a relatively new problem, we started by developing mathematical models. We then proposed lower and upper bounds. The lower bounds are obtained by two cutting plane methods while the upper bounds are determined by a memetic algorithm with population management and a new metaheuristic. The memetic algorithm was also adapted to the SDVRP, giving rise to competitive results
44
Thanh, Phuong Nga. "Conception et planification stratégique des réseaux logistiques complexes." Nantes, 2008. http://www.theses.fr/2008NANT2067.
Анотація:
Dans un contexte de forte concurrence, les entreprises cherchent à améliorer la performance de leur réseau logistique. Des changements deviennent nécessaires en cas d'obsolescence de la chaîne logistique, mais aussi à l'occasion d'événements comme des fusions ou acquisitions, des délocalisations ou un changement de conjoncture. Le but de cette thèse est de modéliser et résoudre un problème de conception et de planification stratégique des réseaux logistiques. Nous développons à cet effet des algorithmes de recherche opérationnelle. Les principales variables de décision concernent l'ouverture, l'agrandissement ou la fermeture de sites, la planification des capacités dans le temps ainsi que la gestion des flux physiques. L'objectif est de minimiser le coût total du système sur un horizon de plusieurs années, tout en satisfaisant les prévisions de demande. Plusieurs contraintes additionnelles sont prises en compte. Citons à titre d'exemple la possibilité de sous-traitance de la production ou la possibilité d'augmenter la capacité des sites au cours du temps. Le problème est modélisé par un programme linéaire en variables mixtes avec notamment des variables de décisions binaires. Trois méthodes de résolutions approchées sont développées. La première est une heuristique basée sur la relaxation linéaire et des règles d'arrondi. Une amélioration est proposée en remplaçant la relaxation linéaire par l'approche D. C. (Difference of Convex Functions). La dernière méthode est une décomposition du problème utilisant les principes de la relaxation Lagrangienne. Les résultats obtenus avec ces méthodes sont comparés aux résultats de référence obtenus avec le solveur Xpress-MPIn a context of strong competition, many companies will seok to improve the performance of their supply chain. Changes are necessary when the supply chain becomes obsolete or in case of signicative changes like mergers, outsourcing or substantial variations of the demand. This research aims at modelling and solving a supply chain design and planning problem over a strategic horizon with some operations research algorithms. The main decision variables concern the facilities that may be opened, expanded or closed, as well as capacity planning and the management of material flow along the supply chain. The objective is to minimise the total logistic cost while satisfying the demand. Additional options include, among others, the possibility to subcontract a part of the production, the possibility to increase the capacity of some facilities. The problem is modeled by a mixed-integer linear program where the integer variables are binary. Three resolution methods are developed. The first is a heuristic based on linear relaxation and some rounding procedures. An improved version of this method is developed by replacing the linear relaxation with the Difference of Convex Functions (D. C. ) approach. The last method is a decomposition method based on Lagrangean relaxation. The results of these methods are compared with the ones obtained with the solver Xpress-MP
45
Picarougne, Fabien. "Recherche d'information sur Internet par algorithmes évolutionnaires." Phd thesis, Tours, 2004. http://tel.archives-ouvertes.fr/tel-00008013.
Анотація:
Dans ce travail de thèse, nous présentons le problème de recherche d'information sur Internet et plus généralement de veille stratégique. Nous remarquons généralement qu'il est nécessaire de passer beaucoup de temps à analyser les résultats fournis par les moteurs de recherche traditionnels afin d'obtenir une réponse satisfaisante. Dans cette thèse, nous avons donc développé un outil de recherche automatique basé sur une stratégie de recherche évolutionnaire. Cet outil explore les pages Web en partant des résultats fournis par les moteurs de recherche traditionnels (comme Google, Altavista, ...). Plusieurs méthodes d'optimisation ont été comparées : une approche génétique, une approche à base de population de fourmis et un algorithme tabou. L'effort de recherche a également été parallélisé et peut être distribué sur plusieurs machines distantes afin de maximiser les ressources disponibles à l'exécution de cette tâche et d'utiliser une architecture parallèle de grande ampleur. Enfin, nous proposons un système de visualisation des résultats d'un moteur de recherche basé sur les propriétés des nuages d'agents afin d'aider les utilisateurs à mieux comprendre les éléments renvoyés par le moteur et de diminuer ainsi le temps nécessaire à leur analyse.
46
Belaïdouni, Mériéma. "Métaheuristiques et paysages de recherche." Angers, 2001. http://www.theses.fr/2001ANGE0022.
Анотація:
Les métaheuristiques sont une classe de méthodes qui fournissent des solutions de bonne qualité en temps raisonnable à des problèmes combinatoires réputés difficiles. Il existe de nombreux travaux d'application de ces méthodes mais très peu d'études s'intéressent à leur aspect fondamental. Ainsi la dynamique et le comportement des métaheuristiques restent méconnus. Cette thèse est dédiée à l'étude de quelques questions fondamentales sur les métaheuristiques. Nous avons adopté une méthodologie en trois axes : 1) l'étude des propriétés et mesures des problèmes combinatoires, 2) l'étude des comportements des métaheuristiques, 3) la mise en relation des mesures des problèmes et des comportements de métaheuristiques. Pour valider cette approche nous l'avons appliquée à deux problèmes NP-complets : MAX-CSP et SAT. Nous avons développé pour le premier axe un état de l'art qui réunit un grand nombre de mesures existantes, puis nous avons classé ces mesures. Nous avons ensuite appliqué et analysé les mesures densité d'état (DOS), distance dans un niveau (DDN), distance entre niveaux (DEN), autocorrélation et densité des coûts du processus (DCP). Concernant le deuxième axe nous avons développé la notion de performance qui fait partie des comportements d'une métaheuristique et nous avons proposé un nouveau critère d'évaluation de la performance basé sur la mesure DCP. Enfin, nous avons dans le troisième axe mis en évidence des relations entre comportements et mesures en analysant les conséquences sur les métaheuristiques, des mesures que nous avons étudiées. Ces mises en relation nous permettent de prévoir ou d'expliquer le comportement et la dynamique des métaheuristiquesMetaheuristics are a class of methods which are able to provide solutions of good quality in a reasonnable amount of time for difficult combinatorial problems. There exist a large number of applications of these methods but only few studies concern their fondamental aspects. This thesis is devoted to study some fondamental issues of metaheuristics. Three tightly related axis are explored : 1)the study of problems properties and measures, 2)the study of dynamics of metaheuristics, 3)the establishment of the relations between measures of problems and dynamics of metaheuristics. To validate this approach we have apllied it to two NP-complete problems : MAX-CSP and SAT
47
Bertel, Sylvain. "Problèmes d'ordonnancement dans un flowshop hybride avec recirculation sous contraintes de gestion du personnel." Tours, 2001. http://www.theses.fr/2001TOUR4029.
Анотація:
Le travail présenté dans ce document s'est déroulé dans le cadre d'une convention CIFRE (Convention Industrielle de Formation par la Recherche) en liaison avec le service de production de la société de services en informatique Atos-Origin et le laboratoire d'informatique (LI) de l'université de Tours. Dans ce document, nous présentons dans un premier temps un état de l'art sur les problèmes de flowshop avec minimisation de la somme pondérée des travaux en retard et ensuite un état de l'art sur les problèmes de gestion de personnel. Un problème d'ordonnancement correspond à un flowshop hybride avec recirculation provenant du contexte industriel du traitement des chèques a été abordé. Pour ce problème, nous proposons deux heuristiques basées sur des règles de priorités et un algorithme génétique. A partir des heuristiques développées, nous proposons une procédure intégrée pouvant s'utiliser sur plusieurs niveaux de décisions. Pour le problème de gestion de personnel, nous proposons plusieurs modèles linéaires en nombre entier et une heurisitique permettant de dimentisonner l'atelier de production. Nous mettons en évidence qu'une procédure intégrée proposant une planification au niveau tactique est plus efficace qu'une planification au niveau opérationnel. Nous terminons le document sur une présentation de l'outil logiciel appelé PLANIF'00This work has been achieved within the context of the research collaboration with an industry (CIFRE), the customer management service Atos-Origin and the computer science laboratory of the university of Tours (LI). In this document, we propose in a first time a survey on hybrid flowshop schedulling problems that minimize the wheighted number of late jobs and manpower scheduling problem. A scheduling problem from an industrial context of cheque processing is studied. For this problem, two heuristics based on priority rules and a metaheuristic are proposed. From developed heuristics, we describe an integrated procedure which can be used at different decision levels. Regarding manpower scheduling, we propose linear programming model and a heuristic that gives the size of the workshop. We notice that a planning defined at a tactical level is moire efficient than a planning defined at an operational level. We end this document with the presentation of a software called PLANIF'00
48
Weill, Jean-Christophe. "Programmes d'échecs de championnat : architecture logicielle, synthèse de fonctions d'évaluation, parallélisme de recherche." Paris 8, 1995. http://www.theses.fr/1995PA080954.
Анотація:
La programmation des jeux de reflexion fut consideree comme the drosophilia melanogaster of machine intelligence. Ce domaine devait permettre l'elaboration de techniques et d'algorithmes reutilisables dans d'autres domaines de l'intelligence artificielle. Selon c. Shannon, il s'agit d'un sujet sensible ou l'avancee est facilement communicable au public. Nous abordons cette question dans le cadre de programmes de jeux devant repondre a un probleme dans des conditions de tournois. Nous comparons les differentes recherches minimax basees sur des elagages alpha-beta avec l'algorithme negac* que nous avons defini et donnons les principaux resultats que nous avons etablis sur sa complexite. Nous definissons, dans le paradigme negamax, le nouvel algorithme de recherche de nombre de preuves et nous le comparons avec notre programme d'echecs ecume, dans le cadre des recherches de mats. Nous exposons un ensemble d'heuristiques qui permettent de rendre les recherches negamax plus rapides et plus fiables en explicitant les options que nous avons prises dans nos programmes d'echecs. Nous presentons nos resultats sur la parallelisation de la recherche minimax pour une machine distribuee: la connection machine 5. Ils nous ont permis de definir une nouvelle methode que nous avons comparee aux meilleures methodes connues jusqu'alors, sur des arbres de jeux simules et reels. Nous continuons par la presentation de notre methode de construction de fonctions d'evaluation en expliquant comment nous avons pu introduire la notion de plan strategique. Nous montrons aussi comment construire automatiquement une fonction d'evaluation par apprentissage dans la finale roi et dame contre roi et dame. Enfin, nous decrivons l'ensemble des caracteristiques de nos programmes d'echecs, dont cumulus 2. 0 qui a remporte le titre de vice-champion du monde d'echecs logiciels toutes categories
49
Zemali, Yacine. "Morcellement de l'espace de recherche en planification : étude théorique et utilisation pour le calcul d'heuristiques." École nationale supérieure de l'aéronautique et de l'espace (Toulouse ; 1972-2007), 2004. http://www.theses.fr/2004ESAE0006.
Анотація:
Les techniques de planification les plus performantes utilisent toutes des heuristiques. Il est démontré que même GraphPlan est un planificateur heuristique. Nous partons du constat que les heuristiques actuelles trouvent leurs limites dans la difficulté des choix de prise en compte des interactions. Nous proposons une approche permettant de faire varier la proportion et la nature des interactions prises en compte au cours d’un calcul d'atteignabilité. Nos travaux reposent sur le morcellement de l’espace de recherche : certains planificateurs raisonnent au niveau des états atteignables à partir de l’état initial, le graphe parcouru par l’algorithme de recherche à pour nœuds des états individualisés. D’autres planificateurs, comme GraphPlan, développent un graphe nivelé dans lequel chaque niveau contient une liste de faits atteignables, représentant un ensemble d’états indifférenciés. Le morcellement est une vision intermédiaire dans la construction du graphe de planification : certains états sont complètement individualisés, alors que d’autres sont groupés par paquets. Il s’agit d’introduire une arborescence contrôlée dans un graphe de planification disjonctif. Nous présentons et formalisons tout d’abord cette technique. Nous proposons et analysons diverses stratégies de contrôle. Enfin, nous présentons l’utilisation de l’analyse d'atteignabilité réalisée par le morcellement dans le cadre du calcul d’une famille d’heuristiques. Certaines sont admissibles et permettent une résolution optimale, alors que d’autres permettent de résoudre les problèmes plus rapidement au détriment de la qualité des plans trouvés. Nous discutons les résultats obtenus afin d’analyser l'impact du morcellement.
50
Galand, Lucie. "Méthodes exactes pour l'optimisation multicritère dans les graphes : recherche de solutions de compromis." Paris 6, 2008. http://www.theses.fr/2008PA066153.
Анотація:
Ces travaux de thèse se situent à la croisée de l'intelligence artificielle et de la recherche opérationnelle, avec pour objectif de fournir des solutions algorithmiques efficaces aux problèmes multicritères admettant un nombre combinatoire de solutions potentielles. Pour cela, nous utilisons des modèles de préférences raffinant la dominance de Pareto et permettant de concentrer la recherche sur une solution de meilleur compromis. Dans cette perspective, nous proposons deux approches pour l'optimisation exacte de problèmes combinatoire multicritères, qui s'appuient sur une approximation linéaire du critère à optimiser. La première approche repose sur une énumération ordonnée des solutions selon cette approximation linéaire, tandis que la seconde approche effectue des coupes dans l'espace de recherche à l'aide de cette approximation linéaire, permettant une réduction considérable du nombre de solutions à explorer. Ces approches nous ont permis, en particulier, de mettre en oeuvre des algorithmes efficaces pour l'optimisation de l'opérateur OWA, de l'intégrale de Choquet et de la norme de Tchebycheff. En complément de ces travaux, nous proposons une exploration interactive de l'ensemble de Pareto à travers l'optimisation de la norme pondérée de Tchebycheff. Nous appliquons ces travaux aux problèmes multicritères de plus court chemin, d'arbre couvrant de poids minimal et de recherche dans des graphes d'états pour lesquels nous avons obtenus des temps de résolution suffisamment rapides pour établir le caractère opérationnel des algorithmes de résolution.