Algorithme génétique

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

PLNE 

Pour une première étude de ce problème, nous allons exposer un modèle de programmation linéaire en nombres entiers qui va permettre d’identier et de formuler clairement toutes les contraintes du problème. Avant de présenter le modèle de PLNE, nous allons introduire les notations utilisées et quelques libertés qui ont été prises. Pour alléger la formulation en PLNE, nous avons fait l’hypothèse que le quai de Clocheville est limité à une place, les autres ne sont pas limités. De plus, nous considérons que toutes les demandes sont préaectées à un jour, enn les bâtiments de Bretonneau sont livrables uniquement par manutentionnaire. Chaque manutentionnaire se voit aecté un unique moyen de transport, certains se déplaceront toujours à pied tandis que d’autres utiliseront toujours le même fenwick. Une des dicultés du modèle est qu’il ne s’agit pas simplement d’un problème de tournées avec plusieurs voyageurs. On doit en fait déterminer plusieurs tournées successives pour plusieurs voyageurs (véhicules), sachant que le nombre de tournées eectuées par chaque voyageur n’est pas connu à l’avance. On xe arbitrairement que chaque véhicule eectuera au plus m tournées. On a un nombre total de moyens de transports égal à w (les camions, les fenwicks, les manutentionnaires à pied), donc on doit déterminer au plus w × m routes. La formulation s’appuie donc sur un ensemble de w × m routes parcourues dans une journée. Cela regroupe l’ensemble Minter des routes inter-hôpitaux et l’ensemble Mintra des routes entre les bâtiments B et T, l’hôpital Bretonneau. L’ensemble de toutes les routes est noté M = Minter ∪ Mintra. A chaque moyen est associé un ensemble de m routes, une route pouvant éventuellement être vide (les routes de 1 à m correspondent au premier véhicule, de m + 1 à 2m au deuxième véhicule, etc.). Chaque route est donc caractérisée par un départ et un retour au même dépôt Dv, et un moyen de transport v (camions, fenwicks, pied). Nous noterons Φ la fonction qui permet de passer d’un indice d’une route k à l’indice du moyen de transport correspondant v = Φ(k). Le nombre nal de routes n’étant pas connu à l’avance, nous xons le nombre m en fonction du système actuel et des quantités demandées par rapport aux capacités des moyens de transports. Chaque type de moyen de transport étant limité, nous imposerons une contrainte de succession d’utilisation de véhicules ou fenwicks entre deux routes utilisant le même véhicule ou fenwick. Enn, nous noterons O un ensemble d’indices de tournées, une même personne  assure un maximum de |O| tournées par jour, une tournée correspond à une route. 

Les variables 

Les variables du PLNE sont les suivantes :  x k,t i,j = 1 si la route k passe par les emplacements i puis j le jour t; 0 sinon (∀k ∈ M, ∀i, j ∈ DΦ(k) ∪ NΦ(k) (i 6= j), ∀t ∈ τ )  depk,t i = date de départ (ou de n de livraison) de la route k le jour t à l’emplacement i si i = NΦ(k) ; date de départ du dépôt de la route k le jour t si i = DΦ(k) (∀k ∈ M, ∀i ∈ DΦ(k) ∪ NΦ(k) , ∀t ∈ τ )  f ink,t = date de n de la tournée k le jour t (∀k ∈ M, ∀t ∈ τ )  IQck,t i,p = 1 si la route k livre au moins un chariot de produits p à l’emplacement i le jour t; 0 sinon (∀k ∈ M, ∀i ∈ NΦ(k) , ∀t ∈ τ, ∀p ∈ P)  Qck,t i,p = α si la route k livre α chariots de produits p à l’emplacement i le jour t; 0 sinon (∀k ∈ M, ∀i ∈ NΦ(k) , ∀t ∈ τ, ∀p ∈ P)  IQtrk1,k2,t p = 1 si la route k1 transporte au moins un chariot de produits p pour la route k2 le jour t; 0 sinon (∀k1 ∈ Minter, k2 ∈ Mintra, ∀t ∈ τ, ∀p ∈ P)  Qtrk1,k2,t p = α si la route k1 transporte α chariots de produit p pour la route k2 le jour t; 0 pour aucune livraison (∀k1 ∈ Minter, k2 ∈ Mintra, ∀t ∈ τ, ∀p ∈ P)  Livk,o,t r = 1 si la personne r est aectée à la route k lors de sa o ieme tournée le jour t; 0 sinon (∀k ∈ M, o ∈ O, ∀t ∈ τ, ∀r ∈ R)  M ar = 1 si la personne r est aectée à des routes de Mintra ; 0 si la personne r est aectée à des routes de Minter (∀r ∈ R)  Ext k1,k0 1 = 1 si la route k1 passe avant k 0 1 à Clocheville ; 0 si la route k 0 1 passe avant k1 à Clocheville (∀k1, k0 1 ∈ Minter, k1 6= k 0 1 et utilisant des véhicules diérents, ∀t ∈ τ ). Clocheville est l’hôpital ne possédant qu’une unique place de déchargement.

Algorithme génétique

Etant donné la complexité du problème, nous avons choisi d’utiliser une méta-heuristique pour le résoudre. La première méta-heuristique testée est un algorithme génétique (Holland [99]), méthode fréquemment utilisée dans les problèmes de tournées de véhicule partir d’un ensemble de solutions initiales, ou population de N individus, elle consiste à faire évoluer cette population en utilisant des opérateurs de sélection, de croisement et de mutation. A chaque itération de l’algorithme, une nouvelle population de solutions ou d’individus est générée. Tout d’abord, un ensemble d’individus est sélectionné pour générer la population suivante. Ces individus sont ensuite croisés pour créer de nouveaux individus et compléter la nouvelle population. Certains de ces nouveaux individus peuvent subir une mutation. Le critère d’arrêt de l’algorithme dans notre cas est un nombre d’itérations sans amélioration de la meilleure solution trouvée (#ite). Algorithme 1 Structure générale de l’algorithme génétique 1: Pcourant ← Initialiser une population de N individus 2: Evaluer chaque individu de Pcourant 3: Sbest ← Le meilleur individu S ∈ Pcourant 4: I ← 0 5: Tant que I < #ite faire 6: Penfant ← Ø 7: Pour j = 0 à j = N/2 faire 8: (P1, P2) ← Sélectionner deux individus parents de Pcourant 9: (E1, E2) ← Croiser les deux parents (P1, P2) pour obtenir deux individus enfants 10: Penfant ← Penfant ∪ {E1, E2} 11: Fin pour 12: Muter aléatoirement des individus de la population Penfant 13: Pcourant ← Penfant 14: Evaluer chaque individu de Pcourant 15: Si il existe un individu S ∈ Pcourant meilleur que Sbest alors 16: Sbest ← S 17: I ← 0 18: Fin si 19: I ← I + 1 20: Fin Tant que Les éléments importants d’un algorithme génétique sont le codage et l’évaluation d’un individu (étapes 2 et 14), l’initialisation d’une population (étape 1), la sélection (étape 8), le croisement (étape 9) et la mutation des individus (étape 12). Ces éléments sont décrits dans les pages qui suivent, dans le cadre de l’adaptation que nous en avons faite au problème de la logistique. Mais avant cela, il est important de noter que l’algorithme génétique proposé prend en paramètre deux grandeurs : N bTinter et N bTintra qui correspondent respectivement aux nombres de tournées Inter-hôpitaux (les camions) et intra-Bretonneau (les manutentionnaires) qui peuvent se dérouler simultanément. Les deux paramètres bornent supérieurement le nombre de chaueurs et de manutentionnaires à 2.N bTinter et 2.N bTintra sans pour autant interdire à l’algorithme génétique de trouver des solutions avec moins d’employés (voir section 3.3.1.2 pour plus de détails)

Codage et évaluation d’un individu

Le codage d’une solution est avant tout basé sur l’aectation des demandes aux véhicules. Un individu est représenté par une liste ordonnée de gènes constitués de deux éléments (veci ;dmdi) avec veci un numéro de véhicule et dmdi un numéro de demande d’un gène i (cf. Figure 3.1 pour une illustration du codage). Cette liste de gènes est découpée en plusieurs segments, chaque segment représentant l’ensemble des demandes à traiter dans une même journée. A partir de ce codage, les tournées inter-hôpitaux des véhicules et intra-Bretonneau des manutentionnaires sont construites suivant deux procédures distinctes qui s’appliquent à chaque segment de manière identique. Un individu est évalué en fonction des retards des livraisons, des dépassements d’autonomies des chariots de l’UCPA et du nombre de chaueurs et manutentionnaires nécessaires. Fig. 3.1  Illustration du codage 

Détermination des tournées des véhicules 

La première procédure détermine pour chaque journée les tournées des véhicules entre les hôpitaux. Les étapes suivantes sont appliquées tant qu’il reste des gènes à traiter dans le segment. Les gènes sont traités dans leur ordre d’apparition dans le segment. Soit (veci ;dmdi) le gène courant :  Si le véhicule veci n’est encore associé à aucune route, on en ouvre une nouvelle.  On ajoute à la n de la route associée au véhicule veci un sommet représentant l’hôpital dont est issue la demande dmdi . Si la capacité restante du véhicule ne permet pas d’accueillir tous les chariots représentant la demande dmdi , on scinde cette demande en deux et on ouvre une autre route associée au véhicule veci avec le reliquat de chariots n’ayant pas pu être emmenés sur la route précédente.  S’il n’est pas encore présent, le dépôt du ux associé à la demande dmdi est inséré en début et en n de route pour le chargement des chariots pleins et le retour des chariots vide (ou l’inverse dans le cas du ux de linge sale). On s’arrange pour placer le dépôt du véhicule en tout début et toute n de route. La gure 3.2 illustre cette première partie de la procédure. Nous supposons dans cet exemple qu’à partir de la demande 21, la capacité du véhicule est atteinte, c’est-à-dire que la quantité de chariots de la demande 21 est trop importante pour qu’elle loge entièrement dans le véhicule. Cette demande sera donc divisée en deux, une première partie des chariots sera livrée à la n de la première tournée puis la seconde partie sera livrée au début de la deuxième tournée. Fig. 3.2  Illustration du codage Les routes ainsi construites sont ensuite exploitées dans l’ordre dans lequel elles ont été créées :  La date de départ d’un véhicule d’une route est calculée en fonction de sa précédente tournée, de la fenêtre de temps de la première demande (inutile de partir trop tôt), du temps de chargement des chariots à livrer ou collecter et du nombre de véhicules circulants au même moment. Une tournée peut être retardée si le nombre de véhicules circulants est égal à N bTinter.  les dates de livraisons/collectes de chaque demande sont ensuite déterminées en fonction de la date de départ du véhicule, des fenêtres de temps associées aux demandes, des durées de déchargement et chargement, des durées de livraison et des places disponibles sur les quais, dépendantes des précédentes routes calculées. Cette étape permet notamment de construire une liste des demandes à livrer à Bretonneau, triée par dates d’arrivées, ainsi qu’une autre liste pour les demandes à collecter.  Une optimisation gloutonne est ensuite appliquée. Elle consiste à tester le déplacement de chaque sommet de la route vers toutes les places possibles. Un sommet est déplacé uniquement s’il améliore un des critères ci-dessous sans détériorer les autres. Les critères sont la durée totale de la tournée, les dates d’arrivée des demandes à Bretonneau (puisque les dates de livraison dans les bâtiments de Bretonneau ne sont pas connus à cette étape) et les retards des livraisons/collectes dans les hôpitaux autres que Bretonneau. Le meilleur déplacement pour chaque sommet est choisi en fonction d’abord de la diminution du retard engendré, puis par rapport aux dates d’arrivées des chariots sur le quai de Bretonneau et enn en fonction de la diminution de la durée totale de la tournée.