Scheduling et routing : tirer parti des solveurs d'optimisation et des LLM
Les développements récents de l'intelligence artificielle font naître de nombreuses attentes pour automatiser des tâches complexes, y compris pour répondre à des besoins opérationnels fondamentaux comme la gestion de planning et l'organisation de tournées. Mais les LLM au coeur de l'IA générative n'ont pas été construits pour résoudre ces problèmes de nature combinatoire. Une autre famille d'algorithmes d'IA, les solveurs, résolvent exactement ces problèmes depuis des décennies, avec des garanties mathématiques et des gains mesurés en production. Et il ne s'agit pas de choisir entre ces deux approches de l'IA : les LLM rendent aujourd'hui les solveurs plus accessibles que jamais.
1. Trois problèmes, trois gisements de gains
L'affectation : qui fait quoi ?
Le problème le plus simple de la famille (l'assignment problem) : répartir des tâches entre des personnes ou des machines, par exemple des dossiers entre gestionnaires, des interventions entre techniciens, des missions entre agents etc. A grande échelle, la gestion manuelle de l'affectation fait face à une complexité exponentielle, là où les solveurs affectent les tâches de manière optimale.
Sans optimisation :
une répartition au tableur, à l'expérience qui « tient », sans qu'on sache si elle est bonne ;
des heures supplémentaires concentrées sur les mêmes personnes, d'autres sous-chargées ;
des règles RH respectées « en principe », jusqu'au contrôle qui prouve le contraire ;
un désistement de dernière minute = une heure de re-planification sous pression.
Avec un solveur :
moins d'heures supplémentaires : charge équilibrée mathématiquement, pas à l'œil
règles RH garanties par construction : une affectation non conforme ne peut pas sortir de l'algorithme
remplacement optimal en quelques secondes, en réorganisant le minimum de monde
Le scheduling : qui fait quoi, et quand ?
La même chose avec la dimension temps : service hospitalier, rotations en 3×8, ligne de production, attribution de quais ou de salles.
Sans optimisation :
des trous et des doublons découverts trop tard ;
des ressources coûteuses utilisées à 70 % faute de bon séquencement ;
des plannings publiés en retard, contestés, refaits ;
aucun moyen de tester un scénario (« et avec 4 équipes ? ») sans des jours de travail.
Avec un solveur :
chaque point d'utilisation des ressources gagné se lit dans le compte d'exploitation ;
des plannings équitables et défendables, chaque décision se justifie par une contrainte explicite ;
des simulations en quelques minutes : changer une hypothèse, relancer, comparer.
Le routing : les tournées
Desservir des dizaines ou centaines de points avec une flotte, sous contraintes de capacités et de créneaux.
Sans optimisation :
des tournées construites par habitude, qui se croisent et reviennent en arrière ;
des créneaux manqués, des pénalités ;
un véhicule de trop engagé « par sécurité » ;
chaque imprévu du matin absorbe le planificateur pendant une heure.
Avec un solveur :
typiquement 5 à 15 % de kilomètres en moins à périmètre identique — parfois un véhicule entier économisé ;
des créneaux tenus par construction ;
une re-optimisation en quelques secondes à chaque imprévu.
Référence du secteur : ORION, le système d'optimisation d'UPS, économise selon les chiffres publics du groupe environ 100 millions de miles par an, soit 300 à 400 M$ annuels.
Le point commun
Ces trois problèmes relèvent de l'optimisation combinatoire sous contraintes : des règles non négociables, un objectif chiffré, et une explosion combinatoire. Ordonner 10 arrêts : 3,6 millions de possibilités. 15 arrêts : 1 300 milliards. 20 arrêts : plus que le nombre de secondes écoulées depuis le Big Bang.
D'où un constat structurel : « fait main » signifie presque toujours « loin de l'optimum ». Non par incompétence, mais parce que le problème dépasse ce qu'un cerveau ou un tableur peut explorer.
À 20 arrêts, plus de combinaisons que de secondes depuis le Big Bang.
2. Pourquoi un LLM seul ne suffit pas
L'idée a été testée rigoureusement, y compris par les créateurs de ces modèles. Quatre limites, toutes structurelles :
Du plausible, pas de l'optimal. Un LLM prédit du texte vraisemblable ; il ne calcule pas les distances, ne compare pas les solutions. Google DeepMind l'a mesuré (Large Language Models as Optimizers, 2023) : dès 50 points, les LLM décrochent, avec des écarts à l'optimum jusqu'à 20 fois supérieurs. Les cas réels en comptent des centaines.
Des règles violées silencieusement. Aucun mécanisme interne ne vérifie les contraintes : agent affecté à deux missions simultanées, temps de travail légal dépassé, camion surchargé, le tout présenté avec assurance. L'erreur se découvre sur le terrain.
Aucune mesure de qualité. Un solveur certifie « à au plus 2 % de l'optimum » donc ce qui reste sur la table. Un LLM ne peut pas produire cette information.
Ni reproductible, ni adapté au recalcul permanent. Deux fois la même question, deux plannings différents. Or un planning vit : absences, annulations, retards, il faut re-optimiser en secondes, plusieurs fois par jour.
Le LLM est une IA du langage. Le planning est un problème de combinatoire.
3. L'IA spécialisée : les solveurs
L'optimisation et la recherche opérationnelle forment l'une des branches les plus anciennes de l'IA. Ses outils, les solveurs, tournent en production depuis des décennies : tournées d'UPS, équipages des compagnies aériennes, ordonnancement industriel.
Le principe inverse la logique habituelle : on ne programme pas la résolution, on déclare le problème : contraintes et objectif. Le solveur explore l'espace des solutions en élaguant des milliards de combinaisons, et rend une solution valide par construction : une règle déclarée ne peut pas être violée.
Trois niveaux d'outils, selon la taille du problème :
OR-Tools / CP-SAT : la boîte à outils open source de Google, gratuite. Son moteur CP-SAT domine depuis 2018 le MiniZinc Challenge, compétition internationale de référence. L'outil de choix pour l'affectation et le scheduling. Pour l'affectation pure, des algorithmes classiques (méthode hongroise) trouvent l'optimum exact en une fraction de seconde.
Le module Routing d'OR-Tools = la brique spécialisée tournées : multi-véhicules, capacités, fenêtres horaires, multi-dépôts. De quelques dizaines à quelques centaines de points, il rend en secondes des solutions de très bonne qualité, reproductibles. Pour situer la maturité du domaine : le solveur académique Concorde a prouvé l'optimum exact sur 85 900 points, à comparer aux 50 points où les LLM décrochent.
Branch and Price pour les très gros problèmes (milliers de points ou de tâches) ou quand l'optimum prouvé est exigé. Principe : décomposer. On découpe en sous-problèmes maîtrisables (« une bonne tournée pour un véhicule », « une bonne semaine pour un agent ») et un algorithme maître recombine ces briques avec garantie de progression vers l'optimum global. C'est la méthode qui planifie les équipages des grandes compagnies aériennes depuis les années 1990.
Un problème de tournées résolu par OR-Tools : contraintes garanties, résultat reproductible.
Diviser pour optimiser : le principe du Branch and Price.
4. Le rôle des LLM : rendre les solveurs accessibles
Si les solveurs marchent depuis si longtemps, pourquoi restent-ils si peu déployés ? Parce qu'ils étaient difficiles d'accès : il fallait un expert pour traduire le métier en modèle mathématique, et l'outil se pilotait à coups de fichiers et de paramètres.
C'est précisément ce que les LLM changent. L'architecture qui s'impose associe les deux : le LLM en couche langage, le solveur en couche résolution.
« Replanifie demain sans le camion 7, en priorisant les clients en retard » → le LLM traduit en paramètres, le solveur calcule, la solution revient garantie.
Une nouvelle règle métier (« jamais plus de deux nuits consécutives pour les nouveaux ») s'exprime en langage naturel et devient une contrainte formelle.
Le LLM restitue et explique le planning aux équipes, à partir des justifications formelles du solveur.
L'intuition de départ était donc juste, deux fois : l'IA règle bien ces problèmes, et le LLM en fait partie. Simplement, le LLM est l'interface, le moteur est une IA spécialisée qui, elle, garantit le résultat.
