Un réseau sans fil multi-saut est un ensemble d’entités mobiles et/ou fixes formant un réseau dynamique temporaire avec ou sans l’aide de toute administration centralisée. Cette particularité rend le routage problématique en cas d’instabilité des éléments qui composent les communications non directes. Afin de palier ces problèmes, de nouvelles formes de routage sont utilisées comme le routage multi-chemin (MC). Le routage MC permet d’envoyer les données sur des chemins multiples et semble être une solution efficace pour ces réseaux. Le but de cette thèse est d’étudier les techniques de routage MC dans un contexte sans fil multi-saut en vue d’obtenir de meilleures performances. Nous avons choisi pour notre étude une extension MC du protocole OLSR, appelée MP-OLSR. Nous évaluons ses performances sous divers scénarios sous NS-2. Ces tests d’évaluation nous ont amenés à mettre en ´evidence deux problèmes dans MP-OLSR : la réactivité du protocole de routage MC suite à des ruptures de route et la stratégie de répartition des données sur les chemins multiples. Nous avons étudié la réactivité de tels mécanismes dans MP-OLSR. Nous avons proposé trois nouvelles techniques de réparation de pannes qui diminuent les temps de rétablissement d’une route et réduisent le taux de perte des flux transmis. Nous proposons aussi un mécanisme qui détecte la dégradation de la qualité des liens durant le transfert d’un trafic de données. Les informations déduites de ce mécanisme servent à adapter la proportion de trafic à affecter à chaque chemin selon les conditions réseaux. Cette nouvelle variante du protocole MP-OLSR est évaluée par simulation. / Wireless multi-hop networks consist of a collection of mobile and/or fixed nodes which dynamically exchange data with (or without) reliance on a (any) centralized administration. They are by definition self-organized. The frequent topological changes make multi-hop routing a crucial issue for these networks. To overcome these problems, new forms of routing schemes are used as the multipath routing (MP). MP routing uses multiple paths to send data and can be regarded as an effective solution for these networks. The purpose of this PhD thesis is to study the MP routing techniques in a wirelessmulti-hop context for better performance. We choose for our study a MP extension of OLSR, called MP-OLSR. We evaluate its performance under various scenarios in NS-2. These tests have led us to highlight two problems in MP-OLSR : the long recovery delays when facing network failure situations and the allocation strategy of data on multiple paths. We define and seek to evaluate the latency introduced by both protocols OLSR and MP-OLSR to find a new path after a link failure. We propose three new different recovery schemes and accordingly extend these original protocols in order to decrease theexpected latency and reduce the packet loss rate of transmitted flow. We also propose a mechanism which is able to detect the deterioration of the link quality during the transfer of data traffic. The information derived from this mechanism is used to adjust the proportion of traffic to be assigned to each path according to network conditions. This new version of MP-OLSR protocol is evaluated by simulation.

Le Doppler ultrasensible est une nouvelle technique d'imagerie ultrasonore permettant d'observer les flux sanguins avec une résolution très fine et sans agent de contraste. Appliquée à l'imagerie microvasculaire cérébrale des rongeurs, cette méthode produit de très fines cartes vasculaires 3D du cerveau à haute résolution spatiale. Ces réseaux vasculaires contiennent des structures tubulaires caractéristiques qui pourraient servir de points de repère pour localiser la position de la sonde ultrasonore et tirer parti des avantages pratiques des appareils à ultrason. Ainsi, nous avons développé un premier système de neuronavigation chez les rongeurs basé sur le recalage automatique d'images cérébrales. En utilisant des méthodes d’extraction de chemins minimaux, nous avons développé une nouvelle méthode isotrope de segmentation pour l’analyse géométrique des réseaux vasculaires en 3D. Cette méthode a été appliquée à la quantification des réseaux vasculaires et a permis le développement d'algorithmes de recalage de nuages de points pour le suivi temporel de tumeurs. / Ultrasensitive Doppler is a new ultrasound imaging technique allowing the observation of blood flows with a very fine resolution and no contrast agent. Applied to cerebral microvascular imaging in rodents, this method produces very fine vascular 3D maps of the brain at high spatial resolution. These vascular networks contain characteristic tubular structures that could be used as landmarks to localize the position of the ultrasonic probe and take advantage of the easy-to-use properties of ultrasound devices such as low cost and portability. Thus, we developed a first neuronavigation system in rodents based on automatic registration of brain images. Using minimal path extraction methods, we developed a new isotropic segmentation framework for 3D geometric analysis of vascular networks (extraction of centrelines, diameters, curvatures, bifurcations). This framework was applied to quantify brain and tumor vascular networks, and finally leads to the development of point cloud registration algorithms for temporal monitoring of tumors.

Dans le cadre du projet Mary River, situé à l'île de Baffin, une ligne de chemin de fer sur du pergélisol doit être construite. Afin d'évaluer le comportement à long terme de la ligne de chemin de fer, le développement d'un modèle prévisionnel de l'endommagement des remblais est nécessaire. L'élaboration du modèle prévisionnel est possible par la réalisation de simulations numériques et d'essais en laboratoire. Les simulations numériques, effectuées avec le logiciel GéoStudio, permettent de prédire le comportement thermique à long terme des remblais et l'état des contraintes additionnelles dans le sol d'infrastructure induites par le remblai. En laboratoire, des essais de fluage et de consolidation au dégel sont réalisés pour caractériser le comportement mécanique des sols. Ces essais permettent de développer une loi de comportement caractérisant le fluage secondaire des sols gelés. Ainsi, la combinaison des simulations numériques et des essais en laboratoire permet de prédire le taux de déformation du sol d'infrastructure à un endroit précis et ce, pour une température et une contrainte définie.

La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions. / Resource management in freight transportation service network design is an important issue that has been studied extensively in recent years. Resources such as vehicles, crews, etc. are factors that can not be ignored when designing a feasible plan for any service network design problem. However, contributions related to resource management issues and service network design are still limited. The goal of the thesis is to fill this gap by taking into account service network design problems with resource management issues. In this thesis, we propose and address three service network design problems that consider resource management. In the first study, we consider the capacitated multi-commodity fixed cost network design with design-balance constraints which is a basic sub-problem for many service design problems because of the capacitated multi-commodity structure as well as its design-balance property. We propose a three-phase matheuristic that combines tabu-search, path-relinking and an exactbased intensification procedure to find high quality solutions. Tabu-search identifies feasible solutions while path-relinking extends the set of feasible solutions. The solutions found by these two meta-heuristics are used to fix arcs as open or close. An exact solver intensifies the search on a restricted problem derived from fixing arcs. The experiments on benchmark instances show that the solution approach finds good solutions to large-scale problems in a reasonable amount of time. The contribution with regard to this study has been accepted in the Journal of Heuristics. In the second study, together with the consideration of the design of routes to transport a set of commodities by vehicles, we extend resources management by explicitly taking account of the number of available vehicles at each terminal. We introduce a matheuristic solution framework based on a cycle-based formulation that includes column generation, slope-scaling, heuristic and exact optimization techniques. As far as we know, this is the first matheuristic procedure developed for a cycle-based formulation. The column generation solves the linear relaxation model and provides a set of cycles to define the approximation model used in slopescaling loop. A heuristic is used to convert each solution to the approximation problem into a feasible solution. Memory-based perturbation procedure is used to enhance the performance of the algorithm. Experiments show that the proposed algorithm is able to find good feasible solutions for the problem. The contribution with regard to this study has been accepted for publication in Transportation Science. In the third study, we examine resources allocation issues in service network design. We aim to address a number of fleet utilization issues which usually appear at the beginning of the season because of the change of demand patterns: 1) reposition resources among terminals to account for shifts in demand patterns; 2) acquire (buy or long-term rent) new resources and as sign them to terminals; 3) outsource particular services. We present an integrated formulation combining these selection-location and scheduled service design decisions. The mixed-integer formulation is defined over a time-space network, the initial period modeling the location de cisions on resource acquisition and positioning, while the decisions on service selection and scheduling, resource assignment and cycling routing, and demand satisfaction being modeled on the rest of the network. We also present a matheuristic solution method combining slope scaling and column generation, discuss its algorithmic performance, and explore the impact of combining the location and design decisions in the context of consolidation carrier service design. This study will be presented at XII International Symposium On Locational Deci sion, in conjunction with the XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. In summary, three studies are considered in this thesis. The first one considers the capaciated multi-commodity fixed cost network design with design-balance constraints, a basic problem in many service network design problems with design-balance constraints. We propose an ef ficient three-phase matheuristic solution method that includes tabu search, path relinking and exact optimization. In the second study, we propose a new service network design model that takes into account resources limitations at each terminal. We also propose an advanced matheuristic framework solution method based on a cycle-based formulation which includes slope-scaling, column generation, heuristics and exact optimization for this problem. The last study addresses resources allocation issues in service network design. We introduce formula tions that model the reposition, acquisition/renting of resources and outsourcing of services. A solution framework based on the slope-scaling approach on cycle-based formulations is pro posed. Tests indicate that these proposed algorithms are able to find good feasible solutions for each of threse problems.

Nous étudions les propriétés métriques locales des ensembles de niveau des applicationshorizontalement différentiables entre des groupes de Carnot, c'est-à-dire différentiable par rapport à la structure sous-riemannienne intrinsèque.Nous considérons des applications dont la différentielle horizontale est surjective,et notre étude peut être vue comme une généralisation du théorème des fonctions implicites pour les groupes de Carnot.Tout d'abord, nous présentons deux notions de tangence dans les groupes de Carnot:la première basée sur la condition de platitude au sens de Reifenberg et la deuxième issue de l'analyse convexe classique.Nous montrons que dans les deux cas, l'espace tangent à un ensemble de niveau coïncide avec le noyau de la différentielle horizontale.Nous montrons que cette condition de tangence caractérise en fait les ensembles de niveaudits ‘co-abéliens', c'est-à-dire ceux pour lesquels l'espace d'arrivée est abélien, et qu'une telle caractérisation n'est pas vraie en général.Ce résultat sur les espaces tangents a plusieurs conséquences remarquables.La plus importante est que la dimension de Hausdorff des ensembles de niveau est celle à laquelle l'on s'attend.Nous montrons également la connectivité locale des ensembles de niveau, et le fait que les ensembles de niveau de dimension 1 sont topologiquement des arcs simples.Pour les ensembles de niveau de dimension 1 nous trouvons une formule de l'aire qui permet d'exprimer la mesure de Hausdorff en termes d'intégrales de Stieltjes généralisées.Ensuite, nous menons une étude approfondie du cas particulier des ensembles de niveau dans les groupes d'Heisenberg.Nous montrons que les ensembles de niveau sont topologiquement équivalents à leurs espaces tangents.Il s'avère que la mesure de Hausdorff des ensembles de niveau de codimension élevée est souvent irrégulière, étant, par exemple, localement nulle ou infinie.Nous présentons une condition simple de régularité supplémentaire pour une application pour assurer la régularité au sens d'Ahlfors des ses ensembles de niveau.Parmi d'autres résultats, nous obtenons une nouvelle caractérisation généraledes graphes Lipschitziens associés à une décomposition en produit semi-direct d'un groupe de Carnot.Nous traitons, en particulier, le cas des groupes de Carnot dont le nombre de stratesest plus grand que $2$.Cette caractérisation nous permet de déduire une nouvelle caractérisation des ensemblesde niveau co-abéliens qui admettent une représentation en tant que graphe. / Metric properties of level sets of differentiable maps on Carnot groupsAbstract.We investigate the local metric properties of level sets of mappings defined between Carnot groups that are horizontally differentiable, i.e.with respect to the intrinsic sub-Riemannian structure. We focus on level sets of mapping having a surjective differential,thus, our study can be seen as an extension of implicit function theorem for Carnot groups.First, we present two notions of tangency in Carnot groups: one based on Reifenberg's flatness condition and another coming from classical convex analysis.We show that for both notions, the tangents to level sets coincide with the kernels of horizontal differentials.Furthermore, we show that this kind of tangency characterizes the level sets called ``co-abelian'', i.e.for which the target space is abelian andthat such a characterization may fail in general.This tangency result has several remarkable consequences.The most important one is that the Hausdorff dimension of the level sets is the expected one. We also show the local connectivity of level sets and, the fact that level sets of dimension one are topologically simple arcs.Again for dimension one level set, we find an area formula that enables us to compute the Hausdorff measurein terms of generalized Stieltjes integrals.Next, we study deeply a particular case of level sets in Heisenberg groups. We show that the level sets in this case are topologically equivalent to their tangents.It turns out that the Hausdorff measure of high-codimensional level sets behaves wildly, for instance, it may be zero or infinite.We provide a simple sufficient extra regularity condition on mappings that insures Ahlfors regularity of level sets.Among other results, we obtain a new general characterization of Lipschitz graphs associated witha semi-direct splitting of a Carnot group of arbitrary step.We use this characterization to derive a new characterization of co-ablian level sets that can be represented as graphs.

Cette thèse est consacrée à l’étude des monoïdes plaxiques par une nouvelle approche utilisant des méthodes issues de la réécriture. Ces méthodes sont appliquées à des présentations de monoïdes plaxiques décrites en termes de tableaux de Young, de bases cristallines de Kashiwara et de modèle des chemins de Littelmann. On étudie le problème des syzygies pour la présentation de Knuth des monoïdes plaxiques. En utilisant la procédure de complétion homotopique basée sur les procédures de complétion de Squier et de Knuth–Bendix, on construit des présentations cohérentes de monoïdes plaxiques de type A. Une telle présentation cohérente étend la notion de présentation convergente d’un monoïde par une famille génératrice de syzygies, décrivant toutes les relations entre les relations. On explicite une présentation cohérente finie des monoïdes plaxiques de type A avec les générateurs colonnes. Cependant, cette présentation n’est pas minimale dans le sens que plusieurs de ses générateurs sont superflus. En appliquant la procédure de réduction homotopique, on réduit cette présentation en une présentation cohérente finie qui étend la présentation de Knuth, donnantainsi toutes les syzygies des relations de Knuth. D’une manière plus générale, on étudie des présentations de monoïdes plaxiques généralisés du point de vue de la réécriture. On construit des présentations convergentes finies de ces monoïdes en utilisant les chemins de Littelmann. De plus, on étudie ces présentations pour le type C en termes de bases cristallines de Kashiwara. En introduisant les générateurs colonnes admissibles, on construit une présentation convergente finie du monoïde plaxique de type C avec des relations explicites. Cette approche nous permettrait d’étudier le problème des syzygies des présentations de monoïdes plaxiques en tout type / This thesis focuses on the study of plactic monoids by a new approach using methods issued from rewriting theory. These methods are applied on presentations of plactic monoids given in terms of Young tableaux, Kashiwara’s crystal bases and Littelmann path model. We study the syzygy problem for the Knuth presentation of the plactic monoids. Using the homotopical completion procedure that extends Squier’s and Knuth–Bendix’s completions procedure, we construct coherent presentations of plactic monoids of type A. Such a coherent presentation extends the notion of a presentation of a monoid by a family of generating syzygies, taking into account all the relations among the relations. We make explicit a finite coherent presentation of plactic monoids of type A with the column generators. However, this presentation is not minimal in the sense that many of its generators are superfluous. After applying the homotopical reduction procedure on this presentation, we reduce it to a finite coherent one that extends the Knuth presentation, giving then all the syzygies of the Knuth relations. More generally, we deal with presentations of plactic monoids of any type from the rewriting theory perspective. We construct finite convergent presentations for these monoids in a general way using Littelmann paths. Moreover, we study the latter presentations in terms of Kashiwara’s crystal graphs for type C. By introducing the admissible column generators, we obtain a finite convergent presentation of the plactic monoid of type C with explicit relations. This approach should allow us to study the syzygy problem for the presentations of plactic monoids for any type

Cette thèse présente l'étude théorique et expérimentale du contrôle<br />des phénomènes de propagation cohérente d'impulsions ultracourtes<br />dans un milieu résonant optiquement dense. Dans une première partie,<br />nous décrivons les phénomènes élémentaires des effets de<br />propagation. L'épaisseur optique caractérise l'importance de la<br />distorsion temporelle qui apparaît en général sur l'impulsion. A<br />l'image des compensateurs à prismes ou à réseaux utilisés pour<br />compenser la dispersion d'un milieu transparent, on montre que cette<br />dispersion résonante peut être compensée par l'utilisation d'un<br />façonneur d'impulsion haute résolution. Dans un second temps, nous<br />développons l'idée de contrôler par un champ fort, les propriétés<br />transitoires d'une autre impulsion faible et résonante qui se<br />propage simultanément dans le milieu. Le champ fort induit des<br />modifications transitoires dans le milieu, qui se répercutent et<br />modifient par rayonnement le champ de l'impulsion résonante qui se<br />propage. Dans un système à trois niveaux en échelle, des modulations<br />visibles sur le profil temporel, révèlent les déplacements lumineux<br />induits de manière non résonante sur les deux états excités. Leur<br />durée caractéristique est plus courte que celle de l'impulsion<br />initiale : il y a un enrichissement du spectre transmis. Ces<br />oscillations résultent du battement entre le champ incident et le<br />champ rayonné dont la fréquence varie sous l'effet des déplacements<br />lumineux. L'excitation "bichromatique" d'un système à deux niveaux,<br />présente deux configurations géométriques qui donnent accès à des<br />informations différentes. En plus des phénomènes précédents qui<br />apparaissent en configuration non colinéaire, les effets des<br />transitions non adiabatiques induites par le champ de contrôle se<br />manifestent également dans le cas colinéaire. Le champ faible est<br />alors une sonde particulièrement sensible à ces effets. Nous<br />étudions enfin une configuration où les deux impulsions, polarisées<br />orthogonalement, excitent de manière résonante un système à quatre<br />niveaux dégénérés deux à deux. Puisque le champ fort mélange les<br />états, les chemins d'émission et d'absorption du champ faible ont<br />des poids équivalents. Ces deux chemins interfèrent modulant ainsi<br />l'énergie de l'impulsion transmise. La combinaison des déplacements<br />lumineux et de ces interférences, permet de contrôler aussi bien le<br />gain que la forme temporelle de l'impulsion.

Titre de la Thèse : L'établissement des chemins de fer dans les Balkans à l'époque ottomane : structuration de l'espace et organisation des échanges (1856-1913)Rejoindre l'Orient, voici sans doute l'une des obsessions de l'Occident. Peut-être l'épopée d'Alexandre le Grand a t-elle contribué à construire cet objectif quasi mystique. Quoi qu'il en soit, le XIXe siècle est celui de sa rationalisation. L'invention de la locomotive et celle du navire à vapeur permettent d'amorcer un processus de mise en réseau du monde. Sur les cinq continents, les villages, les villes et les ports s'interconnectent progressivement, engendrant une mondialisation des flux commerciaux et humains. Ce mouvement est orchestré par les grandes puissances européennes, dont le pouvoir est fondé sur la conquête de nouveaux marchés et sur l'importation des matières premières essentielles à leur essor. Londres et Bombay forment alors deux pivots incontournables, permettant de rediriger les flux en circulation à l'échelle trans-continentale. Entre ces deux points, Suez joue le rôle d'interface entre la mer Rouge et la Méditerranée. Au cours de la seconde moitié du XIXe siècle, l'espace balkanique est progressivement intégré à ce système-monde. L'introduction du rail y induit une profonde redéfinition des rapports de force, que ceux-ci soient d'ordre économique, militaire ou politique. A ce titre, la mise en place de voies ferrées dans les Balkans, à l'époque sous domination de l'Empire ottoman, résulte d'une imbrication de stratégies d'influence, s'exprimant à différentes échelles. Cette thèse se propose de les mettre en lumière. / Reaching the East : this is undoubtedly one of the obsessions of the West. Maybe Alexander the Great's conquests contributed to forge this quasi-mystical aim. Wherever it comes from, the XIXth century is the one of its rationalization. Inventions such as steam locomotive and steamship allow to begin a global networking process. On five continents, villages, cities and ports, are progressively interconnected, generating a globalization of human and trade flows. This movement is orchestrated by the major European powers, whose expansion is based on the conquest of new markets and on the importation of natural resources required for their development. London and Mumbay play at that time a pivotal role, allowing to reroute flows in circulation at the inter-continental scale. Between these two major cities, Suez is an unavoidable crossing point between the Mediterranean and the Red Sea. During the second half of the XIXth century, the Balkan space is progressively integrated to this world-system. In that region, the introduction of railway induces a radical restructuring of power relations, whether political, economical or military. For this reason, the establishment of railways in the Balkans results from an interlacing of influencing strategies, articulated at various scales. This thesis sets out to highlight them.

Le port de Paris ne correspond pas à la définition traditionnelle du terme. On doit observer tout d'abord qu'il s'agit d'un port fluvial. La difficulté de définir le port de Paris tient au fait qu'il consiste en plusieurs types d'installations: canaux, ports à darses, ports sur berges (quais droits et ports de tirage) et donc à des réalités protéiformes. Certains auteurs préfèrent l'expression« ports de Paris», pour en souligner le caractère hétéroclite. Au XIXe siècle, on parlait également des «ports de Paris», c'est-à-dire des installations sur la Seine, par opposition aux canaux. Le port de Paris correspond donc à un ensemble bordé par une soixantaine de kilomètres de rives, dont une partie destinée à la batellerie. La thèse débute à une époque durant laquelle le transport fluvial se trouve confronté aux effets de la concurrence des chemins de fer. Il lui faudra plusieurs décennies pour s'adapter et revêtir une nouvelle fonction, à savoir celle quasi exclusive de pourvoyeuse de pondéreux. Cette conversion s'est opérée essentiellement à travers l'amélioration des infrastructures fluviales. La modernisation portuaire revêtait deux volets, à savoir l'amélioration de l'outillage en vue d'optimiser le conditionnement des marchandises, et celle appartenant à une vision plus globale de la fonction du port de Paris, voire de Paris lui-même. Paris port de mer appartient à cette dernière. On peut avancer l'idée d'une opposition entre un «port réel» et un port «mythique», à savoir une voie alternative visant à transformer la vocation portuaire de la capitale. Des tentatives de réconciliation entre les deux visions se manifestent à travers la création du port d’Ivry, des commissions entre 1911 et 1914 sur la modernisation de l'outillage portuaire. / The Port of Paris does not correspond to the traditional definition of the term. It should first be noted that this is a river port. The difficulty of defining the port of Paris stems from the fact that it consists of several types of installations: canals, ports at docks, ports on banks (straight wharves and pull ports) and therefore protean realities. Some authors prefer the term "ports of Paris" to emphasize its heterogeneous character. In the 19th century, we also talked about the "ports of Paris", that is to designate installations on the Seine, as opposed to canals. The port of Paris thus corresponds to an ensemble bordered by some sixty kilometers of shore, including a part intended for inland navigation This thesis begins at a time when river transport is confronted with the effects of competition from the railways. It will take several decades to adapt and take on a new function, namely the almost exclusive role of provider of weighty. This conversion was mainly achieved through the improvement of river infrastructures. Port modernization had two aspects: improving tooling to optimize the packaging of goods, and integrating a more global vision of the function of the port of Paris, and even of Paris itself. "Paris sea port" belongs to the latter. One can put forward the idea of an opposition between a "real port" and a "mythical" port, an alternative way of transforming the port's vocation to the capital. Attempts at reconciliation between these two visions are manifested through the creation of the port of Ivry, commissions between 1911 and 1914 on the modernization of port equipment.

In this thesis, we consider the k-edge connected L-hop-constrained network design problem. Given a weighted graph G=(N,E), a set D of pairs of terminal nodes, and two integers k,L > 1, it consists in finding in G the minimum cost subgraph containing at least k edge-disjoint paths of at most L edges between each pair in D. This problem is of great interest in today's telecommunication industry, where highly survivable networks need to be constructed.<p><p>We first study the particular case where the set of demands D is reduced to a single pair {s,t}. We propose an integer programming formulation for the problem, which consists in the st-cut and trivial inequalities, along with the so-called L-st-path-cut inequalities. We show that these three classes of inequalities completely describe the associated polytope when k=2 and L=2 or 3, and give necessary and sufficient conditions for them to be facet-defining. We also consider the dominant of the associated polytope, and discuss how the previous inequalities can be separated in polynomial time.<p><p>We then extend the complete and minimal description obtained above to any number k of required edge-disjoint L-st-paths, but when L=2 only. We devise a cutting plane algorithm to solve the problem, using the previous polynomial separations, and present some computational results.<p><p>After that, we consider the case where there is more than one demand in D. We first show that the problem is strongly NP-hard, for all L fixed, even when all the demands in D have one root node in common. For k=2 and L=2,3, we give an integer programming formulation, based on the previous constraints written for all pairs {s,t} in D. We then proceed by giving several new classes of facet-defining inequalities, valid for the problem in general, but more adapted to the rooted case. We propose separation procedures for these inequalities, which are embedded within a Branch-and-Cut algorithm to solve the problem when L=2,3. Extensive computational results from it are given and analyzed for both random and real instances.<p><p>Since those results appear less satisfactory in the case of arbitrary demands (non necessarily rooted), we present additional families of valid inequalites in that situation. Again, separation procedures are devised for them, and added to our previous Branch-and-Cut algorithm, in order to see the practical improvement granted by them.<p><p>Finally, we study the problem for greater values of L. In particular, when L=4, we propose new families of constraints for the problem of finding a subgraph that contains at least two L-st-paths either node-disjoint, or edge-disjoint. Using these, we obtain an integer programming formulation in the space of the design variables for each case.<p><p>------------------------------------------------<p><p>Dans cette thèse, nous considérons le problème de conception de réseau k-arete connexe à chemins L-bornés. Etant donné un graphe pondéré G=(N,E), un ensemble D de paires de noeuds terminaux, et deux entiers k,L > 1, ce problème consiste à trouver, dans G, un sous-graphe de cout minimum tel que, entre chaque paire dans D, il existe au moins k chemins arete-disjoints de longueur au plus L. Ce problème est d'un grand intéret dans l'industrie des télécommunications, où des réseaux hautement fiables doivent etre construits.<p><p>Nous étudions tout d'abord le cas particulier où l'ensemble des demandes D est réduit à une seule paire de noeuds. Nous proposons une formulation du problème sous forme de programme linéaire en nombres entiers, laquelle consiste en les inégalités triviales et de coupe, ainsi que les inégalités dites de L-chemin-coupe. Nous montrons que ces trois types d'inégalités décrivent complètement le polytope associé lorsque k=2 et L=2,3, et donnons des conditions nécessaires et suffisantes pour que celles-ci en définissent des facettes. Nous considérons également le dominant du polytope associé et discutons de la séparation polynomiale des trois classes précédentes.<p><p>Nous étendons alors cette description complète et minimale à tout nombre k de chemins arete-disjoints de longueur au plus 2. De plus, nous proposons un algorithme de plans coupants utilisant les précédentes séparations polynomiales, et en présentons quelques résultats calculatoires, pour tout k>1 et L=2,3.<p><p>Nous considérons ensuite le cas où plusieurs demandes se trouvent dans D. Nous montrons d'abord que le problème est fortement NP-dur, pour tout L fixé et ce, meme si les demandes sont toutes enracinées en un noeud. Pour k=2 et L=2,3, nous donnons une formulation du problème sous forme de programme linéaire en nombres entiers. Nous proposons également de nouvelles classes d'inégalités valides, pour lesquelles nous réalisons une étude faciale. Celles-ci sont alors séparées dans le cadre d'un algorithme de coupes et branchements pour résoudre des instances aléatoires et réelles du problème.<p><p>Enfin, nous étudions le problème pour de plus grandes valeurs de L. En particulier, lorsque L=4, nous donnons de nouvelles familles de contraintes pour le problème consistant à déterminer un sous-graphe contenant entre deux noeuds fixés au moins deux chemins de longueur au plus 4, que ceux-ci doivent etre arete-disjoints ou noeud-disjoints. Grace à ces dernières, nous parvenons à donner une formulation naturelle du problème dans chacun de ces deux cas. <p> / Doctorat en sciences, Spécialisation Informatique / info:eu-repo/semantics/nonPublished