Notation et modélisation d’un
planning dans le domaine du TRM

Structuration des concepts et présentation des modèles de données manipulés

Cette section a pour objectif de présenter le modèle de données sélectionné. La modélisation des données relatives à l’entreprise de transport et au client sont dans un premier temps présentées séparément. Les notions de tournée et planning journalier permettent de faire le lien entre ces deux acteurs dans un deuxième temps. 3.1.1 Modélisation de l’entreprise de transport Le premier acteur du processus de planification est l’entreprise de transport. La figure 3.1 présente les différentes entités d’une entreprise de transport. Une entreprise peut posséder un ou plusieurs entrepôts selon son activité et sa couverture géographique. L’entrepôt permet d’opérer les différentes activités de transport comme le chargement ou déchargement des marchandises ou le stockage provisoire des marchandises. Il est la base d’entreposage des véhicules utilisés pour opérer les tournées. Chaque entrepôt est caractérisé par un nom et une adresse permettant de l’identifier et de le localiser. L’entrepôt correspond généralement au lieu de départ et d’arrivée de l’activité de l’entreprise, en l’occurrence des tournées planifiées. Les problèmes multi-entrepôts (Perl et al., 1985 ; Rath et al., 2014) proposent de traiter la planification en utilisant plusieurs lieux de départ. L’objectif est de minimiser le coût en minimisant les temps de transport. Les entrepôts peuvent être limités par leurs capacités de stockage ou de ressources. Pour réaliser l’ensemble des activités associées à un entrepôt, des ressources sont affectées à un entrepôt. Il s’agit entres autres : des véhicules, des conducteurs, des manutentionnaires, des personnels administratifs et des personnels d’encadrement. Dans la suite, nous allons nous intéresser principalement à deux types de ressources qui sont mobilisés pour réaliser les tournées : les véhicules et les conducteurs (voir 3.1) Les conducteurs correspondent à un type de ressources de l’entreprise. Ils effectuent un ensemble d’activités, telles que définies par le planning établi par le planificateur. Les activités réalisées comprennent, entres autres, des activités de conduite, des activités administratives (édition des bordereaux de livraison, vérification du chargement, etc.), parfois des activités de chargement/déchargement des véhicules, des activités de manutention. Le périmètre des activités d’un conducteur peut être différent selon l’entreprise ou le type d’entreprise (transport dernier kilomètre, messagerie, transport international). Dans la littérature, les conducteurs sont modélisés par différents attributs correspondant par exemple à leurs compétences, leur contrat ou à leurs disponibilités (Laurent et al., 2007 ; Li et al., 2010). Notre objectif est de modéliser le conducteur de la manière la plus globale possible pour prendre en compte le plus de critères. Ainsi, chaque conducteur est décrit par son identifiant qui le rend unique. Cette unicité est d’autant plus importante que chaque conducteur peut avoir des spécificités qui influencent le processus de planification des tournées. Il s’agit par exemple : — du permis de conduite : permis B seul, permis B et C, etc. ; — du nombre d’heures par mois prévues dans le contrat de travail avec l’entreprise : 80 heures par mois, 156 heures par mois ; — de l’expérience acquise : par exemple, l’ancienneté comme conducteur et/ou la connaissance de certains sites ; — la disponibilité comme les périodes de travail (matin, nuit, etc.) ; — des restrictions particulières comme par exemple : port de charges supérieures à 10 kg interdit. Les véhicules correspondent à une autre ressource de l’entreprise. Les véhicules permettent de transporter les marchandises pour les livrer. Dans la littérature, les véhicules sont modélisés par une liste d’attributs permettant de les décrire et de vérifier si certaines contraintes sont respectées lors de l’élaboration du planning. Parmi les contraintes vérifiées, il y a la capacité du véhicule (Golden et al., 2008 ; Toth et al., 2002), l’utilisation de flottes de véhicules hétérogènes (Duhamel et al., 2012). L’apport de cette thèse n’étant pas sur les contraintes liées au véhicule, notre objectif est donc d’inclure des attributs représentatifs des différents problèmes possibles. Car c’est à partir de ces attributs que les contraintes sont modélisées. Un véhicule sera décrit à l’aide d’un identifiant pour l’unicité de chaque véhicule, sa plaque d’immatriculation et des caractéristiques techniques complémentaires comme sa hauteur, sa largeur, sa longueur. Les notions comme la quantité de palettes qu’il peut transporter, son volume utilisable ou encore sa charge utile permettent de définir les caractéristiques de livraison du véhicule. Pour prendre en compte les travaux sur les types d’énergie, des attributs comme le type de véhicule, l’énergie du véhicule, la consommation de 𝐶𝑂2, l’autonomie du véhicule… viennent compléter la liste. 

La modélisation du client L’entreprise de transport n’est pas le seul acteur de cette planification

Le client correspond à l’entreprise qui passe le contrat avec l’entreprise de transport. Il s’agit bien ici de l’entreprise qui commande le service de livraison, la livraison pouvant être effectuée entre deux sites de ce client ou de/vers un site autre. La figure 3.3 décrit la structure d’un client dans le domaine du transport routier de marchandises. Un client peut posséder plusieurs sites, répartis géographiquement, sur lesquels il réalise son activité d’entreprise. Pour effectuer son activité, chaque site a besoin d’être approvisionné en marchandises. Chaque site passe donc des commandes de marchandises qui lui sont propres. Il est nécessaire de modéliser les informations relatives à chaque client : son nom, sa localisation, ses exigences. Les exigences associées à un client, qui devront être prises en compte lors de la construction des tournées, peuvent porter par exemple sur : — l’obligation d’utiliser des véhicules sécurisés pour accéder à ses sites ; — l’obligation d’utiliser d’un type d’énergie particulier, par exemple utilisation de véhicules exclusivement électriques ; — le refus de mutualiser un véhicule, seules des marchandises le concernant pourront être transportées dans ce véhicule ; — l’obligation d’utiliser un véhicule appartenant à une liste pré identifiée, notamment pour des raisons de sécurité car seuls ces véhicules sont habilités pour entrer sur ses sites. Dans la littérature, les notions de client et de site sont souvent confondues (Derigs et al., 2014 ; Gupta et al., 2012) car chaque site est considéré comme un client indépendant. Notre proposition est de distinguer ces deux notions afin de pouvoir identifier clairement les différents sites d’un même client et de pouvoir leur associer des exigences particulières. Le client est pour nous le propriétaire de plusieurs sites. Cela permet par exemple de préciser pour chaque site des caractéristiques qui leur sont propres. Les sites correspondent aux emplacements où doit être livré la marchandise d’un point de vue géographique (Eksioglu et al., 2009). Les sites sont caractérisés par la description des installations permettant d’accueillir le véhicule et les livraisons : — existence ou non d’un quai de livraison ; — existence ou non d’un sas pour le dépôt des marchandises et capacité de ce sas (en nombre de palettes par exemple) ; — le type d’autorisation nécessaire pour l’accès au site (conducteur, véhicule) ; — accessibilité au site avec une hauteur maximale de véhicules ; — les horaires d’ouverture du site et/ou les heures de réception des livraisons. Une structure de données similaire à celle décrivant l’entreprise de transport a été retenue. Pour être approvisionné en marchandises, un site passe une commande. La commande est la description des marchandises qui doivent être livrées d’un site A à un site B pour un client donné. Dans la littérature, la commande est associée à une demande, cette demande représente la quantité de marchandises à charger ou décharger sur un site (Bianchessi et al., 2007 ; Lee et al., 2012). Notre objectif est de prendre en compte les attributs les plus représentatifs de la description d’une commande. Notre proposition se positionne sur les problèmes de recherche où le respect de l’heure de livraison est un critère de planification. L’attribut de l’heure de livraison ou de plage horaire est fondamental pour la suite du manuscrit. Pour nous, la commande est caractérisée par : — sa nature : la quantité de palettes ou de colis, le volume et la surface des marchandises ; — les mouvements attendus : l’entrepôt responsable de la livraison (lieu où la marchandise devra être prélevée), le site de livraison (lieu où la marchandise devra être livrée) ; — l’heure ou la plage horaire à laquelle la commande devra être livrée sur le site destinataire. D’un point de vue de l’entreprise de transport, la commande est un objectif que l’entreprise doit réaliser. La description du site et du client représentent le contexte dans lequel cet objectif est à réaliser.

Modélisation des tournées et plannings journaliers

Après avoir présenté et modélisé l’environnement de la planification, nous allons nous intéresser à la modélisation des tournées et plannings journaliers. Ce sont ces deux concepts qui permettent de représenter l’activité menée par l’entreprise de transport pour satisfaire les différentes demandes de livraison des clients. Le résultat de la phase de planification dans le transport routier de marchandises et plus précisément dans la livraison dernier kilomètre est appelé un planning journalier. Le planning journalier, noté 𝑃 𝐽, représente la vision macroscopique de l’activité d’une entreprise de transport sur une journée. Il modélise l’ensemble des activités réalisées sur une journée par les ressources affectées à un entrepôt d’une entreprise de transport. Il représente les commandes émises par les différents sites des différents clients. Un planning journalier est évalué sur un certain nombre d’indicateurs comme le coût de réalisation, la durée totale d’exécution, l’émission de 𝐶𝑂2… La notion de tournée correspond à l’ensemble des activités réalisées par un couple conducteur-véhicule sur une plage de temps donnée (par exemple journée, matinée). La tournée a pour objectif la livraison d’un ensemble de commandes sur les sites auxquels elles sont destinées. Une tournée est représentée sous la forme d’un processus noté 𝑇. Ce processus correspond à un enchaînement d’activités 𝐴𝑖(𝑖 = 1…𝑎)ordonnées, 𝑎 étant le nombre d’activités nécessaires pour réaliser la tournée. Un exemple de tournée est illustré figure 3.6. La littérature propose de nombreux modèles pour représenter une tournée. La majorité de ces modèles intègre les activités de chargement/déchargement de la marchandise sur les différents sites et les activités de déplacement d’un site à un autre. Ces deux activités correspondent au travail réalisé par les conducteurs. Cependant, lors d’une journée de travail, le conducteur a des périodes où il ne réalise aucune de ces deux activités. Par exemple, il peut se trouver dans une phase d’attente du réceptionniste sur un site. Notre proposition est de prendre en compte et de modéliser dans notre modèle les périodes où le conducteur attend pour représenter la globalité de sa journée de travail. Nous présentons, ci-dessous, les caractéristiques que nous avons retenues pour modéliser ces deux familles d’activité. Pour les activités de chargement et de déchargement, des auteurs (Feillet et al., 2002 ; Güner et al., 2017 ; Lera-Romero et al., 2019) utilisent le terme temps de service. Le temps de service est pour ces auteurs le temps nécessaire pour livrer ou récupérer les marchandises sur un site. Notre proposition est de décomposer ce temps de service en trois types d’activités. Le premier type d’activité nommé « Activity on Site », désigné par « AoS », correspond à l’ensemble des activités réalisées par le conducteur sur le site en cours de livraison. Cette activité inclut le déchargement des marchandises et une partie administrative (comme par exemple la signature des bons de livraison). Le conducteur a également la possibilité de récupérer des marchandises sur le site si la consigne lui en est donnée. Ces marchandises peuvent être à destination de la déchetterie, par exemple pour des encombrants, ou simplement à destination de l’entrepôt quant il s’agit des palettes (retour à vide) pour un stockage temporaire. Le deuxième type d’activité nommé « Start Activity », désigné par « Start », correspond aux différentes étapes réalisées dans l’entrepôt avant le départ de la tournée. Les démarches regroupées au sein de cette activité comportent la prise de poste de l’agent, une partie administrative (comme la préparation des bons de livraison), le chargement du véhicule. La période de passage des consignes données par le planificateur est également incluse dans cette activité. La première activité d’une tournée est de type Start Activity car l’activité représentera la préparation du véhicule avant d’effectuer la tournée. Le troisième type d’activité nommé « End Activity », désigné par « End », est similaire à « Start Activity ». Elle correspond aux différentes étapes réalisées dans l’entrepôt à la fin de la tournée, au retour des livraisons. Les démarches au sein de cette activité regroupent le déchargement du véhicule, son nettoyage, une partie administrative ainsi qu’un « feedback » vers le planificateur. Cette discussion permet au conducteur de faire un retour sur le déroulement de sa tournée mais également de présenter les différents problèmes qu’il a pu rencontrer au cours de celle-ci (par exemple : embouteillage, problème technique du véhicule, mauvaise relation avec le client…). La dernière activité d’une tournée est de type End Activity. Ces trois types d’activités (Activity on site, Start Activity et End Activity) sont caractérisés par une durée d’exécution permettant de connaître le temps nécessaire pour réaliser l’activité, une localisation pour savoir où se situe l’action à réaliser, une heure de début et une heure de fin dans l’objectif de connaître la période de la journée où est réalisée l’activité. Pour les activités de déplacement, dans la littérature les auteurs modélisent ces activités à partir d’une matrice des distances et une matrice des temps de trajet (Ai et al., 2009 ; Ruiz et al., 2019). La valeur de la matrice 𝑑𝑖,𝑗 correspond à la distance ou à la durée nécessaire pour effectuer le trajet entre le site 𝑖 et le site 𝑗. Les activités de déplacement d’un site à un autre sont de type « Move ». Les caractéristiques décrivant cette activité sont la durée de l’activité, l’heure de début et de fin de l’activité, la distance à parcourir et l’émission de 𝐶𝑂2. La distance de l’activité est extraite de la matrice des distances. Les sites de départ et d’arrivée sont connus à l’aide des activités avant et après l’activité de déplacement. La durée d’activité est calculée à partir de la distance et de la vitesse moyenne. L’émission de 𝐶𝑂2 est calculée à partir de la distance parcourue et de l’émission de 𝐶𝑂2 par kilomètre du véhicule effectuant l’activité.