Planification d’une livraison dernier kilomètre

Implémentation des contributions

Cette section présente l’environnement dans lequel les contributions ont été effectuées. Le projet SMART PLANNING financé par l’ANR (ANR-16-CE26-0017) a été le support de l’ensemble de ces travaux. Le projet, associé au domaine du transport routier de marchandises, a permis de regrouper des acteurs de différentes spécialités pour construire de nouveaux corpus de connaissances. Nous présentons ci-dessous de manière plus détaillée les différents acteurs qui ont participé à ce projet. Les contributions que nous avons formulées ont été implémentées dans le prototype RIO-Suite qui est une suite logicielle développée au sein du laboratoire. 

Le projet SMART PLANNING 

Le projet SMART PLANNING est un projet de recherche, financé par l’Agence Nationale de la Recherche (ANR). Il vise à élaborer un module logiciel pour aider le planificateur à choisir un planning en situation complexe et risquée. Ce module prend en compte, dans la construction et l’évaluation de tournées, les nombreux critères économiques, environnementaux, sanitaires, sécuritaires, les contraintes réglementaires et les risques rencontrés lors de la réalisation des tournées. Le projet SMART PLANNING réunit des laboratoires de recherche et des industriels. L’INRS (Institut national de recherche et de sécurité) Nancy est chargé du recueil des données terrain ainsi que de la mise en place d’un indicateur SST (santé et sécurité au travail) pour l’évaluation des tournées et des plannings. L’INUC (Institut national universitaire Jean-François-Champollion) Albi est chargé de l’implémentation de l’interface du prototype de manière à proposer l’ensemble des indicateurs et solutions proposés au planificateur. Le CGI (Centre de Génie Industriel) IMT Mines-Albi est chargé de la génération des solutions avec le respect des contraintes et de l’évaluation des indicateurs de robustesse sur les tournées et plannings journaliers. Les entreprises Deret et Main Forte sont des entreprises du transport routier de marchandises. Elles ont apporté l’expertise du métier de la planification des tournées, fourni les données terrain et permis de valider les différentes propositions et de simuler des expériences à partir de données réelles.

Le prototype RIO-Suite 

Le prototype RIO-Suite 1 est un logiciel open source hébergé au centre de Génie Industriel de l’IMT Mines Albi. Il est issu des prototypes IO-Suite (Benaben et al., 2017)) et Pro-(R)isk (Marmier et al., 2014 ; Nguyen et al., 2013). Ce logiciel est dédié à supporter à la fois l’(I)nteropérabilité au sein de collaborations d’(O)organisations et la gestion des (R)isques. RIO-Suite est le support de nombreux projets présents au sein du laboratoire et adresse de nombreux domaines comme ceux de la gestion de crise, de la santé, de la supply-chain… Le modèle de données présenté au chapitre 3 est hérité du métamodèle de RIO-Suite présenté par Benaben et al. (2017). Pour implémenter mes contributions à ce logiciel, des propositions d’évolution ont été faites et implémentées au sein du prototype. Les principaux apports sont la description plus fine des attributs du concept danger, auparavant implémenté par Fertier (2018), la génération et l’évaluation des risques sur un processus à partir du concept de danger et l’évaluation de la robustesse lors des simulations des scénarios de risques. L’ensemble du cas d’étude est réalisé sur le prototype RIO-Suite. Les données de la planification (entreprise du transport, conducteur, véhicule, client, site et commande) et les dangers sont renseignés pour réaliser la génération des plannings puis l’évaluation de la robustesse. 

Les données manipulées par le planificateur 

L’objectif de cette section est de présenter les données manipulées permettant une fois le planning construit d’évaluer la robustesse. L’ensemble des données manipulées respectent le modèle de données présenté au chapitre 3. Ce modèle de données est la structure permettant de décrire l’ensemble des concepts manipulés par le planificateur. Les conducteurs, véhicules, clients, sites et commandes sont décrits pour nous permettre de proposer un algorithme de génération de plannings journaliers. Ces plannings sont confrontés à un contexte risqué. Pour illustrer notre proposition du chapitre 4, trois dangers constitueront le contexte dans lequel les plannings sont réalisés

Les données de planification

 Le cas d’étude présenté correspond à la planification d’une demi-journée d’une entreprise réelle. Toutes les données sont anonymisées pour des raisons de confidentialité. Le planificateur doit planifier 25 commandes. Ces 25 commandes sont décrites par l’ensemble des attributs présentés dans le chapitre 3. La table 6.1 est une illustration succincte de la description des commandes. Une commande va être décrite par le site de livraison, l’heure de livraison, le nombre de palettes… Dans notre exemple, l’heure de livraison est une heure fixe pour l’ensemble des commandes. Les 25 sites à livrer sont également décrits selon le modèle de données présenté au chapitre 3. La figure 6.1 présente la répartition géographique des sites à livrer. Les sites sont caractérisés par des heures d’ouverture et de fermeture. Aucun site n’a de quai de déchargement et tous les sites appartiennent au même client. La restriction à un client n’impacte pas la proposition des indicateurs de robustesse car ces indicateurs sont basés sur une vision globale de la tournée et du planning ournalier. La partie négociation avec le client n’est pas impactée non plus par cette restriction car elle s’effectue sur les indicateurs de robustesse. Pour les données de l’entreprise de transport, nous utilisons un entrepôt qui possède 15 véhicules et 15 conducteurs. L’ensemble de la description de ces concepts n’impactent pas l’évaluation de la robustesse. Les attributs du véhicule et du conducteur permettent de générer des contraintes lors de la planification et permettent d’évaluer les attributs agrégés des tournées et des plannings journalier. L’ensemble des données du client et de l’entreprise de transport sont nécessaires pour effectuer la planification. 

La génération des plannings journaliers

 L’objectif de cette étape est de construire plusieurs plannings journaliers respectant les exigences client pour réaliser l’ensemble des commandes. A partir de cette liste de plannings possibles, le planificateur pourra comparer ces solutions pour en sélectionner une. Au sein du projet SMART PLANNING, nous avons proposé un algorithme qui est capable de générer de nombreuses solutions. Cet algorithme est un algorithme de placement au plus tôt. Il ne cherche pas à optimiser car même si un planning est évalué sur trois critères dans notre prototype (économique, environnemental et santé sécurité au travail), le contexte risqué peut perturber les plannings et donc les indicateurs associés. Pour réaliser un placement au plus tôt, les listes de commandes, de véhicules et de conducteurs doivent être ordonnées. L’objectif de ces listes est d’identifier, pour chacun de ces concepts, quel est l’individu le plus contraint. Par exemple, concernant le concept commande, la commande se trouvant en première position de la liste est la commande qui a une contrainte horaire la plus élevée. Une livraison dont la contrainte horaire est 8h est plus contraignante qu’une livraison 99 dont la contrainte horaire est entre 8h et 12h. Ainsi, la commande la plus contrainte sera affectée en premier. Un travail mené par l’INRS avec les planificateurs des entreprises partenaires a permis d’identifier les critères à retenir pour chacun des concepts afin d’établir les classements. Dans un premier temps, notre choix est de représenter le raisonnement du planificateur. Pour cela, la méthode multicritère AHP (analyse multicritère hiérarchique) (Saaty, 1995) nous a permis de pondérer l’ensemble des attributs de nos trois concepts (commande, véhicule et conducteur) pour connaître les critères pris en compte en premier par le planificateur lors de la création d’un planning. La construction de cette pondération a été effectuée par des experts du transport routier de marchandises. En utilisant la méthode AHP, nous avons demandé aux experts de répartir un nombre 𝑇 𝑜 de jetons sur les attributs de chaque concept (commande, véhicule et conducteur) pour identifier l’attribut le plus important pour la planification. Par la suite, les experts ont comparé les attributs deux à deux. Pour cela, il a été demandé de noter sur une échelle de 1 à 9 l’importance d’un attribut par rapport à un autre, 1 signifie que les deux attributs sont pris en compte de manière égale et 9 signifie que le premier attribut est beaucoup plus important que le second dans la pondération. A partir de l’ensemble des comparaisons deux à deux, la méthode permet d’obtenir un poids précis de chaque attribut. A partir des poids obtenus par la méthode AHP et des données d’entrée, nous utilisons une deuxième méthode multicritère Promethee (Brans et al., 1985) pour classer par ordre de préférence les données manipulées. Les fonctions de préférence de la méthode ont pour objectif de définir les seuils à partir desquels un attribut est déterminant pour la comparaison. Par exemple, pour l’attribut quantité de palettes qu’un véhicule peut transporter, l’expert doit déterminer à partir de combien de palettes d’écart un véhicule est préféré à un autre. Une fois cette méthode utilisée, nous obtenons une liste pour chaque concept où l’ensemble des éléments est ordonné et pondéré. Notre objectif est de créer des listes ordonnées de commandes, de véhicules et de conducteurs pour utiliser l’algorithme de placement. La combinatoire de ces trois listes dans l’algorithme de placement permet d’obtenir une première solution (un planning journalier complet). Notre objectif est de permettre au planificateur de comparer plusieurs solutions. Pour construire plusieurs solutions, notre choix s’est porté sur un mécanisme d’exploration des solutions proches du raisonnement humain, tel que présenté précédemment. Pour chaque concept, nous avons une liste d’éléments ordonnés selon un poids, obtenu par les approches multicritères présentées ci-dessus. Pour créer une nouvelle liste dans chaque concept, contenant la même liste d’éléments mais ordonnés de manière différente, nous effectuons un tirage aléatoire pondéré par les poids de chaque élément. Une fois le tirage aléatoire pondéré effectué, nous obtenons une nouvelle liste pour chaque concept, et l’utilisation de l’algorithme de placement tel que présenté ci-dessus génère une nouvelle solution. L’ensemble de ces travaux sur la génération de planning à l’aide des méthodes multicritères est soumis dans « Journal of Decision Systems »