Efficient algorithms to solve scheduling problems with a variety of optimization criteria

La programmation par contraintes est une technique puissante pour résoudre, entre autres, des problèmes d’ordonnancement de grande envergure. L’ordonnancement vise à allouer dans le temps des tâches à des ressources. Lors de son exécution, une tâche consomme une ressource à un taux constant. Généralement, on cherche à optimiser une fonction objectif telle la durée totale d’un ordonnancement. Résoudre un problème d’ordonnancement signifie trouver quand chaque tâche doit débuter et quelle ressource doit l’exécuter. La plupart des problèmes d’ordonnancement sont NP-Difficiles. Conséquemment, il n’existe aucun algorithme connu capable de les résoudre en temps polynomial. Cependant, il existe des spécialisations aux problèmes d’ordonnancement qui ne sont pas NP-Complet. Ces problèmes peuvent être résolus en temps polynomial en utilisant des algorithmes qui leur sont propres. Notre objectif est d’explorer ces algorithmes d’ordonnancement dans plusieurs contextes variés. Les techniques de filtrage ont beaucoup évolué dans les dernières années en ordonnancement basé sur les contraintes. La proéminence des algorithmes de filtrage repose sur leur habilité à réduire l’arbre de recherche en excluant les valeurs des domaines qui ne participent pas à des solutions au problème. Nous proposons des améliorations et présentons des algorithmes de filtrage plus efficaces pour résoudre des problèmes classiques d’ordonnancement. De plus, nous présentons des adaptations de techniques de filtrage pour le cas où les tâches peuvent être retardées. Nous considérons aussi différentes propriétés de problèmes industriels et résolvons plus efficacement des problèmes où le critère d’optimisation n’est pas nécessairement le moment où la dernière tâche se termine. Par exemple, nous présentons des algorithmes à temps polynomial pour le cas où la quantité de ressources fluctue dans le temps, ou quand le coût d’exécuter une tâche au temps t dépend de t.

Commande optimale d'un satellite à propulsion électrique utilisant les perturbations pour l'élimination des débris orbitaux en basse altitude

Depuis le lancement du premier satellite Spoutnik 1 en 1957, l’environnement spatial est de plus en plus utilisé et le nombre de débris orbitaux se multiplie naturellement, soit par des explosions, des collisions ou tout simplement par les opérations normales des satellites. Au-delà d'un certain seuil, la densité des débris orbitaux risque de créer une réaction en chaîne incontrôlée : l’effet Kessler. L’élimination des débris orbitaux en basse altitude permettrait de limiter cette réaction et ainsi de préserver l’environnement spatial afin de pouvoir l’utiliser de façon sécuritaire. L’élimination des débris orbitaux est une opération complexe et coûteuse. Elle consiste à déplacer des objets spatiaux inactifs vers une orbite basse pour mener à leur désintégration dans la basse atmosphère terrestre. En utilisant les perturbations orbitales, il est possible de réduire le coût du carburant requis pour effectuer les manœuvres orbitales nécessaires à l’élimination de ces débris. L'objectif principal de cette étude consiste à développer une procédure et une stratégie de commande autonome afin de modifier l'orbite des satellites non opérationnels (débris) pour mener à leur désintégration naturelle tout en optimisant les facteurs carburant et temps. Pour ce faire, un modèle d’atmosphère basé sur le modèle de Jacchia (1977) est développé. Un modèle de la dynamique du satellite inclut aussi les perturbations principales, soit : traînée atmosphérique, non sphéricité et distribution non uniforme de la masse de la Terre. Ces modèles ainsi qu'un algorithme de commande optimale pour un propulseur électrique sont développés et le tout est validé par simulations numériques sur Matlab/Simulink. Au terme de cette étude, les conditions optimales dans lesquelles il faut laisser un débris afin qu'il se désintègre dans la basse atmosphère de la Terre en quelques semaines seront données (type d'orbite : altitude, inclinaison, etc.) ainsi que le coût en carburant pour une telle mission. Cette étude permettra de prouver qu'il est possible de réaliser des missions d'élimination des débris orbitaux tout en réduisant les coûts associés aux manœuvres orbitales par l'utilisation des perturbations naturelles de l'environnement.

Modélisation des structures sandwiches avec un amortissement viscoélastique intégré par une méthode hybride FEM-TMM

Cette thèse traite de la modélisation numérique de la réponse vibro-acoustique de structures sandwiches-composites avec matériaux viscoélastiques intégrés soumises à différents types d’excitations mécaniques et acoustiques. Dans une première phase, nous avons utilisé une approche de synthèse modale pour calculer les principaux indicateurs vibro-acoustiques de la structure : la vitesse quadratique, la puissance rayonnée, la perte par transmission…Ensuite, l’intégrale de Rayleigh a été exploitée pour calculer la puissance rayonnée de chaque structure. L’obstacle majeur que nous avons alors surmonté, était de gérer efficacement la dépendance en fréquence des propriétés de la couche viscoélastique dans l’approche de synthèse modale. Dans une second phase, en partant du champ vibratoire calculé dans la première étape, nous avons développé une méthode hybride FEM-TMM (méthode des éléments finis – méthode de matrices de transfert) pour prédire avec précision et en un temps de calcul acceptable, et jusqu’en hautes fréquences, les principaux paramètres de conception vibro-acoustique de ces structures, notamment l’amortissement équivalent et les nombres d’ondes suivant les deux directions spatiales x et y de propagation de l’onde acoustique. Les validations numériques que nous avons effectuées, montrent bien la robustesse de l'algorithme que nous avons développé. Ce dernier reste toutefois limité à des structures planes. Dans une troisième phase de ce travail, une étude paramétrique sur l’effet de l’emplacement et de la forme de la couche viscoélastique a été réalisée. Cette étude a été faite en se servant de la méthode hybride FEM-TMM pour calculer la réponse acoustique (puissance transmise et perte par transmission).

Réseau calculant asynchrone dédié à la segmentation d'images

National audience

Évaluation de la performance des règles de gestion d'un réservoir de production hydroélectrique mises à jour à l'aide de la programmation dynamique stochastique et d'un modèle hydrologique

L’entreprise Rio Tinto effectue la gestion du système hydrique de la rivière Nechako, situé en Colombie-Britannique (Canada), à partir de règles de gestion optimisées à l’aide d’un algorithme de programmation dynamique stochastique (PDS) et de scénarios d’apports historiques. Les récents développements en recherche opérationnelle tendent à démontrer que la mise à jour des règles de gestion en mode prévisionnel permet d’améliorer la performance des règles de gestion lorsque des prévisions d’ensemble sont utilisées pour mieux cerner les incertitudes associées aux apports à venir. La modélisation hydrologique permet de suivre l’évolution d’un ensemble de processus hydrologiques qui varient dans le temps et dans l’espace (réserve de neige, humidité du sol, etc.). L’utilisation de modèles hydrologiques, en plus d’offrir la possibilité de construire des prévisions d’ensemble qui tiennent compte de l’ensemble des processus simulés, permet de suivre l’évolution de variables d’état qui peuvent être utilisées à même l’algorithme d’optimisation pour construire les probabilités de transition utiles à l’évaluation de la valeur des décisions futures. À partir d’un banc d’essais numériques dans lequel le comportement du bassin versant de la rivière Nechako est simulé à l’aide du modèle hydrologique CEQUEAU, les résultats du présent projet démontrent que la mise à jour des règles avec l’algorithme de PDS en mode prévisionnel permet une amélioration de la gestion du réservoir Nechako lorsque comparée aux règles optimisées avec l’algorithme en mode historique. Le mode prévisionnel utilisant une variable hydrologique combinant un modèle autorégressif d’ordre 5 (AR5) et la valeur maximale de l’équivalent en eau de la neige (ÉENM) a permis de réduire les déversements non-productifs et les inondations tout en maintenant des productions similaires à celles obtenues à l’aide de règles optimisées en mode historique utilisant l’ÉENM comme variable hydrologique. De plus, les résultats du projet démontrent que l’utilisation de prévisions hydrologiques d’ensemble en mode historique pour construire une variable hydrologique permettant d’émettre une prévision du volume d’apport médian pour les huit mois à venir (PVAM) ne permettait pas d’obtenir des résultats de gestion supérieurs à ceux obtenus avec la variable d’ÉENM.

Accumulation de dose à partir de champs de déformation 4D appliqués aux traitements au CyberKnife et à l'IMRT

Le cancer pulmonaire est la principale cause de décès parmi tous les cancers au Canada. Le pronostic est généralement faible, de l'ordre de 15% de taux de survie après 5 ans. Les déplacements internes des structures anatomiques apportent une incertitude sur la précision des traitements en radio-oncologie, ce qui diminue leur efficacité. Dans cette optique, certaines techniques comme la radio-chirurgie et la radiothérapie par modulation de l'intensité (IMRT) visent à améliorer les résultats cliniques en ciblant davantage la tumeur. Ceci permet d'augmenter la dose reçue par les tissus cancéreux et de réduire celle administrée aux tissus sains avoisinants. Ce projet vise à mieux évaluer la dose réelle reçue pendant un traitement considérant une anatomie en mouvement. Pour ce faire, des plans de CyberKnife et d'IMRT sont recalculés en utilisant un algorithme Monte Carlo 4D de transport de particules qui permet d'effectuer de l'accumulation de dose dans une géométrie déformable. Un environnement de simulation a été développé afin de modéliser ces deux modalités pour comparer les distributions de doses standard et 4D. Les déformations dans le patient sont obtenues en utilisant un algorithme de recalage déformable d'image (DIR) entre les différentes phases respiratoire générées par le scan CT 4D. Ceci permet de conserver une correspondance de voxels à voxels entre la géométrie de référence et celles déformées. La DIR est calculée en utilisant la suite ANTs («Advanced Normalization Tools») et est basée sur des difféomorphismes. Une version modifiée de DOSXYZnrc de la suite EGSnrc, defDOSXYZnrc, est utilisée pour le transport de particule en 4D. Les résultats sont comparés à une planification standard afin de valider le modèle actuel qui constitue une approximation par rapport à une vraie accumulation de dose en 4D.

Un modèle pour les algorithmes avec retour sur trace dans les tuteurs par traçage de modèles

La présente thèse décrit des travaux de recherches effectués sur des systèmes tutoriels intelligents (STI) et plus précisément sur les tuteurs par traçage de modèle (MTT). Les travaux de recherche présentés ici s’intéressent à la conception de MTT pour des domaines dans lesquels les étudiants peuvent résoudre la tâche qui leur est assignée de plusieurs façons. Ces domaines comportent parfois des algorithmes avec retour sur trace lorsque l’étudiant ne sait pas forcément quelles sont les alternatives qui feront progresser correctement l’état de la tâche.Cette thèse présente dans un premier temps un système de représentation de connaissances pour les algorithmes avec retour sur trace qui rend les connaissances de cet algorithme exploitables par des agents logiciels. Elle présente dans un second temps un ensemble de processus qui exploitent ces connaissances dans le cadre de MTT pour assurer automatiquement le suivi de l’étudiant et ainsi que la production d’interventions pédagogiques. En premier, ces interventions consistent à fournir à l'étudiant de l’aide pour la prochaine étape qui explique quelles sont les possibilités dont dispose l'étudiant et comment déterminer laquelle est la meilleure. En deuxième, elles fournissent à l'étudiant des rétroactions stratégiques qui lui confirment que son action est valide tout en l’informant de l’existence d’une meilleure alternative le cas échéant. Enfin, elles fournissent à l'étudiant des rétroactions négatives qui lui apprennent dans quelles situations les actions invalides qu’il vient d’effectuer s’appliquent.Une expérimentation a été réalisée avec des étudiants de biologie de l’Université de Sherbrooke pour évaluer les effets de ces interventions sur les choix des étudiants au cours de la résolution de la tâche. Les résultats de cette expérience montrent que les étudiants bénéficiant de ces interventions effectuent plus souvent des choix optimaux, et démontrent ainsi une plus grande maîtrise du domaine.

Utilisation de la tomodensitométrie à deux énergies pour le calcul de dose en curiethérapie à bas débit

Dans la pratique actuelle de la curiethérapie à bas débit, l'évaluation de la dose dans la prostate est régie par le protocole défini dans le groupe de travail 43 (TG-43) de l'American Association of Physicists in Medicine. Ce groupe de travail suppose un patient homogène à base d'eau de même densité et néglige les changements dans l'atténuation des photons par les sources de curiethérapie. En considérant ces simplifications, les calculs de dose se font facilement à l'aide d'une équation, indiquée dans le protocole. Bien que ce groupe de travail ait contribué à l'uniformisation des traitements en curiethérapie entre les hôpitaux, il ne décrit pas adéquatement la distribution réelle de la dose dans le patient. La publication actuelle du TG-186 donne des recommandations pour étudier des distributions de dose plus réalistes. Le but de ce mémoire est d'appliquer ces recommandations à partir du TG-186 pour obtenir une description plus réaliste de la dose dans la prostate. Pour ce faire, deux ensembles d'images du patient sont acquis simultanément avec un tomodensitomètre à double énergie (DECT). Les artéfacts métalliques présents dans ces images, causés par les sources d’iode, sont corrigés à l'aide d’un algorithme de réduction d'artefacts métalliques pour DECT qui a été développé dans ce travail. Ensuite, une étude Monte Carlo peut être effectuée correctement lorsque l'image est segmentée selon les différents tissus humains. Cette segmentation est effectuée en évaluant le numéro atomique effectif et la densité électronique de chaque voxel, par étalonnage stoechiométrique propre au DECT, et en y associant le tissu ayant des paramètres physiques similaires. Les résultats montrent des différences dans la distribution de la dose lorsqu'on compare la dose du protocole TG-43 avec celle retrouvée avec les recommandations du TG-186.

Exploitation du potentiel sismique des étoiles naines blanches

Le but de cette thèse est d’explorer le potentiel sismique des étoiles naines blanches pulsantes, et en particulier celles à atmosphères riches en hydrogène, les étoiles ZZ Ceti. La technique d’astérosismologie exploite l’information contenue dans les modes normaux de vibration qui peuvent être excités lors de phases particulières de l’évolution d’une étoile. Ces modes modulent le flux émergent de l’étoile pulsante et se manifestent principalement en termes de variations lumineuses multi-périodiques. L’astérosismologie consiste donc à examiner la luminosité d’étoiles pulsantes en fonction du temps, afin d’en extraire les périodes, les amplitudes apparentes, ainsi que les phases relatives des modes de pulsation détectés, en utilisant des méthodes standards de traitement de signal, telles que des techniques de Fourier. L’étape suivante consiste à comparer les périodes de pulsation observées avec des périodes générées par un modèle stellaire en cherchant l’accord optimal avec un modèle physique reconstituant le plus fidèlement possible l’étoile pulsante. Afin d’assurer une recherche optimale dans l’espace des paramètres, il est nécessaire d’avoir de bons modèles physiques, un algorithme d’optimisation de comparaison de périodes efficace, et une puissance de calcul considérable. Les périodes des modes de pulsation de modèles stellaires de naines blanches peuvent être généralement calculées de manière précise et fiable sur la base de la théorie linéaire des pulsations stellaires dans sa version adiabatique. Afin de définir dans son ensemble un modèle statique de naine blanche propre à l’analyse astérosismologique, il est nécessaire de spécifier la gravité de surface, la température effective, ainsi que différents paramètres décrivant la disposition en couche de l’enveloppe. En utilisant parallèlement les informations obtenues de manière indépendante (température effective et gravité de surface) par la méthode spectroscopique, il devient possible de vérifier la validité de la solution obtenue et de restreindre de manière remarquable l’espace des paramètres. L’exercice astérosismologique, s’il est réussi, mène donc à la détermination précise des paramètres de la structure globale de l’étoile pulsante et fournit de l’information unique sur sa structure interne et l’état de sa phase évolutive. On présente dans cette thèse l’analyse complète réussie, de l’extraction des fréquences à la solution sismique, de quatre étoiles naines blanches pulsantes. Il a été possible de déterminer les paramètres structuraux de ces étoiles et de les comparer remarquablement à toutes les contraintes indépendantes disponibles dans la littérature, mais aussi d’inférer sur la dynamique interne et de reconstruire le profil de rotation interne. Dans un premier temps, on analyse le duo d’étoiles ZZ Ceti, GD 165 et Ross 548, afin de comprendre les différences entre leurs propriétés de pulsation, malgré le fait qu’elles soient des étoiles similaires en tout point, spectroscopiquement parlant. L’analyse sismique révèle des structures internes différentes, et dévoile la sensibilité de certains modes de pulsation à la composition interne du noyau de l’étoile. Afin de palier à cette sensibilité, nouvellement découverte, et de rivaliser avec les données de qualité exceptionnelle que nous fournissent les missions spatiales Kepler et Kepler2, on développe une nouvelle paramétrisation des profils chimiques dans le coeur, et on valide la robustesse de notre technique et de nos modèles par de nombreux tests. Avec en main la nouvelle paramétrisation du noyau, on décroche enfin le ”Saint Graal” de l’astérosismologie, en étant capable de reproduire pour la première fois les périodes observées à la précision des observations, dans le cas de l’étude sismique des étoiles KIC 08626021 et de GD 1212.

Dynamic Programming Approaches for Estimating and Applying Large-scale Discrete Choice Models

People go through their life making all kinds of decisions, and some of these decisions affect their demand for transportation, for example, their choices of where to live and where to work, how and when to travel and which route to take. Transport related choices are typically time dependent and characterized by large number of alternatives that can be spatially correlated. This thesis deals with models that can be used to analyze and predict discrete choices in large-scale networks. The proposed models and methods are highly relevant for, but not limited to, transport applications. We model decisions as sequences of choices within the dynamic discrete choice framework, also known as parametric Markov decision processes. Such models are known to be difficult to estimate and to apply to make predictions because dynamic programming problems need to be solved in order to compute choice probabilities. In this thesis we show that it is possible to explore the network structure and the flexibility of dynamic programming so that the dynamic discrete choice modeling approach is not only useful to model time dependent choices, but also makes it easier to model large-scale static choices. The thesis consists of seven articles containing a number of models and methods for estimating, applying and testing large-scale discrete choice models. In the following we group the contributions under three themes: route choice modeling, large-scale multivariate extreme value (MEV) model estimation and nonlinear optimization algorithms. Five articles are related to route choice modeling. We propose different dynamic discrete choice models that allow paths to be correlated based on the MEV and mixed logit models. The resulting route choice models become expensive to estimate and we deal with this challenge by proposing innovative methods that allow to reduce the estimation cost. For example, we propose a decomposition method that not only opens up for possibility of mixing, but also speeds up the estimation for simple logit models, which has implications also for traffic simulation. Moreover, we compare the utility maximization and regret minimization decision rules, and we propose a misspecification test for logit-based route choice models. The second theme is related to the estimation of static discrete choice models with large choice sets. We establish that a class of MEV models can be reformulated as dynamic discrete choice models on the networks of correlation structures. These dynamic models can then be estimated quickly using dynamic programming techniques and an efficient nonlinear optimization algorithm. Finally, the third theme focuses on structured quasi-Newton techniques for estimating discrete choice models by maximum likelihood. We examine and adapt switching methods that can be easily integrated into usual optimization algorithms (line search and trust region) to accelerate the estimation process. The proposed dynamic discrete choice models and estimation methods can be used in various discrete choice applications. In the area of big data analytics, models that can deal with large choice sets and sequential choices are important. Our research can therefore be of interest in various demand analysis applications (predictive analytics) or can be integrated with optimization models (prescriptive analytics). Furthermore, our studies indicate the potential of dynamic programming techniques in this context, even for static models, which opens up a variety of future research directions.

Cogestion des ressources naturelles : une approche structurale pour quantifier la contribution des réseaux d'acteurs à la résilience des systèmes socio-écologiques

Alors que les activités anthropiques font basculer de nombreux écosystèmes vers des régimes fonctionnels différents, la résilience des systèmes socio-écologiques devient un problème pressant. Des acteurs locaux, impliqués dans une grande diversité de groupes — allant d’initiatives locales et indépendantes à de grandes institutions formelles — peuvent agir sur ces questions en collaborant au développement, à la promotion ou à l’implantation de pratiques plus en accord avec ce que l’environnement peut fournir. De ces collaborations répétées émergent des réseaux complexes, et il a été montré que la topologie de ces réseaux peut améliorer la résilience des systèmes socio-écologiques (SSÉ) auxquels ils participent. La topologie des réseaux d’acteurs favorisant la résilience de leur SSÉ est caractérisée par une combinaison de plusieurs facteurs : la structure doit être modulaire afin d’aider les différents groupes à développer et proposer des solutions à la fois plus innovantes (en réduisant l’homogénéisation du réseau), et plus proches de leurs intérêts propres ; elle doit être bien connectée et facilement synchronisable afin de faciliter les consensus, d’augmenter le capital social, ainsi que la capacité d’apprentissage ; enfin, elle doit être robuste, afin d’éviter que les deux premières caractéristiques ne souffrent du retrait volontaire ou de la mise à l’écart de certains acteurs. Ces caractéristiques, qui sont relativement intuitives à la fois conceptuellement et dans leur application mathématique, sont souvent employées séparément pour analyser les qualités structurales de réseaux d’acteurs empiriques. Cependant, certaines sont, par nature, incompatibles entre elles. Par exemple, le degré de modularité d’un réseau ne peut pas augmenter au même rythme que sa connectivité, et cette dernière ne peut pas être améliorée tout en améliorant sa robustesse. Cet obstacle rend difficile la création d’une mesure globale, car le niveau auquel le réseau des acteurs contribue à améliorer la résilience du SSÉ ne peut pas être la simple addition des caractéristiques citées, mais plutôt le résultat d’un compromis subtil entre celles-ci. Le travail présenté ici a pour objectifs (1), d’explorer les compromis entre ces caractéristiques ; (2) de proposer une mesure du degré auquel un réseau empirique d’acteurs contribue à la résilience de son SSÉ ; et (3) d’analyser un réseau empirique à la lumière, entre autres, de ces qualités structurales. Cette thèse s’articule autour d’une introduction et de quatre chapitres numérotés de 2 à 5. Le chapitre 2 est une revue de la littérature sur la résilience des SSÉ. Il identifie une série de caractéristiques structurales (ainsi que les mesures de réseaux qui leur correspondent) liées à l’amélioration de la résilience dans les SSÉ. Le chapitre 3 est une étude de cas sur la péninsule d’Eyre, une région rurale d’Australie-Méridionale où l’occupation du sol, ainsi que les changements climatiques, contribuent à l’érosion de la biodiversité. Pour cette étude de cas, des travaux de terrain ont été effectués en 2010 et 2011 durant lesquels une série d’entrevues a permis de créer une liste des acteurs de la cogestion de la biodiversité sur la péninsule. Les données collectées ont été utilisées pour le développement d’un questionnaire en ligne permettant de documenter les interactions entre ces acteurs. Ces deux étapes ont permis la reconstitution d’un réseau pondéré et dirigé de 129 acteurs individuels et 1180 relations. Le chapitre 4 décrit une méthodologie pour mesurer le degré auquel un réseau d’acteurs participe à la résilience du SSÉ dans lequel il est inclus. La méthode s’articule en deux étapes : premièrement, un algorithme d’optimisation (recuit simulé) est utilisé pour fabriquer un archétype semi-aléatoire correspondant à un compromis entre des niveaux élevés de modularité, de connectivité et de robustesse. Deuxièmement, un réseau empirique (comme celui de la péninsule d’Eyre) est comparé au réseau archétypique par le biais d’une mesure de distance structurelle. Plus la distance est courte, et plus le réseau empirique est proche de sa configuration optimale. La cinquième et dernier chapitre est une amélioration de l’algorithme de recuit simulé utilisé dans le chapitre 4. Comme il est d’usage pour ce genre d’algorithmes, le recuit simulé utilisé projetait les dimensions du problème multiobjectif dans une seule dimension (sous la forme d’une moyenne pondérée). Si cette technique donne de très bons résultats ponctuellement, elle n’autorise la production que d’une seule solution parmi la multitude de compromis possibles entre les différents objectifs. Afin de mieux explorer ces compromis, nous proposons un algorithme de recuit simulé multiobjectifs qui, plutôt que d’optimiser une seule solution, optimise une surface multidimensionnelle de solutions. Cette étude, qui se concentre sur la partie sociale des systèmes socio-écologiques, améliore notre compréhension des structures actorielles qui contribuent à la résilience des SSÉ. Elle montre que si certaines caractéristiques profitables à la résilience sont incompatibles (modularité et connectivité, ou — dans une moindre mesure — connectivité et robustesse), d’autres sont plus facilement conciliables (connectivité et synchronisabilité, ou — dans une moindre mesure — modularité et robustesse). Elle fournit également une méthode intuitive pour mesurer quantitativement des réseaux d’acteurs empiriques, et ouvre ainsi la voie vers, par exemple, des comparaisons d’études de cas, ou des suivis — dans le temps — de réseaux d’acteurs. De plus, cette thèse inclut une étude de cas qui fait la lumière sur l’importance de certains groupes institutionnels pour la coordination des collaborations et des échanges de connaissances entre des acteurs aux intérêts potentiellement divergents.

Optimization models and methods for real-time transportation planning in forestry

Lors du transport du bois de la forêt vers les usines, de nombreux événements imprévus peuvent se produire, événements qui perturbent les trajets prévus (par exemple, en raison des conditions météo, des feux de forêt, de la présence de nouveaux chargements, etc.). Lorsque de tels événements ne sont connus que durant un trajet, le camion qui accomplit ce trajet doit être détourné vers un chemin alternatif. En l’absence d’informations sur un tel chemin, le chauffeur du camion est susceptible de choisir un chemin alternatif inutilement long ou pire, qui est lui-même "fermé" suite à un événement imprévu. Il est donc essentiel de fournir aux chauffeurs des informations en temps réel, en particulier des suggestions de chemins alternatifs lorsqu’une route prévue s’avère impraticable. Les possibilités de recours en cas d’imprévus dépendent des caractéristiques de la chaîne logistique étudiée comme la présence de camions auto-chargeurs et la politique de gestion du transport. Nous présentons trois articles traitant de contextes d’application différents ainsi que des modèles et des méthodes de résolution adaptés à chacun des contextes. Dans le premier article, les chauffeurs de camion disposent de l’ensemble du plan hebdomadaire de la semaine en cours. Dans ce contexte, tous les efforts doivent être faits pour minimiser les changements apportés au plan initial. Bien que la flotte de camions soit homogène, il y a un ordre de priorité des chauffeurs. Les plus prioritaires obtiennent les volumes de travail les plus importants. Minimiser les changements dans leurs plans est également une priorité. Étant donné que les conséquences des événements imprévus sur le plan de transport sont essentiellement des annulations et/ou des retards de certains voyages, l’approche proposée traite d’abord l’annulation et le retard d’un seul voyage, puis elle est généralisée pour traiter des événements plus complexes. Dans cette ap- proche, nous essayons de re-planifier les voyages impactés durant la même semaine de telle sorte qu’une chargeuse soit libre au moment de l’arrivée du camion à la fois au site forestier et à l’usine. De cette façon, les voyages des autres camions ne seront pas mo- difiés. Cette approche fournit aux répartiteurs des plans alternatifs en quelques secondes. De meilleures solutions pourraient être obtenues si le répartiteur était autorisé à apporter plus de modifications au plan initial. Dans le second article, nous considérons un contexte où un seul voyage à la fois est communiqué aux chauffeurs. Le répartiteur attend jusqu’à ce que le chauffeur termine son voyage avant de lui révéler le prochain voyage. Ce contexte est plus souple et offre plus de possibilités de recours en cas d’imprévus. En plus, le problème hebdomadaire peut être divisé en des problèmes quotidiens, puisque la demande est quotidienne et les usines sont ouvertes pendant des périodes limitées durant la journée. Nous utilisons un modèle de programmation mathématique basé sur un réseau espace-temps pour réagir aux perturbations. Bien que ces dernières puissent avoir des effets différents sur le plan de transport initial, une caractéristique clé du modèle proposé est qu’il reste valable pour traiter tous les imprévus, quelle que soit leur nature. En effet, l’impact de ces événements est capturé dans le réseau espace-temps et dans les paramètres d’entrée plutôt que dans le modèle lui-même. Le modèle est résolu pour la journée en cours chaque fois qu’un événement imprévu est révélé. Dans le dernier article, la flotte de camions est hétérogène, comprenant des camions avec des chargeuses à bord. La configuration des routes de ces camions est différente de celle des camions réguliers, car ils ne doivent pas être synchronisés avec les chargeuses. Nous utilisons un modèle mathématique où les colonnes peuvent être facilement et naturellement interprétées comme des itinéraires de camions. Nous résolvons ce modèle en utilisant la génération de colonnes. Dans un premier temps, nous relaxons l’intégralité des variables de décision et nous considérons seulement un sous-ensemble des itinéraires réalisables. Les itinéraires avec un potentiel d’amélioration de la solution courante sont ajoutés au modèle de manière itérative. Un réseau espace-temps est utilisé à la fois pour représenter les impacts des événements imprévus et pour générer ces itinéraires. La solution obtenue est généralement fractionnaire et un algorithme de branch-and-price est utilisé pour trouver des solutions entières. Plusieurs scénarios de perturbation ont été développés pour tester l’approche proposée sur des études de cas provenant de l’industrie forestière canadienne et les résultats numériques sont présentés pour les trois contextes.

Algorithmique et complexité des systèmes à compteurs

Réalisé en cotutelle avec l'École normale supérieure de Cachan – Université Paris-Saclay

Algorithmes de construction et correction d'arbres de gènes par la réconciliation

Les gènes, qui servent à encoder les fonctions biologiques des êtres vivants, forment l'unité moléculaire de base de l'hérédité. Afin d'expliquer la diversité des espèces que l'on peut observer aujourd'hui, il est essentiel de comprendre comment les gènes évoluent. Pour ce faire, on doit recréer le passé en inférant leur phylogénie, c'est-à-dire un arbre de gènes qui représente les liens de parenté des régions codantes des vivants. Les méthodes classiques d'inférence phylogénétique ont été élaborées principalement pour construire des arbres d'espèces et ne se basent que sur les séquences d'ADN. Les gènes sont toutefois riches en information, et on commence à peine à voir apparaître des méthodes de reconstruction qui utilisent leurs propriétés spécifiques. Notamment, l'histoire d'une famille de gènes en terme de duplications et de pertes, obtenue par la réconciliation d'un arbre de gènes avec un arbre d'espèces, peut nous permettre de détecter des faiblesses au sein d'un arbre et de l'améliorer. Dans cette thèse, la réconciliation est appliquée à la construction et la correction d'arbres de gènes sous trois angles différents: 1) Nous abordons la problématique de résoudre un arbre de gènes non-binaire. En particulier, nous présentons un algorithme en temps linéaire qui résout une polytomie en se basant sur la réconciliation. 2) Nous proposons une nouvelle approche de correction d'arbres de gènes par les relations d'orthologie et paralogie. Des algorithmes en temps polynomial sont présentés pour les problèmes suivants: corriger un arbre de gènes afin qu'il contienne un ensemble d'orthologues donné, et valider un ensemble de relations partielles d'orthologie et paralogie. 3) Nous montrons comment la réconciliation peut servir à "combiner'' plusieurs arbres de gènes. Plus précisément, nous étudions le problème de choisir un superarbre de gènes selon son coût de réconciliation.

Un modèle rétroactif de réconciliation utilité-confidentialité sur les données d’assurance

Le partage des données de façon confidentielle préoccupe un bon nombre d’acteurs, peu importe le domaine. La recherche évolue rapidement, mais le manque de solutions adaptées à la réalité d’une entreprise freine l’adoption de bonnes pratiques d’affaires quant à la protection des renseignements sensibles. Nous proposons dans ce mémoire une solution modulaire, évolutive et complète nommée PEPS, paramétrée pour une utilisation dans le domaine de l’assurance. Nous évaluons le cycle entier d’un partage confidentiel, de la gestion des données à la divulgation, en passant par la gestion des forces externes et l’anonymisation. PEPS se démarque du fait qu’il utilise la contextualisation du problème rencontré et l’information propre au domaine afin de s’ajuster et de maximiser l’utilisation de l’ensemble anonymisé. À cette fin, nous présentons un algorithme d’anonymat fortement contextualisé ainsi que des mesures de performances ajustées aux analyses d’expérience.