Le 22/04/2022 par houssin :
Titre : Optimisation de la couverture partielle dans les réseaux
Encadrement :
Laurent Houssin (ISAE-Supaero)
Sonia Cafieri (ENAC)
Localisation :
Toulouse : ISAE-Supaero ou ENAC
Contexte et littérature
La conception de réseaux est un large domaine pour lequel les modèles dépendent des applications désirées. Une classification de ces problèmes est disponible dans Magnanti and Wong (1984) et un point commun de ces problèmes est que leur modélisation conduit à des problèmes d’optimisation discrets ou mixtes (arbre couvrant, plus court chemin, emplacement d’installation…). Les champs d’application concernent les transports, les télécommunications, l’énergie, les chaines logistiques. Ces problèmes trouvent également naturellement leur place dans le tournant écologique que doit prendre le 21e siècle : conception des réseaux électriques, détermination des transports publics, gestion du trafic et de la congestion en environnement urbains.
Il est généralement trop couteux de connecter tous les nœuds d’un réseau, c’est pourquoi un choix judicieux doit être fait pour déterminer un sous-réseau qui satisfait la demande. Ce sous-réseau peut être spécifié par un ensemble de paires origine-destination. Parmi les problèmes les plus connus de conception de réseaux, le problème de la couverture maximale sous des contraintes de budget (MC) et celui de la couverture partielle sous des contraintes de réalisation minimale (PC) présentent un grand intérêt dans de nombreux champs d’application. Les deux problèmes considèrent un ensemble de paires origine-destination pondérées par un trafic entre les deux sommets.
Le problème MC est assez classique dans la littérature, il consiste à couvrir au mieux la demande des paires origine-destination tout en respectant un budget alloué à la construction du réseau. Concernant le problème PC, la problématique a été peu étudiée à part récemment dans Bucarey et al. 2022. Dans ce dernier problème, on cherche à minimiser le coût du réseau sous des contraintes de service minimum (plus précisément, un seuil de demande à respecter). Des travaux très récents (Bucarey et al. 2022) ont proposé une méthode basée sur la décomposition de Benders pour la résolution de ces 2 problèmes.
Verrous scientifiques
La prise en compte des incertitudes qui peuvent affecter les données de ces problèmes conduit à développer de nouveaux modèles d’optimisation et à adapter les techniques de résolution. Plus précisément, la version robuste du problème MC a été étudiée et récemment Conde et al. 2021 ont proposé une décomposition de Benders pour le problème de minimisation du regret. Cependant, il n’y a pas, à notre connaissance, de version robuste du problème (PC).
Objectif et méthodes envisagées
L’objectif de cette thèse est de proposer de nouveaux algorithmes de résolution basées sur des outils modernes de programmation mathématique entière tels que la décomposition de Benders, la génération de colonnes ou la relaxation lagrangienne pour la résolution de problèmes de conception de réseaux dans leur version nominal ou robuste. Dans un premier temps la version robuste du problème PC pourra être étudiée. Les versions « min regret » et « minimax » présentent toutes les deux un intérêt. D’autre part, l’étude des versions de ce problème avec capacité sur les nœuds pourra également être envisagée.
Références :
Magnanti, T. L. and Wong, R. T., Network Design and Transportation Planning: Models and Algorithms, Transportation Science, Volume 18, 1984.
V. Bucarey, B. Fortz, N. González-Blanco, M. Labbé, J. A. Mesa, 2022 Benders decomposition for network design covering problems, Computers & Operations Research, Volume 137, 2022.
E. Conde, M. Leal, A robust optimization model for distribution network design under a mixed integer set of scenarios, Computers & Operations Research, Volume 136, 2021.
Profil recherché :
Nous recherchons des profils issus de la recherche opérationnelle avec de bonnes compétences en programmation informatique.
Dossier de candidature :
– CV détaillé,
– Relevé des notes du Master indiquant le classement,
– Lettre de motivation,
– Éventuelles recommandations.
Contact :
