En informatique, les images sont numériques et donc composées de pixels en 2D et de voxels en 3D. Dans une scène virtuelle 3D, il est impossible de manipuler directement les objets comme des ensembles de voxels en raison du trop gros volume de données. Les objets sont alors polyédrisés, c’est-à-dire remplacés par une collection de facettes. Pour ce faire, il est primordial de savoir décider si un sous-ensemble de voxels peut être transformé en une facette dans la représentation polyédrique. Ce problème est appelé reconnaissance de plans discrets. Pour le résoudre, nous mettons en place un nouvel algorithme spécialement adapté pour les ensembles de voxels denses dans une boite englobante. Notre méthode atteint une complexité quasi-linéaire dans ce cas et s’avère efficace en pratique. En parallèle, nous nous intéressons à un problème algorithmique annexe intervenant dans notre méthode de reconnaissance de plans discrets. Il s’agit de calculer les deux enveloppes convexes des points de Z2 contenus dans un domaine vertical borné et situés de part et d’autre d’une droite quelconque. Nous proposons une méthode de complexité optimale et adaptative pour calculer ces enveloppes convexes. Nous présentons le problème de manière détournée : déterminer le nombre rationnel à dénominateur borné qui approxime au mieux un nombre réel donné. Nous établissons le lien entre ce problème numérique et son interprétation géométrique dans le plan. Enfin, nous proposons indépendamment un nouvel algorithme pour calculer l’épaisseur d’un ensemble de points dans le réseau Zd. Notre méthode est optimale en 2D et gloutonne mais efficace en dimension supérieure / In computer science, pictures are digital and so, they are composed of pixels in 2D or of voxels in 3D. In 3D virtual scenes, we cannot directly manipulate objects as sets of voxels because the data are too huge. As a result, the objects are transformed into polyhedra, i.e. collections of facets. For this, we must be able to decide if a subset of voxels can be replaced by a facet in the polyhedrisation. This problem is called digital plane recognition. To solve it, we design a new algorithm especially adapted for sets of voxels which are dense in a bounding box. Our method achieves a quasi-linear worst-case time complexity in this case and it is efficient in practice. In parallel, we study another algorithmic problem which occures in our digital plane recognition algorithm. It is computing the two convex hulls of grid points lying in a bounded vertical domain and located on either side of a straight line. We propose an optimal time complexity method to compute these convex hulls and which is also output sensitive. We present the problem in a different way : find the rational number of bounded denominator that best approximates a given real number. We establish the link between this numerical problem and geometry. Finally, we independently propose a new algorithm to compute the lattice width of a set of points in Zd. Our method is optimal in 2D and is greedy but efficent in higher dimension

Dans cette thèse, nous développons un modèle du second ordre pour la représentation des formes (courbes et surfaces) grâce à la théorie des cycles normaux. Le cycle normal d'une forme est le courant associé à son fibré normal. En introduisant des métriques à noyaux sur les cycles normaux, nous obtenons une mesure de dissimilarité entre formes qui prend en compte leurs courbures. Cette mesure est ensuite utilisée comme terme d'attache aux données dans une optique d'appariement et d'analyse de formes par les déformations. Le chapitre 1 est une revue du domaine de l'analyse de formes par les déformations. Nous insistons plus particulièrement sur la mise en place théorique et numérique du modèle de Large Deformation Diffeomorphic Metric Mapping (LDDMM). Le chapitre 2 se concentre sur la représentation des formes par les cycles normaux dans un cadre unifié qui englobe à la fois les formes continues et discrètes. Nous précisons dans quelle mesure cette représentation contient des informations de courbure. Enfin nous montrons le lien entre le cycle normal d'une forme et son varifold. Dans le chapitre 3, nous introduisons les métriques à noyaux. Ainsi, nous pouvons considérer les cycles normaux dans un espace de Hilbert avec un produit scalaire explicite. Nous détaillons ce produit scalaire dans le cas des courbes et surfaces discrètes avec certains noyaux, ainsi que le gradient associé. Nous montrons enfin que malgré le choix de noyaux simples, nous ne perdons pas toutes les informations de courbures. Le chapitre 4 utilise cette nouvelle métrique comme terme d'attache aux données dans le cadre LDDMM. Nous présentons de nombreux appariements et estimations de formes moyennes avec des courbes ou des surfaces. L'objectif de ce chapitre est d'illustrer les différentes propriétés des cycles normaux pour l'analyse des déformations sur des exemples synthétiques et réels. / In this thesis, we develop a second order model for the representation of shapes (curves or surfaces) using the theory of normal cycles. The normal cycle of a shape is the current associated with its normal bundle. Introducing kernel metrics on normal cycles, we obtain a dissimilarity measure between shapes which takes into account curvature. This measure is used as a data attachment term for a purpose of registration and shape analysis by deformations. Chapter 1 is a review of the field of shape analysis. We focus on the setting of the theoretical and numerical model of the Large Deformation Diffeomorphic Metric Mapping(LDDMM).Chapter 2 focuses on the representation of shapes with normal cycles in a unified framework that encompasses both the continuous and the discrete shapes. We specify to what extend this representation encodes curvature information. Finally, we show the link between the normal cycle of a shape and its varifold. In chapter 3, we introduce the kernel metrics, so that we can consider normal cycles in a Hilbert space with an explicit scalar product. We detail this scalar product for discrete curves and surfaces with some kernels, as well as the associated gradient. We show that even with simple kernels, we do not get rid of all the curvature informations. The chapter 4 introduces this new metric as a data attachment term in the framework of LDDMM. We present numerous registrations and mean shape estimation for curves and surfaces. The aim of this chapter is to illustrate the different properties of normal cycles for the deformations analysis on synthetic and real examples.

La tomographie est un ensemble de techniques visant à reconstruirel’intérieur d’un objet sans toucher l’objet lui même comme dans le casd’un scanner. Les principes théoriques de la tomographie ont été énoncéspar Radon en 1917. On peut assimiler l’objet à reconstruire à une image,matrice, etc.Le problème de reconstruction tomographique consiste à estimer l’objet àpartir d’un ensemble de projections obtenues par mesures expérimentalesautour de l’objet à reconstruire. La tomographie discrète étudie le cas où lenombre de projections est limité et l’objet est défini de façon discrète. Leschamps d’applications de la tomographie discrète sont nombreux et variés.Citons par exemple les applications de type non destructif comme l’imageriemédicale. Il existe d’autres applications de la tomographie discrète, commeles problèmes d’emplois du temps.La tomographie discrète peut être considérée comme un problème d’optimisationcombinatoire car le domaine de reconstruction est discret et le nombrede projections est fini. La programmation mathématique en nombres entiersconstitue un outil pour traiter les problèmes d’optimisation combinatoire.L’objectif de cette thèse est d’étudier et d’utiliser les techniques d’optimisationcombinatoire pour résoudre les problèmes de tomographie. / The tomographic imaging problem deals with reconstructing an objectfrom a data called a projections and collected by illuminating the objectfrom many different directions. A projection means the information derivedfrom the transmitted energies, when an object is illuminated from a particularangle. The solution to the problem of how to reconstruct an object fromits projections dates to 1917 by Radon. The tomographic reconstructingis applicable in many interesting contexts such as nondestructive testing,image processing, electron microscopy, data security, industrial tomographyand material sciences.Discete tomography (DT) deals with the reconstruction of discret objectfrom limited number of projections. The projections are the sums along fewangles of the object to be reconstruct. One of the main problems in DTis the reconstruction of binary matrices from two projections. In general,the reconstruction of binary matrices from a small number of projections isundetermined and the number of solutions can be very large. Moreover, theprojections data and the prior knowledge about the object to reconstructare not sufficient to determine a unique solution. So DT is usually reducedto an optimization problem to select the best solution in a certain sense.In this thesis, we deal with the tomographic reconstruction of binaryand colored images. In particular, research objectives are to derive thecombinatorial optimization techniques in discrete tomography problems.

Les méthodes de recalage d’images, qui ont pour but l’alignement de deux ou plusieurs images dans un même système de coordonnées, sont parmi les algorithmes les plus anciens et les plus utilisés en vision par ordinateur. Les méthodes de recalage servent à établir des correspondances entre des images (prises à des moments différents, par différents senseurs ou avec différentes perspectives), lesquelles ne sont pas évidentes pour l’œil humain. Un type particulier d’algorithme de recalage, connu comme « les méthodes de recalage déformables à l’aide de modèles graphiques » est devenu de plus en plus populaire ces dernières années, grâce à sa robustesse, sa scalabilité, son efficacité et sa simplicité théorique. La gamme des problèmes auxquels ce type d’algorithme peut être adapté est particulièrement vaste. Dans ce travail de thèse, nous proposons plusieurs extensions à la théorie de recalage déformable à l’aide de modèles graphiques, en explorant de nouvelles applications et en développant des contributions méthodologiques originales.Notre première contribution est une extension du cadre du recalage à l’aide de graphes, en abordant le problème très complexe du recalage d’une tranche avec un volume. Le recalage d’une tranche avec un volume est le recalage 2D dans un volume 3D, comme par exemple le mapping d’une tranche tomographique dans un système de coordonnées 3D d’un volume en particulier. Nos avons proposé une formulation scalable, modulaire et flexible pour accommoder des termes d'ordre élevé et de rang bas, qui peut sélectionner le plan et estimer la déformation dans le plan de manière simultanée par une seule approche d'optimisation. Le cadre proposé est instancié en différentes variantes, basés sur différentes topologies du graph, définitions de l'espace des étiquettes et constructions de l'énergie. Le potentiel de notre méthode a été démontré sur des données réelles ainsi que des données simulées dans le cadre d’une résonance magnétique d’ultrason (où le cadre d’installation et les stratégies d’optimisation ont été considérés).Les deux autres contributions inclues dans ce travail de thèse, sont liées au problème de l’intégration de l’information sémantique dans la procédure de recalage (indépendamment de la dimensionnalité des images). Actuellement, la plupart des méthodes comprennent une seule fonction métrique pour expliquer la similarité entre l’image source et l’image cible. Nous soutenons que l'intégration des informations sémantiques pour guider la procédure de recalage pourra encore améliorer la précision des résultats, en particulier en présence d'étiquettes sémantiques faisant du recalage un problème spécifique adapté à chaque domaine.Nous considérons un premier scénario en proposant un classificateur pour inférer des cartes de probabilité pour les différentes structures anatomiques dans les images d'entrée. Notre méthode vise à recaler et segmenter un ensemble d'images d'entrée simultanément, en intégrant cette information dans la formulation de l'énergie. L'idée principale est d'utiliser ces cartes estimées des étiquettes sémantiques (fournie par un classificateur arbitraire) comme un substitut pour les données non-étiquettées, et les combiner avec le recalage déformable pour améliorer l'alignement ainsi que la segmentation.Notre dernière contribution vise également à intégrer l'information sémantique pour la procédure de recalage, mais dans un scénario différent. Dans ce cas, au lieu de supposer que nous avons des classificateurs arbitraires pré-entraînés à notre disposition, nous considérons un ensemble d’annotations précis (vérité terrain) pour une variété de structures anatomiques. Nous présentons une contribution méthodologique qui vise à l'apprentissage des critères correspondants au contexte spécifique comme une agrégation des mesures de similarité standard à partir des données annotées, en utilisant une adaptation de l’algorithme « Latent Structured Support Vector Machine ». / Image registration methods, which aim at aligning two or more images into one coordinate system, are among the oldest and most widely used algorithms in computer vision. Registration methods serve to establish correspondence relationships among images (captured at different times, from different sensors or from different viewpoints) which are not obvious for the human eye. A particular type of registration algorithm, known as graph-based deformable registration methods, has become popular during the last decade given its robustness, scalability, efficiency and theoretical simplicity. The range of problems to which it can be adapted is particularly broad. In this thesis, we propose several extensions to the graph-based deformable registration theory, by exploring new application scenarios and developing novel methodological contributions.Our first contribution is an extension of the graph-based deformable registration framework, dealing with the challenging slice-to-volume registration problem. Slice-to-volume registration aims at registering a 2D image within a 3D volume, i.e. we seek a mapping function which optimally maps a tomographic slice to the 3D coordinate space of a given volume. We introduce a scalable, modular and flexible formulation accommodating low-rank and high order terms, which simultaneously selects the plane and estimates the in-plane deformation through a single shot optimization approach. The proposed framework is instantiated into different variants based on different graph topology, label space definition and energy construction. Simulated and real-data in the context of ultrasound and magnetic resonance registration (where both framework instantiations as well as different optimization strategies are considered) demonstrate the potentials of our method.The other two contributions included in this thesis are related to how semantic information can be encompassed within the registration process (independently of the dimensionality of the images). Currently, most of the methods rely on a single metric function explaining the similarity between the source and target images. We argue that incorporating semantic information to guide the registration process will further improve the accuracy of the results, particularly in the presence of semantic labels making the registration a domain specific problem.We consider a first scenario where we are given a classifier inferring probability maps for different anatomical structures in the input images. Our method seeks to simultaneously register and segment a set of input images, incorporating this information within the energy formulation. The main idea is to use these estimated maps of semantic labels (provided by an arbitrary classifier) as a surrogate for unlabeled data, and combine them with population deformable registration to improve both alignment and segmentation.Our last contribution also aims at incorporating semantic information to the registration process, but in a different scenario. In this case, instead of supposing that we have pre-trained arbitrary classifiers at our disposal, we are given a set of accurate ground truth annotations for a variety of anatomical structures. We present a methodological contribution that aims at learning context specific matching criteria as an aggregation of standard similarity measures from the aforementioned annotated data, using an adapted version of the latent structured support vector machine (LSSVM) framework.

La programmation bi-niveau désigne une classe de problèmes d'optimisation emboîtés impliquant deux joueurs.Un joueur meneur annonce une décision à un joueur suiveur qui détermine sa réponse parmi l'ensemble des solutions d'un problème d'optimisation dont les données dépendent de la décision du meneur (problème de niveau bas).La décision optimale du meneur est la solution d'un autre problème d'optimisation dont les données dépendent de la réponse du suiveur (problème de niveau haut).Lorsque la réponse du suiveur n'est pas unique, on distingue les problèmes bi-niveaux optimistes et pessimistes,suivant que la réponse du suiveur soit respectivement la meilleure ou la pire possible pour le meneur.Les problèmes bi-niveaux sont souvent utilisés pour modéliser des problèmes de tarification. Dans les applications étudiées ici, le meneur est un vendeur qui fixe un prix, et le suiveur modélise le comportement d'un grand nombre de clients qui déterminent leur consommation en fonction de ce prix. Le problème de niveau bas est donc de grande dimension.Cependant, la plupart des problèmes bi-niveaux sont NP-difficiles, et en pratique, il n'existe pas de méthodes générales pour résoudre efficacement les problèmes bi-niveaux de grande dimension.Nous introduisons ici une nouvelle approche pour aborder la programmation bi-niveau.Nous supposons que le problème de niveau bas est un programme linéaire, en variables continues ou discrètes,dont la fonction de coût est déterminée par la décision du meneur.Ainsi, la réponse du suiveur correspond aux cellules d'un complexe polyédral particulier,associé à une hypersurface tropicale.Cette interprétation est motivée par des applications récentes de la géométrie tropicale à la modélisation du comportement d'agents économiques.Nous utilisons la dualité entre ce complexe polyédral et une subdivision régulière d'un polytope de Newton associé pour introduire une méthode dedécomposition qui résout une série de sous-problèmes associés aux différentes cellules du complexe.En utilisant des résultats portant sur la combinatoire des subdivisions, nous montrons que cette décomposition mène à un algorithme permettant de résoudre une grande classe de problèmes bi-niveaux en temps polynomial en la dimension du problème de niveau bas lorsque la dimension du problème de niveau haut est fixée.Nous identifions ensuite des structures spéciales de problèmes bi-niveaux pour lesquelles la borne de complexité peut être améliorée.C'est en particulier le cas lorsque la fonction coût du meneur ne dépend que de la réponse du suiveur.Ainsi, nous montrons que la version optimiste du problème bi-niveau peut être résolue en temps polynomial, notammentpour des instancesdans lesquelles les données satisfont certaines propriétés de convexité discrète.Nous montrons également que les solutions de tels problèmes sont des limites d'équilibres compétitifs.Dans la seconde partie de la thèse, nous appliquons cette approche à un problème d'incitation tarifaire dans les réseaux mobiles de télécommunication.Les opérateurs de données mobiles souhaitent utiliser des schémas de tarification pour encourager les différents utilisateurs à décaler leur consommation de données mobiles dans le temps, et par conséquent dans l'espace (à cause de leur mobilité), afin de limiter les pics de congestion.Nous modélisons cela par un problème bi-niveau de grande taille.Nous montrons qu'un cas simplifié peut être résolu en temps polynomial en utilisant la décomposition précédente,ainsi que des résultats de convexité discrète et de théorie des graphes.Nous utilisons ces idées pour développer une heuristique s'appliquant au cas général.Nous implémentons et validons cette méthode sur des données réelles fournies par Orange. / Bilevel programming deals with nested optimization problems involving two players. A leader annouces a decision to a follower, who responds by selecting a solution of an optimization problem whose data depend on this decision (low level problem). The optimal decision of the leader is the solution of another optimization problem whose data depend on the follower's response (high level problem). When the follower's response is not unique, one distinguishes between optimistic and pessimistic bilevel problems, in which the leader takes into account the best or worst possible response of the follower.Bilevel problems are often used to model pricing problems.We are interested in applications in which the leader is a seller who announces a price, and the follower models the behavior of a large number of customers who determine their consumptions depending on this price.Hence, the dimension of the low-level is large. However, most bilevel problems are NP-hard, and in practice, there is no general method to solve efficiently large-scale bilevel problems.In this thesis, we introduce a new approach to tackle bilevel programming. We assume that the low level problem is a linear program, in continuous or discrete variables, whose cost function is determined by the leader. Then, the follower responses correspond to the cells of a special polyhedral complex, associated to a tropical hypersurface. This is motivated by recent applications of tropical geometry to model the behavior of economic agents.We use the duality between this polyhedral complex and a regular subdivision of an associated Newton polytope to introduce a decomposition method, in which one solves a series of subproblems associated to the different cells of the complex. Using results about the combinatorics of subdivisions, we show thatthis leads to an algorithm to solve a wide class of bilevel problemsin a time that is polynomial in the dimension of the low-level problem when the dimension of the high-level problem is fixed.Then, we identify special structures of bilevel problems forwhich this complexity bound can be improved.This is the case when the leader's cost function depends only on the follower's response. Then, we showthe optimistic bilevel problem can be solved in polynomial time.This applies in particular to high dimensional instances in which the datasatisfy certain discrete convexity properties. We also show that the solutions of such bilevel problems are limits of competitive equilibria.In the second part of this thesis, we apply this approach to a price incentive problem in mobile telecommunication networks.The aim for Internet service providers is to use pricing schemes to encourage the different users to shift their data consumption in time(and so, also in space owing to their mobility),in order to reduce the congestion peaks.This can be modeled by a large-scale bilevel problem.We show that a simplified case can be solved in polynomial time by applying the previous decomposition approach together with graph theory and discrete convexity results. We use these ideas to develop an heuristic method which applies to the general case. We implemented and validated this method on real data provided by Orange.

Ce travail de thèse aborde le problème de la détection et de l’isolation des pannes à base de modèle du système dynamique non linéaire. Les techniques de détection et d’identification de pannes sont déjà appliquées aux systèmes industriels et elles jouent un rôle important pour assurer les performances attendues des systèmes automatiques. Les différentes approches du diagnostic des systèmes dynamiques semblent être souvent le résultat de contextes différents notamment en ce qui concerne les applications visées et le cahier des charges qui en résulte. Ainsi, la nature des informations disponibles sur le système ou le type de défauts à détecter conduit à la mise en œuvre de stratégies spécifiques. Dans cette étude on suppose disposer d’un modèle de fonctionnement du système et les pannes considérées sont celles qui conduisent le système à ne plus suivre ce modèle. Après avoir introduit la notion de platitude différentielle pour un système dynamique non linéaire continu, plusieurs exemples de systèmes dynamiques différentiellement plats sont introduits. Les redondances analytiques mises en évidence par cette propriété sont dans une première étape utilisées pour détecter des pannes. Ceci conduit à développer des estimateurs d’ordre supérieurs pour les dérivées des sorties plates du système et des estimateurs non linéaires de l’état du système. Cette approche est mise en œuvre dans le cadre de la détection de pannes des moteurs d’un Quadri-Rotor.La notion de platitude pour les systèmes dynamiques discrets est alors introduite. Il est alors possible de développer une nouvelle approche pour la détection des pannes, fondée sur la redondance temporelle entre les informations résultant des mesures directes de composantes du vecteur d’état du Quadri-Rotor et les estimations des sorties plates à chaque instant d’échantillonnage. Cette approche qui est illustrée ici aussi dans le cas du Quadri-Rotor, permet aussi de développer une méthode d’identification en ligne des pannes en se basant sur la chronologie de la propagation de leurs effets / This PhD is submitted in model-based faults detection and isolation in nonlinear dynamic system. The techniques of faults detection and isolation are already being applied to industrial systems and have played an important role to ensure the expected performance of automated systems. The differences in approaches to diagnosis of dynamic systems often seem to be the result of different contexts including in respect of applications and referred the specification that follows. Thus, the nature of information available on the system or the type of fault detection leads to the implementation of specific strategies. In this study we have assumed a model of system operation and faults considered are those that lead the system to no longer follow this model.After introducing the concept of differential flatness for a nonlinear dynamical system continued, several examples of differentially flat systems dynamics are introduced. The analytical redundancy highlighted by this property is a first step used to detect faults. This leads to develop estimators for higher order derivatives of the outputs flat of the system and estimator plate for nonlinear system state. This approach is implemented in the context of fault detection engine of a Quadri-Rotor.The notion of flatness for discrete dynamical systems is introduced. It is then possible to develop a new approach for fault detection based on temporal redundancy between the information from direct measurements of components of the state vector of Quadri-Rotor and estimates of output flat at each sampling instant. This approach is illustrated here as in the case of the Quadri-Rotor, can also develop a method for online identification of fault based on the chronology of the spread of their effects

Le sujet principal de cette thèse porte sur l'approximation polynômiale des fonctions aléatoires au moyen de la projection L2 aléatoire discrète, et son application aux problèmes inverses pour les équations aux dérivées partielles avec des données aléatoires. Les motivations proviennent de l'approximation paramétrique de la solution de modèles aux dérivées partielles. La thèse se compose de deux parties, avec un chapitre d'introduction qui résume les techniques modernes de l'approximation polynômiale des fonctions de variables aléatoires. La première partie, du chapitre 1 au chapitre 4, contient l'analyse théorique de la projection L2 aléatoire discrète pour résoudre le problème direct, par exemple, pour rapprocher les moments d'une fonction aléatoire à partir de ses observations, ou pour calculer la solution à un modèle numérique avec des coefficients stochastiques. La stabilité et l'optimalité de l'erreur d'approximation évaluée dans la norme L2 pondérée sont traités. Dans la dernière partie de la thèse, composé des chapitres 5 et 6, la méthodologie développée précédemment pour le problème direct est appliqué aux problèmes inverses pour les équations aux dérivées partielles à coefficients stochastiques. La méthode de factorisation est appliquée dans le cadre de la tomographie par impédance électrique, d'abord dans le cas de coefficient inhomogène, puis dans le cas de coefficient constante par morceaux, à valeurs dans chaque région affectée par l'incertitude. Enfin, dans le chapitre 6 les variantes de la méthode de factorisation proposées dans le chapitre précédent sont accélérés en utilisant les techniques qui ont été présentés dans la première partie de la thèse.

Les problèmes d'optimisation combinatoire sont généralement NP-difficiles et les méthodes exactes demeurent inefficaces pour les résoudre rapidement. Les métaheuristiques sont des méthodes génériques de résolution connues et utilisées pour leur efficacité. Elles possèdent souvent plusieurs paramètres qui s'avèrent fastidieux à régler pour obtenir de bonnes performances. Il est alors intéressant de chercher à rendre plus évident, voire à automatiser, ce réglage des paramètres. Le paysage d'un problème d'optimisation combinatoire est une structure, basée sur la notion de voisinage, permettant de caractériser le problème puis de suivre la dynamique d'une méthode d'optimisation pour comprendre son efficacité. Les travaux de cette thèse portent sur l'analyse de paysage de problèmes d'optimisation combinatoire et le lien étroit avec certaines classes de métaheuristiques, basées sur une exploration du voisinage des solutions. Ainsi, nous montrons l'influence de la structure de paysage sur la dynamique d'une métaheuristique, pour deux problèmes issus de la logistique. Ensuite, nous analysons les caractéristiques du paysage qui permettent de concevoir et/ou paramétrer des métaheuristiques, principalement des recherches locales, efficaces. La neutralité est, en particulier, une caractéristique structurelle importante des paysages. De tels paysages présentent de nombreux plateaux bloquant la progression d'une recherche locale. Après une analyse fine des plateaux, nous prouvons que cette structure neutre ne doit pas être ignorée. Puis, nous utilisons plusieurs informations liées à la neutralité, et plus particulièrement aux plateaux bloquants, pour concevoir une première recherche locale simple à mettre en œuvre et efficace. Enfin, pour approfondir nos travaux sur les structures neutres, nous avons choisi d'exploiter la neutralité à tous les niveaux du paysage pour concevoir une nouvelle recherche locale basée sur la capacité des solutions d'un même plateau à produire une amélioration. Une stratégie de guidage vers cette solution est alors proposée. La thèse se termine par l'analyse comparative des deux méthodes d'optimisation proposées pour les problèmes neutres afin d'en exploiter de nouvelles caractéristiques, et ainsi, renforcer le lien entre l'analyse de paysage et la conception de méthodes efficaces.

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques. / The Vehicle Routing Problem (VRP) is an important key to efficient logistics system management, which can result in higher level of customer satisfaction because more customers can be served in a shorter time. In broad terms, it deals with designing optimal delivery or collection routes from one or several depot(s) to a number of geographically scattered customers subject to side constraints. The VRP is a discrete optimization and computationally hard problem and has been extensively studied by researchers and practitioners during the past decades. Being complex problems with numerous and relevant potential applications, researchers from the fields of computer science, operations research and industrial engineering have developed very efficient algorithms, both of exact and heuristic nature, to deal with different types of VRPs. However, VRP research has often been criticized for being too focused on oversimplified versions of the routing problems encountered in real-life applications. Consequently, researchers have recently turned to variants of the VRP which before were considered too difficult to solve. These variants include those attributes and constraints observed in real-life planning and lead to solutions that are executable in practice. These extended problems are called Multi-Attribute Vehicle Routing Problems (MAVRPs). The main purpose of this thesis is to study different practical aspects of three multi-attribute vehicle routing problems which will be modeled in it. Besides that, since the VRP has been proved to be NP-hard in the strong sense such that it is impossible to optimally solve the large-sized problems in a reasonable computational time by means of traditional optimization approaches, novel heuristics will be designed to efficiently tackle the created models.

Une structure en béton doit assurer des fonctions structurales qui vont au delà de la simple résistance. Dans ce cadre, la fissuration du béton armé joue un rôle primordial sur la durabilité, l'étanchéité et même la sûreté des structures. La structure poreuse du béton rend naturellement possible la pénétration au cours du temps d'espèces délétères. En outre, sous l'effet des chargements mécaniques et des conditions environnementales au sens large, le béton se fissure. Les fissures constituent, elles aussi, des voies préférentielles pour la pénétration de fluides ou d'agents agressifs et ajoutent de manière significative leur contribution à la dégradation des performances structurelles. Dans la thèse une stratégie de modélisation macroscopique probabiliste du couplage entre fissuration et transferts de fluides dans les structures en béton est présentée. Le béton est modélisé comme un milieu poreux saturé d'eau tandis que la fissuration (mécanique) est modélisée au travers d'une approche numérique probabiliste tenant compte de l'hétérogénéité naturelle du matériau et des effets d'échelle qu'elle induit. L'hypothèse physique de base du modèle de fissuration est que chaque élément fini peut être considéré comme représentatif d'un volume de matière hétérogène dont le comportement est géré par son degré d'hétérogénéité, défini comme le rapport entre le volume élémentaire et un volume représentatif de l'hétérogénéité du matériau. Dans la formulation développée, les propriétés mécaniques du matériau sont considérées comme des variables aléatoires (non corrélés) distribuées dans les éléments du maillage selon des distributions statistiques validées expérimentalement. Une approche par analyse inverse permet d'accéder aux paramètres de fonctions de distribution qui, selon les hypothèses du modèle, varient en fonction de la dimension des éléments finis. Le couplage fissuration-transfert est traité de manière faible, sous l'hypothèse d'absence d'interaction entre les deux processus (à savoir que la fissuration de l'élément fini, d'origine mécanique, induit une variation locale de sa perméabilité). L'utilisation d'une loi de Poiseuille modifiée et adaptée expérimentalement selon un protocole développé dans le cadre de la thèse permet de mettre en relation une telle variation avec l'ouverture de fissure et de prendre en compte, de manière macroscopique, les principales causes d'écart entre l'écoulement idéalisé, représenté par la loi de Pouiselle, et l'écoulement dans des fissures réelles. Une approche de type Monte-Carlo permet de valider les résultats des simulations mécaniques et hydriques. Les capacités de la stratégie de modélisation proposée en termes de prédiction des débits d'eau en milieu fissuré sont explorées au travers de la simulation d'essais de perméabilité sous charge sur des éprouvettes cylindriques soumises à du fendage. Ces essais sont utilisés dans le cadre du protocole expérimentale. Une première validation à l'échelle d'un élément structurel multifissuré est presentée. Elle consiste en la simulation d'un essai (récemment proposé dans la littérature) developpé pour l'étude de l'impact de la fissuration sur les propriétés de transfert de tirants en béton armé / Concrete durability is strongly affected by the flow of fluids, gas and pollutants in its porous matrix. The presence of cracks weakens the resistance of concrete porous matrix and constitutes preferential flow paths for aggressive components. In the thesis, a probabilistic numerical modeling strategy for modeling fluids transfers in cracked concrete structures is presented. The concrete is modeled in the framework of water saturated porous media. Its (mechanical) cracking is modeled by means of a macroscopic probabilistic approach, explicitly taking into account material heterogeneity as well as size effects. The main assumption of the model, developed in the frame of the the Finite Element Method, is to consider a finite element volume as a volume of heterogeneous material and to assume that physical mechanisms influencing the cracking processes remain the same whatever the scale of observation. At the scale of the finite element, mechanical properties are then functions of its own volume. To describe the heterogeneity of the material, these mechanical properties are consider as uncorrelated random variables distributed over the finite element mesh. Characteristics of statistical distribution laws are directly depending on the degree of heterogeneity of the finite element (the ratio between its volume and the volume of the coarsest aggregate) and of the quality of the cement paste. An inverse analysis approach allows to find their parameters as functions of the elementary volume. A weak coupling between cracking and fluid transfers is considered, under the assumption of no interaction between the two processes (i.e. the mechanically produced cracking of a finite element induce a local variation of its permeability tensor). An experimentally adapted Pouiseuille law, based on an original experimental protocol, allows to relate this permeability variation to the crack aperture and to macroscopically take into account the influence of crack roughness, aperture variation and tortuosity. A Monte-Carlo like approach is used in order to statistically validate mechanical and hydraulic simulations. The coupling strategy is validated in two phases, both at the scale of a laboratory specimen and at the scale of a multi-cracked structural element