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.

Identification of patients at risk of poor outcomes following hip or knee arthroplasty

Les arthroplasties totales de la hanche (ATH) et du genou (ATG) sont souvent offertes aux patients atteints de dégénérescence articulaire sévère. Bien qu’efficace chez la majorité des patients, ces interventions mènent à des résultats sous-optimaux dans de nombreux cas. Il demeure difficile d’identifier les patients à risque de résultats sous-optimaux à l’heure actuelle. L’identification de ces patients avant la chirurgie pourrait permettre d’optimiser la gamme de soins et de services offerts et de possiblement améliorer les résultats de leur chirurgie. Ce mémoire a comme objectifs : 1) de réaliser une revue systématique des déterminants associés à la douleur et aux incapacités fonctionnelles rapportées par les patients à moyen-terme suivant ces deux types d’arthroplastie et 2) de développer des modèles de prédiction clinique permettant l’identification des patients à risque de mauvais résultats en terme de douleur et d’incapacités fonctionnelles suivant l’ATH et l’ATG. Une revue systématique de la littérature identifiant les déterminants de la douleur et de la fonction suivant l’ATH et l’ATG a été réalisée dans quatre bases de données jusqu’en avril 2015 et octobre 2014, respectivement. Afin de développer un algorithme de prédiction pouvant identifier les patients à risque de résultats sous-optimaux, nous avons aussi utilisé des données rétrospectives provenant de 265 patients ayant subi une ATH à l’Hôpital Maisonneuve-Rosemont (HMR) de 2004 à 2010. Finalement, des données prospectives sur 141 patients recrutés au moment de leur inclusion sur une liste d’attente pour une ATG dans trois hôpitaux universitaires à Québec, Canada et suivis jusqu’à six mois après la chirurgie ont permis l’élaboration d’une règle de prédiction clinique permettant l’identification des patients à risque de mauvais résultats en terme de douleur et d’incapacités fonctionnelles. Vingt-deux (22) études d’une qualité méthodologique moyenne à excellente ont été incluses dans la revue. Les principaux déterminants de douleur et d’incapacités fonctionnelles après l’ATH incluaient: le niveau préopératoire de douleur et de fonction, un indice de la masse corporelle plus élevé, des comorbidités médicales plus importantes, un état de santé générale diminué, une scolarité plus faible, une arthrose radiographique moins sévère et la présence d’arthrose à la hanche controlatérale. Trente-quatre (34) études évaluant les déterminants de douleur et d’incapacités fonctionnelles après l’ATG avec une qualité méthodologique moyenne à excellente ont été évaluées et les déterminants suivant ont été identifiés: le niveau préopératoire de douleur et de fonction, des comorbidités médicales plus importantes, un état de santé générale diminué, un plus grands niveau d’anxiété et/ou de symptômes dépressifs, la présence de douleur au dos, plus de pensées catastrophiques ou un faible niveau socioéconomique. Pour la création d’une règle de prédiction clinique, un algorithme préliminaire composé de l’âge, du sexe, de l’indice de masse corporelle ainsi que de trois questions du WOMAC préopératoire a permis l’identification des patients à risque de résultats chirurgicaux sous-optimaux (pire quartile du WOMAC postopératoire et percevant leur hanche opérée comme artificielle avec des limitations fonctionnelles mineures ou majeures) à une durée moyenne ±écart type de 446±171 jours après une ATH avec une sensibilité de 75.0% (95% IC: 59.8 – 85.8), une spécificité de 77.8% (95% IC: 71.9 – 82.7) et un rapport de vraisemblance positif de 3.38 (98% IC: 2.49 – 4.57). Une règle de prédiction clinique formée de cinq items du questionnaire WOMAC préopratoire a permis l’identification des patients en attente d’une ATG à risque de mauvais résultats (pire quintile du WOMAC postopératoire) six mois après l’ATG avec une sensibilité de 82.1 % (95% IC: 66.7 – 95.8), une spécificité de 71.7% (95% IC: 62.8 – 79.8) et un rapport de vraisemblance positif de 2.9 (95% IC: 1.8 – 4.7). Les résultats de ce mémoire ont permis d’identifier, à partir de la littérature, une liste de déterminants de douleur et d’incapacités fonctionnelles après l’ATH et l’ATG avec le plus haut niveau d’évidence à ce jour. De plus, deux modèles de prédiction avec de très bonnes capacités prédictives ont été développés afin d’identifier les patients à risque de mauvais résultats chirurgicaux après l’ATH et l’ATG. L’identification de ces patients avant la chirurgie pourrait permettre d’optimiser leur prise en charge et de possiblement améliorer les résultats de leur chirurgie.

Interrelated product design activities sequencing with efficient tabu search algorithms

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.