Дисертації з теми "Localisation optimale"

Des avancées importantes ont été réalisées dans le domaine de la robotique mobile. L'usage croissant des robots terrestres et des drones de petite taille, n'est possible que par l'apport de capacités d'autonomie de mouvement dans l'environnement d'évolution. La problématique de la localisation du système, par la mise en correspondance de mesures issues des capteurs embarqués avec des primitives contenues dans une carte, est primordiale. Ce processus, qui s'appuie sur la mise en oeuvre de techniques de fusion, a été très étudié. Dans cette thèse, nous proposons de définir des méthodes de planification du mouvement d'un mobile, avec pour objectif de garantir une performance de localisation à partir d'une carte incertaine donnée a priori, et ce lors de l'exécution. Une méthode de génération contrôlée de réalisations de cartes bruitées, exploitant la théorie des processus ponctuels, est d'abord présentée. Cette base de cartes permet de construire des cartes multi-niveaux pour la localisation. Le critère d'optimisation est défini à partir de fonctionnelles de la borne de Cramèr-Rao a posteriori, qui tient compte de l'incertitude sur la dynamique du mobile et de la cartographie incertaine. Nous proposons différentes approches, basées sur la méthode de cross-entropie, pour obtenir des stratégies de déplacement avec des modèles de dynamique discret et continu. La qualité des solutions optimales fournies par ces approches heuristiques est analysée en utilisant des résultats de la théorie des valeurs extrêmes. Enfin, nous esquissons une démarche pour l'amélioration ciblée de cartes sous contrainte de ressources afin d'améliorer la performance de localisation.

Cette thèse contient deux parties : la première partie est consacrée aux méthodes de résolution du problème de localisation de dépôts avec équilibrage proposé par Crainic, Dejax et Delorme en 1986. Deux relaxations lagrangiennes sont proposées dans la thèse. Elles sont ensuite utilisées pour construire un algorithme optimal et un algorithme heuristique. L'algorithme optimal que nous avons proposé est un algorithme de séparation et d’évaluation progressive. La première relaxation lagrangienne est appliquée pour l'évaluation des bornes inférieures. Nous proposons aussi une règle efficace pour la séparation. En ce qui concerne la résolution heuristique du problème, les algorithmes gloutons (ascendant, descendant), d'amélioration par échange et une heuristique lagrangienne sont adaptés en tenant compte de la structure spécifique du problème. Dans la deuxième partie, nous modélisons une extension du problème de localisation de dépôts avec équilibrage. Cette extension consiste à introduire les contraintes de capacité pour les dépôts. Nous proposons une relaxation faible et deux relaxations lagrangiennes. Les algorithmes de résolution présentes dans la première partie s'adaptent aussi au nouveau problème.

Le travail presente procede de l'ambition d'optimiser l'electronique associee a une chambre proportionnelle multifils, utilisee pour la localisation des particules dans la physique nucleaire. Une premiere partie donne un rappel des principes d'operation d'un detecteur gazeux et presente les differentes possibilites pour l'architecture de l'electronique de lecture. Dans la deuxieme partie, apres une comparaison des differentes possibilites pour l'electronique de traitement du signal en vue de maximiser le rapport de signal sur bruit, nous presentons un filtre variable en temps qui permet de simplifier l'electronique standard. La methode reside dans un circuit de restitution de ligne de base de second ordre. Un deuxieme aspect etudie concerne l'algorithme de calcul, qui joue un role significatif si l'on veut obtenir la meilleure precision possible avec un detecteur donne. La derniere partie presente la realisation de l'electronique de detection dans le plan focal du spectrometre bbs a kvi (groningen, pays-bas). Nous avons developpe un systeme complet de 256 voies de codage, depuis des preamplificateurs jusqu'a l'electronique d'acquisition des donnees. Le systeme est base sur des cartes specifiques au standard vxi - taille d. Un processeur numerique de signal (dsp) sur chaque carte vxi traite le calcul du centre de gravite des charges et fournit directement la position dans le plan concerne. Un excellent niveau de bruit est obtenu dans un environnement multiprocesseur.

La thèse étudie l'impact de l'aménagement urbain optimal surla diffusion des prix des logements dans un marché immobilier local. À travers une analyse du champ de la localisation optimale et de l'économétrie spatiale, cette étude vise à considérer comment les propriétés des graphes et les modèles de localisation optimale peuvent contribuer à mieux comprendre et à évaluer les impacts des effets de multiplicateur spatial dans l'économie. Pour ce faire, la recherche s'appuie sur une méthodologie combinant la création d'outils d'aide à la décision et l'étude des prix immobiliers par un modèle économétrique spatiale hiérarchique. Les résultats démontrent que la prise en compte des relations spatiales optimales permet une étude plus précise des impacts de l'aménagement urbain sur la diffusion des prix. A contrario, la considération de relations spatiales “classiques" sur ou sous-estime les impacts
This dissertation studies the effect of optimal urban planning on housing prices diffusion in local real-estate markets. The study uses facility location theory and spatial econometrics to investigate how graph properties and optimal location models can contribute to a better understanding and evaluation of the impact of spatial multiplier effects in the economy. To this end, the research is based on a methodology that combines the creation of decision-support tools and the study of real estate prices using hierarchical spatial econometric models. The results states that using optimal spatial relationships enables a more precise analysis of the impacts of urban planning on the diffusion of prices. Conversely, the consideration of “classical” spatial relationships either underestimates or overestimates the spatial impacts

Le travail de cette thèse est basé sur deux outils : le packing d'un ensemble et les espaces de Wasserstein. Une première partie s'intéresse à la localisation de la masse d'une mesure de probabilité Mu. Lorsque Mu est régulière, les ensembles de niveau de sa densité fournissent une bonne notion pour localiser les zones "denses" de masse, mais perdent leur sens pour les mesures à support fini, comme dans le cas de la mesure empirique. Nous définissons alors une fonction Tau dite de taille, sur les fermés d'un espace métrique, basée sur leur packing. Les ensembles de plus petite Tau-taille ayant une masse 1 − alpha donnée permettent de localiser les zones denses de Mu, même dans les cas irréguliers. Nous montrons que les ensembles de plus petite Tau-taille pour Mu et alpha fixés dépendent continuement de Mu et de alpha, pour la distance de Hausdorff. Nous en tirons une nouvelle méthode de quantification de Mu, robuste et stable. Une seconde partie s'intéresse à la distance de Wasserstein entre une probabilité mu et la mesure empirique associée. Nous obtenons une majoration non asymptotique de l'espérance de cette distance, dans la cadre d'un espace métrique quelconque. Une particularisation aux espaces de dimension finie permet de mettre en valeur la précision de cette majoration. Nous obtenons aussi dans le cas des mesures gaussiennes sur les espaces de Banach, de nouvelles majorations qui coïncident asymptotiquement avec celles des meilleurs quantifieurs possibles. À l'aide d'inégalités de concentration, nous établissons des bornes de déviations. Enfin, nous utilisons ces résultats pour définir des tests statistiques non asymptotiques et non paramétriques d'adéquation à une famille de lois. Une troisième partie s'intéresse au barycentre d'une famille finie de mesures de probabilité. La moyenne de Fréchet fournit une extension de la notion de barycentre aux espaces métriques, nous permettant de le définir sur les espaces de Wasserstein. Nous montrons son existence, puis, en étudions les propriétés de continuité en les mesures de probabilité. Nous discutons enfin de l'application pratique de ces résultats en agrégation de mesures empiriques et en mélange d'images
The study of this manuscript is based on two disctincts tools : the packing and the Wasserstein spaces. A first part focuses on the measure localization of a probability Mu. For a regular Mu, the level sets of its density are a good notion to localize where measure is dense, but loose its meaning for a finitely supported measure such as the empirical measure. We thus define a function Tau , called size function, on the closed sets, based on the packing of the sets. The sets of smallest Tau -size with a given probability 1 − alpha localize dense areas, even if Mu is not regular. We show that these smallest sets given Mu and alpha depend continuously on Mu and alpha, for the Hausdorff distance. We derive a new method to quantize Mu in a robust and stable way. A second part focuses on the Wasserstein distance between a probability measure and the associated empirical measure. We obtain a non asymptotic upper bound of the expectation of this distance, for any arbitrary underlying metric space. An application of the result to finite dimensional spaces shows the accuracy of the bound. We also obtain new bounds for the case of Gaussian measure on Banach spaces that coincide asymptotically with the best quantizers possible. Using concentration inequalities, we show deviation bounds. Finally, we use these results to define non asymptotic and non parametric statistical tests of goodness of fit to a family of probability measures. A third part focuses on the barycenter of a finite family of probability measures. The Fréchet mean is an extension to the notion of barycenter to metric spaces, and gives us a way to define barycenter on Wasserstein spaces. We show the existence of these barycenters and then study properties of continuity on the family of measures. We then discuss practical applications in agreagation of empirical measures and texture mixing

Robots have been widely used for various applications, such as smart transportation, environment monitoring, surveillance, search and rescue. Autonomous navigation, as a core prerequisite for the robots to successfully realise these applications, relies heavily on robot localisation. Global Positioning System (GPS) fails to satisfy many applications in robotics in terms of accuracy and availability. Therefore, robot localisation in GPS-denied 3D space is in great demand. However, due to sensor noise and real world uncertainty, robot localisation in GPS-denied 3D space is a challenging problem. The work in this thesis describes three novel localisation algorithms to localise the robots accurately and efficiently in different .scenarios. .optimal state estimation, including filter based and optimisation based methods, is adopted to elegantly deal with the noise and the uncertainty in a probabilistic perspective. Firstly, a Moving Horizon Estimation (MHE) based localisation algorithm is proposed for single beacon based robot localisation. The performance and observability analyses are also conducted to evaluate the proposed method. Secondly, single beacon based multi-robot cooperative localisation problem is addressed by a constrained MHE based approach. Its discussion answers why and how multi-robot cooperation and optimisation constraints benefit the localisation system. The initial pose estimation problem and observability analysis of the multi-robot system are also studied. Thirdly, an unscented Kalman filter based algorithm is proposed for Vision-aided Inertial Navigation System (VINS) by only using low-cost camera and Inertial Measurement Unit (IMU) to perform pose estimation and camera-IMU extrinsic self-calibration. Trifocal tensor based geometric constraints and point transfer of three-view geometry are incorporated into VINS. Tested by both simulations and experiments, the proposed methods are verified to be effective for robot localisation in GPS-denied 3D space.

Cette these est consacree a l'etude d'algorithmes de localisation d'objets de formes connues, dans des sequences d'images fortement bruitees. Nous presentons tout d'abord deux algorithmes, optimaux au sens de la theorie statistique de l'estimation (maximum de vraisemblance), pour des modeles d'image probabilistes parametriques. Le fond de la scene est modelise par un bruit non-recouvrant blanc et homogene. Les intensites des pixels de la cible sont supposees dans un cas connues et dans l'autre cas inconnues. Ces deux approches permettent d'obtenir deux algorithmes performants et complementaires. Nous montrons que considerer un fond blanc et homogene constitue deux hypotheses limitatives. En utilisant les resultats de la theorie de la detection (maximum du rapport de vraisemblance), nous developpons des algorithmes plus efficaces dans le cas ou le fond est inhomogene. Nous introduisons ensuite des pretraitements afin de prendre en compte la presence de textures correlees dans les images reelles. Ces modifications permettent d'elargir le domaine d'application des deux algorithmes precedemment etudies. Enfin, pour obtenir une technique unique, nous proposons un modele d'image qui s'adapte automatiquement a l'adequation eventuelle entre les niveaux de gris de la reference et ceux de la cible presente dans l'image a analyser. Nous obtenons ainsi un seul algorithme, performant et fiable dans de nombreuses situations realistes.

Au cours de cette thèse, nous avons abordé des problématiques liées à l’optimisation de déploiement et la localisation de cible dans les réseaux de capteurs. Nous avons tout d'abord proposé un premier modèle pour l’optimisation de deux objectifs contradictoires : le nombre de capteurs déployés ainsi que la précision de la localisation. Quatre algorithmes multi-objectifs classiques ont été implémentés, et des versions hybrides ont également été proposées.Une variante du précédent problème est également étudiée, dédiée aux applications de localisation indoor. Les algorithmes proposés pour le premier problème n'ont montré qu'une efficacité relative au cours des premières expérimentations. Une nouvelle heuristique est alors développée, et les résultats ont montré de très bonnes performances sur les instances de taille réduite, ainsi que de bien meilleures performances que les autres algorithmes implémentés sur des instances de grande taille.Enfin, la notion de connectivité et de couverture est également traitée et intégrée dans un modèle linéaire de déploiement. Un algorithme Branch and Bound a été développé afin de traiter ce problème, puis des tests ont été effectués afin de le comparer aux solveurs linéaires actuels
In this thesis, a joint approach for deployment optimization and target tracking in sensor networks is developed. First, we have proposed a linear model to minimize the number of deployed sensors and maximize the accuracy of the localization. We have also implemented several multi-objective methods and proposed hybridization for some of them.We have also proposed a modification of the previous model, taking into account the indoor localization constraints. Two methods of the previous problem have been used, and a specific heuristic has been developed.Finally, two linear models taking into account coverage and connectivity have been proposed. A Branch and Bound algorithm has also been developed, considering a geometric lower bound and two properties to reduce the number of fathomed nodes

L'objectif principal de cette thèse est de mettre en lumière les caractéristiques fondamentales des comportements rationnels des individus pour préciser ainsi les mécanismes de structuration des localisations et des déplacements dans l'espace urbain à l'équilibre. Le but est alors de comparer ces structures d'équilibre avec les structures socialement optimales pour la collectivité, et d'identifier dans ce cas les "externalités" à l'origine des divergences entre les deux types de configuration. Dans une approche plus normative, l'objectif final est enfin de déterminer les politiques publiques à mettre en place pour modifier (ou tout au moins infléchir) le "comportement de masse" de localisation et de déplacement des individus pour restaurer l'optimum collectif urbain. Dans cette perspective, l'ensemble des analyses théoriques de la thèse, menées dans le cadre de dynamiques spatiales et temporelles, se situe dans le paradigme néoclassique de l'économie du bien-être. . . Notre recherche s'articule autour de deux parties, découpage fondé sur la distinction entre les questions de localisation et celles de déplacement, étant entendu que de très fortes relations de causalité relient les deux domaines de recherche
The main object of this thesis is to bring to light the fondamental features of individual's rational behaviours in order to specify the equilibrium configuration of locations and movements in urban area. In such a case, the object is to compare this equilibrium configurations with socially optimal structures and to identify the externalities which explain the differences between the two types of configurations. In a normative approach, the final object is to precise the public policies that the government has to set in order to modify (or to influence) the location's and movement's homogeneous behaviours of individuals and finally, to restore the urban social optimum. From this point of view, the theoretical analysis of this thesis (which are conducted in spatial and temporal dynamic frameworks) are lead in the neoclassical paradigm of the "welfare economics". . . Our work is divided into two parts based on the distinction between location's questions and movement's questions

Cette thèse porte sur l'étude du positionnement optimale des réseaux de capteurs pour la localisation de sources. Nous avons étudié deux approches: l'approche basée sur les performances de l'estimation en termes d'erreur quadratique moyenne et l'approche basée sur le seuil statistique de résolution (SSR).Pour le première approche, nous avons considéré les bornes inférieures de l'erreur quadratique moyenne qui sont utilisés généralement pour évaluer la performance d'estimation indépendamment du type d'estimateur considéré. Nous avons étudié deux types de bornes: la borne Cramér-Rao (BCR) pour le modèle où les paramètres sont supposés déterministes et la borne Weiss-Weinstein (BWW) pour le modèle où les paramètres sont supposés aléatoires. Nous avons dérivé les expressions analytiques de ces bornes pour développer des outils statistiques afin d'optimiser la géométrie des réseaux de capteurs. Par rapport à la BCR, la borne BWW peut capturer le décrochement de l'EQM des estimateurs dans la zone non-asymptotique. De plus, les expressions analytiques de la BWW pour un modèle Gaussien général à moyenne paramétré ou à covariance matrice paramétré sont donnés explicitement. Basé sur ces expressions analytiques, nous avons étudié l'impact de la géométrie des réseaux de capteurs sur les performances d'estimation en utilisant les réseaux de capteurs 3D et 2D pour deux modèles des observations concernant les signaux sources: (i) le modèle déterministe et (ii) le modèle stochastique. Nous en avons ensuite déduit des conditions concernant les propriétés d'isotropie et de découplage.Pour la deuxième approche, nous avons considéré le seuil statistique de résolution qui caractérise la séparation minimale entre les deux sources. Dans cette thèse, nous avons étudié le SSR pour le contexte Bayésien moins étudié dans la littérature. Nous avons introduit un modèle des observations linéarisé basé sur le critère de probabilité d'erreur minimale. Ensuite, nous avons présenté deux approches Bayésiennes pour le SSR, l'une basée sur la théorie de l'information et l'autre basée sur la théorie de la détection. Ces approches pourront être utilisée pour améliorer la capacité de résolution des systèmes.

Les processus ponctuels spatiaux forment une branche de la statistique spatiale utilisée dans des domaines d'application variés (foresterie, géo-marketing, sismologie, épidémiologie...) et développée par de récents travaux théoriques. Nous nous intéressons principalement dans cette thèse à l'apport de la théorie des processus ponctuels spatiaux pour des problèmes de positionnement optimal, ainsi que pour la définition de nouveaux indices de concentration basés sur les distances en économétrie. Le problème de positionnement optimal s'écrit souvent comme un problème d'optimisation prenant en compte des données geo-référencées auxquelles peuvent être associées des caractéristiques. Pour prendre en compte l'aléa, nous considérons ces données issues d'un processus ponctuel spatial pour résoudre un problème de positionnement stochastique plus réaliste qu'un modèle déterministe. A travers l'étude du positionnement optimal d'une nouvelle caserne de pompiers dans la région toulousaine, nous développons une méthode de résolution stochastique permettant de juger de la variabilité de la solution optimale et de traiter des bases de données volumineuses. L'approche implémentée est validée par des premiers résultats théoriques sur le comportement asymptotique des solutions optimales empiriques. La convergence presque sure des solutions optimales empiriques de l'étude de cas précédente est obtenue dans un cadre i.i.d. en utilisant la théorie de Vapnik-Cervonenkis. Nous obtenons aussi la convergence presque sure des solutions optimales empiriques, dans un cadre plus général, pour un problème de positionnement dérivé du problème de transport de Monge-Kantorovich. Nous nous intéressons ensuite à des indices de concentration basés sur des distances en économétrie. Ces indices de concentration peuvent s'écrire comme des estimateurs de caractéristiques du second ordre de processus ponctuels marqués. Nous définissons ensuite un estimateur non-paramétrique d'une nouvelle caractéristique d'un processus ponctuel spatial marqué définissant ainsi un nouvel indice de concentration améliorant ceux déjà existants. Dans un cadre asymptotique avec fenêtre d'observation bornée, notre estimateur est asymptotiquement sans biais.

Ce document synthétise mes travaux de thèse de doctorat en Automatique Productiqueà Grenoble INP (Institut National Polytechnique), thèse préparée au sein dudépartement automatique du laboratoire GIPSA-lab (Grenoble Image Parole Signal etAutomatique). Ce travail s’inscrit dans le cadre du contrôle local et de la supervisiondes systèmes de trafic routier. Les principales contributions portent sur la modélisation,la supervision et la commande locale des systèmes de trafic routier.La contribution apportée à la modélisation du trafic est l’ajout d’un modèle d’incertitudesur le modèle CTM (Cell Transmission Model [Daganzo, 1994]). Ce nouveaumodèle permet de prendre en compte les incertitudes sur différents paramètres dumodèle pour in-fine proposer de nouvelles stratégies de commandes commutées robustes.Outre cette approche de modélisation, nous proposons un niveau de supervisionpermettant d’une part d’estimer en temps réel le mode de fonctionnement et d’autrepart de détecter, localiser et estimer certaines fautes sur le système. L’estimation dynamiquede mode de fonctionnement nous permet de connaître l’état de congestion (ou denon-congestion) de l’aménagement routier considéré. Nous sommes en mesure de détecterdes fautes telles que des chutes de vitesse ou des chutes de capacité survenant sur la route.Enfin, nous proposons deux lois de commandes locales basées sur la théorie dessystèmes à commutations. Ainsi, le schéma de contrôle s’adaptera dynamiquementaux changements de propriétés du système. Ces lois de commande ont pour objet des’insérer dans un schéma de régulation hiérarchique
This document synthesizes my Phd thesis work in Automatic Control in Grenoble-INP. This thesis has been prepared in the automatic control department of thelaboratory GIPSA-lab. This work is situated in the area of traffic systems control andsupervision. Our contributions are about modeling, supervision and local traffic control.The CTM traffic model has been extended with a model of uncertainties. Thisnews model allows us to take into account the uncertain parameters of the model, topropose new robust switched control law.In addition to this modeling approach, we propose some developments on supervisionof trafic systems. On one hand, we can estimate the operating mode of thesystem in real time and on the other hand to estimate some faults on the system. Thedynamical estimation of the operating mode allows us to know the state of congestion(or non congestion) of the road. We are able to estimate faults such as speed fall andcapacities drop that may appear.Finally, we propose two control laws based on switching systems control. The developedcontrollers adapt their geometry to the properties of the system. The purposeof these controllers is to be inserted in a hierarchic control scheme

L'efficacité du transport des marchandises en ville est un sujet complexe préoccupant les autorités locales depuis de nombreuses années. Les enjeux sont immenses, une meilleure organisation du trafic devant permettre d'augmenter la sécurité, réduire les nuisances, minimiser les coûts. La Logistique Urbaine vise à concevoir des systèmes de distribution des marchandises en ville permettant d'acheminer les flux dans les meilleures conditions à la fois pour la communauté et les transporteurs. Cette thèse se deroule dans le cadre du projet ANR MODUM qui propose un système basé sur un anneau de Centres de Distribution Urbains (CDU) situés autour d'une ville. La première partie étudie ce système d'un point de vue stratégique et tactique. Le Multicommodity-Ring Location Routing Problem aborde les décisions concernants l'installation et la connexion en anneau des CDU en simplifiant les détails plus tactiques. Trois méthodes ont été developpées et testées sur un jeu d'instances exhaustif se révélant très efficaces. The Multicommodity-Ring Vehicle Routing Problem est le problème dérivé que l'on obtient quand l'anneau est fixé. Une approche de type Branch&Price est proposée pour ce problème. La deuxième partie porte sur le Vehicle Routing Problem with Intermediate Replenishment Facilities, un problème plus tactique qui se produit dans un système logistique lorsque les véhicules peuvent se recharger auprès des points de remplissage et effectuer plusieurs tournées lors d'une même journée. Plusieurs algorithmes exacts ont été developpés et testés. Les résultats obtenus sur des jeux d'instances tirés de la littérature sont prometteurs
Urban freight transport is a matter of increasing concern in the economic, commercial, social and environmental operations of our cities, due to the constantly increasing growth and urbanization of the civilization. An improved managem ent of the traffic related to the freight transport can have a positive impact in many respects : security, congestion of the road network, noise and air pollution, costs. City Logistics studies the dynamic management of urban freight transport in order to deliver distribution systems solutions that may be suitable for both the community and freight carriers. This thesis originates from the ANR Project MODUM, which proposes a freight distribution system based on a ring of Urban Distribution Centers (UDCs) located in the outskirts of a city. In the first part, this system is studied from both a strategic and a tactical point of view. The Multicommodity-Ring Location Routing Problem (MRLRP) considers long-term decisions, i.e. the installation of the UDCs and the ring connection, without disregarding more tactical aspects. The MRLRP has been tackled by three solution methods, which proved effective on a large set of test instances. In the second part of the thesis, the Vehicle Routing Problem with Intermediate Replenishment Facilities (VRPIRF) is studied. The VRPIRF is a more tactical problem that arises in City Logistics each time both the multi-trip and the multi-depot features, i.e. the possibility for a vehicle to be reloaded at one of a set of facilities, are present. Several exact algorithms, namely two of type Branch&Cut and two of type Branch& Price, have been developed for this problem. computational experiments on benchmark instances taken from the literature have been conducted to assess their performance, leading to very promising results

Cette thèse s’inscrit dans le cadre d’un projet visant à développer un robot mobile autonome capable de réaliser des tâches spécifiques dans une zone préalablement définie par l’utilisateur. Afin de faciliter la mise en œuvre du système, des balises radiofréquences fournissant des mesures de distance par rapport au robot sont disposées au préalable autour du terrain. Le déploiement du robot s’effectue en deux phases, une première d’apprentissage du terrain, puis une seconde, où le robot effectue ses tâches de façon autonome. Ces deux étapes nécessitent de résoudre les problèmes de localisation et de localisation et cartographie simultanées pour lesquels différentes solutions sont proposées et testées en simulation et sur des jeux de données réelles. De plus, afin de faciliter l’installation et d’améliorer les performances du système, un algorithme de placement des balises est présenté puis testé en simulation afin de valider notamment l’amélioration des performances de localisation
This thesis is part of a project which aims at developing an autonomous mobile robot able to perform specific tasks in a preset area. To ease the setup of the system, radio-frequency beacons providing range measurements with respect to the robot are set up beforehand on the borders of the robot’s workspace. The system deployment consists in two steps, one for learning the environment, then a second, where the robot executes its tasks autonomously. These two steps require to solve the localization and simultaneous localization and mapping problems for which several solutions are proposed and tested in simulation and on real datasets. Moreover, to ease the setup and improve the system performances, a beacon placement algorithm is presented and tested in simulation in order to validate in particular the improvement of the localization performances

Nous considérons un problème d'ordonnancement à une machine avec dates de fin impératives et nous cherchons caractériser l'ensemble des solutions optimales, sans les énumérer. Nous supposons que les travaux sont numérotés selon la règle EDD et que cette séquence est réalisable. La méthode consiste à utiliser le treillis des permutations et d'associer à la permutation maximale du treillis la séquence EDD. Afin de caractériser beaucoup de solutions, nous cherchons une séquence réalisable aussi loin que possible de cette séquence. La distance utilisée est le niveau de la séquence dans le treillis, qui doit être minimum (le plus bas possible). Cette nouvelle fonction objectif est étudiée. Quelques cas particuliers polynomiaux sont identifiés, mais la complexité du problème général reste ouverte. Quelques méthodes de résolution, polynomiales et exponentielles, sont proposées et évaluées. Le niveau de la séquence étant en rapport avec la position des travaux dans la séquence, de nouvelles fonctions objectifs en rapport avec les positions des travaux sont identifiées et étudiées. Le problème de la minimisation de la somme pondérée des positions des travaux est prouvé fortement NP-difficile. Quelques cas particuliers sont étudiés et des méthodes de résolution proposées et évaluées
We consider a single machine scheduling problem with deadlines and we want to characterise the set of optimal solutions, without enumerating them. We assume that jobs are numbered in EDD order and that this sequence is feasible. The key idea is to use the lattice of permutations and to associate to the supremum permutation the EDD sequence. In order to characterize a lot of solutions, we search for a feasible sequence, as far as possible to the supremum. The distance is the level of the sequence in the lattice, which has to be minimum. This new objective function is investigated. Some polynomially particular cases are identified, but the complexity of the general case problem remains open. Some resolution methods, polynomial and exponential, are proposed and evaluated. The level of the sequence being related to the positions of jobs in the sequence, new objective functions related to the jobs positions are identified and studied. The problem of minimizing the total weighted positions of jobs is proved to be strongly NP-hard. Some particular cases are investigated, resolution methods are also proposed and evaluated

Cette thèse porte sur le développement de modèles mathématiques et d’algorithmes d’optimisation pour la conception de chaînes logistiques durables. Nous proposons des modèles mono-périodiques, multi-produits et multi-modes de transport à quatre niveaux (fournisseurs, unités de production, entrepôts et clients) couvrant les piliers économique et environnemental du développement durable. Les variables de décision concernent la localisation des sites logistiques intermédiaires (unités de production et entrepôts), les choix de technologie et de mode de transport, et la détermination des flux de produits. Un premier modèle est basé uniquement sur la minimisation des coûts totaux. Ce modèle est étendu au cas bi-objectif en considérant la minimisation des émissions de CO2. Nous proposons une procédure d’optimisation basée sur la recherche à voisinage large (LNS : Large Neighborhood Search). L’application de cette méthode à un problème à variables mixtes tel que la conception de chaîne logistique est inédite. Notre extension au cas bi-objectif fait intervenir l’algorithme récent de recherche locale multi-directionnelle. Les expérimentations numériques permettent d’évaluer la pertinence de nos modèles et de comparer les performances de nos algorithmes à celles d’un solveur du marché
This thesis focuses on the development of mathematical models and optimization algorithms for the design of sustainable supply chains. We propose single-period, multi-commodity, multi-mode, four level models (suppliers, production facilities, warehouses and customers) covering economic and environmental pillars of sustainable development. The decision variables are related to the location of the intermediate logistics sites (production units and warehouses), the choice of technology and mode of transport, and the determination of product flow. A first model is based solely on minimizing total costs. This model is extended to bi-objective minimization by considering CO2 emissions. We propose an optimization procedure based on the Large Neighborhood Search (LNS) metaheuristic, which had almost never been applied to problems with mixed variables such as design supply chain. Our extension to the bi-objective case involves the use of the multi-directional local search (MDLS). Extensive numerical experiments assess the relevance of our model and compare the performance of our algorithms to those of a state-of-the-art solver

Le succès dans l'utilisation de méthodes exactes d’optimisation combinatoire pour des problèmes de grande taille est encore limité à certains problèmes ou à des classes spécifiques d'instances de problèmes. Une approche alternative consiste soit à utiliser des métaheuristiques ou des matheuristiques qui reposent en partie sur des méthodes exactes. Dans le contexte de l'optimisation combinatoire, nous nous intéressons des heuristiques permettant de choisir les heuristiques appliquées au problème traité. Dans cette thèse, nous nous concentrons sur l'optimisation à l’aide d’hyperheuristiques pour des problèmes logistiques. Nous proposons un cadre hyperheuristique qui effectue une recherche dans l'espace des algorithmes heuristiques et apprend comment changer l'heuristique courante systématiquement tout au long du processus de telle sorte qu'une bonne séquence d'heuristiques permet d’obtenir des solutions de haute qualité. Nous étudions plus particulièrement deux problèmes en logistique pour lesquels nous proposons des HHs: un problème de planification d’interventions sur des puits de forage et un problème conjoint de localisation de hubs et de routage. Ensuite, nous comparons les performances de plusieurs HH décrites dans la littérature pour le second problème abordé reposant sur différentes méthodes de sélection heuristique telles que la sélection aléatoire, la fonction de choix, une approche de Q-Learning et un algorithme de colonie de fourmis. Les résultats numériques prouvent l'efficacité de HHs pour les deux problèmes traités, et la pertinence d'inclure l'information venant d’une relaxation de Lagrangienne pour le deuxième problème
Success in using exact methods for large scale combinatorial optimization is still limited to certain problems or to specific classes of instances of problems. The alternative way is either using metaheuristics or matheuristics that rely on exact methods in some ways. In the context of combinatorial optimization, we are interested in heuristics to choose heuristics invoked to solve the addressed problem. In this thesis, we focus on hyperheuristic optimization in logistic problems. We focus on proposing a hyperheuristic framework that carries out a search in the space of heuristic algorithms and learns how to change the incumbent heuristic in a systematic way along the process in such a way that a good sequence of heuristics produces high quality solutions. We propose HHs for two problems in logistics: the workover rig scheduling problem and the hub location routing problem. Then, we compare the performances of several HHs described in the literature for the latter problem, which embed different heuristic selection methods such as a random selection, a choice function, a Q-Learning approach, and an ant colony based algorithm. The computational results prove the efficiency of HHs for the two problems in hand, and the relevance of including Lagrangian relaxation information for the second problem

In this thesis, by being motivated from the challenges in perinatal networks, we address design, evaluation and flow control of a stochastic healthcare network where there exist multiple levels of hospitals and different types of patients. Patients are supposed urgent; thus they can be rejected and overflow to another facility in the same network if no service capacity is available at their arrival. Rejection of patients due to the lack of service capacity is the common phenomenon in overflow networks. We approach the problem from both strategic and operational perspectives. In strategic part, we address a location & capacity planning problem for adjusting the network to better meet demographic changes. In operational part, we study the optimal patient admission control policies to increase flexibility in allocation of resources and improve the control of patient flow in the network. Finally, in order to evaluate the performance of the network, we develop new approximation methodologies that estimate the rejection probabilities in each hospital for each arriving patient group, thus the overflow probabilities among hospitals. Furthermore, an agent-based discrete-event simulation model is constructed to adequately represent our main applicationarea: Nord Hauts-de-Seine Perinatal Network. The simulation model is used to evaluate the performance of the complex network and more importantly evaluate the strength of the optimal results of our analytical models. The developed methodologies in this thesis are combined in a decision support tool, foreseen under the project "COVER", which aims to assist health system managers to effectively plan strategic and operational decisions of a healthcare network and evaluate the performance of their decisions.

Dans ce travail de thèse, on s'intéresse é l'emploi de techniques de traitement de signal de systèmes de communication MIMO (Multiple Input Multiple Output) pour des applications aux réseaux de capteurs sans fil. Les contraintes énergétiques de cette classe de réseau font appel à des topologies particulières et le réseau peut être perçu comme étant un ensemble de grappes de nœuds capteurs. Ceci ouvre la porte à des techniques avancées de communication de type MIMO. Dans un premier temps, les différents aspects caractérisant les réseaux de capteurs sans fil sont introduits. Puis, les efforts engagés pour optimiser la conservation de l'énergie dans ces réseaux sont résumés. Les concepts de base de systèmes MIMOs sont abordés dans le deuxième chapitre et l'exploration par voie numérique de différentes pistes de la technologie MIMO sont exposées. Nous nous intéressons à des techniques de diversité de polarisation dans le cadre de milieux de communication riches en diffuseurs. Par la suite, des méthodes de type beamforming sont proposées pour la localisation dans les réseaux de capteurs sans fil. Le nouvel algorithme de localisation est présenté et les performances sont évaluées. Nous identifions la configuration pour la communication inter-grappes qui permet pour les meilleurs compromis entre énergie et efficacité spectrale dans les réseaux de capteurs sans fil. Finalement, nous envisageons la technique de sélection de nœuds capteurs afin de réduire la consommation de l'énergie dans le réseau de capteur sans fil
The aim of this work is to study from a signal processing point of view the use of MIMO (Multiple Input Multiple Output) communication systems for algorithms dedicated to wireless sensor networks. We investigate energy-constrained wireless sensor networks and we focus on cluster topology of the network. This topology permits for the use of MIMO communication system model. First, we review different aspects that characterize the wireless sensor network. Then, we introduce the existing strategies for energy conservation in the network. The basic concepts of MIMO systems are presented in the second chapter and numerical results are provided for evaluating the performances of MIMO techniques. Of particular interest, polarization diversity over rich scattering environment is studied. Thereafter, beamforming approach is proposed for the development of an original localization algorithm in wireless sensor network. The novel algorithm is described and performances are evaluated by simulation. We determine the optimal system configuration between a pair of clusters that permits for the highest capacity to energy ratio in the fourth chapter. The final chapter is devoted to sensor nodes selection in wireless sensor network. The aim of using such technique is to make energy conservation in the network