Deux variantes du problème Ring Star
10/11/2023 à 10h22
M. Julien KHAMPHOUSONE présente ses travaux en soutenance le 10/11/2023 à 10h22
À l'adresse suivante : Université Paris Dauphine PSL Place du Maréchal de Lattre de Tassigny 75016 Paris Salle des thèse - D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Deux variantes du problème Ring Star
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide à la Décision
Section CNU
27 - Informatique
Directeur(s)
M. André ROSSI
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. André ROSSI | Professeur des universités | UNIVERSITE PARIS DAUPHINE - PSL | Directeur de thèse |
| Mme Safia KEDAD-SIDHOUM | Professeur des universités | CONSERVATOIRE NATIONAL DES ARTS ET MÉTIERS | Rapporteure |
| M. Laurent HOUSSIN | Associate professor | INSTITUT SUPÉRIEUR DE L'AÉRONAUTIQUE ET DE L'ESPACE | Rapporteur |
| Mme Dominique QUADRI | Professeur des universités | UNIVERSITÉ PARIS SACLAY | Examinatrice |
| M. Fabian CASTAÑO | Ingénieur de recherche | FRUBANA | Co-encadrant de thèse |
| Mme Sonia TOUBALINE | Maître de conférences | UNIVERSITE PARIS DAUPHINE - PSL | Co-encadrante de thèse |
Résumé
Dans les réseaux de télécommunication, les réseaux de transport, la logistique et plusieurs autres domaines, la conception de réseaux induit de nombreux problèmes sous-jacents. Dans cette thèse, nous nous intéressons à la structure à deux niveaux composée d'une ossature et d'une partie tributaire. L'un des problèmes avec cette architecture est le problème Ring Star où un dépot est défini à l'avance. Les noeuds sont sélectionnés ou non en tant qu'hubs et ces hubs et le dépôt sont reliés par un "Ring" tandis que les noeuds non sélectionnés forment la partie tributaire en étant connectés à un noeud du ring pour former la partie "Star". Nous introduisons deux variantes du problème Ring Star. Une variante à capacité de survie et une variante résiliente. Nous formulons un PLNE ainsi qu'un algorithme de Branch-and-Benders-cut pour les deux problèmes. Des propriétés sont étudiées, elles permettent des améliorations computationnelles mises en évidence par des expérimentations numériques.