La logistique interne des ateliers de production repose de plus en plus sur des flottes de robots mobiles autonomes (AMR) chargés d'acheminer les produits semi-finis entre les machines ou de les approvisionner en composants. La planification de ces transports doit être cohérente avec le plan de production : chaque transfert doit s'insérer dans la fenêtre temporelle imposée par l'ordonnancement, sans en dégrader la performance. Des travaux récents ont modélisé ce problème comme un Pickup-and-Delivery Problem (PDP) avec contraintes de précédence issues du plan de production, et ont développé un algorithme de Branch-and-Price (B&P) basé sur une décomposition de Dantzig-Wolfe. Cet algorithme décompose le problème global en un problème maître de partitionnement d'ensemble, et en un sous-problème de pricing correspondant à la recherche d'un plus court chemin élémentaire avec contraintes de ressources (ESPPRC) dans le graphe de transport et pénalités d'avance/retard. La résolution de ce sous-problème constitue le principal verrou algorithmique : faute d'un algorithme dédié, il est actuellement confié à un solveur MILP généraliste, ce qui limite fortement les performances sur les instances de grande taille.

Dans la grande majorité des ateliers de production réels, la topologie du réseau de transport est fortement structurée. Les robots circulent sur un réseau de voies balisées dont le graphe fonctionnel, représentant les itinéraires possibles entre buffers, peut naturellement être modélisé comme un graphe orienté acyclique (DAG). Cette hypothèse est raisonnable lorsque, par construction ou par convention d'exploitation, les flux entre buffers sont unidirectionnels et ne forment pas de cycles : c'est le cas notamment dans les ateliers organisés en flux tirés (lignes en U, lignes de production, lignes arborescentes). L'hypothèse DAG simplifie profondément le sous-problème de pricing : l'espace des routes élémentaires est fini et de cardinalité polynomiale (sans cycle, toute route visite chaque buffer au plus une fois), et le calcul du plus court chemin sur un DAG se réduit à une programmation dynamique en O(|V|+|A|) par balayage dans l'ordre topologique.

L'objectif de ce stage est d'explorer cette hypothèse structurelle et d'en tirer parti pour concevoir un algorithme de pricing dédié, significativement plus rapide que la résolution MILP, et d'évaluer son impact sur les performances globales du B&P. Le travail se déclinera en trois grandes étapes. Dans un premier temps, le stagiaire formalisera la structure du graphe DAG et ses conséquences sur la définition des routes et des ressources du problème de pricing, en portant une attention particulière aux interactions entre la non-monotonie du coût réduit (due aux pénalités d'avance/retard issues du couplage production-transport) et la structure acyclique du graphe. Dans un second temps, le stagiaire développera et implémentera l'algorithme de pricing par programmation dynamique, en intégrant les ressources du problème (capacités, fenêtres de temps, contraintes de précédence ). Enfin, l'algorithme sera intégré dans le B&P existant et évalué sur des instances benchmarks issues de la littérature de l'ordonnancement de job-shop (instances de Lawrence et Applegate-Cook, adaptées à une topologie DAG) ainsi que sur des instances synthétiques couvrant différentes structures et densités de réseaux acycliques.

Les résultats attendus sont : (i) une analyse formelle des propriétés du pricing sous hypothèse DAG, (ii) un algorithme de pricing implémenté et intégré dans le B\&P, et (iii) une évaluation computationnelle comparée avec le pricing MILP.

Ce sujet s'adresse aux étudiant(e)s de niveau Master 1 ou 2 à dominante Recherche Opérationnelle, Mathématiques Appliquées ou Informatique. Des compétences en programmation (Python ou C++) et des bases en optimisation combinatoire (programmation linéaire en nombres entiers, algorithmes de graphes) sont requises. Une connaissance des méthodes de décomposition (génération de colonnes, Branch-and-Price) sera appréciée sans être indispensable.

Merci de soumettre votre candidature en joignant un CV, une lettre de motivation et vos derniers relevés de notes.