Itinéraire des sous-commandes dans le réseau amont et le réseau direct

Télécharger le fichier pdf d’un mémoire de fin d’études

4S Network

La société 4S Network accompagne ses clients dans la conception et l’organisation de solutions in-novantes dédiées à la supply chain. Ce type de société, initialement appelée Third-party logistics (3PL) (logistique tierce partie), gère les flux logistiques de ses clients et coordonne les différents acteurs de leur supply chain. L’objectif est d’améliorer la performance de la chaîne logistique globale. Avec l’évolution des métiers de la logistique, le terme de Third-party logistics (3PL) a été étendu : les 4PL sont spécialisés dans le conseil et la mise en place de nouvelles solutions logistiques, tandis que les 5PL offrent en plus de nouveaux services en systèmes d’information améliorant les performances des chaînes logistiques [52]. 4S Network exerce aujourd’hui en tant que 3PL, 4PL ou 5PL. Dans cette thèse, pour plus de clarté, on assimilera ces trois secteurs au métier du 3PL.
4S Network travaille sur trois axes majeurs :
• Une visualisation de l’empreinte environnementale du transport, par le développement d’une pla-teforme web collaborative 1 servant de tableau de bord pour le calcul des émissions de CO2. Cette plateforme permet de piloter une stratégie environnementale d’entreprise dans le domaine du transport de marchandises.
• Un fonctionnement collaboratif en réseau par le produit/service KAYPAL MR2 permettant de piloter un réseau de palettes carton. Sur une palette, deux couches de produits différents sont séparées par une palette, appelée palette de séparation. L’idée est de remplacer ces palettes de séparation en bois par des palettes en carton réutilisables en moyenne 5 fois.
• La conception et gestion d’un réseau collaboratif, où l’objectif est de mettre en place des projets de mutualisation du transport. Cette thèse s’inscrit dans ce contexte, et plus particulièrement sur le projet des Centres de Routage Collaboratifs3, appelé CRC services, pour la grande distribution.

CRC services

Cette thèse a été réalisée dans le contexte de la montée en puissance du projet CRC services, initié en 2012. Son objectif principal est d’intervenir en support à la création du réseau et de produire des outils d’optimisation afin d’en améliorer le fonctionnement. On considère ici le cas d’une coopération entre plusieurs fournisseurs et distributeurs de la grande distribution, autour de plateformes de cross-docking appelées Centres de Routage Collaboratif (CRC) 4.
Dans un réseau logistique classique de la grande distribution on trouve généralement trois types d’acteurs :
• Les fournisseurs – qui possèdent leur propre réseau logistique d’entrepôts et d’usines de produc-tion. Ces sites sont les points de départ des expéditions. On appelle site fournisseur tout site d’un fournisseur.
• les clients qui reçoivent les commandes. On trouve dans cette catégorie des entrepôts de la grande distribution, des supermarchés ou des enseignes plus petites.
• les transporteurs qui délivrent les commandes d’un fournisseur jusqu’à un client.
Une commande d’un client vers un fournisseur est composée d’un ensemble de produits (que l’on défi-nira plus tard par lignes de commandes) qui peuvent être répartis sur différents sites. L’unité logistique est la palette. Des palettes composées de différents produits peuvent être préparées sur des sites fournis-seurs.
En France, l’essentiel du transport routier de marchandises est assuré par des PME/TPE (97% des entreprises ont moins de 50 salariés). Ces entreprises ne disposent généralement pas d’un réseau logis-tique et d’un volume de commandes suffisant pour transporter elles même leurs marchandises vers leurs clients. Il arrive même que le transporteur auquel un fournisseur a confié ses commandes sous-traite une partie des transports par manque de flux aller ou retour dans certaines régions. Cette accumula-tion d’intermédiaires sans organisation globale ne peut pas être efficace : la répartition des flux sur un nombre élevé de transporteurs engendre un faible taux de remplissage des véhicules. Ainsi, sur le plan économique, les fournisseurs paient plus cher pour de petits volumes de palettes livrés. Concernant la qualité de service, la fréquence de livraison que peut proposer un fournisseur n’est pas aussi élevée que le souhaiteraient les clients. D’un point de vue environnemental, un plus grand nombre de véhicules en sous capacité sont affrétés. Ils ont un impact négatif élevé sur l’environnement.
Pour remédier aux problèmes listés ci-dessus, 4S Network souhaite orchestrer une collaboration plus verticale (entre fournisseurs, transporteurs et clients) sur un secteur d’activité donné : la grande distribution. Contrairement aux approches classiques qui consistent à consolider les flux à proximité des fournisseurs, le service CRC propose un ensemble de points de consolidation proches des clients. Il offre la possibilité aux fournisseurs d’alimenter un CRC en camions pleins sur de longues distances. CRC services se place comme l’interlocuteur des clients pour convenir d’un créneau de livraison pour l’ensemble de leurs fournisseurs et réaliser efficacement des tournées de livraison depuis le CRC. Ce fonctionnement permet à des fournisseurs de toutes tailles de pouvoir transporter leurs marchandises à des prix raisonnables dans le réseau logistique. Enfin, les transporteurs peuvent collaborer avec le service CRC en proposant leurs services de transport pour certaines régions. Ils peuvent également mettre à disposition une partie de leurs plateformes logistiques, afin d’y proposer le service CRC. En échange, le service CRC leur garantit des flux à la fois plus volumineux et plus réguliers.
Ce projet propose également un réseau logistique transparent entre fournisseurs et clients : grâce à un service de traçabilité des palettes passant par les CRC, les fournisseurs peuvent avoir une vision du transit de leurs commandes, ainsi que des coûts associés. Cette prise en compte globale du volume et le traitement global du transport de l’ensemble des couples fournisseur-client permet une optimisation des flux beaucoup plus efficace à tous les niveaux.
On retrouve donc dans cette nouvelle organisation du réseau logistique les trois types d’entités vus précédemment, auxquels viennent s’ajouter les plateformes collaboratives régionales (CRC). Elles per-mettent de réaliser plus simplement la mutualisation des marchandises en aval des CRC et facilitent la collaboration entre transporteurs. Ce fonctionnement est profitable à tous les acteurs :
• L’organisation du transport des commandes pour les fournisseurs est simplifiée : les commandes à destination de plusieurs clients d’une même région sont envoyées vers un unique CRC.
• Les transporteurs ont en charge un volume de commande suffisant pour assurer de bons taux de remplissage des véhicules : ils ne doivent plus se soucier de sous-traiter une partie de leur transport à d’autres transporteurs.
• Les clients gagnent en qualité de service : l’accroissement des taux de remplissage permet aux fournisseurs d’envoyer de plus petites commandes sans augmenter le coût du transport. Cela per-met donc une hausse des fréquences de livraison. Dans le même temps, le nombre de véhicules à réceptionner diminue, car les commandes de différents fournisseurs sont regroupées sur CRC et livrées ensemble aux clients.
En parallèle de la thèse, CRC services a fait l’objet d’un projet Predit avec partenariat avec GS1 et Mines ParisTech à partir de 2013. Un projet pilote a démarré en 2014 avec la mise en place d’une première plateforme CRC dans le sud de la France à Saint Martin De Crau. Elle dessert plus de 100 plateformes de distributeurs tels que Auchan, Métro ou Intermarché dont les marchandises proviennent de plusieurs fournisseurs comme SC Johnson, le Pool GILDE (Mapa Spontex, Bourjois, Wilkinson Sword), Mars, Ferrero. Cette initiative de mutualisation a été récompensée par le « Grand Prix des ROIS de la Supply Chain » en 2016. La même année, cinq nouvelles plateformes CRC ont été ouvertes à Arras, Brumath, Lomme, Nantes et Bordeaux. L’objectif est d’implanter une douzaine de CRC sur toute la France, avec plusieurs centaines de milliers de mouvements de palettes prévus dès 2018.

Sites du réseau logistique

Nous considérons un réseau logistique tel qu’illustré par la figure 2.1. Il comprend trois fournisseurs avec respectivement 2, 4 et 1 sites logistiques, deux CRC et 18 clients. On distingue un réseau amont, allant des fournisseurs aux CRC et un réseau aval, allant des CRC aux clients. On considère de plus que des commandes peuvent être expédiées directement du fournisseur au client. On parle alors de réseau direct.

Réseau amont

Le réseau amont concerne le transport entre les sites de production ou d’entreposage des fournisseurs et les CRC. Les sites des fournisseurs sont les origines de tous les produits qui transitent dans le réseau. Un fournisseur peut posséder un ou plusieurs sites : certains dédiés à la production (usines) et d’autres au stockage (entrepôts). Ces sites peuvent avoir différentes fonctions logistiques. Afin de généraliser ces fonctions on ne distingue pas les usines des entrepôts, mais on considère que chaque site fournisseur peut posséder – ou non – les fonctions logistiques suivantes :
• Transfert. On définit le transfert par l’action de décharger des marchandises d’un véhicule et de les recharger dans un véhicule différent.
• Préparation de commande. La préparation de commande ou picking consiste à regrouper diffé-rents produits sur une même palette. Elle implique un transfert pour les produits qui ne sont pas fabriqués sur le site de préparation. Nous reviendrons plus longuement sur cette fonction dans la section 2.4.2.

Réseau aval

Le réseau aval réalise la distribution des marchandises depuis les CRC jusqu’aux clients. Les véhicules partent de chaque CRC et livrent un ou plusieurs clients.

Flux de marchandises : commandes et sous-commandes

Commandes

Une commande est définie comme un ensemble de produits qu’un fournisseur doit livrer à un client a une date donnée. La taille d’une commande peut-être exprimée suivant différentes dimensions : nombre de palettes et/ou poids. Notons qu’une commande a une destination unique, mais peut avoir plusieurs origines : les produits d’une commande peuvent provenir de différents sites d’un même fournisseur, mais doivent être livrés au client par le même véhicule.

La préparation de commande

On distingue deux types de palettes :
• Les palettes homogènes contiennent un seul type et une quantité toujours identique de produits. En sortie de production, toutes les palettes sont supposées homogènes.
• Les palettes hétérogènes peuvent contenir plusieurs types de produits et des quantités ajustées pour correspondre à une commande particulière. Le fait de créer une palette hétérogène est appelé préparation de commandes ou picking. Les usines ne sont pas toujours en mesure d’effectuer cette préparation de commande et les palettes d’une commande doivent parfois être préparées dans un entrepôt ou une autre usine du fournisseur. Lorsque la préparation ne peut-être faite sur le site de production, la préparation se traduit donc par un transfert sur un site de préparation du fournisseur. CRC services ne gère pas les stocks des fournisseurs, qui garde la main sur ses flux internes. Aussi, ne sont communiquées à CRC services que les quantités correspondant aux commandes des clients et les décisions de passage par les sites de préparation de commande.
Exemple 1. La figure 2.2 illustre un exemple de préparation de palettes. Une commande comprend 5 types de produits A,B,C,D et E), avec une demande respective de 1.9, 0.7, 0.6, 0.4 et 0.1 palettes. Le produit A (1.9 palettes) est réparti sur deux palettes : une palette homogène P 1 et une palette hétérogène P 2 d’où l’on a retiré 10% de produit A. Les autres produits B, C, D et E sont regroupés sur deux palettes hétérogènes P 3 et P 4. La commande globale est donc composée de quatre palettes. P 1 est la seule palette qui ne nécessite pas de préparation de commande.

Transporteurs et tournées de véhicules

Les transporteurs sont les acteurs qui transportent les marchandises des sites des fournisseurs jusqu’aux clients. On considère dans cette thèse que le transport est sous-traité. 4S Network ne possède pas de flotte ni de plateforme logistique et confie le transport et les opérations de cross-docking à un ensemble de prestataires logistiques spécialisé. Le réseau logistique fonctionnant grâce à plusieurs prestataires, plusieurs structures tarifaires et contraintes métier peuvent y cohabiter. Dans cette section, nous décri-vons les différents types de tournées et les structures tarifaires usuellement rencontrées.
On appelle tournée le trajet emprunté par un véhicule entre plusieurs sites du réseau logistique mutualisé. Le transport étant sous-traité, on considère des tournées ouvertes, c’est-à-dire qui ne prennent pas en compte le voyage des véhicules de leur dépôt jusqu’au premier site visité, ni le retour au dépôt après visite au dernier client. De plus, le nombre de sites visités par tournée est souvent limité à trois. Cette contrainte est courante dans le domaine du transport de la grande distribution française : cela permet de limiter les risques de retard en cascade. On appelle segment le trajet direct d’un véhicule entre deux sites. Une tournée est donc composée d’un ou plusieurs segments.

Types de tournées et structures tarifaires dans le réseau amont

Dans le réseau amont, on considère une structure tarifaire dite less-than-truckload (Less-than-truckload (LTL)). Cette tarification est généralement utilisée en transport routier de marchandises pour facturer le transport d’un petit nombre de palettes dans un véhicule. Pour une région d’origine donnée, elle est représentée par une matrice qui fixe un prix pour chaque destination et chaque valeur possible de chargement. Le tarif Less-than-truckload (LTL) est dégressif : le prix unitaire à la palette diminue (de façon non linéaire) lorsque le nombre de palettes augmente.
Un coût fixe de transfert est appliqué à chaque palette transférée d’un véhicule à un autre. Enfin, un dernier coût appelé coût d’ouverture de porte, est facturé pour chaque arrêt d’un véhicule entre son point de départ et son point d’arrivée.

Types de tournées et structures tarifaires dans le réseau aval

Dans le réseau aval, on considère une structure tarifaire dite full truckload Full-truckload (FTL). En transport routier de marchandises, ce tarif est utilisé pour facturer l’utilisation d’un camion complet sur un itinéraire prédéterminé. Il ne dépend pas du nombre de palettes transportées.
Une tournée dans le réseau aval part d’un CRC et visite un ou plusieurs clients. Le nombre maximum de clients visités par une tournée varie entre 3 à 5.
Exemple 2. La figure 2.4 présente un exemple de transport dans le réseau aval avec 2 CRC et 11 clients. Trois tournées partent de chaque CRC. Deux CRC peuvent livrer un même client si celui-ci est assez proche des deux CRC.
Le tarif FTL est calculé comme suit : la zone de chalandise de chaque CRC est divisée en plusieurs zones associées à un coût. Le tarif FTL correspond à celui de la zone traversée la plus chère. De plus, un coût d’ouverture de porte est ajouté à chaque arrêt du véhicule chez un client.
Exemple 3. La figure 2.5 donne un exemple de la répartition des clients dans les zones. Une tournée aval visite 3 clients situés dans les zones 2, 3 et 4.
La figure 2.6 montre le coût associé à chaque zone. La zone 4 étant la plus chère, c’est cette dernière qui est retenue pour obtenir le coût de location du véhicule. Il faut ensuite y ajouter trois fois le coût unitaire d’ouverture de porte pour obtenir le prix total de la tournée.

Conception de réseau de transport

Les chaînes logistique complexes incluent plusieurs types de sites avec des fonctions variées (sites de production, d’assemblage, de stockage longue durée, de préparation de commandes, de cross-docking, centres de distribution, sites clients, etc.). Le réseau logistique prend donc la forme d’un graphe à plu-sieurs niveaux. La notion de conception de réseau recouvre plusieurs types de décision : localisation et dimensionnement des sites, choix des modes de transport, allocation des produits et clients à chaque site, définition des flux logistiques récurrents, recherche de prestataires.
Concernant les décisions purement stratégiques (localisation, dimensionnement, allocation), on parle de Supply Chain Network Design. Nous renvoyons le lecteur à l’état de l’art de Melo et al. [73] ou au chapitre de Alumur et al. [1]. Un état de l’art du problème de localisation et routage d’un réseau à N-échelons est proposé par Gonzalez-Feliu [46]. Dans cette catégorie, Gendron et Semet [43] étudient un problème de localisation et routage à trois échelons pour un problème de livraison rapide. L’objectif est de déterminer les itinéraires des commandes en minimisant les coûts de transport et d’utilisation des plateformes. Les auteurs montrent qu’une modélisation basée sur les chemins est toujours meilleure qu’une modélisation basée sur les arcs.
Nous utilisons la définition proposée par Campbell [15] pour définir les problèmes de conception de réseau avec une tarification LTL. Les demandes prises en compte dans ces problèmes peuvent avoir une origine et une destination correspondant à des sites clients mais, le plus souvent, les demandes sont agré-gées et se réfèrent à des plateformes d’entrées ou de sorties du réseau (appelées end-of-line en anglais). Les sommets du réseau correspondent donc à ces plateformes et les arcs aux trajets les plus courts entre deux sommets. Une caractéristique forte est que les distances entre plateformes généralement élevées : cela encourage la consolidation des commandes de petite taille sur les plateformes et permet de rentabi-liser l’usage des véhicules. Le problème consiste à déterminer les capacités de transport à installer sur les arcs de manière à permettre l’acheminement des commandes en minimisant les coûts de transport. Ce coût est constitué d’un coût fixe pour l’utilisation de chaque arc et d’un coût variable lié au passage des commandes dans le réseau. Crainic [31] définit et nomme ce problème multi commodity network design. Sa résolution permet de répondre à des questions généralement stratégiques ou tactiques.
Le nombre d’articles traitant de conception de réseau est considérable. C’est pourquoi nous focali-sons cette section sur deux caractéristiques étudiées dans cette thèse :
• la modélisation de la tarification LTL par une fonction linéaire par morceaux ;
• le merge-in-transit qui est une pratique consistant à regrouper les produits d’une commande (ou les produits qui constituent le produit final), au cours de leur itinéraire dans le réseau logistique, sur des plateformes dédiées.

Fonctions de coût linéaires par morceaux

Supposer que le transport est sous-traité nous impose d’utiliser dans les modèles mathématiques les mêmes tarifs que ceux pratiqués par les transporteurs. Ils peuvent être très différents d’un transporteur à l’autre. Outre les différents tarifs qui dépendent uniquement du nombre de kilomètres, une caracté-ristique de cette thèse est d’utiliser la tarification LTL, qui dépendant de la distance mais également du chargement des véhicules. De nombreux transporteurs proposent des matrices qui calculent un tarif selon deux dimensions : le nombre de palettes transportées et le nombre de kilomètres parcourus. Le tarif à la palette diminue avec la charge, de manière non linéaire. Dans cette thèse, comme dans d’autres travaux de la littérature, cette dégressivité est modélisée par une fonction linéaire par morceaux. Chan et al. [18] et Hill et al. [51] utilisent une fonction linéaire par morceaux appelée modified all-unit discount cost (MAUD). Avec cette fonction, il est parfois profitable de déclarer un volume de marchandises plus grand pour bénéficier d’un tarif à la palette plus attractif. Lapierre et al. [62] construisent un fonction de coût composite en combinant plusieurs types de fonctions linéaires par morceaux. Muriel et al. [77] étudient un problème de multi-flot dans un réseau où les coûts sont modélisés par une fonction linéaire par morceaux. Ils développent une heuristique basée sur la relaxation linéaire du modèle. Chang [19] résolvent un problème bi-objectif de transport dans un réseau multimodal. Les deux objectifs à minimi-ser sont le coût de transport, modélisé par une fonction linéaire par morceaux et la durée du transport. La méthode de résolution développée décompose le problème en un ensemble de petits problèmes plus faciles à résoudre.
Croxton et al. [32] comparent trois modèles de coûts linéaire par morceaux. Ils montrent que les relaxations linéaires de ces trois modélisations sont équivalentes et peuvent être approximées par leurs enveloppes convexes inférieures. Un résultat appréciable est que si la fonction linéaire par morceaux est concave, alors son enveloppe convexe inférieure est linéaire, et peut-être représentée par la droite joi-gnant l’origine et le point de la fonction de charge maximale. Moccia et al. [75] étendent cette propriété en montrant que, sous certaines conditions, l’enveloppe convexe inférieure d’une fonction linéaire par morceaux non concave peut-être représentée par cette même droite. Cet article a inspiré les travaux de recherche présentés au chapitre 7.

Merge-in-transit

La contrainte de regroupement est centrale pour les problèmes de transport dans le réseau mutualisé. En effet, les sous-commandes d’une commande n’ont pas toutes la même origine et doivent se regrouper sur une plateforme pour être livrées au client dans le même véhicule. Chopra et al. [22] définissent la notion de merge-in-transit comme le regroupement de plusieurs parties d’une commande provenant de différents sites afin de les livrer ensemble au client. Cole et al. [24] proposent un modèle de conception de réseau avec des contraintes de regroupement lié à un système d’information géographique. Ce modèle détermine l’ouverture de centres de regroupement et l’itinéraire des marchandises. Croxton et al. [33] étudient un problème de conception de réseau logistique avec contraintes de regroupement ainsi qu’une structure de coût linéaire par morceaux. Les auteurs proposent un algorithme de plans coupants suivi d’un branch-and-bound. Dans Song et al. [87], la plateforme de cross-docking est utilisée comme un centre de regroupement. Le problème est résolu grâce à une relaxation lagrangienne.

Planification opérationnelle des transports dans un réseau

Cette section traite d’un famille de problèmes de conception de réseau intégrant des décisions plus opé-rationnelles que dans la section précédente. Le problème consiste à définir le service (trajet, chargement, horaire) de chaque acteur du réseau mutualisé dans un horizon de quelques jours à quelques semaines.
On parle alors de Service Network Design (Service Network Design Problem (SNDP)). La modélisation de ce problème repose essentiellement sur le multicommodity network design décrit plus haut, mais en y ajoutant de nouvelles considérations d’ordre tactique ou opérationnel. Wieberneit et al. [98] propose une étude des variantes du SNDP. Crainic [29] classifient les SNDP en deux catégories : le frequency service network design problem est utilisé pour répondre à des problématiques tactiques assez proches du niveau opérationnel (par exemple choisir entre plusieurs politiques de transport dans le réseau), le dynamic service network design problem répond a des problématiques beaucoup plus opérationnelles, comme déterminer les itinéraires au jour le jour dans un réseau.
Les problèmes de type Service Network Design Problem (SNDP) reposent sur des graphes espace-temps décrits au chapitre précédent. L’intégration de composantes opérationnelles dans un problème tactique passe par la gestion de la flotte de véhicules. Une première manière approche pour prendre en considération une flotte de véhicules est d’ajouter des contraintes équilibrant le nombre de véhicules entrant et sortant de chaque plateforme. Ces contraintes d’équilibre sont l’occasion d’introduire un coût de repositionnement des véhicules voyageant à vide. Nous mentionnons quelques articles entrant dans cette catégorie en section 4.2.1.
Une approche encore plus précise pour représenter des décisions censées se répéter au cours du temps (semaines types de travail, lignes de transport régulières) est de recourir à des plans de transports cycliques, c’est-à-dire comportant un arc de retour entre un sommet de la dernière période et un sommet de la première période du graphe espace temps. On définit alors des tournées appelées cycles, abordées en section 4.2.2.

Équilibre

Jarrah et al. [54] proposent une modélisation intégrant des contraintes d’équilibre entre le nombre de véhicules entrant et sortant sur chaque sommet du réseau. Ils considèrent une tarification FTL et des coûts de manutention de marchandises en cas de transfert d’un véhicule à un autre. Le problème résul-tant est résolu avec une méthode de slope scaling. Erera et al. [38] étudient un problème de plans de chargement avec fenêtres de temps, tarification FTL et coûts de transfert à chaque sommet. Ils intègrent une contrainte d’équilibre des flux de véhicules sur chaque sommet. Ce problème est résolu avec une recherche locale basée sur la résolution de PLNE. Ce travail est étendu dans [39] : à partir d’un plan de chargement, le trajet de chaque véhicule et les journées de travail de chaque conducteur sont déter-minés. Une approche en trois phases est utilisée : la première phase fait correspondre les expéditions des marchandises avec le départ des véhicules, la deuxième détermine les fenêtres horaires de chaque expédition et la troisième créé les journées de travail des conducteurs.

Cycles

Andersen et al. [4] présentent un modèle de SNDP multi-modal reposant sur des cycles dans un graphe espace temps. Andersen et al. [3] proposent des modélisations plus génériques du SNDP intégrant des cycles et montrent que les modèles dont les variables représentent des cycles de véhicules surpassent ceux basés sur les arcs. Pedersen et al. [80] proposent un modèle générique ainsi qu’une recherche tabou. Teypaz et al. [92] proposent un algorithme de décomposition où trois sous-problèmes sont résolus séquentiellement : l’itinéraire des commandes, les cycles empruntés par les véhicules, et la planification dans le temps de ces véhicules. Pour ce même type de problème, Andersen et al. [2] proposent un algorithme de branch-and-price où deux type colonnes sont générées : des tournées de véhicules et des itinéraires marchandises. On y retrouve la co-existence de la vision véhicule (tournées) et de la vision marchandises (itinéraires). Crainic et al. [30] intègrent un troisième type de coût lié à l’utilisation des véhicules. La méthode de résolution est basée sur la génération de colonnes et un algorithme de slope scaling qui résout itérativement un problème relaxé.

Coûts

Les problèmes de type SNDP considèrent généralement deux types de coûts liés au transport ([92], [2], [10]) : un coût fixe lié à l’ouverture d’un service qui représente l’utilisation d’un véhicule pour réaliser un trajet d’un sommet à un autre du réseau et un coût variable relatif au flux de marchandises trans-porté. La méthode exacte développée récemment par Boland et al. [10] prend en compte ces deux types de coûts. Leur algorithme, appelé Dynamic Discretization Discovery, permet de trouver des solutions optimales dans un réseau espace-temps discrétisé à la minute, pour des instances comprenant jusqu’à 200 commandes. Au chapitre 8, nous décrirons comment étendre l’utilisation de cet algorithme à un problème combinant Service Network Design et tournées de véhicules. Notons enfin les articles qui, tout comme dans cette thèse, utilisent une tarification LTL ([54] [38] [75] [66] [67]) ou des coûts de transfert ([54] [38] [75] [66] [67]).

Application des problèmes de type SNDP

Les problèmes de types SNDP peuvent avoir plusieurs champs d’application, notamment en transport multi-modal. L’article de Moccia et al. [75] considère un SNDP pour la conception de plans de transport sur un réseau multimodal en Italie. Le problème est résolu avec une heuristique basée sur la génération de colonnes. Chang [19] étudie un problème de SNDP bi-objectif dans un réseau multi-modal. Le pre-mier objectif est de minimiser les coûts de transport, modélisé par des fonctions linéaires par morceaux. Le second objectif est de minimiser la durée du transport. Le problème est résolu par une heuristique basée sur la relaxation lagrangienne.
Un autre champ d’application est le transport express. Lin [66] étudie la planification du transport express pour une entreprise taïwanaise. Le réseau en étoile est constitué de terminaux et de plateformes intermédiaires. Une première modélisation, basée sur la modélisation de SNDP, est proposée ainsi que deux algorithmes : une relaxation lagrangienne et une énumération implicite. Cette dernière donne de meilleurs résultats sur des instances réelles allant jusqu’à dix terminaux et trois plateformes intermé-diaires. Lin et al. [67] proposent une nouvelle modélisation de ce problème intégrant une contrainte de conservation des flux des véhicules à chaque sommet. Ils proposent également un algorithme d’énumé-ration implicite pour un problème similaire à [66]. L’algorithme d’énumération est testé sur des données provenant d’une compagnie de transport aérien express qui possède 13 avions. Kim et. al [57] étudient un problème de SNDP dans un réseau multi-modal pour l’expédition express de marchandises. Leur modèle comprend une contrainte d’équilibre des flux de véhicules. Leur heuristique basée sur la généra-tion de colonnes et de plans coupants permet de trouver de bonnes solutions à des problèmes de grande taille. Armacost et al. [5] modélisation un SNDP pour l’expédition express de marchandises avec nou-veau type de variables qu’ils nomment variables composites. Les auteurs montrent que la relaxation linéaire de leur modèle est meilleure que celle du modèle classique.

Table des matières

1 Introduction 
1.1 La mutualisation du transport : motivations et enjeux
1.2 Problématiques de recherche de cette thèse
1.3 Plan de la thèse
2 Description du réseau logistique mutualisé 
2.1 4S Network
2.2 CRC services
2.3 Sites du réseau logistique
2.3.1 Réseau amont
2.3.2 Réseau aval
2.4 Flux de marchandises : commandes et sous-commandes
2.4.1 Commandes
2.4.2 La préparation de commande
2.4.3 Sous-commandes
2.5 Transporteurs et tournées de véhicules
2.5.1 Types de tournées et structures tarifaires dans le réseau amont
2.5.2 Types de tournées et structures tarifaires dans le réseau aval
2.6 Itinéraires des commandes et sous-commandes
2.6.1 Itinéraire des sous-commandes dans le réseau amont et le réseau direct
2.6.2 Itinéraire des commandes dans le réseau aval
2.7 Un exemple de fonctionnement global du réseau
3 Cadre scientifique de la thèse 
3.1 Facturation du transport
3.2 Fonction linéaire par morceaux
3.2.1 Définition
3.2.2 Modélisation pour un véhicule
3.2.3 Modélisation pour plusieurs véhicules
3.3 Modélisation des transports dans un réseau espace temps
3.4 Génération de colonnes
3.5 La recherche tabou
4 État de l’art : problèmes de conception de réseau logistique et tournées riches de véhicules 
4.1 Conception de réseau de transport
4.1.1 Fonctions de coût linéaires par morceaux
4.1.2 Merge-in-transit
4.2 Planification opérationnelle des transports dans un réseau
4.2.1 Équilibre
4.2.2 Cycles
4.2.3 Coûts
4.2.4 Application des problèmes de type SNDP
4.2.5 Synthèse
4.3 Tournées de véhicules avec transfert
4.3.1 Tournées de véhicules avec cross-dock
4.3.2 Problèmes de collectes et livraisons avec transferts
4.4 Problèmes riches de tournées de véhicules
4.4.1 Tournées multi-trip
4.4.2 Contraintes temporelles sur les tournées
4.4.3 Transport sous-traité
4.4.4 Collaboration entre transporteurs
4.5 Conclusion
5 Modèles mathématiques pour l’estimation des coûts dans le réseau mutualisé 
5.1 Introduction
5.2 Description du problème modélisé
5.2.1 Définition des ensembles du réseau logistique
5.2.2 Tournées de véhicules et structure tarifaire
5.2.3 Flux et structure des marchandises
5.3 Modélisation des transferts
5.3.1 Structure de transfert complète
5.3.2 Structure de transfert en étoile
5.4 Modèles mathématiques
5.4.1 Itinéraire amont
5.4.2 Itinéraire aval
5.4.3 Itinéraires directs
5.4.4 Lien entre réseau amont et réseau aval
5.4.5 Satisfaction de la demande
5.4.6 Modélisation des tournées
5.4.7 Fonction objectif
5.4.8 Deux modèles mathématiques
5.5 Tests numériques
5.5.1 Instances
5.5.2 Résultats
5.6 Conclusion
6 Distribution depuis les CRC : un problème riche de tournées de véhicules 
6.1 Description du problème
6.1.1 Commandes
6.1.2 Modélisation : un sommet pour chaque commande
6.1.3 Transport
6.1.4 Définition du problème traité
6.2 La génération de colonnes pour les problèmes riches de tournées de véhicules
6.3 Méthode de résolution
6.3.1 Modélisation du problème maître
6.3.2 Ensemble de colonnes initiales
6.3.3 Résolution des sous-problèmes
6.3.4 Tests de réalisabilité d’une insertion
6.4 Tests numériques
6.4.1 Instances
6.4.2 Paramétrage
6.4.3 Résultats
6.4.4 Analyse des résultats selon le pourcentage d’horaires fixés
6.5 Conclusion et perspectives
7 Optimisation conjointe des réseaux amont et aval 
7.1 Introduction
7.2 Modélisation du réseau amont
7.2.1 Description et modélisation du réseau
7.2.2 Coût des tournées dans le réseau amont
7.3 Modélisation du réseau aval
7.3.1 Description et modélisation du réseau
7.3.2 Coûts des tournées dans le réseau aval
7.4 Commandes et sous-commandes
7.5 Modélisation du problème FSNDRP −CRC
7.5.1 Modèle FSNDRP −CRC
7.5.2 Modélisation pour la génération de colonnes FLSNDRP −CRC
7.6 Matheuristique pour la résolution du SNDRP-CRC
7.6.1 Solution initiale
7.6.2 SP1 – Génération des itinéraires amont
7.6.3 SP2 – Génération des tournées de véhicules aval
7.7 Tests numériques
7.7.1 Génération des instances
7.7.2 Paramétrage de la recherche tabou
7.7.3 Écart entre la relaxation linéaire et la solution
7.7.4 Influence de la discrétisation
7.7.5 Influence du coût de stockage
7.8 Conclusion et perspectives
8 Conception intégrée de plans de chargement et de tournées de véhicules 
8.1 Introduction
8.2 Description du problème
8.3 Formulations sur les tournées et sur les arcs du SNDRP
8.3.1 Notations
8.3.2 Réseau espace temps
8.3.3 Modélisation du SNDP
8.3.4 Formulation FR
8.3.5 Formulation FA
8.4 Méthode de résolution
8.5 Tests numériques
8.5.1 Instances
8.5.2 Comparaison des deux formulations
8.5.3 Comparaison logistique
8.6 Conclusion
9 Outils logiciels réalisés 
9.1 Choix technologiques
9.2 Outil de simulation
9.2.1 Présentation de l’outil
9.2.2 Données d’entrées et paramètres
9.2.3 Résultats
9.3 Outil opérationnel
9.3.1 Présentation de l’outil
9.3.2 Utilisation de l’outil
9.4 Conclusion et perspectives
10 Conclusion 
Acronymes 

Télécharger le rapport complet