Models and algorithms for the capacitated location-routing problem

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48].

Complexité de la communication sur un canal avec délai

Nous introduisons un nouveau modèle de la communication à deux parties dans lequel nous nous intéressons au temps que prennent deux participants à effectuer une tâche à travers un canal avec délai d. Nous établissons quelques bornes supérieures et inférieures et comparons ce nouveau modèle aux modèles de communication classiques et quantiques étudiés dans la littérature. Nous montrons que la complexité de la communication d’une fonction sur un canal avec délai est bornée supérieurement par sa complexité de la communication modulo un facteur multiplicatif d/ lg d. Nous présentons ensuite quelques exemples de fonctions pour lesquelles une stratégie astucieuse se servant du temps mort confère un avantage sur une implémentation naïve d’un protocole de communication optimal en terme de complexité de la communication. Finalement, nous montrons qu’un canal avec délai permet de réaliser un échange de bit cryptographique, mais que, par lui-même, est insuffisant pour réaliser la primitive cryptographique de transfert équivoque.

Sur les prolongements de sous-copules

L’objet du travail est d’étudier les prolongements de sous-copules. Un cas important de l’utilisation de tels prolongements est l’estimation non paramétrique d’une copule par le lissage d’une sous-copule (la copule empirique). Lorsque l’estimateur obtenu est une copule, cet estimateur est un prolongement de la souscopule. La thèse présente au chapitre 2 la construction et la convergence uniforme d’un estimateur bona fide d’une copule ou d’une densité de copule. Cet estimateur est un prolongement de type copule empirique basé sur le lissage par le produit tensoriel de fonctions de répartition splines. Le chapitre 3 donne la caractérisation de l’ensemble des prolongements possibles d’une sous-copule. Ce sujet a été traité par le passé; mais les constructions proposées ne s’appliquent pas à la dépendance dans des espaces très généraux. Le chapitre 4 s’attèle à résoudre le problème suivant posé par [Carley, 2002]. Il s’agit de trouver la borne supérieure des prolongements en dimension 3 d’une sous-copule de domaine fini.

Amplification de l'amplitude : analyse et applications

Ce mémoire étudie l'algorithme d'amplification de l'amplitude et ses applications dans le domaine de test de propriété. On utilise l'amplification de l'amplitude pour proposer le plus efficace algorithme quantique à ce jour qui teste la linéarité de fonctions booléennes et on généralise notre nouvel algorithme pour tester si une fonction entre deux groupes abéliens finis est un homomorphisme. Le meilleur algorithme quantique connu qui teste la symétrie de fonctions booléennes est aussi amélioré et l'on utilise ce nouvel algorithme pour tester la quasi-symétrie de fonctions booléennes. Par la suite, on approfondit l'étude du nombre de requêtes à la boîte noire que fait l'algorithme d'amplification de l'amplitude pour amplitude initiale inconnue. Une description rigoureuse de la variable aléatoire représentant ce nombre est présentée, suivie du résultat précédemment connue de la borne supérieure sur l'espérance. Suivent de nouveaux résultats sur la variance de cette variable. Il est notamment montré que, dans le cas général, la variance est infinie, mais nous montrons aussi que, pour un choix approprié de paramètres, elle devient bornée supérieurement.

A Characterization of Exact Non-atomic Market Games

Continuous exact non-atomic games are naturally associated to certain operators between Banach spaces. It thus makes sense to study games by means of the corresponding operators. We characterize non-atomic exact market games in terms of the properties of the associated operators. We also prove a separation theorem for weak compact sets of countably additive measures, which is of independent interest.

Some Implications of the Zero Lower Bound on Interest Rates for the Term Structure and Monetary Policy

In an economy where cash can be stored costlessly (in nominal terms), the nominal interest rate is bounded below by zero. This paper derives the implications of this nonnegativity constraint for the term structure and shows that it induces a nonlinear and convex relation between short- and long-term interest rates. As a result, the long-term rate responds asymmetrically to changes in the short-term rate, and by less than predicted by a benchmark linear model. In particular, a decrease in the short-term rate leads to a decrease in the long-term rate that is smaller in magnitude than the increase in the long-term rate associated with an increase in the short-term rate of the same size. Up to the extent that monetary policy acts by affecting long-term rates through the term structure, its power is considerably reduced at low interest rates. The empirical predictions of the model are examined using data from Japan.

Sélection des substrats lors de l’exercice prolongé avec ingestion de glucides : études par traçage au 13C

Les principaux substrats oxydés à l’exercice, soit les glucides, les lipides et les pro- téines ne contribuent pas tous au même niveau à la fourniture d’énergie lors de l’effort prolongé. De plus, le glucose peut provenir de différentes sources endogènes (muscle, foie) et exogènes. Plusieurs facteurs peuvent influencer leur contribution respective incluant : la masse musculaire impliquée et l’entraînement préalable, le sexe, l’état nutritionnel et les conditions environnementales. L’utilisation d’isotopes stables, tels que le carbone 13 (13C), combinée à la calorimétrie indirecte respiratoire corrigée pour l’excrétion d’urée dans l’urine et la sueur, permet de différencier les substrats endogènes et exogènes et d’évaluer la contribution de leur oxydation à la fourniture d’énergie. Ces méthodes d’investigation permettant d’apprécier la sélection des substrats lors de l’exercice prolongé avec ingestion de glucose ont permis d’effectuer les comparaisons qui ont fait l’objet des trois études de cette thèse. Dans la première étude, la sélection des substrats au cours d’un effort prolongé effectué avec les membres inférieurs ou les membres supérieurs a été comparée avec et sans ingestion de glucose. Une différence modeste fut observée entre la sélection des substrats selon le mode d’exercice avec l’ingestion d’eau, celle-ci favorisant légèrement l’oxydation des glucides lors de l’effort avec les membres supérieurs. La quantité de glucose exogène oxydée était plus faible lors de l’exercice avec les membres supérieurs qu’avec les membres supérieurs, mais sa contribution plus importante, conséquence d’une dépense énergétique plus faible. Dans la deuxième étude, on a comparé la sélection des substrats chez des sujets mas- culins et féminins et les effets d’une alimentation enrichie en glucides ou de l’ingestion de glucose, au cours d’un exercice prolongé d’une durée de deux heures. On reconnaît généralement que, pour une même puissance relative, les femmes utilisent moins de glucides et davantage de lipides que les hommes. Les effets séparés d’une alimentation riche en glucides ou de l’ingestion de glucose pendant l’exercice sur la sélection des substrats furent pourtant similaires chez les deux sexes. L’effet combiné des deux procédures de supplémentation est toutefois plus important chez la femme que chez l’homme, soutenant l’hypothèse qu’un léger déficit en glucides soit présent chez les femmes. Dans la troisième étude, l’oxydation des substrats et particulièrement celle d’amidon exogène au cours d’une marche prolongée à une faible puissance de travail a été décrite. Les individus qui pratiquent des activités physiques prolongées à des intensités faibles (< 40 %VO2max) sont encouragés à ingérer des glucides et de l’eau pendant l’effort, mais la contribution de leur oxydation à la fourniture d’énergie est relativement peu connue. Nous avons montré que, contrairement aux observations précédemment effectuées à jeun sans ingestion de glucides pendant l’effort, les glucides (incluant de source exogène) peuvent fournir une très grande partie de l’énergie lorsqu’ils sont ingérés à des intervalles réguliers au cours de l’exercice prolongé. Dans l’ensemble, les résultats des études expérimentales présentées dans cette thèse montrent que les glucides ingérés peuvent fournir une grande proportion de l’énergie pendant l’exercice prolongé. Toutefois, le mode d’exercice, le sexe et la puissance de travail mènent à des variations qui sont en grande partie liées à une dépense énergétique variable selon les conditions et les groupes d’individus ayant des caractéristiques différentes.