Recherche Opérationnelle pour les Réseaux et le Transport (RORT)

Titre :

Recherche Opérationnelle pour les Réseaux et le Transport (RORT)

Section :

Optionnel

État pour cette année :

OPEN

Mots clés :

Réseaux, Transport, Programmation Mathématique

Ects :

2

Responsable :

José Neto (Télécom Sud Paris)

Intervenants :

José Neto (Télécom Sud Paris)

Sonia Vanier (Ecole Polytechnique)

Prérequis :

Programmation mathématique (simplexe, dualité, Branch & Bound), Méthodes de décomposition en PLNE

Objectif :

L’objectif de ce module est d’apporter des compétences concernant la modélisation ainsi que les méthodes de résolution de problèmes rencontrés dans les réseaux (d’énergie, de transport, de télécommunications). Il complète les cours obligatoires du MPRO par l’illustration et la mise en oeuvre de concepts et techniques qui y sont déjà introduits (méthodes de génération de contraintes/colonnes, de décomposition). Il vise aussi à introduire d’autres approches importantes (programmation biniveau, théorie des jeux) pour aborder toute une diversité de problématiques liées aux réseaux et impliquant une hiérarchie dans les décisions (tarification, positionnement d’infrastructures).

Contenu / Plan :

L’organisation du cours est structurée en trois parties. Les deux premières séances de cours sont dédiées à la présentation de modèles relatifs à divers problèmes rencontrés dans les réseaux ainsi qu’à la mise en oeuvre de méthodes d’optimisation pour les résoudre. Les séances suivantes sont essentiellement consacrées à la réalisation d’un projet (qui ne devrait nécessiter que peu ou pas de travail à la maison). Un examen écrit (1h30) portant sur les deux premières séances de cours est réalisé lors de la quatrième séance. A l’issue des six séances un rapport et le code source sont à remettre pour l’évaluation du projet.

• Séance 1 : Problèmes liés aux tournées de véhicules et multiflots dans les réseaux : modèles et méthodes de résolution.
• Séance 2 : Introduction à la programmation biniveau et à la théorie des jeux appliquées aux réseaux.
• Séances 3 : Projet.
• Séance 4 : Examen écrit (1h30) + Projet.
• Séance 5 : Projet.
• Séance 6 : Projet.

Bibliographie :

• Algorithmic Game Theory. Cambridge University Press (2007).
• Barnhart C., Hane C. A., Vance P. H. (2000). Using branch-and-price-and-cut to solve origin- destination integer multicommodity flow problems. Operations Research 48(2) :318-326.
• Frangioni A., Gendron B. (2009). 0-1 reformulations of the multicommodity capacitated net- work design problem. Discrete Applied Mathematics 157(6) : 1229-1241.
• Kleinert, T., Labbé, M., Ljubić, I., Schmidt, M. (2021). A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization. EURO Journal on Computational Optimization , Vol. 9, 100007.
• Toth, P., Vigo, D. (2014). Vehicle Routing : Problems, Methods, and Applications. MOS-SIAM Series on Optimization.

Liens :

(aucun)

Compétences visées :

Au terme du module RORT, l’étudiant sera à même de

• modéliser divers problèmes classiquement rencontrés dans les réseaux, et
• élaborer et mettre en œuvre des méthodes d’optimisation appropriées pour les résoudre.

Modalités de contrôle :

• Un compte-rendu de projet écrit + fichiers sources.
• Un examen écrit (1h30).