Problème dynamique de transports de patients

Le problème abordé a pour objectif d’optimiser les tournées des ambulances de manière à minimiser les coûts de transports dépendant de deux facteurs principaux : les appels aux ambulances privées et les frais kilométriques. L’effectif des ambulanciers est supposé constant pour l’optimisation des tournées puisque le nombre d’ambulanciers est déterminé par le deuxième problème étudié. Néanmoins les demandes en ambulanciers émanant du  ne sont pas à négliger pour résoudre ce problème. L’objectif est d’affecter les demandes de transports aux équipes ambulancières. Les équipes et leurs horaires de travail sont ffixés à l’avance, mais de manière à être plus réaliste, quelques heures/minutes supplémentaires pourront être autorisés. Chaque équipe se voit affecter un lieu de départ et un véhicule à sa prise de fonction, mais elle pourra en changer en cours de journée en fonction des transports à effectuer. Il existe deux types de véhicules, les véhicules usuels, dits de type C et les véhicules médicalisés, dits de type A. Leurs nombres sont limités et chaque véhicule est assigné à un dépôt. Les demandes de transports arrivent à la centrale au l de l’eau durant toute la journée, elles peuvent se distinguer par le type de véhicule nécessaire et un caractère d’urgence. Certaines demandes proviennent des services de soins du CHRU, tandis que d’autres émanent du SAMU. Ces dernières ont la particularité d’être extrêmement prioritaires et de n’être connues que très peu de temps à l’avance. Une demande de transport de patient est caractérisée par un lieu de départ, un lieu d’arrivée, une durée de prise en charge du patient hors véhicule, une fenêtre de temps dépendante du niveau de priorité de la demande, et un type de transport. Il existe trois types de transports : classique, contagieux et médicalisé. Dans le cas classique, le transport peut être effectué par un véhicule de type A ou C. Dans le cas d’un transport contagieux, un véhicule de type C doit être utilisé et le véhicule doit être désinfecté par l’équipe avant de pouvoir être réutilisé. Cependant, étant donné que l’opération de désinfection dure une heure, l’équipe peut la différer et utiliser un autre véhicule en attendant de revenir plus tard réaliser la désinfection. Enfin, un transport médicalisé nécessite un véhicule de type A plus spacieux qui peut accueillir du matériel médical. Il s’agit de transports de patients dans un état critique avec la surveillance d’un médecin de l’unité de soins d’origine durant tout le trajet. Après le transport du patient, il faut ramener le médecin à son unité d’origine mais ce retour peut s’effectuer avec un autre patient pour gagner du temps. Quand la charge de travail est plus importante que la capacité de réponse de la Centrale des Ambulanciers, les régulateurs font appel à des compagnies privées, mais cette sous-traitance induit un surcoût non négligeable qui dépend uniquement du trajet du patient. Ce coût peut donc être estimé pour chaque demande à l’avance. Chaque demande assurée par le CHRU engendre uniquement des frais kilométriques. Une solution du problème est donc une affectation des demandes aux véhicules du CHRU ou aux compagnies privées. Même si toutes les demandes étaient connues à l’avance, la tâche ne serait pas simple. Or là, seuls 30% des transports sont programmés en début de matinée pour la journée même, les autres demandes de transports arrivent en temps réel. Donc un aspect dynamique apparaît en plus pour ce problème.

Dimensionnement et d’affection des ambulanciers 

Le problème de dimensionnement et d’affectation des ambulanciers est fortement lié à l’activité aléatoire du SAMU. Ses interventions ne peuvent pas être connues à l’avance. Même si deux types d’activités jour et nuit se dégagent, les heures d’interventions et leur nombre sont difficiles à prévoir ou même à estimer. De plus, pour chaque intervention, plusieurs procédures se dégagent, selon la gravité, qui ne nécessitent pas les mêmes ressources. Des règles dépendant principalement de l’état du patient et des situations géographiques, déterminent le type de secours à envoyer et donc la nécessité d’ambulanciers ou non. Le problème consiste à trouver la meilleure organisation pour le CHRU de Tours en terme de coût mais aussi de qualité de transport (temps d’attente, envoie de secours, etc.). Une organisation pour ce problème est dénie par non seulement un nombre d’ambulanciers au SAMU et à la CA mais aussi par leurs horaires et par une politique de gestion des ambulanciers affectée au SAMU. Cette politique de gestion délimite les interventions possibles d’un ou plusieurs ambulanciers au SAMU : Peut-il faire du transport primaire ou secondaire ? Adulte ou Pédiatrique ? Enfin un autre point à déterminer dans cette organisation est le nombre d’ambulanciers envoyés par la CA suite à une demande de SAMU. Par défaut, les ambulanciers sont envoyés par paires puisqu’ils constituent une équipe pour la CA, mais d’après le SAMU un seul ambulancier est nécessaire pour la plupart des interventions.

Littérature autour de ce problème 

Cette partie présente la littérature autour de ce problème, ou plus exactement de ces deux sous-problèmes qui ne sont pas de même nature. Le premier sous-problème appartient à la classe des problèmes de transports dont la littérature est abondante et s’enrichit chaque année. Alors que pour le deuxième problème, la littérature est très restreinte puisque ce problème est particulier et spécifique au contexte du CHRU de Tours. Cet état de l’art qui a pour objectif de situer le problème par rapport à la littérature existante est décomposé de la manière suivante :  Problèmes de tournées sur arcs ;  Problèmes de tournées sur noeuds ;  Le problème du voyageur de commerce ;  Problèmes de transports dans le milieu hospitalier. Une introduction générale sur les problèmes de transports a été réalisée dans la section 2.2 du chapitre 2. Le problème dynamique de transports de patients appartient à la classe des problèmes de tournées de véhicules (à la catégorie des « Pickup and Delivery Problems »). Sur la gure 2.3 de la section 2.2, notre problème se situe entre le DARP (Dial A Ride Problem) et le SCP (Stacker Crane Problem). Si nous utilisons la notation présentée dans cette section, notre problème serait noté [ 1-1 | P/D | m ]. Il existe deux grandes classes de problèmes de planication de tournées : les problèmes de tournées sur arc et les problèmes de tournées sur noeuds. Les paragraphes suivants présentent l’intersection non vide de chacune de ces classes avec le problème de transports de patients.

 Problèmes de tournées sur arcs

 Le problème de transports de patients peut être vu sous la forme d’un problème de tournées sur arcs. Il sut de considérer un graphe déni par un ensemble de sommets (dépôts des véhicules, points de départ des patients, points d’arrivées des patients), un ensemble d’arêtes entre chaque sommet de manière à rendre le graphe connexe, et un ensemble d’arcs pour chaque demande de transport de patient du sommet origine vers le sommet destination. L’objectif est de trouver l’itinéraire de chaque véhicule tel que chaque arcs soit traversé une seule fois par un véhicule. Ce type de représentation se rapproche du problème du postier chinois mixte, du problème du postier rural mixte, ou encore du Stacker Crane Problem. Le problème simple et classique de tournées sur arcs consiste à trouver dans un graphe non orienté un cycle passant par toutes les arêtes, ou dans le cas d’un graphe orienté un circuit passant par tous les arcs. Ce problème est connu sous le nom du problème du postier chinois ([92] ou [67]). La complexité de ce problème dépend du graphe. Pour un graphe uniquement constitué d’arêtes ou d’arcs, le problème est polynomial. Cependant pour un graphe constitué d’arêtes et d’arcs le problème (problème du postier chinois mixte) devient NP-Dicile comme le montre Papadimitriou [156] à l’aide d’une réduction pseudo polynomiale vers le problème 3-SAT. Le problème des k-postiers chinois mixtes, introduit par Pearn [158], est assez proche de notre problème. L’objectif de ce problème est de trouver, en minimisant un critère donné, les k routes des postiers partant d’un même sommet de départ dans un graphe sachant que chaque arc et arête fait partie d’au moins une route d’un postier. Dans les articles de Pearn [158] et Zhang [200], les auteurs montrent certains cas polynomiaux du problème : graphe avec uniquement des arcs, graphe avec uniquement des arêtes, ou encore d’autres cas dépendants de la parité du graphe, de son caractère « Eulérien », des distances , etc. Cependant dans notre problème ces circuits doivent passer uniquement une fois par un sous-ensemble d’arc, c’est le cas du problème du postier rural mixte. Ce dernier consiste à trouver dans un graphe non orienté un cycle passant par un sous-ensemble d’arêtes, ou dans le cas d’un graphe orienté un circuit passant par un sous-ensemble d’arcs. Dans les articles de Romero [169] et Corberán et al. [41], des méthodes exactes pour résoudre ce problème avec seulement un postier sont présentées. Dans un autre article de Corberán et al. [40], deux méthodes heuristiques sont exposées : l’une est basée sur la résolution de problèmes de ot et d’appariement, et l’autre est une recherche tabou avec une phase d’intensication et deux niveaux de diversication. Ce même problème avec en plus des pénalités pour certains tours, voire des interdictions, a été étudié par Corberán et al. [39]. Dans cet article, il propose une transformation polynomiale en un problème de voyageur de commerce asymétrique et une heuristique de résolution basée sur deux autres heuristiques de la littérature sur ce problème sans les pénalités. Parmi les extensions de ce problème, il existe le problème du postier rural avec des « classes » de dates de n (cf. [135]). Ces classes introduisent la contrainte suivante : à chaque arête est associée une date avant laquelle elle doit être parcourue par le postier. Dans l’article de Letchford et Eglese , les auteurs présentent un modèle de programmation linéaire en nombres entiers (PLNE) pour ce problème et sa résolution par la méthode des plans sécants. Le problème intitulé « Stacker Crane Problem » consiste à trouver un circuit de coût minimal passant par tous les arcs d’un graphe dont tous les sommets sont reliés entre eux par des arêtes. C’est un cas particulier du problème précédent. Il a été étudié dans un premier temps par Frederickson et al. [77], qui a montré la complexité du problème (NP-dicile par transformation avec le problème du voyageur de commerce). L’auteur a également mis au point une heuristique avec une garantie de performance de 4/3 (ratio d’approximation). Dans un article de Righini et Trubian , les auteurs proposent d’autres heuristiques avec des résultats théoriques pour chacune d’entre elles en considérant un cas plus général du problème (la possibilité d’inégalité triangulaire). Enn dans l’article de Coja-Oghlan et al., les auteurs s’intéressent à un cas particulier de ce problème, le « Stacker Crane Problem on trees », et mettent au point une heuristique qui, d’après eux, est très proche de l’optimal voire exacte. Toutefois, les problèmes de transports à la personne avec des véhicules de capacité unitaire, sont très peu abordés dans la littérature sous cette forme de problème. De plus, les diverses extensions des problèmes à tournée sur arcs restent encore éloignés de notre problème de transports de patients en considérant toutes les contraintes.

Problèmes de tournées sur noeuds 

Les problèmes de tournées sur noeuds sont beaucoup plus étudiés dans la littérature que les problèmes de tournées sur arcs. La famille des problèmes de tournées sur noeuds pour le transport de personnes est appelé Dial a Ride Problem (DARP). Ce problème consiste à déterminer les tournées de véhicules pour transporter toutes les personnes de leurs lieux de départ vers leurs lieux de destination en respectant la capacité des véhicules. Ce problème est aussi basé sur un graphe généralement connexe et dont les sommets correspondent aux lieux de départs et d’arrivées des personnes. Le DARP est un problème particulier du VRPPD (« Vehicle Routing Problem with Pickup and Delivery »), une des premières études sur ce problème a été réalisée par Stein . Contrairement aux VRPPD, les DARP s’appliquent aux transports de personnes et non de marchandises. Cette particularité se traduit par la restriction suivante : une personne à transporter a un seul sommet de départ et un seul sommet de destination possible. L’une des premières études sur le DARP a été réalisée par Psaraftis [162] pour le cas d’un seul véhicule, et Jaw et al. [105] dans le cas de plusieurs véhicules. Une étude complète et assez récente sur la littérature des DARP (modèles et algorithmes) est disponible dans l’article de Cordeau et Laporte [44]. Dans cet article, les auteurs rappellent les trois modèles mathématiques existants avec leurs résolutions optimales :  Cordeau formule ce problème sous forme de PLNE en prenant en compte deux dépôts, une quantité de personnes à chaque sommet, une durée de service à chaque sommet, une capacité pour chaque véhicule, un temps de trajet maximal pour chaque véhicule, un coût de transport pour chaque arc dépendant du véhicule, un temps de trajet maximal pour chaque personne, et des fenêtres de temps pour chaque demande. 133 6.2. LITTÉRATURE AUTOUR DE CE PROBLÈME La fonction objectif est de minimiser la somme totale des coûts de transports. L’auteur propose une procédure par séparation et évaluation pour résoudre ce problème.  Ropke et al. [170] présentent quant à eux deux modèles résolus aussi à l’aide d’une procédure par séparation et évaluation. Leurs modèles tiennent compte d’une otte de véhicules homogènes, de fenêtres de temps, un temps de trajet maximal pour chaque personne, et une quantité de personnes à chaque sommet. L’objectif est aussi de minimiser la somme totale des coûts de transports.  Enn la dernière formulation concerne uniquement le problème d’ordonnancement des visites des clients dans une seule route : déterminer la séquence des clients assurés par un véhicule qui minimise son temps de trajet. Etant donné un véhicule, le but est de calculer l’heure de départ du dépôt et le temps de début de chaque service à chaque sommet de la route tel que les fenêtres de temps soient respectées et la durée de route minimisée [174]. De nombreux problèmes appartenant à la famille des DARP avec plusieurs véhicules ont été étudiés. Dans l’article de Cordeau et Laporte [43], les auteurs considèrent ce type de problème avec des fenêtres de temps pour les demandes, des capacités propres à chaque véhicule, et des durées de trajets maximales aussi bien pour les personnes que pour les véhicules. Ils proposent une recherche tabou pour résoudre ce problème. Durant la recherche de solutions, des solutions irréalisables (qui violent la contrainte des capacités du véhicule ou des fenêtres de temps) peuvent être explorées. L’évaluation des solutions est une combinaison linéaire entre la somme des coûts de chaque route et de fonctions évaluant le niveau des contraintes violées. Les coecients de la combinaison linéaire aectés à ces fonctions augmentent avec le nombre d’itérations de manière à obtenir une solution réalisable à la n de l’algorithme. Sachant qu’une solution est représentée par un ensemble de couples : numéro de véhicule et numéro de demande de transport, l’opérateur de voisinage consiste à changer le numéro de véhicule d’un couple. Cette opération revient à supprimer un sommet d’une route et à l’ajouter dans une autre route selon une procédure basée sur le calcul du « forward time slack » d’un sommet (cf. [174]). Tout le voisinage d’une solution n’est pas exploré entièrement, une règle s’appuyant sur des sommets critiques permet de diminuer l’ensemble des solutions à explorer. Enn, en plus du critère d’aspiration (rendre possible l’exploration de solution tabou si elle améliore la meilleure solution trouvée), la recherche tabou possède une phase de diversication (forcer la recherche de solutions vers d’autres voisinages pas encore ou peu explorés). Une autre étude se basant sur les mêmes contraintes du problème précédent, excepté le temps de trajet maximal, a été menée par Rekiek et al. [166] dans un contexte de transport de personnes handicapées. La problématique est la suivante : étant donné plusieurs dépôts avec pour chacun une zone de couverture des demandes, l’objectif est de satisfaire toutes les demandes en minimisant le nombre de véhicules. Les auteurs proposent un algorithme génétique pour résoudre ce problème. Chaque solution est décomposée en plusieurs gènes caractérisés par un véhicule et les sommets des demandes qu’il dessert. L’opérateur de croisement consiste à prendre aléatoirement une sous séquence de gènes d’un parent an de l’insérer aléatoirement dans la séquence d’un autre parent, puis d’appliquer un opérateur de réparation. Ce dernier élimine les sommets doublons et réinsère les sommets manquants. L’opérateur de mutation permet soit de créer aléatoirement des nouveaux groupes de véhicules, soit d’en éliminer, soit d’échanger les sommets entre gènes (véhicules). Une procédure regroupant les gènes de bonne qualité en les déplaçant est aussi implémentée an d’augmenter la chance de les diuser dans les individus de la génération suivante. La fonction objectif de ce problème est de maximiser la moyenne au carré de « l’ecacité des véhicules », calculée comme un ratio entre la durée réelle de la route d’un véhicule sans compter les attentes et la durée maximum de la route. Parmi les méthodes de résolutions performantes, il existe les méthodes à deux phases comme par exemple celle proposée par Dumas et al. [65]. La première phase consiste à créer des groupes de personnes dans la même région à servir approximativement au même moment. Ces groupes sont ensuite combinés pour former le parcours des véhicules en se basant sur une technique de génération de colonnes. Enn, la deuxième phase réordonnance chaque route des véhicules en utilisant des algorithmes de la littérature avec un unique véhicule. Les auteurs ont réussi à résoudre facilement des instances avec 200 personnes à transporter, cependant les grandes instances exigent l’utilisation d’une technique de décomposition spatiale et temporelle des données pour éviter un temps de résolution trop important. La phase de formation des groupes a ensuite été reprise et améliorée par Desrosiers et al. [58]. Les résultats obtenus sont établis sur des jeux de données comprenant près de 3000 personnes. Enfin, Ioachim et al. [103] ont montré l’avantage, en terme de qualité de solution, à recourir à une technique d’optimisation par construction de groupes.