Recherche · Optimisation & planning

La meilleure décision sous contraintes, et l'explication quand il n'y en a pas

Plannings d'équipes, tournées de techniciens, affectation de livraisons, découpe de matière, mix de production : ces décisions ont une meilleure réponse, que l'on peut calculer. VVL permet de les décrire en quelques lignes et les confie à un solveur de contraintes. Le modèle de langage peut aider à écrire le modèle, mais la solution est calculée, pas devinée.

Comment ça marche

Quatre éléments, un solveur

Un problème se déclare avec quatre éléments : les décisions à prendre et leurs bornes, les contraintes à respecter absolument, les préférences qui peuvent être sacrifiées avec un poids, et l'objectif à maximiser ou à minimiser. VVL compile cette description vers le solveur CP-SAT de Google OR-Tools.

Le langage offre des outils autour du solveur : validation du modèle, explication, génération du code, rapport en langage naturel, et surtout un diagnostic quand le problème n'a pas de solution. Une couche de planning ajoute des notions métier : horizon, ressources, tâches, durées, précédences, ressources qui ne peuvent pas faire deux choses à la fois. Des fonctions de géolocalisation fournissent les distances entre adresses pour les tournées.

Aucun appel au modèle de langage pendant la résolution.

optimize:problemVVL

[optimize:problem "prod"
  [decision $x Integer [min 0] [max 10]]
  [decision $y Integer [min 0] [max 10]]
  [assert (($x + $y) <= 12)]          # capacité totale de l'atelier
  [maximize ((3 * $x) + (5 * $y))]]   # marge à maximiser

[optimize:solve "prod" [time_limit 5] [backend "cp-sat"]]

Résultat obtenu sur le serveur : x = 2, y = 10, statut OPTIMAL, marge 56.

Exemples en entreprise

Plannings, tournées, chantiers

Planning d'équipe sur une semaine

Trois personnes, cinq jours, au moins deux présents chaque jour, au plus quatre jours chacun, Alice absente le mercredi. On cherche le planning qui mobilise le moins de jours au total.

Résultat obtenu sur le serveur : planning optimal de 10 jours-personnes, deux personnes chaque jour, Alice absente le mercredi.

roulementVVL

$jours  = [list "lun" "mar" "mer" "jeu" "ven"]
$equipe = [list "alice" "bob" "carol"]
[optimize:problem Roulement
  [for $e $equipe [for $j $jours
    [decision "w_${e}_${j}" Integer [min 0] [max 1]]]]
  [for $j $jours
    [assert ([sum $e $equipe "w_${e}_${j}"] >= 2)]]     # au moins deux présents
  [for $e $equipe
    [assert ([sum $j $jours "w_${e}_${j}"] <= 4)]]     # quatre jours au plus
  [assert ($w_alice_mer == 0)]                         # Alice absente mercredi
  [minimize [sum $e $equipe [sum $j $jours "w_${e}_${j}"]]]]
[optimize:solve Roulement]

Affectation des livraisons

Chaque commande doit être livrée une fois, chaque livreur prend au plus deux commandes. En remplaçant l'objectif par la somme des distances entre livreurs et clients, le même modèle devient une optimisation de tournée.

Résultat obtenu sur le serveur : les quatre commandes affectées, aucun livreur au-delà de deux, statut OPTIMAL.

tournéesVVL

$livreurs  = [list "L1" "L2" "L3"]
$commandes = [list "C1" "C2" "C3" "C4"]
[optimize:problem Tournees
  [for $l $livreurs [for $c $commandes
    [decision "x_${l}_${c}" Integer [min 0] [max 1]]]]
  [for $c $commandes
    [assert ([sum $l $livreurs "x_${l}_${c}"] == 1)]]   # chaque commande servie une fois
  [for $l $livreurs
    [assert ([sum $c $commandes "x_${l}_${c}"] <= 2)]]  # capacité par livreur
  [minimize [sum $l $livreurs [sum $c $commandes "x_${l}_${c}"]]]]
[optimize:solve Tournees]

# variante tournée : minimiser les kilomètres
# [minimize [sum $l $livreurs [sum $c $commandes
#     ([geo:distance "${l}" "${c}"] * "x_${l}_${c}")]]]

Planning de chantier

Techniciens, véhicule, précédences

La pose demande un technicien et le véhicule, le test demande un technicien et ne peut commencer qu'après la pose. Chaque ressource ne fait qu'une chose à la fois. On cherche à terminer au plus tôt.

Précédence pose → test, une seule tâche à la fois par ressource.

planning:problemVVL

[planning:problem Chantier
  [horizon 0 480]
  [resource "tech_thomas" [kind "technician"]]
  [resource "tech_sarah"  [kind "technician"]]
  [resource "utilitaire"  [kind "vehicle"]]
  [task "pose" [duration 240]]
  [task "test" [duration 60]]
  [on-resource-group "pose" "installer" [resources "tech_thomas" "tech_sarah"]]
  [on-resource-group "pose" "vehicle"   [resources "utilitaire"]]
  [on-resource-group "test" "installer" [resources "tech_thomas" "tech_sarah"]]
  [no-overlap-resource "tech_thomas"]
  [no-overlap-resource "tech_sarah"]
  [no-overlap-resource "utilitaire"]
  [precedence "pose" "test"]
  [objective minimize-makespan]]
[optimize:solve Chantier]

Résultat obtenu sur le serveur : pose de 0 à 240 minutes, test à partir de 240, fin des travaux à 300 minutes, solution optimale.

Tournées de techniciens de maintenance

Cas d'étude de maintenance de chaudières : cinq visites à répartir entre techniciens selon leurs qualifications, leurs créneaux et leur zone. Le modèle compte 20 décisions, 13 contraintes strictes et 3 préférences pondérées.

Résultat documenté : solution optimale en 0,04 seconde, les cinq visites dans la zone du technicien. La version qui minimise les kilomètres réels, à partir des adresses, aboutit à 32 km pour toute la flotte.

Quand il n'y a pas de solution

Trouver le conflit, pas seulement dire non

Un objectif de production impossible à tenir avec les capacités disponibles. Le solveur isole le plus petit ensemble de contraintes incompatibles, pour que le responsable sache laquelle renégocier.

Le diagnostic du conflit

Le volume demandé dépasse la somme des deux capacités : aucune combinaison ne tient.

Résultat obtenu sur le serveur : conflit entre trois contraintes, le volume demandé et les deux capacités ; en retirer une seule rend le problème faisable.

why-infeasibleVVL

[optimize:problem Objectif
  [decision $a Integer [min 0] [max 10]]
  [decision $b Integer [min 0] [max 10]]
  [assert (($a + $b) >= 15)]     # volume demandé
  [assert ($a <= 3)]              # capacité de la ligne A
  [assert ($b <= 4)]              # capacité de la ligne B
  [maximize ($a + $b)]]
[optimize:solve Objectif]           # no solution (status=INFEASIBLE)
[optimize:why-infeasible Objectif]

Décrire le problème en français

Pour un premier jet, le problème peut être décrit en langage naturel. Le modèle de langage écrit le modèle, que l'on peut relire, puis le solveur le résout. Une intention supplémentaire s'ajoute de la même façon.

en langage naturelVVL

[optimize "Une équipe de trois personnes, Alice, Bob et Carol, doit assurer la présence pendant deux jours. Chaque jour il faut au moins deux personnes au poste. Alice ne peut travailler qu'un seul jour. On veut minimiser le nombre total de jours travaillés." "Planning"]
[print [optimize:code Planning]]                           # le modèle généré, lisible
$sol = [optimize:solve Planning]
[intent "Alice doit travailler au moins un jour" "Planning"]
$sol2 = [optimize:solve Planning]

Garanties

Ce qu'il garantit, et ses limites

Une solution annoncée comme optimale l'est pour le modèle décrit : c'est une preuve du solveur, pas une estimation.
Une impossibilité est expliquée par l'ensemble minimal de contraintes en conflit.
Le modèle reste lisible et versionnable, y compris lorsqu'il a été écrit par le modèle de langage.
Les modèles sont linéaires : produits de deux décisions, divisions et puissances ne sont pas acceptés, et une faute de frappe dans un mot-clé est signalée plutôt qu'ignorée.

Passer à la pratique

Appliquer ces travaux à vos processus ?

Ces outils sont des instructions du langage VVL : nos partenaires les mettent en œuvre chez leurs clients, sur les plateformes ProSuite.

Devenir partenaire Tous les sujets