Relaxation lagrangienne et flot maximal pour un problème de transbordement

Session : LTSS3-3 / LTSS3 : Conception et gestion de réseau logistique
Vendredi 12 février 10:30 - 11:10 Salle : GI042
Lotte Berghman, Cyril Briand, Roel Leus et Pierre Lopez

Nous étudions l’ordonnancement des opérations de chargement/déchargement des camions dans un entrepôt. Nous nous concentrons sur le crossdocking (transbordement), qui favorise les transferts de produits entrants directement aux camions sortants, en minimisant le stockage intermédiaire dans l’entrepôt. Le problème crucial est de décider des actions à faire à chaque quai, en organisant une rotation rapide les camions permettant de respecter les fenêtres de présence des camions dans l’entrepôt. Notre étude concerne le niveau opérationnel : les camions sont répartis entre les différents quais de manière à minimiser le stockage pendant le transfert du produit. L’organisation interne de l’entrepôt n’est pas explicitement prise en considération ; on fait ainsi l’hypothèse que les ressources nécessaires pour charger ou décharger les camions sont disponibles en quantités suffisantes pour assurer la bonne exécution d’un ordonnancement. On suppose de plus que les quais peuvent être utilisés indifféremment pour le chargement ou le déchargement. Cette communication s’intéresse à comparer expérimentalement les bornes obtenues par résolution directe d’une formulation de programmation linéaire indexée par le temps avec une relaxation lagrangienne résolue par l’algorithme “push-relabel” de Goldberg.

Mots clés : crossdocking, problème de transbordement, programmation linéaire, relaxation, lagrangienne, flot maximal