De nombreuses problématiques du monde industriel peuvent être modélisées par un problème d’optimisation, qu’il s’agisse de planifier une production, d’organiser des tournées de livraison ou de gérer des stocks. Il existe déjà des méthodes efficaces comme la programmation par contraintes, la recherche locale (connaissez-vous Oscar.cbls ?). Aujourd’hui, une nouvelle approche vient agrandir cette famille : l’ Optimisation basée sur des diagrammes de décisions (DDO) .
Comment fonctionne-t-elle ? Quels sont ses avantages pour vos opérations ? Et comment peut-elle vous être utile ? Cet article vous l’explique tout simplement.
Date: 17 octobre 2025
Asset
A propos des projets
Pour trouver la meilleure solution à un problème, DDO explore un diagramme où chaque "nœud" est un carrefour. Ce carrefour représente un état précis à un instant T. Cet état contient toutes les informations nécessaires pour générer les prochaines directions directions possibles.
Prenons un exemple simple : une tournée de service à domicile. Vous avez un technicien et plusieurs clients à visiter, chacun avec ses propres disponibilités. L’objectif : trouver le trajet le plus court tout en respectant les contraintes horaires de tout le monde.
Par exemple, un état pourrait être :
“Je suis actuellement chez le client 2, il est 10h00, et il me reste les clients 1 et 3 à visiter.”
À partir de cet état, la décision à prendre sera :
“Quel est le prochain client le plus pertinent à visiter maintenant, connaissant les temps de trajet ?”
Le graphe ci-dessous représente une petite instance de ce problème. Pour chaque nœud, nous avons une fenêtre de disponibilité et le temps de trajet vers les autres nœuds. Le diagramme de décision représente tous les chemins possibles, et le chemin en vert nous montre la séquence optimale (ici la plus courte).
Bien sûr, dans la réalité, avec des dizaines de clients, le nombre de chemins possibles explose, menant à un diagramme gigantesque et impossible à calculer.
Pour éviter de construire un diagramme immense, DDO calcule une sous-estimation (la tournée prendra au moins X heures) et une surestimation (elle prendra au plus Y heures) basées sur des diagrammes plus petits. Par étapes successives, il affine ces deux bornes jusqu’à ce qu’elles se rejoignent pour ne laisser qu’une seule voie possible : la solution optimale.
Les problèmes industriels sont souvent caractérisés par un grand nombre de contraintes métiers. Sur une tournée de livraison, il faut gérer la capacité du véhicule, les horaires des clients, mais aussi des précédences (récupérer un colis en A avant de le livrer en B), des compétences techniques, etc.
Pour de nombreuses méthodes d’optimisation, chaque nouvelle contrainte ajoute une couche de complexité. La marge de manœuvre se réduit, et il devient difficile de trouver une solution de qualité.
Le DDO, lui, fonctionne à l’inverse :
Il tire parti des contraintes pour accélérer ses calculs.
Comme il construit la solution étape par étape, dès qu’un chemin partiel viole une contrainte, toute la branche d’explorations qui en découle est coupée. Les contraintes ne sont plus des obstacles, mais des guides qui élaguent l’arbre de recherche pour trouver la solution plus vite.
Le DDO excelle particulièrement pour résoudre des problèmes de séquencement et d’ordonnancement. Voici quelques cas d’usage concrets :
Dans le cadre du projet européen Deep Scheduling, par exemple, nous utiliserons DDO pour planifier les étapes de fabrication en métallurgie afin d’obtenir un acier de haute qualité tout en réduisant les émissions de CO2 et la consommation d’énergie.
Convaincus par le potentiel de cette méthode, nous développons DDOLib, une librairie logicielle open source en Java, en collaboration avec l’UCLouvain (Pr Pierre Schaus de ICTEAM et Roger Kameugne).
L’objectif est double :
Si vos défis opérationnels impliquent des problèmes de séquencement complexes avec de nombreuses contraintes, la technologie DDO offre une perspective nouvelle et puissante. En transformant ces contraintes en alliées, elle ouvre la voie à des solutions plus rapides et plus robustes. Avec des outils open source comme DDOLib, cette approche devient aujourd’hui accessible pour optimiser les processus au cœur de votre industrie.
Voir en ligne : DDOLib