Une société de télécommunication américaine souhaite automatiser et optimiser le plan d'un réseau de fibre optique dans une ville.

Chaque adresse cliente doit être connectée par une succession de fibres optiques à l'un des « central offices » positionnés dans la ville.

L'objectif est de minimiser le coût du déploiement du réseau, qui est une fonction de deux quantités : la longueur totale des segments de rues sur lesquels un ou plusieurs câbles de fibre optique sont déployés (travaux de voirie) et le nombre de points de séparation des câbles de fibre optique (reconnexion des fibres optiques une à une entre deux câbles).

Ce problème peut être modélisé comme un problème de « prize collecting Steiner forest » avec des décisions et des contraintes structurelles additionnelles. Les décisions supplémentaires sont les localisations des points de séparation de câbles. Ces points ne sont pas nécessairement situés aux nœuds de degrés supérieurs à 3 dans la solution puisqu'il est possible de faire courir plusieurs câbles en parallèle sur la même arête du graphe.

Le réseau doit respecter une contrainte globale de hiérarchie en 3 couches, et les câbles utilisés dans les 2 couches les plus basses ont des capacités fixées (idéalement saturées). Les nœuds du réseau auxquels un câble de fibre optique est séparé doivent également satisfaire de nombreuses contraintes : leur degré est borné (et sature idéalement le degré maximal), ils ont des préférences de placement dans le graphe et ils doivent respecter une distance moyenne maximale à une adresse cliente connectée.

Nous présenterons une heuristique de résolution à base de décomposition et de destruction-réparation locale. LocalSolver est utilisé pour effectuer un clustering des adresses et décider du placement de « central offices » secondaires. Ensuite, une solution initiale sans placement des séparateurs, obtenue avec l'heuristique pcst-fast, est améliorée progressivement en itérant calcul des localisations préférées des séparateurs et ré-optimisation du réseau dans chaque sous-niveau de la hiérarchie.

Cette heuristique permet de trouver des solutions de bonne qualité en moins de 10 minutes sur des instances réelles avec $500.000$ arêtes et $150.000$ adresses clientes.