Skip to Main content Skip to Navigation
Conference papers

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].
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/inria-00587926
Contributor : Imbrosciano Sébastien <>
Submitted on : Thursday, April 21, 2011 - 5:00:19 PM
Last modification on : Wednesday, February 3, 2021 - 3:10:06 AM
Long-term archiving on: : Friday, July 22, 2011 - 3:03:09 AM

File

algotel2011.Imbrosciano.hal.pd...
Files produced by the author(s)

Identifiers

  • 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. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2011, Cap Estérel, France. ⟨inria-00587926⟩

Share

Metrics

Record views

286

Files downloads

566