Algorithme mémétique

Optimisation des tournées et dimensionnement des équipes : Modèle appliqué

Contraintes et hypothèses du modèle appliqué

Tout d’abord, la première évolution du modèle concerne les tournées de collecte des chariots (linge sale et salubrité). A l’exception de Bretonneau, les tournées de collecte peuvent être vues comme des tournées de livraison effectives de chariots vides, sachant qu’une personne dépose autant de chariots vides qu’elle collecte de chariots pleins. A Bretonneau, la synchronisation des tournées de manutentionnaires et des tournées de collectes ne permet pas de considérer uniquement des tournées de type livraison (une tournée collectant des chariots à Bretonneau doit attendre que ces chariots soient collectés par les manutentionnaires). Cependant, nous considérons l’hypothèse que les collectes des chari Bretonneau peuvent être réalisées la vieille au soir pour une collecte par les véhicules le lendemain matin au quai. Pour modéliser cet aspect, il sut de représenter les demandes à collecter à Bretonneau par des demandes de chariots à livrer avec des fenêtres de temps en n d’après midi. En considérant uniquement des tournées de livraisons, la complexité de l’étape d’évaluation d’un individu, en particulier pour les tournées des manutentionnaires, diminue. Comme le CHRU n’est pas certain de prendre en compte tous les ux dans le projet de la réorganisation de la logistique, il faut prévoir le cas où certains ux ne seront pas gérés, en particulier la salubrité. Pour ce cas, il surait de retirer dans les données toutes les demandes affectées à ceux. Cependant, il existe actuellement une équipe appartenant à la salubrité qui se charge de collecter les chariots de linge sales et de déchets à Bretonneau. Cette équipe pourrait donc intervenir en parallèle de l’équipe de manutention, et collecterait à leur place le linge sale. Suite à ce souhait du CHRU, nous avons ajouté un attribut Brp par type de produit p égale à 1 si le ux est à prendre en compte à l’intérieure de Bretonneau, 0 sinon. Les demandes appartenant à un ux p tel que Brp = 0, seront considérées comme livrées au quai de Bretonneau, et le calcul des retards s’effectuera par rapport à leurs dates d’arrivée au quai et de leurs dates de n livraison dénies par li,p,t. Après une étude approfondie du terrain de Bretonneau, il n’est nalement pas envisageable que les manutentionnaires puissent livrer certains bâtiments par fenwick extérieur. Comme présenté dans le chapitre 1 section 1.2.9, un sous-ensemble de bâtiments de Bretonneau peut être livré par des manutentionnaires (les cinq plus importants) parmi lesquels certains sont livrables uniquement par fenwick (étant donné la distance des couloirs sous terrains et la possibilité d’augmenter le nombre de fenwicks), et un autre sous-ensemble peut être livré par véhicule (cf. gure 4.1). Nous avons donc changé les points de livraisons pour prendre en compte cet aspect et retiré la possibilité de livrer par fenwick extérieur. D’autre part, la gestion des manutentionnaires et le calcul des tournées intra-Bretonneau ont été revus. Il paraît difficilement concevable de donner à chaque manutentionnaire la liste précise des chariots à livrer de chacune de ses tournées avec les dates à laquelle il doit partir du Quai. Nous avons donc décidé de déterminer les tournées intra en fonction du comportement qu’aurait un manutentionnaire vis-à-vis des chariots arrivant sur le quai. Ce comportement doit tenir compte des facteurs suivants : la priorité des chariots, des dates au plus tôt de livraison (un manutentionnaire ne prendra pas les chariots s’il sait qu’il va attendre dans le service), la destination des chariots (regroupement par bâtiment) et de la disponibilité des fenwicks. Nous détaillerons l’algorithme du comportement d’un manutentionnaire dans la section 4.2 suivante. Un dernier point rectifié concerne le temps de livraison de chaque point tli,p par les manutentionnaires ou les chauffeurs. Ce temps dépend du type de chariot pour différencier le temps de dépaquetages des chariots, et aussi des temps moyens d’accès aux services à livrer. Cependant, un élément non négligeable pour le calcul du temps de livraison d’un point est l’ascenseur. Seuls deux chariots peuvent être logés dans tous les ascenseurs de hôpitaux. Lorsqu’un livreur arrive au pied du bâtiment, il ne peut monter les chariots que deux par deux. Pour modéliser cette nouvelle contrainte, nous remplaçons la donnée tli,p par deux nouvelles :  tai : le temps moyens d’accès aux services au point i.  tdp : le temps de déposer ou dépaqueter si besoin, les chariots de produit p. Lorsqu’un chauffeur arrive au pied d’un bâtiment d’un point i pour livrer en produits p le jour t une quantité qi,p,t de chariots, le temps total de livraison avec chargement et déchargement des chariots est égal à qi,p,t × (2 × tchp + tdp) + 2 × tai × dqi,p,t/2e. Le temps total de livraison pour un manutentionnaire est déni par la même expression sans le terme tchp de chargement/déchargement des chariots du véhicule. Enn, les contraintes prises en compte dans ce modèle, contrairement au modèle précédent, sont les suivantes :  un temps de production ou de préparation des chariots par type p modélisé par une heure de début au plus tôt hp et une durée dpp par chariot de production ou préparation.  et un type de place pour chaque quai de chaque point de livraison. Ce type est soit « haut » soit « bas », et influence le temps de chargement et déchargement des chariots à un quai qui ne dépend plus d’uniquement du type de produit (le type haut permettant de charger et décharger plus rapidement). Lorsqu’un véhicule arrive à un quai, il mobilisera en priorité une place de type haut.

Impacts sur les algorithmes existants

L’une des plus grosses modications des deux méta-heuristiques développées pour le précédent modèle concerne l’évaluation d’une solution pour prendre en compte les temps de production, les types de places et le fait que certains ux véhiculés par les camions ne sont pas pris en charge par les manutentionnaires. Pour la simulation du comportement des manutentionnaires, nous avons mis en place un nouvel algorithme. Ce dernier est plus simple à expliquer que celui du modèle précédent puisqu’il n’intègre pas de tournées de type collecte. L’algorithme consiste à exécuter une procédure décrite par la gure 4.2 (les constantes , α et λ sont des paramètres,  ≈ 15 min., α ≈ 3 heures, λ ≈ 5 min). Cette procédure est exécutée à un instant t lorsque le nombre de tournées intra se déroulant au même moment est inférieur à N bTintra et des chariots attendant sur le quai de Bretonneau peuvent être livrés. La sélection des chariots doit se faire toujours en respectant la condition 1 dénie par :  li,p,t est la plus petite valeur parmi tous les chariots sur le quai à l’instant t  ei,p,t < t +  et li,p,t < t + α L’algorithme génétique possède la même structure que celle décrite à la section 3.3 du chapitre précédent. Cependant la génération de la population initiale proposée en section 3.3.2 a été améliorée de manière à mieux répartir les chariots dans les véhicules. Les N individus de cette population sont générés de la manière suivante :  Découper la période considérée τ en plusieurs demi-journées.  Pour les demandes attribuées à un jour particulier, aecter chaque demande dont l’intersection entre la fenêtre de temps correspondante et la demi-journée est la plus grande parmi les deux demi-journées concernées.  Aecter aléatoirement les autres demandes (non attribuées à un jour) aux demijournées.  Enn, pour chaque demi-journée :  Trier aléatoirement les demandes aectées à cette demi-journée.  Aecter un numéro de véhicule pour chaque demande de manière suivante :  Trier aléatoirement dans une liste les véhicules.  Prendre le premier véhicule de cette liste, et lui aecter les x premières demandes jusqu’à atteindre sa capacité maximum.  Positionner ce véhicule à la n de la liste et réitérer à l’étape précédente s’il reste des demandes à aecter dans la demi-journée considérée. Nous avons également modié l’opérateur de croisement type PMX de telle sorte que les deux sous-segments échangés entre les deux individus soient positionnés au même niveau dans le codage des deux solutions. La recherche tabou possède, elle aussi, la même structure que celle décrite à la section 3.4 du chapitre précédent.

Algorithme mémétique

Le terme algorithme mémétique (Moscato [149]) est souvent utilisé pour désigner les méthodes de résolution qui hybrident une recherche à base de population, comme un algorithme évolutionnaire et une recherche par voisinage, comme une recherche locale. L’algorithme mémétique, décrit ici, est le résultat d’une hybridation des deux méthodes précédentes : l’algorithme génétique et la recherche tabou. La structure générale de cette hybridation est présentée par l’algorithme 3. Nous avons ajouté à l’algorithme génétique présenté à la section 3.3, une étape d’amélioration de la population qui fait appel à la recherche tabou. Cette recherche tabou est exécutée sur chaque individu de la population courante avec une probabilité PT S. Le nombre d’itérations de la recherche tabou dépend de l’itération courante I de l’algorithme génétique, il est xé à I/4. Le critère d’arrêt de l’algorithme mémétique est un nombre d’itérations sans amélioration #ite de la meilleure solution trouvée. L’algorithme mémétique utilise le même codage d’une solution que les deux précédents algorithmes développés. La construction de la population initiale, les opérateurs de sélection, de croisement et mutation sont les mêmes que l’algorithme génétique. Après l’étape de mutation, l’algorithme tabou est exécuté sur chaque individu de la population avec une probabilité PT S. Seul un ensemble d’individus de la population est donc amélioré par la tabou avec un nombre d’itérations égal à bI/4c. Le calcul du voisinage d’une solution et la gestion de la liste tabou pour l’étape d’amélioration des individus sont identiques à ceux de la recherche tabou. L’application systématique de la recherche tabou à tout individu demanderait trop de temps, ce qui justie l’utilisation d’une probabilité PT S. Le choix de limiter le nombre d’itérations de la recherche tabou à I/4 permet de répartir les rôles entre elle et l’algorithme génétique. Initialement c’est l’algorithme génétique qui prévaut, puis au l des itérations I/4 augmente et la recherche tabou inuence de plus en plus la recherche

 Algorithme génétique

Après des tests préliminaires, la taille de la population a été xée à N = 200, la probabilité de mutation Pmut à 60% et dans le cas d’une mutation l’opérateur agissant sur le numéro de véhicule est choisi avec une probabilité de 40% contre 60% pour l’opérateur agissant sur le déplacement d’un gène. Les paramètres importants correspondant au nombre maximal des tournées inter-hôpitaux et intra-Bretonneau se déroulant au même moment ont été xés à N bTinter = 8 et N bTintra = 3. Comme pour le chapitre précédent, nous nous avons ensuite étudié l’inuence de l’opérateur de sélection (sélection des 50% meilleurs (M), sélection par roulette (R) et sélection par tournoi (T)) et l’inuence de l’opérateur de croisement (par recopie (C) ou par insertion (I)). Un couple (sélection, croisement) est encore appelé une conguration. Les tableaux 4.4 et 4.5 résument les résultats sur 100 instances de chacune des six congurations pour #ite = 200 et #ite = 400. ∆i est la moyenne sur toutes les instances des écarts relatifs de la solution trouvée par la conguration i à la meilleure solution trouvée par l’ensemble des 6 congurations. L’écart type est indiqué par σ(∆i). N bmin est le nombre de fois où la conguration i trouve la meilleure solution et T ps indique le temps moyen de résolution en secondes.L’opérateur de croisement I semble être beaucoup moins performant que l’opérateur .quelque soit l’opérateur de sélection et le nombre d’itérations sans amélioration. Tandis que les opérateurs de sélection M et T semblent largement dominer l’opérateur R. Enn, parmi les deux congurations dominantes (C, M) et (C, T), (C,M) permet d’obtenir de meilleures solutions quelque soit le nombre d’itérations sur la moyenne des écarts relatifs. Par rapport aux résultats expérimentaux du chapitre précédent, l’opérateur de croisement I est devenu inutile. Les tableaux 4.6 et 4.7 présentent une moyenne sur les 100 instances de la fonction objectif, de la somme des retards en minutes, de la somme des dépassements des autonomies des chariots repas, des bornes inférieure et supérieure du nombre de manutentionnaires, des bornes inférieure et supérieure du nombre de chaueurs, du nombre de demandes en retard et du nombre de demandes en chariot repas pour lesquelles l’autonomie d’au moins un chariot a été dépassée.