Logo LAAS-Carnot

Offres de recrutement et d’emploi au LAAS BOREAL 1.1.1

Stage

Visualisation du stage: STA629

Stage 2019-2020

S.NGUEVEU

ROC

DO

Optimisation combinatoire, Non linéarité, génération de colonnes, Approximation de fonctions

Conception de réseaux avec flots multiproduits prenant en compte la congestion

Ce stage se déroule dans le cadre d'une collaboration entre des chercheurs du LAAS-Toulouse (France) et du CIRRELT-Montréal (Canada).

Un problème de flot multi-produits de coût minimum consiste à satisfaire à coût minimum les demandes pour un ensemble de produits émanant de différentes sources, circulant sur le même réseau et devant être acheminés à différentes destinations. Une extension de ce problème au niveau stratégique/tactique est le problème de conception de réseau qui consiste à déterminer une configuration (ensemble de liaisons à inclure dans le réseau et dimentionnement de leurs capacités) de manière à minimiser la somme de coûts fixes des liaisons choisies et des coûts de routage des produits à travers le réseau ainsi construit. Ce problème que nous noterons MCF émerge généralement dans les réseaux de télécommunications, réseaux de transport et logistique, etc.

L'objectif de la collaboration est d'aborder des problèmes MCF avec des fonctions de coûts non linéaires, qui émergent lorsque sont pris en compte les files d'attente et les retards dû à la congestion dans les réseaux induits par l'aspect aléatoire des arrivées de demandes en produits au réseau et/ou des durées de trajets sur les différents arcs/liaisons. La congestion sur les arcs est modélisée comme un ratio entre le flot total et le surplus de capacité en voyant les arcs comme un système de file d'attente à une machine avec une loi de poisson des arrivées et des temps de services suivant une loi exponentielle. La congestion est vue comme le résultat des variations entre les dates d'arrivées et les durées de services sur les arcs à capacité limitée. Les problèmes résultants sont donc des MCF avec congestion.

Ce stage comprendra une recherche bibliographique des travaux récents sur le sujet ou des sujets voisins, ainsi que l’analyse des propriétés structurelles de tels problèmes. Cette analyse s'accompagnera d'une prise en main des outils de programmation mathématique de type génération de colonnes et de coupes permettant la résolution efficace des sous-problèmes dont le problème posé est une généralisation. Il s’agira enfin de développer des algorithmes de résolution du problème complet dont l’efficacité sera évaluée sur des jeux de données déjà disponibles.

Lieu du stage : Toulouse (LAAS) + possibilté de séjour ponctuel à Montréal (CIRRELT)

Poursuite en thèse possible

Master ou Ingénieur

Possibilité d'indemnisation

1

5 à 6 mois

Pour obtenir des informations complémentaires, contactez le responsable à cette adresse: