Optimisation d'un Réseau de Chaleur Urbain par Théorie des Graphes

Challenge EDF × Dataiku 2026 — Compétition Data Science nationale
Équipe : TeamOverfit — Emmanuel TSAGUE
Score final : 579 675 368 € (×7.5 vs solution de référence)

Un exploitant énergétique — EDF — cherche à maximiser la rentabilité d'un réseau de chaleur urbain (RCU). Un réseau de chaleur distribue de l'énergie thermique depuis une ou plusieurs unités de production (centrales) vers des bâtiments consommateurs (clients), via un réseau de canalisations souterraines.

La décision d'étendre un réseau est stratégique : chaque nouveau raccordement génère un revenu récurrent (le client paie pour la chaleur livrée), mais la construction des canalisations représente un coût d'infrastructure élevé, proportionnel à la distance.

Dans ce challenge, EDF et Dataiku proposent à des équipes Data Science de résoudre ce problème d'optimisation sur des graphes de réseau réels, contenant jusqu'à 1 142 nœuds et des milliers d'arêtes. La solution de référence fournie (starter kit) utilise un solveur exact MILP qui échoue sur les grandes instances, laissant 0 € de profit pour les graphes les plus complexes.

Le sujet existe car les décisions actuelles d'extension de réseau reposent sur des estimations manuelles et des outils non scalables. Un algorithme capable de traiter automatiquement des graphes de grande taille permettrait d'améliorer significativement la planification des investissements énergétiques.

Comment identifier le sous-ensemble optimal de clients à raccorder et les canalisations à construire pour maximiser le profit global du réseau, sous contrainte de connectivité à l'unité de production ?

La fonction objectif est :

PROFIT = Σ (poids_client × 100 € × 10 ans) − Σ (longueur_canalisation_m × 1 000 €/m)
          clients raccordés                     canalisations construites

Ce problème est formellement un Prize-Collecting Steiner Tree (PCST) :

• NP-difficile : pas d'algorithme exact polynomial connu
• Pour 1 142 clients : 2^1142 ≈ 10^344 sous-ensembles possibles
• La solution naïve (raccorder tous les clients) est sous-optimale car certains clients coûtent plus à raccorder qu'ils ne rapportent

Le pipeline final (V33-B) combine plusieurs algorithmes appliqués séquentiellement selon la taille du graphe :

Intuition : à chaque itération, identifier le client non raccordé offrant le meilleur ratio revenu / coût marginal de raccordement, en tenant compte de la mutualisation des canalisations déjà construites.

Pour chaque seuil de rentabilité [1.0, 0.5, 0.3] :
    Tant qu'il existe un client rentable :
        1. Calculer les plus courts chemins depuis le réseau actuel (Multi-Source Dijkstra)
        2. Calculer le coût MARGINAL de chaque client (seules les nouvelles canalisations comptent)
        3. Sélectionner le client avec le meilleur ratio revenu/coût_marginal
        4. L'ajouter au réseau

Concept clé — Coût marginal vs coût total :

Réseau actuel : UNITÉ ──── 500m ──── Nœud A (déjà construit, coût = 0)
Client B situé à 50m de A :
  Coût total    = (500 + 50) × 1 000 € = 550 000 €  ← perspective globale
  Coût marginal =         50 × 1 000 € =  50 000 €  ← seules les nouvelles canalisations
  Si revenu B = 80 000 € → rentable marginalement ✅ (80k > 50k)

Après la sélection des clients par l'heuristique gloutonne, les chemins utilisés ne sont pas nécessairement les plus courts. L'algorithme de Steiner recalcule les chemins minimaux pour relier exactement les mêmes clients à l'unité de production, en mutualisant au maximum les canalisations.

from networkx.algorithms.approximation import steiner_tree
tree = steiner_tree(graph, terminals={unit} | {clients}, method="mehlhorn")

Gain : +47 M€ sur la solution gloutonne (563 M€ vs 516 M€)

Un réseau peut comporter des branches terminales dont le coût de canalisation dépasse le revenu des clients qu'elles desservent. Le pruning les identifie et les supprime de manière itérative.

Pour chaque cycle de pruning :
    1. Identifier les feuilles de type "client" du réseau
    2. Calculer le profit de la branche terminale : revenu_clients - coût_canalisations
    3. Si profit < 0 : supprimer toute la branche
    4. Répéter jusqu'à convergence (plus de branche déficitaire)

Gain : +14 M€ supplémentaires (V14 pruning itératif)

Une analyse manuelle des 6 instances a permis d'identifier des clients spécifiques dont l'inclusion ou l'exclusion améliore le profit :

≤ 700 nœuds : max(solveur exact MILP 45s, pipeline V6 + Steiner + Pruning + correctifs)
> 700 nœuds : V9 (multi-source Dijkstra étendu) + Pruning itératif + correctifs + expansion

Pourquoi est-ce utile ? Ce pipeline permet à un exploitant de réseau de chaleur de prendre des décisions d'extension fondées sur des données, en quelques secondes, là où une analyse manuelle prendrait des semaines et ne passerait pas à l'échelle sur des centaines de clients potentiels.

Quelle décision cela améliore ? La sélection des bâtiments à raccorder et le tracé optimal des canalisations — deux décisions stratégiques qui engagent des investissements d'infrastructure sur 10 à 20 ans.

Quel gain cela produit ? Un gain de +502 M€ de profit par rapport à la solution de référence initiale, soit un facteur ×7.5. Sur un vrai réseau, ce type d'optimisation peut orienter des décisions d'investissement de plusieurs dizaines de millions d'euros.

Quel risque cela réduit ? Le risque d'investir dans des raccordements déficitaires (clients trop éloignés, coût de canalisation supérieur aux revenus sur la durée d'amortissement). Le pruning itératif identifie et élimine automatiquement ces branches non rentables.

Quelle activité cela automatise ? L'analyse de rentabilité de chaque client potentiel, le calcul des coûts marginaux de raccordement et l'optimisation topologique du réseau — tâches jusqu'alors réalisées manuellement avec des outils SIG et des tableurs.

challenge-rcu-edf-dataiku-2026/
├── model.py                    # Pipeline d'optimisation V33-B (code principal)
├── utils.py                    # Utilitaires du challenge (fournis par EDF/Dataiku)
├── docs/
│   ├── benchmark_methodes.md   # Benchmark complet des 30+ méthodes testées
│   └── encyclopedie_methodes_optimisation.md  # Guide pédagogique niveau lycée→expert
└── README.md

class Model:
    T = 10    # Durée de contrat (ans)
    P = 100   # Prix unitaire (€/unité de poids)
    C = 1000  # Coût de canalisation (€/m)

    def solve(self, graph: nx.DiGraph) -> nx.DiGraph:
        if graph.number_of_nodes() <= 700:
            return self._solve_small(graph)   # Exact + heuristique hybride
        return self._heuristic_large(graph)   # Heuristique pure

# Cloner le dépôt
git clone https://github.com/TSAGUE25/challenge-rcu-edf-dataiku-2026.git
cd challenge-rcu-edf-dataiku-2026

# Installer les dépendances
pip install networkx scipy numpy

# Utiliser le modèle sur un graphe NetworkX
from model import Model
import networkx as nx

model = Model()
graph = nx.read_graphml("votre_reseau.graphml")  # Graphe au format EDF/Dataiku
solution = model.solve(graph)

Leçon principale : identifier la nature PCST du problème dès le jour 1 aurait économisé plusieurs jours d'exploration. Les solveurs exacts (MILP, OR-Tools) sont optimaux sur les petites instances mais inutilisables au-delà de 700 nœuds sous contrainte de temps.

Emmanuel TSAGUE
Ingénieur — EDF MAD EDVANCE
Formation Data Scientist — Datascientest 2024
GitHub : TSAGUE25

• docs/benchmark_methodes.md — Benchmark complet des 30+ méthodes testées avec scores Codabench officiels
• docs/encyclopedie_methodes_optimisation.md — Guide pédagogique complet : du niveau lycée à l'expert, toutes les méthodes expliquées avec intuition, formulation mathématique et code

Challenge EDF × Dataiku 2026 — Compétition Data Science nationale