Un algorithme pour le déploiement des réseaux FTTH

Résumé : Le problème de déploiement optimal d'un réseau FTTH (Fiber To The Home) consiste à concevoir un plan d'installation de fibres optiques de coût minimal permettant de connecter un ensemble de clients à un noeud de raccordement via un ensemble de coupleur. Nous présentons une modélisation de ce problème basée sur le concept de flot avec multiplicateurs et nous montrons comment obtenir par génération de colonnes une solution optimale fractionnaire du programme linéaire correspondant. Cette approche nécessite de résoudre à chaque itération un problème de plus court chemin généralisé multi-contraint. Pour cela, nous décrivons un algorithme pseudo-polynomial qui généralise au cas avec multiplicateurs l'algorithme de plus court chemin multi-contraint introduit dans [DS88].
Type de document :
Communication dans un congrès
Ducourthial, Bertrand et Felber, Pascal. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2011, Cap Estérel, France. 2011
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00587926
Contributeur : Imbrosciano Sébastien <>
Soumis le : jeudi 21 avril 2011 - 17:00:19
Dernière modification le : vendredi 9 mars 2018 - 11:26:01
Document(s) archivé(s) le : vendredi 22 juillet 2011 - 03:03:09

Fichier

algotel2011.Imbrosciano.hal.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00587926, version 1

Collections

Citation

Sébastien Imbrosciano, Alexandre Laugier, Yann Vaxès. Un algorithme pour le déploiement des réseaux FTTH. Ducourthial, Bertrand et Felber, Pascal. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2011, Cap Estérel, France. 2011. 〈inria-00587926〉

Partager

Métriques

Consultations de la notice

145

Téléchargements de fichiers

196