Spelling suggestions: "subject:"métaheuristique"" "subject:"métatheuristiques""
1 |
Modèles mathématiques et algorithmes pour la résolution du problème de tournées du personnel de soins à domicile / Mathematical models and algorithms for the home care routing and scheduling problemCissé, Mohamed 21 June 2017 (has links)
Le soin à domicile est un secteur en plein essor ces dernières années. Cela est dû au vieillissement de la population, à la volonté de réduire les coûts hospitaliers et d’assurer le bien-être du patient en le gardant dans son cadre familial tout en maintenant la qualité des soins. L’organisation de ces soins nécessite une prise de décisions aux niveaux stratégique, tactique et opérationnel. Cette thèse s’articule autour de l’étude de problèmes apparaissant uniquement au niveau opérationnel. Ces problèmes traitent de la planification des tournées du personnel de soins à domicile. La première étape de cette étude a consisté à faire une revue de la littérature. De nombreux modèles mathématiques ont été formulés dans la littérature. Cependant, ces modèles étaient dédiés à une structure de soins à domicile spécifique et pouvaient être difficilement transposés. Nous proposons ici une approche générique tant du point de vue de la modélisation que des méthodes de résolutions. À cet effet, nous avons identifié les caractéristiques fréquemment rencontrées dans la littérature à travers cette revue de la littérature. Un modèle générique a été proposé prenant en compte la plupart des caractéristiques. Ce modèle générique constitue un socle pour la construction de méthodes de résolution. Deux méthodes de résolution ont été conçues. La première méthode est une méthode par décomposition et la deuxième méthode est un algorithme hybride génétique avec gestion de la population. Ces deux méthodes utilisent des représentations d’une solution issues de la littérature et adaptées aux caractéristiques du problème. Des expérimentations numériques ont été réalisées dans le but d’évaluer les méthodes proposées et de se comparer à la littérature. / The home care is a growing sector. Many questions research problems exist. We can identify at strategic level the districting problem ; at tactical level, the resource dimensioning problem ; and operational level, the operation assignment and the home care routing and scheduling problem. This thesis focuses on the last one. For this purpose, we propose a state of the art, a generic model and two solutions methods hybrid genetic algorithm and a decomposition.
|
2 |
Algorithmes pour les problèmes de tournées à la demande / Algorithms for on-demand touring problemsZhao, Xiagang 06 May 2011 (has links)
Dans le cadre de cette thèse, nous nous intéressons au problème du transport à la demande. Nous proposons des heuristiques pour résoudre ce problème de manière rapide et efficace. Dans cette thèse, nous traitons trois problèmes : le premier est le Dial-a-ride (DARP standard). Pour ce problème, nous proposons des heuristiques basées sur la technique d’insertion et une technique de propagation de contrainte. Nous proposons aussi la procédure SPLIT et des opérateurs classiques de recherche locale pour résoudre ce problème. Le second est le DARP multicritères pour laquelle nous proposons un schéma de type ELS. Le troisième est un problème de transport à la demande avec contraintes financières (DARPF), qui est une extension de DARP. Nous résolvons ce problème grâce à une heuristique d’insertion et une technique de propagation de contraintes. La fonction objectif détermine les caractéristiques des tournées. Des résultats expérimentaux montrent que nos (méta-) heuristiques donnent des résultats plus favorables aux clients (meilleure qualité de service) / As part of this thesis, we investigate the vehicle routing problem. We propose heuristics to solve this problem quickly and efficiently. In this thesis, we deal with three problems: the first is the Dial-a-ride problem. For this problem, we propose heuristics based on the technique of insertion and a constraint propagation technique. We propose also the procedure SPLIT and some operators of local research to solve this problem. The second is the multi-criteria DARP for which we propose an ELS framework. The third is a DARP problem with financial constraints (DARPF), which is an extension of DARP. We solve this problem thanks to insertion heuristics using a constraint propagation technique. The objective function determines the characteristics of the tour. Experimental results show that our (meta-) heuristics give results more favorable to customers (better quality of service)
|
3 |
Proposition et étude d'une extension du RCPSP pour la Mutualisation entre plusieurs sites : définition, formalisation, méthodes exactes et métaheuristiques / Proposition and study of an extension of the RCPSP with resource pooling between distant sitesLaurent, Arnaud 10 October 2017 (has links)
Cette thèse a pour objet l’étude d’une extension du RCPSP, un problème d’ordonnancement de tâches et d’affectation de ressources. Cette extension considère un aspect multi-site au problème. Cette extension a pour but de modéliser des problématiques de mutualisation de ressources entre plusieurs sites, comme c’est notamment le cas dans les communautés hospitalières. Pour résoudre ce problème nous avons proposé des méthodes exactes ainsi que des méthodes approchées. Deux modèles mathématiques ont été proposés et comparés sur de petites instances générées. Des méthodes approchées ont également été proposées. Ces méthodes s’articulent sur un couplage méta-heuritique / algorithme d’ordre strict et permettent d’explorer un espace de recherche restreint. Trois différents codages de solution ont été proposés ainsi que trois algorithmes d’ordre strict correspondant à chacun des trois codages. Ces différentes méthodes ont été comparées et analysées selon les instances et le temps de calcul alloué. / Résumé non disponible
|
4 |
Ordonnancement d’un système de production industriel complexe : flow shop hybride avec des machines dédiées soumis à différentes contraintes temporelles / Scheduling of a complex industrial production system : hybrid flow shop with dedicated machines and different time constraintsHarbaoui, Houda 14 December 2018 (has links)
L’accroissement des profits, à travers l’amélioration de la productivité et la réduction des pertes de matières, représente un objectif primordial pour les entreprises industrielles. Dans cette thèse, nous nous intéressons à la résolution d’un problème industriel complexe réel avec des contraintes de temps. Nous nous sommes intéressés, tout d’abord, à un objectif principal, soit la minimisation des dates de fin de production, suivi d’un objectif secondaire qui est la minimisation des quantités de déchets non recyclables. Dans un premier temps, nous avons modéliséle problème par des modèles mathématiques, que nous avons résolu à l’aide d’un solveur. Dans un second temps, nous avons proposé une méthode approchée en forme d’algorithmes évolutionnistes. Cette méthode est appliquée aux deux objectifs mentionnés ci-dessus séparément. Une troisième méthode est ensuite appliquée à l’objectif principal, à savoir une méthode arborescente approchée. Nous avons testé les algorithmes proposés sur des instances inspirées d’un cas réel ; issues d’une entreprise du secteur agroalimentaire et sur des instances inspirées de la littérature. / Increasing profits, through the improvement of productivity and minimizing waste, is a primary objective for industrial companies. In this thesis, we are interested insolving a real complex industrial problem with time constraints. Firstly, we were interested in minimizing completion time (Cmax). Secondly, we focused on minimizing of non-recyclable waste. As a first step, we formulated the problem by mathematical models, which we solved using a solver. In a second step, we proposed an approximate method in the form of evolutionary algorithms. Both methods were applied to the two objectives mentioned above separately. Then, a third method which is a tree-search algorithm was applied only to the main objective. We tested the proposed algorithms on instances inspired from a real case; from an agri-food business, and also on instances inspired from the literature.
|
5 |
Coopération méta heuristique et logique floue pour le dimensionnement d'une installation hybride / Meta heuristics cooperation and fuzzy logic for the design of a hybrid systemBen Jemaa, Abdelhak 12 December 2015 (has links)
Cette thèse propose la méthodologie de dimensionnement optimal pour optimiser la configuration de système d'énergie hybride. Pour cela, nous utilisons une approche pour la génération de base de règles floues et une optimisation automatiques au moyen d'algorithme génétique et d'un PSO adaptés avec le floue. Ces algorithmes nous permet d'obtenir le nombre optimal de panneaux photovoltaïques, d'éoliennes et des batteries, minimisant le coût total du système et garantissant la disponibilité permanente de l'électricité pour couvrir les besoins énergétiques. L'historique horaire de vitesse du vent, d’ensoleillement, sont utilisés pour modéliser la production des éoliennes, la production photovoltaïque et de charge. Le coût total est la fonction objective et la taille technique est une contrainte. / This thesis proposes the optimum sizing methodology to optimize the configuration of hybrid energy system. For this, we use an approach for automatic fuzzy rule base generation and optimization by means of Fuzzy-Adaptive Genetic Algorithm and fuzzy adaptive PSO. This Algorithms allows us to obtain the optimal number of photovoltaic panels, wind turbines and storages units, ensuring the minimal global high efficiency system total cost and guaranteeing the permanent availability of energy to cover the load energy requirements. Historical hourly wind speed, solar irradiance and load data are used to stochastically model the wind turbines, photovoltaic generation and load. The total cost is the objective function and the technical size is a constraint.
|
6 |
Système de gestion d'énergie d'un véhicule électrique hybride rechargeable à trois rouesDenis, Nicolas January 2014 (has links)
Résumé : Depuis la fin du XXème siècle, l’augmentation du prix du pétrole brut et les problématiques environnementales poussent l’industrie automobile à développer des technologies plus économes en carburant et générant moins d’émissions de gaz à effet de serre. Parmi ces technologies, les véhicules électriques hybrides constituent une solution viable et performante. En alliant un moteur électrique et un moteur à combustion, ces véhicules possèdent un fort potentiel de réduction de la consommation de carburant sans sacrifier son autonomie. La présence de deux moteurs et de deux sources d’énergie requiert un contrôleur, appelé système de gestion d’énergie, responsable de la commande simultanée des deux moteurs. Les performances du véhicule en matière de consommation dépendent en partie de la conception de ce contrôleur. Les véhicules électriques hybrides rechargeables, plus récents que leur équivalent non rechargeable, se distinguent par l’ajout d’un chargeur interne permettant la recharge de la batterie pendant l’arrêt du véhicule et par conséquent la décharge de celle-ci au cours d’un trajet. Cette particularité ajoute un degré de complexité pour ce qui est de la conception du système de gestion d’énergie. Dans cette thèse, nous proposons un modèle complet du véhicule dédié à la conception du contrôleur. Nous étudions ensuite la dépendance de la commande optimale des deux moteurs par rapport au profil de vitesse suivi au cours d’un trajet ainsi qu’à la quantité d’énergie électrique disponible au début d’un trajet. Cela nous amène à proposer une technique d’auto-apprentissage visant l’amélioration de la stratégie de gestion d’énergie en exploitant un certain nombre de données enregistrées sur les trajets antérieurs. La technique proposée permet l’adaptation de la stratégie de contrôle vis-à-vis du trajet en cours en se basant sur une pseudo-prédiction de la totalité du profil de vitesse. Nous évaluerons les performances de la technique proposée en matière de consommation de carburant en la comparant avec une stratégie optimale bénéficiant de la connaissance exacte du profil de vitesse ainsi qu’avec une stratégie de base utilisée couramment dans l’industrie. // Abstract : Since the end of the XXth century, the increase in crude oil price and the environmental concerns lead the automotive industry to develop technologies that can improve fuel savings and decrease greenhouse gases emissions. Among these technologies, the hybrid electric vehicles stand as a reliable and efficient solution. By combining an electrical motor and an internal combustion engine, these vehicles can bring a noticeable improvement in terms of fuel consumption without sacrificing the vehicle autonomy. The two motors and the two energy storage systems require a control unit, called energy management system, which is responsible for the command decision of both motors. The vehicle performances in terms of fuel consumption greatly depend on this control unit. The plug-in hybrid electric vehicles are a more recent technology compared to their non plug-in counterparts. They have an extra internal battery charger that allows the battery to be charged during OFF state, implying a possible discharge during a trip. This particularity adds complexity when it comes to the design of the energy management system. In this thesis, a complete vehicle model is proposed and used for the design of the controller. A study is then carried out to show the dependence between the optimal control of the motors and the speed profile followed during a trip as well as the available electrical energy at the beginning of a trip. According to this study, a self-learning optimization technique that aims at improving the energy management strategy by exploiting some driving data recorded on previous trips is proposed. The technique allows the adaptation of the control strategy to the current trip based on a pseudo-prediction of the total speed profile. Fuel consumption performances for the proposed technique will be evaluated by comparing it with an optimal control strategy that benefits from the exact a priori knowledge of the speed profile as well as a basic strategy commonly used in industry.
|
7 |
Conception de commande tolérante aux défauts pour les systèmes multi-agents : application au vol en formation d'une flotte de véhicules autonomes aériens / FDI/FT Methods Design to multi-agent systems : Application to formation control of a fleet of autonomous aerial vehiclesBelkadi, Adel 12 October 2017 (has links)
Ces dernières années, l’émergence des nouvelles technologies tels que la miniaturisation des composants, les dispositifs de communication sans fils, l’augmentation de la taille de stockage et les capacités de calcul, a permis la conception de systèmes multi-agents coopératifs de plus en plus complexes. L’un des plus grands axes de recherche dans cette thématique concerne la commande en formation de flottes de véhicules autonomes. Un grand nombre d’applications et de missions, civiles et militaires, telles que l’exploration, la surveillance, et la maintenance, ont alors été développées et réalisées dans des milieux variés (terre, air, eau). Durant l’exécution de ces tâches, les véhicules doivent interagir avec leur environnement et entre eux pour se coordonner. Les outils de communication disponibles disposent souvent d’une portée limitée. La préservation de la connexion au sein du groupe devient alors un des objectifs à satisfaire pour que la tâche puisse être accomplie avec succès. Une des possibilités pour garantir cette contrainte est le déplacement en formation permettant de préserver les distances et la structure géométrique du groupe. Il est toutefois nécessaire de disposer d’outils et de méthodes d’analyse et de commande de ces types de systèmes afin d’exploiter au maximum leurs potentiels. Cette thèse s’inscrit dans cette direction de recherche en présentant une synthèse et une analyse des systèmes dynamiques multi-agents et plus particulièrement la commande en formation de véhicules autonomes. Les lois de commande développées dans la littérature pour la commande en formation permettent d’accomplir un grand nombre de missions avec un niveau de performance élevé. Toutefois, si un défaut/défaillant apparaît dans la formation, ces lois de commandes peuvent s’avérer très limitées, engendrant un comportement instable du système. Le développement de commandes tolérantes aux défauts devient alors primordial pour maintenir les performances de commande en présence de défauts. Cette problématique sera traitée dans ce mémoire de thèse et concernera le développement et la conception de commandes en formation tolérantes au défaut dévolu à une flotte de véhicules autonomes suivant différente configuration/structuration / In recent years, the emergence of new technologies such as miniaturization of components, wireless communication devices, increased storage size and computing capabilities have allowed the design of increasingly complex cooperative multi-agent systems. One of the main research axes in this topic concerns the formation control of fleets of autonomous vehicles. Many applications and missions, civilian and military, such as exploration, surveillance, and maintenance, were developed and carried out in various environments. During the execution of these tasks, the vehicles must interact with their environment and among themselves to coordinate. The available communication tools are often limited in scope. The preservation of the connection within the group then becomes one of the objectives to be satisfied in order to carry out the task successfully. One of the possibilities to guarantee this constraint is the training displacement, which makes it possible to preserve the distances and the geometrical structure of the group. However, it is necessary to have tools and methods for analyzing and controlling these types of systems in order to make the most of their potential. This thesis is part of this research direction by presenting a synthesis and analysis of multi-agent dynamical systems and more particularly the formation control of autonomous vehicles. The control laws developed in the literature for formation control allow to carry out a large number of missions with a high level of performance. However, if a fault/failure occurs in the training, these control laws can be very limited, resulting in unstable system behavior. The development of fault tolerant controls becomes paramount to maintaining control performance in the presence of faults. This problem will be dealt with in more detail in this thesis and will concern the development and design of Fault tolerant controls devolved to a fleet of autonomous vehicles according to different configuration/structuring
|
8 |
Isomorphisme Inexact de Graphes par Optimisation ÉvolutionnaireBärecke, Thomas 22 October 2009 (has links) (PDF)
L'isomorphisme inexact de graphes est un problème crucial pour la définition d'une distance entre graphes, préalable nécessaire à une multitude d'applications allant de l'analyse d'images à des applications biomédicales en passant par la reconnaissance optique de caractères. Ce problème est encore plus complexe que celui de l'isomorphisme exact. Alors que ce dernier est un problème de décision de complexité au moins de classe P et qui ne s'applique qu'à des graphes exactement identiques, l'isomorphisme inexact est un problème combinatoire de complexité de classe NP qui permet de prendre en compte des perturbations dues au bruit, qui apparaissent fréquemment dans les applications réelles. Dans ce cadre, nous choisissons d'étudier une solution basée sur les algorithmes génétiques pouvant être appliquée à l'isomorphisme exact et inexact. Nous proposons des opérateurs de croisement généraux pour tout problème représenté par un codage de permutation, ainsi que des opérateurs spécifiques à l'isomorphisme de graphes qui exploitent une heuristique gloutonne. Nous réalisons une étude exhaustive pour comparer ces opérateurs avec les opérateurs existants, soulignant leurs propriétés, avantages et inconvénients respectifs. Nous étudions par ailleurs plusieurs pistes d'amélioration de l'algorithme, en théorie ou en pratique, considérant successivement les objectifs d'accélération de l'exécution, d'augmentation de la précision et de garantie de résultat optimal. Nous proposons pour cela de combiner l'approche proposée avec d'autres techniques telles que des heuristiques générales comme la recherche locale, des heuristiques dédiées comme l'algorithme A*, et des outils pratiques comme la parallélisation. Ces travaux conduisent à la définition d'une méthode générique pour la résolution de tous les problèmes d'isomorphismes de graphes, qu'il s'agisse d'isomorphismes exact ou inexact, d'isomorphismes de graphes de même taille ou d'isomorphismes de sous-graphes. Nous illustrons enfin la validité de cette solution générale par trois applications concrètes issues de domaines différents, la recherche d'images et la chimie, qui présentent chacune des caractéristiques spécifiques, utilisant des graphes attribués ou non, soumis aux perturbations plutôt structurelles ou au niveau d'attributs.
|
9 |
Algorithmes pour les problèmes de tournées à la demandeZhao, Xiagang 06 May 2011 (has links) (PDF)
Dans le cadre de cette thèse, nous nous intéressons au problème du transport à la demande. Nous proposons des heuristiques pour résoudre ce problème de manière rapide et efficace. Dans cette thèse, nous traitons trois problèmes : le premier est le Dial-a-ride (DARP standard). Pour ce problème, nous proposons des heuristiques basées sur la technique d'insertion et une technique de propagation de contrainte. Nous proposons aussi la procédure SPLIT et des opérateurs classiques de recherche locale pour résoudre ce problème. Le second est le DARP multicritères pour laquelle nous proposons un schéma de type ELS. Le troisième est un problème de transport à la demande avec contraintes financières (DARPF), qui est une extension de DARP. Nous résolvons ce problème grâce à une heuristique d'insertion et une technique de propagation de contraintes. La fonction objectif détermine les caractéristiques des tournées. Des résultats expérimentaux montrent que nos (méta-) heuristiques donnent des résultats plus favorables aux clients (meilleure qualité de service)
|
10 |
Amélioration des métaheuristiques d'optimisation à l'aide de l'analyse de sensibilité / Improvement of optimization metaheuristics with sensitivity analysisLoubiere, Peio 21 November 2016 (has links)
L'optimisation difficile représente une classe de problèmes dont la résolution ne peut être obtenue par une méthode exacte en un temps polynomial.Trouver une solution en un temps raisonnable oblige à trouver un compromis quant à son exactitude.Les métaheuristiques sont une classe d'algorithmes permettant de résoudre de tels problèmes, de manière générique et efficiente (i.e. trouver une solution satisfaisante selon des critères définis: temps, erreur, etc.).Le premier chapitre de cette thèse est notamment consacré à la description de cette problématique et à l'étude détaillée de deux familles de métaheuristiques à population, les algorithmes évolutionnaires et les algorithmes d'intelligence en essaim.Afin de proposer une approche innovante dans le domaine des métaheuristiques, ce premier chapitre présente également la notion d'analyse de sensibilité.L'analyse de sensibilité permet d'évaluer l'influence des paramètres d'une fonction sur son résultat.Son étude caractérise globalement le comportement de la fonction à optimiser (linéarité, influence, corrélation, etc.) sur son espace de recherche.L'incorporation d'une méthode d'analyse de sensibilité au sein d'une métaheuristique permet d'orienter sa recherche le long des dimensions les plus prometteuses.Deux algorithmes réunissant ces notions sont proposés aux deuxième et troisième chapitres.Pour le premier algorithme, ABC-Morris, la méthode de Morris est introduite dans la métaheuristique de colonie d'abeilles artificielles (ABC).Cette inclusion est dédiée, les méthodes reposant sur deux équations similaires.Afin de généraliser l'approche, une nouvelle méthode, NN-LCC, est ensuite développée et son intégration générique est illustrée sur deux métaheuristiques, ABC avec taux de modification et évolution différentielle.L'efficacité des approches proposées est testée sur le jeu de données de la conférence CEC 2013. L'étude se réalise en deux parties: une analyse classique de la méthode vis-à-vis de plusieurs algorithmes de la littérature, puis vis-à-vis de l'algorithme d'origine en désactivant un ensemble de dimensions, provoquant une forte disparité des influences / Hard optimization stands for a class of problems which solutions cannot be found by an exact method, with a polynomial complexity.Finding the solution in an acceptable time requires compromises about its accuracy.Metaheuristics are high-level algorithms that solve these kind of problems. They are generic and efficient (i.e. they find an acceptable solution according to defined criteria such as time, error, etc.).The first chapter of this thesis is partially dedicated to the state-of-the-art of these issues, especially the study of two families of population based metaheuristics: evolutionnary algorithms and swarm intelligence based algorithms.In order to propose an innovative approach in metaheuristics research field, sensitivity analysis is presented in a second part of this chapter.Sensitivity analysis aims at evaluating arameters influence on a function response. Its study characterises globally a objective function behavior (linearity, non linearity, influence, etc.), over its search space.Including a sensitivity analysis method in a metaheuristic enhances its seach capabilities along most promising dimensions.Two algorithms, binding these two concepts, are proposed in second and third parts.In the first one, ABC-Morris, Morris method is included in artificial bee colony algorithm.This encapsulation is dedicated because of the similarity of their bare bone equations, With the aim of generalizing the approach, a new method is developped and its generic integration is illustrated on two metaheuristics.The efficiency of the two methods is tested on the CEC 2013 conference benchmark. The study contains two steps: an usual performance analysis of the method, on this benchmark, regarding several state-of-the-art algorithms and the comparison with its original version when influences are uneven deactivating a subset of dimensions
|
Page generated in 0.0465 seconds