Itinéraires, plannings, configurations et affectations peuvent contenir trop de possibilités pour être explorés exhaustivement. Une heuristique estime quelles branches semblent prometteuses. Elle accélère la décision, mais encode aussi une préférence qu'il faut rendre explicite.
Transformer le problème en espace de recherche
Il faut définir un état initial, les actions possibles, les contraintes, le test de réussite et le coût d'un chemin. Cette représentation est souvent plus importante que l'algorithme. Une contrainte oubliée produit une solution mathématiquement élégante mais inutilisable.
La granularité change aussi la difficulté. Un planning à la minute crée plus d'états qu'un planning par créneaux. Réduire intelligemment l'espace, fixer les choix impossibles et séparer les décisions indépendantes peut apporter plus de vitesse qu'une heuristique sophistiquée.
Choisir une estimation alignée sur le résultat
L'heuristique classe les états selon une estimation du chemin restant ou de leur intérêt. Si elle sous-estime certains coûts réels, la recherche favorisera systématiquement de mauvaises options. Le score doit donc traduire les priorités du produit, comme le délai, la distance, le prix ou la charge.
Plusieurs critères peuvent être combinés, mais les pondérations doivent avoir un sens observable. Une analyse de sensibilité montre si une petite variation change complètement la solution. Dans ce cas, mieux vaut présenter plusieurs compromis que prétendre avoir découvert une réponse unique.
Définir quand arrêter
Dans un produit, la meilleure solution théorique arrivée trop tard n'a aucune valeur. On fixe un budget de temps ou de calcul, une qualité minimale et une stratégie de repli. Le système peut conserver la meilleure solution valide rencontrée et l'améliorer tant que le budget le permet.
La surveillance porte sur la qualité, le temps de recherche et le taux de cas sans solution. Les cas difficiles doivent être enregistrés pour améliorer la représentation ou les contraintes. Une heuristique devient fiable lorsque ses erreurs et ses compromis sont connus, pas lorsqu'elle semble rapide sur une démonstration.
Avant d'optimiser
- Formaliser états, actions, coûts et contraintes
- Réduire l'espace avec les règles certaines
- Relier l'heuristique à des priorités métier observables
- Tester la sensibilité aux pondérations
- Fixer budget, seuil de qualité et solution de repli
La recherche heuristique accepte de ne pas tout voir pour trouver une solution utile à temps. Sa qualité dépend de la représentation du problème, de l'estimation choisie et de la transparence des compromis.