Decomposition-Based Integer Programming, Stochastic Programming, and Robust Optimization Methods for Healthcare Planning, Scheduling, and Routing Problems

Il existe de nombreuses applications de planification, d'ordonnancement et de confection de tournées dans les systèmes de santé. La résolution efficace de ces problèmes peut aider les responsables de la santé à fournir des services de meilleure qualité, en utilisant efficacement les ressources médicales disponibles. En raison de la nature combinatoire de ces problèmes, dans de nombreux cas, les algorithmes de programmation en nombres entiers standards dans les logiciels commerciaux de programmation mathématique tels que CPLEX et Gurobi ne peuvent pas résoudre efficacement les modèles correspondants. Dans cette thèse, nous étudions trois problèmes de planification, d'ordonnancement et de confection de tournées des soins de santé et proposons des approches à base de décomposition utilisant la programmation en nombres entiers, la programmation stochastique et une méthode d'optimisation robuste. Le premier article de cette thèse présente un problème intégré de planification et d'ordonnancement dans le cadre des salles d'opération. Cette situation implique d'optimiser l'ordonnancement et l'affectation des chirurgies aux différentes salles d'opération, sur un horizon de planification à court terme. Nous avons pris en compte les heures de travail quotidiennes maximales des chirurgiens, le temps de nettoyage obligatoire alloué lors du passage de cas infectieux à des cas non infectieux et le respect des dates limites des chirurgies. Nous avons aussi empêché le chevauchement des chirurgies effectuées par le même chirurgien. Nous avons formulé le problème en utilisant un modèle de programmation mathématique et développé un algorithme «branch-and-price-and-cut» basé sur un modèle de programmation par contraintes pour le sous-problème. Nous avons mis en place des règles de dominance et un algorithme de détection d'infaillibilité rapide. Cet algorithme, basé sur le problème du sac à dos multidimensionnel, nous permet d'améliorer l'efficacité du modèle de programmation de contraintes. Les résultats montrent que notre méthode présente un écart à l'optimum moyen de 2,81%, ce qui surpasse de manière significative la formulation mathématique compacte dans la littérature. Dans la deuxième partie de cette thèse, pour la première fois, nous avons étudié l'optimisation des problèmes de tournées de véhicules avec visites synchronisées (VRPS) en tenant compte de stochasticité des temps de déplacement et de service. En plus d'envisager un problème d'ordonnancement des soins de santé à domicile, nous introduisons un problème d'ordonnancement des salles d'opération avec des durées stochastiques qui est une nouvelle application de VRPS. Nous avons modélisé les VRPS qui ont des durées stochastiques en programmation stochastique à deux niveaux avec des variables entières dans les deux niveaux. L'avantage du modèle proposé est que, contrairement aux modèles déterministes de la littérature VRPS, il n'a pas de contraintes «big-M». Cet avantage entraine en contrepartie la présence d'un grand nombre de variables entières dans le second niveau. Nous avons prouvé que les contraintes d'intégralité sur les variables du deuxième niveau sont triviales ce qui nous permet d'appliquer l'algorithme «L-shaped» et son implémentation branch-and-and-cut pour résoudre le problème. Nous avons amélioré le modèle en développant des inégalités valides et une fonction de bornes inférieures. Nous avons analysé les sous-problèmes de l'algorithme en L et nous avons proposé une méthode de résolution qui est beaucoup plus rapide que les algorithmes de programmation linéaire standards. En outre, nous avons étendu notre modèle pour modéliser les VRPS avec des temps de déplacement et de service dépendant du temps. Les résultats de l'optimisation montrent que, pour le problème stochastique de soins à domicile, l'algorithme «branch-and-cut» résout à l'optimalité les exemplaires avec 15 patients et 10% à 30% de visites synchronisées. Il trouve également des solutions avec un écart à l'optimum moyen de de 3,57% pour les cas avec 20 patients. De plus l'algorithme «branch-and-cut» résout à l'optimalité les problèmes d'ordonnancement stochastique des salles d'opération avec 20 chirurgies. Ceci est une amélioration considérable par rapport à la littérature qui fait état de cas avec 11 chirurgies. En outre, la modélisation proposée pour le problème dépendant du temps trouve des solutions optimales pour d'une grande portion des exemplaires d'ordonnancement de soins de santé à domicile avec 30 à 60 patients et différents taux de visites synchronisées. Dans la dernière partie de cette thèse, nous avons étudié une catégorie de modèles d'optimisation robuste en deux étapes avec des variables entières du problème adversaire. Nous avons analysé l'importance de cette classe de problèmes lors de la modélisation à deux niveaux de problèmes de planification de ressources robuste en deux étapes où certaines tâches ont des temps d'arrivée et des durées incertains. Nous considérons un problème de répartition et d'affectation d'infirmières comme une application de cette classe de modèles robustes. Nous avons appliqué la décomposition de Dantzig-Wolfe pour exploiter la structure de ces modèles, ce qui nous a permis de montrer que le problème initial se réduit à un problème robuste à une seule étape. Nous avons proposé un algorithme Benders pour le problème reformulé. Étant donné que le problème principal et le sous-problème dans l'algorithme Benders sont des programmes à nombres entiers mixtes, il requiert une quantité de calcul importante à chaque itération de l'algorithme pour les résoudre de manière optimale. Par conséquent, nous avons développé de nouvelles conditions d'arrêt pour ces programmes à nombres entiers mixtes et fourni des preuves de convergence. Nous avons développé également un algorithme heuristique appelé «dual algorithm». Dans cette heuristique, nous dualisons la relaxation linéaire du problème adversaire dans le problème reformulé et générons des coupes itérativement pour façonner l'enveloppe convexe de l'ensemble d'incertitude. Nous avons combiné cette heuristique avec l'algorithme Benders pour créer un algorithme plus efficace appelé algorithme «Benders-dual algorithm». De nombreuses expériences de calcul sur le problème de répartition et d'affectation d'infirmières sont effectuées pour comparer ces algorithmes.