Olivier Gerard soutiendra sa thèse le jeudi 24 novembre à 10h dans l’amphithéâtre Parmentier, à l’UFR de Science d'Amiens.
Résumé
Dans cette thèse, nous nous sommes intéressés à un problème de planification du parcours de soin du patient, proposé par l'entreprise Evolucare Technologies. L'objectif de l'entreprise est de fournir un logiciel capable de produire des plannings respectant les diverses contraintes et répondant au mieux aux souhaits des patients et des équipes soignantes. Le projet LORH incarne la réponse d'Evolucare à ce problème, que nous avons étudié et pour lequel nous avons proposé plusieurs méthodes de résolution. Ce problème NP-difficile est proche du Resource Constraint Project Scheduling Problem (RCPSP), une problématique reconnue de la littérature.
Nous avons en premier lieu décrit formellement la problématique et élaboré la fonction objectif. Notre première approche est un modèle de programmation linéaire en nombre entier 0-1 intégrant l'ensemble des variables et des contraintes du problème. Les solutions initiales requises pour nos méthodes de résolution ont été obtenues avec un algorithme de construction aléatoire. Notre seconde approche est une recherche locale nommée Adaptive Large Neighborhood Search (ALNS) utilisant un ensemble de mouvements développés spécifiquement pour ce problème. Nous avons ensuite proposé un algorithme génétique, et des opérations de croisement et de mutation adaptées à notre problématique. Enfin, notre dernière méthode est également un algorithme génétique, avec une gestion de la diversité des solutions pour limiter le phénomène de convergence précoce vers des optimums locaux.
Nous avons évalué ces méthodes sur un ensemble d'instances générées à partir de problèmes rapportés par Evolucare. Le modèle de programmation linéaire, implémenté sous CPLEX, nous a permis d'obtenir la solution optimale sur certaines de nos instances. Nous avons ensuite obtenu avec l’ALNS des solutions optimales supplémentaires et de meilleures bornes supérieures sur toutes nos familles d'instances. Ces résultats ont été améliorés successivement par l’algorithme génétique classique et l’algorithme génétique avec gestion de la diversité, avec un gain de 16.42% entre l’ALNS et ce dernier. Nous avons également évalué nos méthodes sur les instances de la littérature RCPSP et obtenu un écart moyen de 5.4% avec les solutions optimales avec nos deux algorithmes génétiques.
Jury
Mme. Sandra BRINGAY, Professeure des universités, Université Paul-Valéry Montpellier 3 -- Rapporteur
M. Antoine JOUGLET, Professeur des universités, Université de Technologie de Compiègne -- Rapporteur
M. François DELBOT, Maître de conférences, Université Paris Ouest Nanterre -- Examinateur
M. Gilles DEQUEN, Professeur des universités, Université de Picardie Jules Verne -- Examinateur
Mme. Corinne LUCET, Maîtresse de conférences, Université de Picardie Jules Verne -- Directrice de thèse
Mme. Laure BRISOUX-DEVENDEVILLE, Maîtresse de conférences, Université de Picardie Jules Verne -- Co-directrice de thèse
M. Sylvain DARRAS, Docteur, Evolucare Technologies -- Invité.
