Les systèmes de vélos en libre-service ont connu ces dernières années un développement sans précédent. Bien que les premières tentatives de mise en place remontent aux années 60, l'arrivée de technologies permettant un suivi des différents véhicules mis à la disposition du grand public et de l'état des bornes de stationnement en temps réel a rendu ces systèmes plus attractifs. Plus de 200 villes disposent de tels systèmes et cette tendance se poursuit avec l'entrée en fonctionnement du système de New York prévue pour mars 2013. La fin de l'année 2011 a été marquée par l'arrivée d'un nouvel avatar de ce type de transport avec la mise en place d'Autolib à Paris. L'objectif de cette thèse est de proposer des algorithmes d'aide à la décision pour l'optimisation de réseaux de transport en libre-service. L'exploitation de ces systèmes, qui fleurissent actuellement un peu partout dans le monde, pose en effet de nombreux problèmes, l'un des plus cruciaux étant celui de la régulation. Cette dernière a pour objectif de maintenir dans chaque station un nombre de vélos ni trop faible, ni trop élevé, afin de satisfaire au mieux la demande. Cette régulation se fait souvent par le biais de camions qui effectuent des tournées sur le réseau. Il apparaît rapidement que la question d'une régulation optimale à l'aide d'une flotte fixée de camions est une question difficile. La thèse est divisée en deux parties. Dans la première partie, le cas “statique” est considéré. Les déplacements de véhicules dus aux usagers sont négligés. Cela traduit la situation la nuit ou lorsque le système est fermé à la location. L'opérateur doit redistribuer les véhicules afin que ceux-ci soient disposés selon une répartition définie. Les problèmes de rééquilibrage avec un ou plusieurs camions sont traités. Pour chacun des deux cas, un algorithme est proposé et utilisé pour résoudre des instances de tailles variées. La seconde partie traite du cas “dynamique” dans lequel les utilisateurs interagissent avec le système. Afin d'étudier ce système complexe, un simulateur a été développé. Il est utilisé pour comparer différentes stratégies de redistribution des véhicules. Certaines utilisent des camions se déplaçant dans la ville pendant la journée. D'autres tentent d'organiser une régulation intrinsèque du système par le biais d'une politique d'incitation : des prix mis à jour régulièrement encouragent les usagers à rendre leur véhicule dans certaines stations. Enfin, si on choisit de ne pas utiliser de camion durant la journée, la question de la détermination du nombre optimal de véhicules à disposer à chaque station se pose. Deux méthodes de recherche locale visant à minimiser le temps total perdu par les usagers sont présentées. Les résultats obtenus peuvent servir pour la définition des répartitions cibles de la première partie. Durant ma thèse, j'ai pu participer à deux challenges EURO/ROADEF, celui de 2010 proposé par EDF et celui de 2012 proposé par Google. Dans les deux cas, mon équipe a atteint les phases finales. Lors de l'édition de 2010, notre méthode est arrivée quatrième et a donné lieu à une publication. En 2012, notre méthode est arrivée dix-huitième sur tous les participants. Les travaux menés dans ces cadres sont ajoutés en annexe / Bikes sharing systems have known a growing success all over the world. Several attempts have been made since the 1960s. The latest developments in ICT have enabled the system to become efficient. People can obtain real-time information about the position of the vehicles. More than 200 cities have already introduced the system and this trend keeps on with the launching of the NYC system in spring 2013. A new avatar of these means of transportation has arrived with the introduction of Autolib in Paris end of 2011.The objective of this thesis is to propose algorithms that may help to improve this system efficiency. Indeed, operating these systems induces several issues, one of which is the regulation problem. Regulation should ensures users that a right number of vehicles are present at any station anytime in order to fulfill the demand for both vehicles and parking racks. This regulation is often executed thanks to trucks that are travelling the city. This regulation issue is crucial since empty and full stations increase users' dissatisfaction. Finding the optimal strategy for regulating a network appears to be a difficult question. This thesis is divided into two parts. The first one deals with the “static” case. In this part, users' impact on the network is neglected. This is the case at night or when the system is closed. The operator faces a given repartition of the vehicles. He wants the repartition to match a target one that is known a priori. The one-truck and multiple-truck balancing problems are addressed in this thesis. For each one, an algorithm is proposed and tested on several instances. To deal with the “dynamic” case in which users interact with the system, a simulator has been developed. It is used to compare several strategies and to monitor redistribution by using trucks. Strategies not using trucks, but incentive policies are also tested: regularly updated prices are attached to stations to deter users from parking their vehicle at specified stations. At last, the question to find the best initial inventory is also addressed. It corresponds to the case when no truck are used within the day. Two local searches are presented and both aim at minimizing the total time lost by users in the system. The results obtained can be used as inputs for the target repartitions used in the first part. During my thesis, I participated to two EURO-ROADEF challenges, the 2010 edition proposed by EDF and the 2012 one by Google. In both case, my team reached the final phase. In 2010, our method was ranked fourth over all the participants and led to the publication of an article. In 2012, we ranked eighteenth over all the participants. Both works are added in the appendix

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2015-2016 / Nous abordons deux problèmes différents et complémentaires : le problème du chemin couvrant (ou CPP) et le problème du chemin de recherche optimal (ou OSP). Le CPP est un défi important en robotique mobile alors que l’OSP est un classique de la théorie de la recherche. Nous effectuons d’abord une revue de littérature qui souligne leurs différences et leurs similitudes du point de vue d’une opération de recherche. Le CPP et l’OSP sont comparés par rapport aux données connues sur la position d’un objet de recherche. Ensuite, nous formalisons une généralisation du problème CPP aux détections imparfaites et distantes nommée CPPIED. Nous présentons un algorithme heuristique efficace qui utilise à la fois la programmation dynamique et une réduction au problème du voyageur de commerce (TSP). Nous appliquons l’algorithme dans le contexte des opérations de déminage sous-marin sur des cartes qui contiennent plus de 21 000 cellules. Nous poursuivons par l’étude d’un nouveau modèle de programmation par contraintes (CP) pour l’OSP pour lequel nous proposons une amélioration de la définition de la fonction objectif. Cette nouvelle définition permet un filtrage plus fort des variables de probabilité prodiguant ainsi une amélioration des performances du modèle. Nous proposons, pour l’OSP, une nouvelle heuristique nommée « détection totale » (ou TD). Les résultats expérimentaux démontrent que notre modèle, utilisé avec l’heuristique TD, est compétitif avec des algorithmes de séparation et d’évaluation (ou branch-and-bound) spécifiques au problème de l’OSP (l’approche CP étant plus générale). Cette dernière observation supporte notre assertion que la CP est un bon outil pour résoudre des problèmes de la théorie de la recherche. Finalement, nous proposons la contrainte de transition de Markov (Mtc) en tant que nouvel outil de modélisation pour simplifier l’implémentation de modèles basés sur les chaînes de Markov. Nous démontrons, tant empiriquement que formellement, que l’arithmétique des intervalles est insuffisante pour l’atteinte de la cohérence de bornes, c’est-à-dire, pour filtrer les variables de probabilité de cette contrainte. Or, l’arithmétique des intervalles est l’outil utilisé par les solveurs CP pour filtrer une Mtc lorsque celle-ci est décomposée en contraintes arithmétiques individuelles. Nous proposons donc un algorithme basé sur la programmation linéaire qui atteint la cohérence de bornes. Du fait que la programmation linéaire est coûteuse en temps de calcul pour un solveur CP lorsqu’utilisée à chaque noeud de l’arbre de recherche, nous proposons aussi une approche intermédiaire basée sur le problème du sac à dos fractionnel. L’utilisation des Mtcs est illustrée sur l’OSP. / We tackle two different and complementary problems: the coverage path planning (CPP) and the optimal search path (OSP). The CPP is a main challenge in mobile robotics. The OSP is a classic from search theory. We first present a review of both problems that highlights their differences and their similarities from the point of view of search (coverage) operations. Both problems are positioned on the continuum of the a priori knowledge on the whereabouts of a search object. We then formalize an extension of the CPP we call the CPP with imperfect extended detections (CPPIED). We present a novel and powerful heuristic algorithm that uses dynamic programming and a traveling salesman (TSP) reduction. We apply the method to underwater minesweeping operations on maps with more than 21 thousand cells. We then study a novel constraint programming (CP) model to solve the OSP.We first improve on using the classical objective function found in the OSP definition. Our novel objective function, involving a single modification of the operators used to compute the probability of success of a search plan, leads to a stronger filtering of the probability variables of the model. Then, we propose a novel heuristic for the OSP: the total detection (TD) heuristic. Experiments show that our model, along with the proposed heuristic, is competitive with problem-specific branch-and-bounds supporting the claim that CP is a good technique to solve search theory problems. We finally propose the Markov transition constraint (Mtc) as a novel modeling tool in CP to simplify the implementation of models based on Markov chains. We prove, both empirically and theoretically, that interval arithmetic is insufficient to filter the probability variables of a single Mtc, i.e., to enforce bounds consistency on these variables. Interval arithmetic is the only available tool to filter an Mtc when it is decomposed into individual arithmetic constraints. We thus propose an algorithm based on linear programming which is proved to enforce bounds consistency. Since linear programming is computationally expensive to use at each node of the search tree of a CP solver, we propose an in-between solution based on a fractional knapsack filtering. The Mtc global constraint usage is illustrated on a CP model of the OSP.

La présente étude porte sur l'optimisation d'un générateur thermoélectrique inclus dans un échangeur de chaleur à écoulements croisés. Un générateur thermoélectrique est un appareil constitué de semi-conducteurs qui génère de l'électricité lorsqu'il est traversé par un flux de chaleur, de là son implementation dans un échangeur de chaleur. L'objectif principal sera d'utiliser un outil d'optimisation, en l'occurrence un algorithme génétique, afin de déterminer les designs optimaux qui satisferont un ensemble de critères. Préalablement aux optimisations, un modèle complet a d'abord dû être créé avec l'aide du logiciel Matlab. Il s'agit de modéliser numériquement l'échangeur de chaleur ainsi que le générateur thermoélectrique qui en est partie intégrante. La modélisation considère plusieurs facteurs dont le nombre d'étages de l'échangeur, le courant traversant les modules thermoélectriques, le nombre de modules thermoélectriques et la géométrie de l'échangeur. Le code est ensuite validé numériquement avec des exemples théoriques ou des résultats issus de la littérature. Une fois la modélisation effectuée, il faut définir les objectifs à minimiser ou maximiser. Il sera utile de maximiser la puissance électrique produite par le système, minimiser le volume de l'échangeur, minimiser la puissance de pompage requise, minimiser le nombre de modules thermoélectriques requis ainsi que maximiser les profits générés par le système sur une période de temps donnée. Initialement, nous ne considérerons que la maximisation de la puissance électrique fournie par le système selon différentes contraintes physiques (différence de température ou débit capacitif fixés). Nous optimiserons aussi les connections électriques dans le système pour constater si les designs suggérés par l'algorithme d'optimisation sont réalisables. Suite à cela, nous étudierons des cas multi-objectifs. Plusieurs objectifs seront considérés simultanément durant l'optimisation et nous analyserons les fronts de Pareto (ensemble des solutions possibles) selon les différents objectifs qui auront été considérés. Finalement, une optimisation thermoéconomique sera réalisée sur le système afin de valider si ce dernier est rentable ou sinon les correctifs qu'il faudrait y apporter pour rendre le tout profitable.

Face à la complexité qui caractérise les problèmes d'optimisation de grande taille l'exploration complète de l'espace des solutions devient rapidement un objectif inaccessible. En effet, à mesure que la taille des problèmes augmente, des méthodes de solution de plus en plus sophistiquées sont exigées afin d'assurer un certain niveau d 'efficacité. Ceci a amené une grande partie de la communauté scientifique vers le développement d'outils spécifiques pour la résolution de problèmes de grande taille tels que les méthodes hybrides. Cependant, malgré les efforts consentis dans le développement d'approches hybrides, la majorité des travaux se sont concentrés sur l'adaptation de deux ou plusieurs méthodes spécifiques, en compensant les points faibles des unes par les points forts des autres ou bien en les adaptant afin de collaborer ensemble. Au meilleur de notre connaissance, aucun travail à date n'à été effectué pour développer un cadre conceptuel pour la résolution efficace de problèmes d'optimisation de grande taille, qui soit à la fois flexible, basé sur l'échange d'information et indépendant des méthodes qui le composent. L'objectif de cette thèse est d'explorer cette avenue de recherche en proposant un cadre conceptuel pour les méthodes hybrides, intitulé la recherche itérative de l'espace restreint, ±Iterative Restricted Space Search (IRSS)>>, dont, la principale idée est la définition et l'exploration successives de régions restreintes de l'espace de solutions. Ces régions, qui contiennent de bonnes solutions et qui sont assez petites pour être complètement explorées, sont appelées espaces restreints "Restricted Spaces (RS)". Ainsi, l'IRSS est une approche de solution générique, basée sur l'interaction de deux phases algorithmiques ayant des objectifs complémentaires. La première phase consiste à identifier une région restreinte intéressante et la deuxième phase consiste à l'explorer. Le schéma hybride de l'approche de solution permet d'alterner entre les deux phases pour un nombre fixe d'itérations ou jusqu'à l'atteinte d'une certaine limite de temps. Les concepts clés associées au développement de ce cadre conceptuel et leur validation seront introduits et validés graduellement dans cette thèse. Ils sont présentés de manière à permettre au lecteur de comprendre les problèmes que nous avons rencontrés en cours de développement et comment les solutions ont été conçues et implémentées. À cette fin, la thèse a été divisée en quatre parties. La première est consacrée à la synthèse de l'état de l'art dans le domaine de recherche sur les méthodes hybrides. Elle présente les principales approches hybrides développées et leurs applications. Une brève description des approches utilisant le concept de restriction d'espace est aussi présentée dans cette partie. La deuxième partie présente les concepts clés de ce cadre conceptuel. Il s'agit du processus d'identification des régions restreintes et des deux phases de recherche. Ces concepts sont mis en oeuvre dans un schéma hybride heuristique et méthode exacte. L'approche a été appliquée à un problème d'ordonnancement avec deux niveaux de décision, relié au contexte des pâtes et papier: "Pulp Production Scheduling Problem". La troisième partie a permit d'approfondir les concepts développés et ajuster les limitations identifiées dans la deuxième partie, en proposant une recherche itérative appliquée pour l'exploration de RS de grande taille et une structure en arbre binaire pour l'exploration de plusieurs RS. Cette structure a l'avantage d'éviter l'exploration d 'un espace déjà exploré précédemment tout en assurant une diversification naturelle à la méthode. Cette extension de la méthode a été testée sur un problème de localisation et d'allocation en utilisant un schéma d'hybridation heuristique-exact de manière itérative. La quatrième partie généralise les concepts préalablement développés et conçoit un cadre général qui est flexible, indépendant des méthodes utilisées et basé sur un échange d'informations entre les phases. Ce cadre a l'avantage d'être général et pourrait être appliqué à une large gamme de problèmes.

Ce mémoire vise à définir et quantifier les émissions de gaz à effet de serre (GES) émises par le réseau de transport logistique de notre partenaire industriel. En parallèle, nous détaillons plusieurs scénarios d'optimisation possibles afin de réduire son empreinte carbone. Cela se fait par optimisation mathématique, par laquelle les déplacements entre l'entreprise et ses différents partenaires, de l'approvisionnement à la livraison au client final, pour différents types de produits et différents transporteurs avec différents types de véhicules sont considérés. Plus précisément, notre objectif est de décrire et de représenter la différence entre la situation actuelle et la solution obtenue en optimisant le réseau en termes de distance parcourue, de GES émis, de consolidation des livraisons ainsi que de production et de stocks nécessaires. Suite à l'analyse quantitative et qualitative des résultats, nous sommes en mesure de fournir de nombreuses suggestions d'amélioration à l'entreprise en ce qui concerne la gestion de son transport interne et externe. Un certain nombre d'indicateurs de performance clés sont également évalués, les plus importants étant l'inventaire et le nombre de voyages effectués. Ceux-ci sont considérablement réduits dans notre scénario optimisé. Pour garantir des résultats commerciaux optimaux, nous proposons un modèle de résolution en deux étapes comprenant une modélisation mathématique du problème suivie d'une amélioration manuelle de la solution. De plus, les méthodes de calcul utilisées pour mesurer les émissions de GES sont basées sur la distance parcourue ainsi que sur la capacité utilisée de chaque véhicule, attribuant ainsi l’utilisation du véhicule à l’entreprise (tandis que la capacité restante est utilisée par d’autres compagnies lorsque le transporteur consolide ses opérations). Cela nous permet d'estimer les émissions générées même lorsque la construction des routes de différents transporteurs n'est pas exactement connue. La coordination, la consolidation et la synchronisation des différents voyages liés aux activités de l’entreprise nous ont permis de réduire les émissions de GES jusqu’à 23%, soit 3,438.64 tonnes de CO2e économisées sur une base annuelle, soit 2,733,354 km. De plus, nos observations des résultats ont mis en évidence une multitude de recommandations concernant l’utilisation des transporteurs, la réduction des stocks et le contrôle des flux de transport au sein de l’entreprise. / This thesis aims to define and quantify the greenhouse gas (GHG) emission emitted by our industrial partner’s logistics transportation network. Next to that, we detail several possible optimization scenarios in order to reduce its carbon footprint. This is done via mathematical optimization, in which the trips between the company and its various partners, from supply to delivery to the end customer, for different types of products and different carriers with different types of vehicles are considered. More specifically, our purpose is to describe and represent the difference between the current situation and the solution obtained by optimizing the network in terms of distance traveled, GHG emitted, consolidation of deliveries as well as production and stock needed. Following the quantitative and qualitative analysis of the results, we are able to provide numerous suggestions for improvements to the company with regard to the management of its internal and external transport. A number of key performance indicators are also evaluated, most importantly inventory and the number of trips. These are drastically reduced in our optimized scenario. To ensure optimal business results, we propose a two-step resolution model that includes mathematical modeling of the problem followed by manual improvement of the solution. In addition, the calculation methods used to measure GHGs emitted are based on the distance traveled as well as the capacity used of each vehicle, thus assigning vehicle usage to the company (while the remaining vehicle space is to be used by other companies when the carrier consolidates its operation). This allows us to estimate the emissions generated even when the construction of routes of different carriers is not exactly known. The coordination, consolidation and synchronization of the various trips related to the company’s activities allowed us to reduce the GHGs emitted by up to 23%, which translates into 3,438.64 tons of CO2e saved on a yearly basis, or 2,733,354 km. In addition, our observations of the results highlighted a multitude of recommendations regarding the use of carriers, the reduction of inventory and the control of transport flows within the company.

Lorsque le temps est manquant, la simulation-optimisation est une méthode très utilisée pour déterminer le « meilleur » scénario possible. En contexte manufacturier, on peut vouloir déterminer les paramètres de production qui vont maximiser la productivité d'une ligne de production. Le nombre de scénarios possibles (représentant différentes configurations possibles de la ligne) étant souvent très grand, tous les scénarios ne peuvent être simulés. La simulation-optimisation permet de trouver un « bon » scénario, i.e. le scénario donnant les meilleurs résultats par rapport à des critères définis (ici, la productivité) dans un contexte où le temps ne permet pas de simuler toutes les possibilités. Dans le cas où l'on cherche à déterminer la productivité combinée de plusieurs lignes de production, on cherche alors plusieurs scénarios qui, conjointement, vont maximiser ce critère, i.e. la « meilleure combinaison » de scénarios. Or, lorsqu'on recherche le meilleur ensemble de scénarios et non le meilleur scénario, les méthodes classiques s'appliquent difficilement. À notre connaissance, le problème de la recherche de la meilleure combinaison de scénarios n'a pas été introduit formellement dans la littérature. Cette thèse propose une définition formelle de ce problème et un cadre pour le résoudre. Le cadre proposé utilise la simulation dans le but d'évaluer des scénarios. L'optimisation est ensuite utilisée pour déterminer la meilleure combinaison de scénarios. Le nombre de scénarios à simuler est tel qu'il n'est pas possible de tous les évaluer. Nous proposons aussi d'utiliser certaines méthodes de recherche dans les arbres, issues de la programmation par contraintes pour déterminer quels scénarios devraient être évalués en premier. La pertinence du cadre est démontrée par son application à travers plusieurs problèmes industriels. La première application s'attarde à résoudre des problèmes de planification tactique liés à l'industrie du bois d'œuvre nord-américaine. Cette dernière fabrique presque exclusivement des produits de commodité (c'est-à-dire des produits aux dimensions et propriétés standards destinés à la construction). Il arrive que certains clients veuillent aussi des produits avec des caractéristiques spécifiques. Le contexte manufacturier actuel ne permet pas au scieur de connaître le panier de produits global qui découlera de l'introduction d'un nouveau produit. En effet, du fait de la divergence des flux et de la co-production associées à la transformation de la matière première en scierie, l'ajout d'un autre produit à fabriquer entraîne des répercussions sur l'ensemble du panier de produits. Nous proposons donc d'utiliser le cadre pour intégrer à la planification tactique la demande pour des produits spécifiques jamais fabriqués auparavant. Le cadre utilise un simulateur de débitage de billes couplé à un modèle de planification pour réaliser un plan. Ce dernier permet au décideur d'évaluer quelles demandes pour des produits sur mesure devraient être acceptées, quoi produire et quand, ainsi que les paramètres de l'équipement à utiliser et la matière première à acheter/consommer à chaque période. La seconde application du cadre présentée dans cette thèse a pour but d'améliorer les décisions prises par un système de découpe de bois de plancher soumis à de fortes contraintes de production. La découpe d'un ensemble d'images de planches provenant de productions passées est simulée pour différentes configurations du système. Une base de données caractérisant la production attendue pour chaque configuration est ainsi générée. Le simulateur est le système réel utilisé « hors-ligne ». À partir des informations obtenues, nous établissons ensuite un horaire de production en utilisant un modèle d'optimisation linéaire maximisant la valeur attendue de la production. L'horaire permet de définir comment configurer le système de découpe tout au long de la production. Le cadre peut aussi être appliqué pour résoudre d'autres problèmes du même type comme, par exemple, pour la conception d'usines en réseau dans une chaîne logistique. Enfin, pour illustrer et vérifier la pertinence de l'utilisation de certaines méthodes de recherche dans les arbres pour déterminer l'ordre d'évaluation des scénarios, la démarche est appliquée au problème de découpe de bois de plancher mentionné préalablement. L'étude réalisée montre que les méthodes issues de la programmation par contraintes pourraient se révéler efficaces pour résoudre ce type de problèmes. En effet, la méthode Limited Discrepancy Search (LDS) obtient des résultats très semblables à une heuristique spécialement élaborée pour le cas étudié. Or LDS est une méthode générique et pourrait s'appliquer à d'autres cas.

L'objectif de nos travaux est de faire la synthèse de mouvements plausibles et réalistes de marche humaine dans divers environnements de synthèse. Bien que la solution proposée puisse également s'appliquer aux autres mouvements de locomotion humains ou animaux, nos travaux traitent uniquement du problème de la marche humaine. Afin de résoudre ce problème, nous avons développé une approche permettant de générer une multitude de variations d'une animation issue de capture de mouvement. Ces variations sont obtenues en adaptant le mouvement original à un environnement de synthèse dont les paramètres, tels que l'inclinaison du sol ou la courbure de la trajectoire, sont variés. Nous sommes donc en mesure de produire un mouvement de marche courbe ou de marche sur un plan incliné à partir d'un mouvement de marche en ligne droite sur un sol horizontal, ce que nous qualifions d'extrapolation de mouvement. Une animation initiale, obtenue par capture de mouvement, est essentielle à la solution proposée. Adapter ce mouvement à un nouvel environnement de synthèse consiste essentiellement à ajuster les caractéristiques globales du mouvement, telles que l'orientation du personnage et sa vitesse de déplacement. Ce faisant, nous sommes en mesure de conserver les détails plus fins du mouvement qui lui confèrent son aspect humain, tels que le mouvement des bras ou la vitesse avec laquelle un pied entre en contact avec le sol. En conservant les détails fins du mouvement d'origine, la solution proposée assure un certain réalisme dans les mouvements synthétisés. Dans la solution proposée, l'adaptation du mouvement initial est basée sur le paradigme des contraintes spatio-temporelles, où la synthèse du mouvement est posée comme un problème d'optimisation numérique. En plus d'être une formulation élégante du problème, ce paradigme est tout indiqué pour faire la synthèse de mouvements physiquement plausibles. En combinant ce paradigme avec l'utilisation d'une animation initiale issue de capture de mouvement, nous sommes en mesure de produire des animations de mouvements humains plausibles et réalistes. En pratique, le problème d'optimisation sous-tendu par l'adaptation d'un mouvement par contraintes spatio-temporelles est fortement non linéaire et opère dans un espace à très grande dimensionnalité. Cette complexité peut fortement ralentir le processus d'optimisation et aller jusqu'à en empêcher la convergence. La solution proposée fait donc appel à plusieurs mécanismes afin de réduire cette complexité. Notons qu'aucun de ces mécanismes ne vient compromettre la polyvalence de l'approche, en limitant la complexité du modèle biomécanique du personnage par exemple. Parmi ces mécanismes, deux sont des contributions originales : une technique d'estimation rapide des forces de réaction du sol et une approche d'optimisation incrémentale. Ces deux mécanismes visent à simplifier le processus d'optimisation en fournissant une solution initiale très proche de la solution optimale. La technique d'estimation des forces de réaction du sol sert à donner à ces paramètres une valeur initiale qui est relativement proche de leur valeur optimale, ce qui simplifie significativement la tâche d'optimisation subséquente. Cette technique consiste à trouver, pour les phases de support double, les forces de réaction du sol minimisant l'effort interne du personnage. Ce problème peut être exprimé comme une séquence de sous-problèmes de programmation quadratiques. Cette formulation est un aspect central de notre contribution et elle permet d'atteindre la solution très efficacement. L'approche d'optimisation incrémentale proposée s'inspire des méthodes de continuation. Le mouvement original est considéré comme une solution, un mouvement optimal, pour l'environnement de capture. L'environnement de synthèse est ensuite modifié graduellement, en augmentant l'inclinaison du sol par petits incréments par exemple. À chaque incrément, un nouveau mouvement optimal est trouvé en utilisant la solution de l'incrément précédent comme point de départ. On procède de la sorte jusqu'à l'obtention du mouvement désiré pour l'environnement de synthèse considéré. Si les incréments sont suffisamment petits, la différence entre deux problèmes d'optimisation consécutifs sera petite et il en sera de même pour leur optimum respectif.

La conception d'un microsystème de conversion d'énergie éolienne représente le cœur de cette étude. L'attention est dérivée vers le générateur sans balais à aimant permanent et auto-commutation, avec la configuration de rotor externe et des tensions électromotrices de forme trapézoïdale. L'objectif global de la thèse est représentée par la tentative de déterminer les paramètres optimaux de conception géométriques et électriques du générateur qui donne les plus faibles pertes totales dans le système, en fonctionnant sous un cycle du vent à long terme et ainsi en augmentant l'efficacité globale du système. En avance à l'optimisation, un modèle de simulation adapté doit être développé en termes de précision des résultats et du temps de simulation. Cela se fait dans la première partie de la thèse en déterminant le niveau de modélisation, ainsi que les variables de conception de chacun des composants du système. Comme l'optimisation fait appel à un algorithme pour le processus de conception, la réduction du temps de simulation a été étudiée dans la troisième et la quatrième partie de la thèse, en développant une méthode appropriée qui permet l'intégration et l'exploitation des données provenant du profil de vitesse du vent lors la détermination de la totalité des pertes de puissance du système. Par la suite, la méthode d'optimisation est présentée, même les résultats optimaux obtenus, ainsi que la comparaison de plusieurs paramètres d'entrée / sortie. Enfin, des essais expérimentaux sont également effectués sur un générateur de référence afin de vérifier la technique de commutation et de contrôle électronique. / The design of a micro-wind energy conversion system represents the core of this study. The attention is derived towards the brushless DC permanent magnet generator with outer rotor configuration and trapezoidal induced back-EMF voltages. The global aim of the thesis is represented by the attempt of determining the optimal geometrical and electrical design parameters of the BLDCPM generator that give the minimum total power losses in the system, over long-term wind speed cycle operation and thereby increasing the efficiency of the overall system. In advance to the optimization, an adapted simulation model needs to be developed in terms of results accuracy and simulation time. This is done in the first part of the thesis by determining the modeling level, as well as the design variables of each component of the system. As the optimization appeals to an algorithm for the design process, the reduction of the simulation time has been investigated in the third and fourth part of the thesis by developing a suitable method that allows the integration and exploitation of the available data from the wind-speed profile when determining the totality of the power losses in the system. Afterwards, the optimization methodology is presented along with the optimum results obtained, as well as comparison of several input/output parameters. Finally, experimental tests are also carried out on a reference BLDCPM machine prototype in order to verify its electronic commutation and control technique

Dans cette thèse, nous traitons essentiellement des problèmes de lot sizing en désassemblage avec une structure de produits à désassembler à deux niveaux sans composants communs. Nous traitons deux problèmes différents. Dans le premier problème, nous considérons un seul produit et la contribution porte sur le développement de deux modèles de programmation en nombres entiers. Le premier modèle est considéré sans ventes perdues où toutes les demandes doivent être satisfaites, et le deuxième est considéré avec ventes perdues où les demandes peuvent ne pas être satisfaites. Pour la résolution de ce problème, nous développons d’abord une approche analytique permettant de calculer les stocks de surplus (avant la résolution du problème) à la fin de l’horizon de planification. Ensuite, nous adaptons trois heuristiques connues pour leurs performances et largement utilisées dans le problème lot sizing en production « Silver Meal, Part Period Balancing et Least Unit Cost ». Dans le deuxième problème, nous considérons plusieurs produits avec contrainte de capacité et la contribution porte sur l’extension des deux modèles précédents. Le premier est également considéré sans ventes perdues et le deuxième avec ventes perdues. En ce qui concerne la résolution de ce problème et compte tenu de sa complexité, un algorithme génétique est d’abord proposé. Ensuite, afin d’améliorer cet algorithme, nous intégrons une heuristique Fix-and-Optimize dans ce dernier tout en proposant une approche hybride. Finalement, des tests sont effectués sur de nombreuses instances de la littérature afin de montrer l’efficacité et les limites de chaque approche de résolution / In this thesis, we mainly deal with lot sizing problems by disassembling with a structure of products to disassemble with two levels and without commonality components. We treat two different problems. In the first problem, we consider a single product whose contribution focuses on developing the two programming models integers. The first model is considered without lost sales where all demands must be satisfied, and the second one is considered with lost sales where demands may not be met. To solve this problem, we first develop an analytical approach to calculate the surplus stocks (before solving the problem) at the end of the planning horizon. Then we adapt three heuristics known for their performance and widely used in the lot sizing problem of production "Silver Meal, Part Period Balancing and Least Unit Cost". In the second problem, we consider a number of products with capacity constraint, and the contribution relates to the extension of the two previous models. The first is considered without lost sales and the second with lost sales. Regarding the resolution of this problem and given its complexity, a genetic algorithm is first proposed. Then, to improve this algorithm, we integrate a Fix-and-Optimize heuristic in the latter while offering a hybrid approach. Finally, various tests are performed on different literature instances to demonstrate the effectiveness and limitations of each solving approach

La Diagonalisation Conjointe par Congruence (DCC) d'un ensemble de matrices apparaît dans nombres de problèmes de traitement du signal, tels qu'en Analyse en Composantes Indépendantes (ACI). Les développements récents en ACI sous contrainte de non négativité de la matrice de mélange, nommée ACI semi-non négative, permettent de tirer profit d'une modélisation physique réaliste des phénomènes observés tels qu'en audio, en traitement d'image ou en ingénierie biomédicale. Par conséquent, durant cette thèse, l'objectif principal était non seulement de concevoir et développer des algorithmes d'ACI semi-non négative basés sur de nouvelles méthodes de DCC non négative où la matrice de passage recherchée est non négative, mais également d'illustrer leur intérêt dans le cadre d'applications pratiques de séparation de sources. Les algorithmes de DCC non négative proposés exploitent respectivement deux stratégies fondamentales d'optimisation. La première famille d'algorithmes comprend cinq méthodes semi-algébriques, reposant sur la méthode de Jacobi. Cette famille prend en compte la non négativité par un changement de variable carré, permettant ainsi de se ramener à un problème d'optimisation sans contrainte. L'idée générale de la méthode de Jacobi est de i) factoriser la matrice recherchée comme un produit de matrices élémentaires, chacune n'étant définie que par un seul paramètre, puis ii) d'estimer ces matrices élémentaires l'une après l'autre dans un ordre spécifique. La deuxième famille compte un seul algorithme, qui utilise la méthode des directions alternées. Un tel algorithme est obtenu en minimisant successivement le Lagrangien augmenté par rapport aux variables et aux multiplicateurs. Les résultats expérimentaux sur les matrices simulées montrent un gain en performance des algorithmes proposés par comparaison aux méthodes DCC classiques, qui n'exploitent pas la contrainte de non négativité. Il semble que nos méthodes peuvent fournir une meilleure précision d'estimation en particulier dans des contextes difficiles, par exemple, pour de faibles valeurs de rapport signal sur bruit, pour un petit nombre de matrices à diagonaliser et pour des niveaux élevés de cohérence de la matrice de passage. Nous avons ensuite montré l'intérêt de nos approches pour la résolution de problèmes pratiques de séparation aveugle de sources. Pour n'en citer que quelques-uns, nous sommes intéressés à i) l'analyse de composés chimiques en spectroscopie par résonance magnétique, ii) l'identification des profils spectraux des harmoniques (par exemple, de notes de piano) d'un morceau de musique mono-canal par décomposition du spectrogramme, iii) l'élimination partielle du texte se trouvant au verso d'une feuille de papier fin. Ces applications démontrent la validité et l'intérêt de nos algorithmes en comparaison des méthodes classique de séparation aveugle de source. / The Joint Diagonalization of a set of matrices by Congruence (JDC) appears in a number of signal processing problems, such as in Independent Component Analysis (ICA). Recent developments in ICA under the nonnegativity constraint of the mixing matrix, known as semi-nonnegative ICA, allow us to obtain a more realistic representation of some real-world phenomena, such as audios, images and biomedical signals. Consequently, during this thesis, the main objective was not only to design and develop semi-nonnegative ICA methods based on novel nonnegative JDC algorithms, but also to illustrate their interest in applications involving Blind Source Separation (BSS). The proposed nonnegative JDC algorithms belong to two fundamental strategies of optimization. The first family containing five algorithms is based on the Jacobi-like optimization. The nonnegativity constraint is imposed by means of a square change of variable, leading to an unconstrained problem. The general idea of the Jacobi-like optimization is to factorize the matrix variable as a product of a sequence of elementary matrices which is defined by only one parameter, then to estimate these elementary matrices one by one in a specific order. The second family containing one algorithm is based on the alternating direction method of multipliers. Such an algorithm is derived by successively minimizing the augmented Lagrangian function of the cost function with respect to the variables and the multipliers. Experimental results on simulated matrices show a better performance of the proposed algorithms in comparison with several classical JDC methods, which do not use the nonnegativity as constraint prior. It appears that our methods can achieve a better estimation accuracy particularly in difficult contexts, for example, for a low signal-to-noise ratio, a small number of input matrices and a high coherence level of matrix. Then we show the interest of our approaches in solving real-life problems. To name a few, we are interested in i) the analysis of the chemical compounds in the magnetic resonance spectroscopy, ii) the identification of the harmonically fixed spectral profiles (such as piano notes) of a piece of signal-channel music record by decomposing its spectrogram, iii) the partial removal of the show-through effect of digital images, where the show-through effect were caused by scanning a semi-transparent paper. These applications demonstrate the validity and improvement of our algorithms, comparing with several state-of-the-art BSS methods.