Optimisation des tournées

Modèle statique du problème des ambulanciers 

Dans cette première étude nous avons ramené le problème d’optimisation de tournées d’ambulances à un problème proche du problème du multi-voyageurs de commerce. Nous présentons dans une première section la notation et la modélisation du problème, puis nous proposons deux méthodes de résolution. La première est basée sur la Programmation Linéaire en Nombre Entier (PLNE) en utilisant certaines techniques de pré-processing et de coupes (Kergosien et al. [111]). Nous avons également étendu ce PLNE à un problème de tournée de personnel de soin pour l’hospitalisation à domicile qui ne sera pas détaillé dans ce document ([117] et [114]). Et la deuxième est une heuristique : une recherche tabou avec mémoire adaptative (Kergosien et al. [112]). 

7.1.1 Définition et modélisation

 La première étude aborde le problème dans une version statique. Nous supposons que nous connaissons toutes les demandes de transports à l’avance. Ces demandes sont caractérisées par une heure de prise en charge du patient à son lieu d’origine qui est estimée en fonction de l’heure réelle de rendez-vous du patient au service de destination. Les heures de départ des équipes sont à déterminer mais une durée de travail maximale est à respecter. Nous considérons également que chaque équipe est aectée à un véhicule pour toute la journée. Pour cette première étude, nous ne nous intéressons pas en détail aux diérents type de transports. Cependant, nous considérons que tous les véhicules ne peuvent pas eectuer tous les transports. Cette contrainte permet d’introduire la notion de type de véhicule à utiliser pour un type de transport. Mais elle permet aussi de généraliser le problème en tenant compte par exemple des différents matériels médicaux requis pour certains transports. Etant donné les transports à effectuer dans une journée, l’objectif est de proposer les affectations des véhicules aux demandes et de définir les trajets des véhicules de manière à minimiser les coûts de transports (appel aux ambulances privées et frais kilométriques) et en s’assurant de ne pas faire attendre trop longtemps un patient. Ce dernier critère revient à minimiser le plus grand retard. 

Notation 

Soit R l’ensemble des n demandes de transports de la journée, chaque demande i est caractérisée par :  Un lieu de départ depi du patient et son lieu de destination desti ,  Un temps tdepi,desti de déplacement du véhicule entre les points de départ depi et de destination desti ,  Un temps tdesti,depi de déplacement du véhicule entre les points de destination desti et de départ depi ,  Un temps pi de prise en charge du patient par les ambulanciers pour eectuer le transport en dehors du véhicule (temps pour aller chercher le patient dans le service origine et l’amener au véhicule, et le temps de l’évacuer du véhicule pour l’amener au service de destination), ce temps de prise en charge vient s’additionner au temps de transport.  Une date ei de rendez-vous pour le départ du patient de la demande i. Le patient ne peut pas être pris en charge par les ambulanciers avant cette date et doit attendre le moins possible l’ambulance qui va effectuer son transport. Soit V l’ensemble des m véhicules (ambulances du CHRU et ambulances du privé), chaque véhicule v est caractérisé par :  Un dépôt Dv, on considère qu’un véhicule n’effectue qu’une seule tournée, qu’il quitte son dépôt en début de tournée et n’y revient qu’en n de tournée. Nous notons également D l’ensemble des dépôts.  Une durée maximale Tv d’utilisation du véhicule k avant de revenir au dépôt. Cette durée permet de représenter des contraintes liées à la durée de travail des ambulanciers ou à la limitation du carburant.  Un coût c v a,b engendré par l’utilisation du véhicule v pour effectuer le trajet du point a au point b. La prise en compte du véhicule dans les coûts se justie par le fait que les ambulances privées sont plus coûteuses que les ambulances de la Centrale des Ambulanciers. De plus, un coût xe de mobilisation par véhicule pourra être ajouté à chaque sortie de chaque dépôt. Chaque patient ne peut pas être transporté par n’importe quel véhicule. Les véhicules présentent des caractéristiques diverses requises pour transporter tel ou tel type de patient. Nous affectons à chaque véhicule v et à chaque demande i un vecteur binaire Sv et Hi . Chaque attribut sv,u de Sv est égal à 1 si le véhicule v possède la caractéristique u et 0 sinon. Et chaque attribut hi,u de Hi est égal à 1 si la demande i nécessite la caractéristique u pour le transport et 0 sinon.

Modélisation

n Le problème consiste à répondre à toutes les demandes de transports en respectant les contraintes et en minimisant deux critères qui sont le coût total de déplacements de tous les véhicules mobilisés et le temps d’attente maximum des patients avant leur prise en charge. Ce problème est équivalent à un PVC dans un graphe G orienté asymétrique et fortement connexe. Ce graphe est constitué d’un ensemble de sommets divisé en deux sous-ensembles : un sous-ensemble D de sommets pour tous les dépôts des véhicules, et un sous-ensemble R de sommets pour toutes les demandes de transports. Un arc entre deux sommets (i,j) ∈ R×R symbolise le traitement de la demande i et le passage à la demande j comme le montre la gure 7.1. L’arc possède donc :  Une longueur di,j égale à tdepi,desti + pi + tdesti,depj .  Un coût w v i,j égal à c v depi,desti + c v desti,depj .