Étude d'un problème de tournées de véhicules sur les arcs avec contraintes de capacité et coûts de service dépendants du temps

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

Génération efficace de graphes d’appels dynamiques complets

Analyser le code permet de vérifier ses fonctionnalités, détecter des bogues ou améliorer sa performance. L’analyse du code peut être statique ou dynamique. Des approches combinants les deux analyses sont plus appropriées pour les applications de taille industrielle où l’utilisation individuelle de chaque approche ne peut fournir les résultats souhaités. Les approches combinées appliquent l’analyse dynamique pour déterminer les portions à problèmes dans le code et effectuent par la suite une analyse statique concentrée sur les parties identifiées. Toutefois les outils d’analyse dynamique existants génèrent des données imprécises ou incomplètes, ou aboutissent en un ralentissement inacceptable du temps d’exécution. Lors de ce travail, nous nous intéressons à la génération de graphes d’appels dynamiques complets ainsi que d’autres informations nécessaires à la détection des portions à problèmes dans le code. Pour ceci, nous faisons usage de la technique d’instrumentation dynamique du bytecode Java pour extraire l’information sur les sites d’appels, les sites de création d’objets et construire le graphe d’appel dynamique du programme. Nous démontrons qu’il est possible de profiler dynamiquement une exécution complète d’une application à temps d’exécution non triviale, et d’extraire la totalité de l’information à un coup raisonnable. Des mesures de performance de notre profileur sur trois séries de benchmarks à charges de travail diverses nous ont permis de constater que la moyenne du coût de profilage se situe entre 2.01 et 6.42. Notre outil de génération de graphes dynamiques complets, nommé dyko, constitue également une plateforme extensible pour l’ajout de nouvelles approches d’instrumentation. Nous avons testé une nouvelle technique d’instrumentation des sites de création d’objets qui consiste à adapter les modifications apportées par l’instrumentation au bytecode de chaque méthode. Nous avons aussi testé l’impact de la résolution des sites d’appels sur la performance générale du profileur.

Problèmes de comportement à long terme chez les patients pédiatriques atteints de leucémie lymphoblastique aiguë

Les améliorations dans les protocoles de traitement pour la majorité des cancers pédiatriques ont augmenté de façon marquée les taux de survie. Cependant, des risques élevés de multiples problèmes de santé chez les survivants sont bien documentés. En ce qui concerne spécifiquement les problèmes neuropsychologiques, les principaux facteurs de risque individuels connus à ce jour (l’âge au diagnostic, le genre du patient, l’exposition aux radiations) demeurent insuffisants pour cibler efficacement et prévenir les séquelles à long terme. Les objectifs généraux de cette thèse étaient : 1) la caractérisation des trajectoires individuelles de problèmes de comportement chez une population de patients pédiatriques atteints de leucémie lymphoblastique aiguë; 2) l’identification des principaux déterminants génétiques, médicaux et psychosociaux associés aux problèmes de comportements. Les hypothèses étaient : 1) Il existe une association entre les trajectoires individuelles de problèmes de comportement et a - des facteurs psychosociaux liés au fonctionnement familial, b - des polymorphismes dans les gènes modérateurs des effets thérapeutiques du méthotrexate et des glucocorticoïdes, c - des variables liées aux traitements oncologiques. 2) L'utilisation de modèles statistiques multi-niveaux peut permettre d’effectuer cette caractérisation des trajectoires individuelles et l’identification des facteurs de risque associés. 138 patients pédiatriques (0-18 ans) ayant reçu un diagnostic de leucémie lymphoblastique aiguë entre 1993 et 1999 au CHU Ste-Justine ont participé à une étude longitudinale d’une durée de 4 ans. Un instrument validé et standardisés, le Child Behavior Checklist, a été utilisé pour obtenir un indice de problèmes de comportement, tel que rapporté par la mère, au moment du diagnostic, puis 1, 2, 3 et 4 ans post-diagnostic. Des données génétiques, psychosociales et médicales ont aussi été collectées au cours de cette même étude longitudinale, puis ont été exploitées dans les modélisations statistiques effectuées. Les résultats obtenus suggèrent que les problèmes de comportement de type internalisés et externalisés possèdent des trajectoires et des facteurs de risque distincts. Les problèmes internalisés sont des manifestations de troubles affectifs chez le patient, tels que des symptômes dépressifs ou anxieux, par exemple. Ceux-ci sont très prévalents tôt après le diagnostic et se normalisent par la suite, indiquant des difficultés significatives, mais temporaires. Des facteurs médicaux exacerbant l'expérience de stress, soit le risque de rechute associé au diagnostic et les complications médicales affectant la durée de l'hospitalisation, ralentissent cette normalisation. Les problèmes externalisés se manifestent dans le contact avec autrui; des démonstrations d’agression ou de violence font partie des symptômes. Les problèmes externalisés sont plus stables dans le temps relativement aux problèmes internalisés. Des variables pharmacologiques et génétiques contribuent aux différences individuelles : l'administration d’un glucocorticoïde plus puissant du point de vue des effets pharmacologiques et toxicologiques, ainsi que l’homozygotie pour l’haplotype -786C844T du gène NOS3 sont liés à la modulation des scores de problèmes externalisés au fil du temps. Finalement, le niveau de stress familial perçu au diagnostic est positivement corrélé avec le niveau initial de problèmes externalisés chez le patient, tandis que peu après la fin de la période d’induction, le niveau de stress familial est en lien avec le niveau initial de problèmes internalisés. Ces résultats supportent l'idée qu'une approche holistique est essentielle pour espérer mettre en place des interventions préventives efficaces dans cette population. À long terme, ces connaissances pourraient contribuer significativement à l'amélioration de la qualité de vie des patients. Ces travaux enrichissent les connaissances actuelles en soulignant les bénéfices des suivis longitudinaux et multidisciplinaires pour comprendre la dynamique de changement opérant chez les patients. Le décloisonnement des savoirs semble devenir incontournable pour aspirer dépasser le cadre descriptif et atteindre un certain niveau de compréhension des phénomènes observés. Malgré des défis méthodologiques et logistiques évidents, ce type d’approche est non seulement souhaitable pour étudier des processus dynamiques, mais les travaux présentés dans cette thèse indiquent que cela est possible avec les moyens analytiques actuels.

Avantages comparés dynamiques. Impact du Tokyo Round sur le commerce extérieur des États-Unis (période : 1970-1992).

Rapport de recherche

Évaluation des performances de couverture d'un GARCH multivarié à corrélations conditionnelles dynamiques de type Engle (2002).

Rapport de recherche

Identification, Weak Instruments and Statistical Inference in Econometrics

We discuss statistical inference problems associated with identification and testability in econometrics, and we emphasize the common nature of the two issues. After reviewing the relevant statistical notions, we consider in turn inference in nonparametric models and recent developments on weakly identified models (or weak instruments). We point out that many hypotheses, for which test procedures are commonly proposed, are not testable at all, while some frequently used econometric methods are fundamentally inappropriate for the models considered. Such situations lead to ill-defined statistical problems and are often associated with a misguided use of asymptotic distributional results. Concerning nonparametric hypotheses, we discuss three basic problems for which such difficulties occur: (1) testing a mean (or a moment) under (too) weak distributional assumptions; (2) inference under heteroskedasticity of unknown form; (3) inference in dynamic models with an unlimited number of parameters. Concerning weakly identified models, we stress that valid inference should be based on proper pivotal functions —a condition not satisfied by standard Wald-type methods based on standard errors — and we discuss recent developments in this field, mainly from the viewpoint of building valid tests and confidence sets. The techniques discussed include alternative proposed statistics, bounds, projection, split-sampling, conditioning, Monte Carlo tests. The possibility of deriving a finite-sample distributional theory, robustness to the presence of weak instruments, and robustness to the specification of a model for endogenous explanatory variables are stressed as important criteria assessing alternative procedures.

La technologie de l’information et les avantages comparés dynamiques, le cas américain.

Rapport de recherche

Les investissements en technologies flexibles de production: problèmes d'évaluation et considérations stratégiques.

Rapport de recherche