Résolution d'un problème de logistique avec l'IA

lab-logo
Le Machine Learning et le Deep Learning ont le vent en poupe dans l’industrie. Cependant, les approches plus conventionnelles ne doivent pas être négligées, car elles permettent de résoudre de nombreux problèmes d’organisation, de planning et de logistique avec peu de données.

Un problème de logistique

Considérons une problématique tout à fait actuelle :

Il y a une pandémie. Les hôpitaux doivent s’organiser rapidement pour soigner les malades.

Il faut un algorithme qui associe les personnes infectées et les hôpitaux en fonction de plusieurs critères tels que la gravité de la maladie, l’âge et l’emplacement du patient, la capacité et l’équipement des hôpitaux, etc.

Carte de la pandémie Fig. 1. Carte de la pandémie, réduite à 4 paramètres : localisation et gravité des patients, localisation et capacité des hôpitaux.

Il est possible de penser qu’un réseau de neurones conviendrait parfaitement à ce problème: des configurations différentes sur beaucoup de paramètres qui doivent être réduits à une solution unique et optimale.

Cependant, certains inconvénients compromettent une telle approche:

  • Le modèle doit être entraîné, il faut de nombreuses données historiques sur les cas précédents,
  • Beaucoup de temps serait perdu à nettoyer et à consolider les données récoltées,
  • Différentes architectures devraient être testées durant de longues sessions d’entraînement.

En revanche, en formulant le problème sous forme de satisfiabilité booléenne, la situation n’aurait aucun des inconvénients susmentionnés tout en donnant une solution sous-optimale en temps polynomial et non déterministe (problème NP-complet), et sans la nécessité de devoir regroupes un jeu de données historiques.

Formulation du problème

La carte de la pandémie (1) illustre les résultats de notre algorithme qui associera les personnes infectées aux hôpitaux. Il existe plusieurs frameworks pour la résolution des contraintes. Google Optimization Tools (a.k.a., OR-Tools) est une suite logicielle open source pour résoudre les problèmes d’optimisation combinatoire. Notre problème sera modélisé en utilisant ce framework en Python.

from ortools.sat.python import cp_model

Un notebook complet pour ce prolbème peut-être trouvé ici.

Paramètres

Pour le moment, simplifions le problème à 4 paramètres:

  • Localisation des personnes infectées
  • Severité de la maladie chez ces personnes
  • Localisation des hôpitaux
  • Nombre de lits dans chaque hôpital

Définissions ces paramètres en python:

# Number of hospitals
n_hospitals = 3
# Number of infected people
n_patients = 200
# Number of beds in every hospital
n_beds_in_hospitals = [30,50,20]
# Location of infected people -- random integer tuple (x,y)
patients_loc = [(randint(0, 100), randint(0, 100)) for _ in range(n_patients)]
# Location of hospitals -- random integer tuple (x,y)
hospitals_loc = [(randint(0, 100), randint(0, 100)) for _ in range(n_hospitals)]
# Illness severity -- 1 = mild -> 5 = severe
patients_severity = [randint(1, 5) for _ in range(n_patients)]

Variables

Un problème de satisfaction des contraintes consiste en un ensemble de variables auxquelles des valeurs doivent être affectées de manière à ce qu’un ensemble de contraintes soit satisfait.

  • Soit I l’ensemble des hôpitaux
  • Soit Jᵢ l’ensemble des lits de l’hôpital i
  • Soit K l’ensemble des patients

Nous pouvons définir notre série de variables:

Si dans l’hôpital i, le lit j est pris par la personne k alors xᵢⱼₖ = 1.

Nous pouvons ajouter ces variables à notre modèle:

model = cp_model.CpModel()
x = {}
for i in range(n_hospitals):
for j in range(n_beds_in_hospitals[i]):
for k in range(n_patients):
x[(i,j,k)] = model.NewBoolVar("x(%d,%d,%d)" % (i,j,k))

Contraintes dures

Les contraintes dures définissent un objectif pour notre modèle. Elles sont essentielless, si elles ne sont pas respectées, le problème ne peut pas être résolu:
 
  • Il doit y avoir au plus une seule personne dans chaque lit,
  • Il doit y avoir au plus un lit  attribué à chaque personne.
     

Concentrons-nous sur la première contrainte. Pour chaque lit j dans chaque hôpital i :

  • Soit il y a un unique patient k,
  • Soit le lit est vide.

Par conséquent, la contrainte est exprimable de la façon suivante:

Notre solveur fait de l’optimisation combinatoire, il ne peut traiter que des contraintes sur des nombres entiers. Par conséquent, l’expression de la contrainte doit être formulée de la façon suivante :

Cette inégalité peut être ajoutée à notre modèle.

# Each bed must host at most one person
for i in range(n_hospitals):
for j in range(n_beds_in_hospitals[i]):
model.Add(sum(x[(i,j,k)] for k in range(n_patients)) <= 1)

Ensuite, traitons la seconde contrainte pour chaque patient k:

  • Soit il est dans un unique lit j dans un hôpital i,
  • Soit il est chez lui.

De la même façon, cette contrainte est exprimable sous la forme d’une inéquation :

Finalement, il est possible de l’ajouter au modèle.

# Each person must be placed in at most one bed
for k in range(n_patients):
inner_sum = []
for i in range(n_hospitals):
inner_sum.append(sum(x[(i,j,k)] for j in range(n_beds_in_hospitals[i])))
model.Add(sum(inner_sum) <= 1)

Contraintes douces

Viennent ensuite les contraintes douces. Notre solution doit essayer de les satisfaire au maximum, mais elles ne sont pas indispensables pour trouver une solution:

  • Chaque personne malade devrait être placée dans un lit,
  • Chaque personne devrait être prise en charge par l’hôpital le plus proche,
  • Les personnes malades dans un état grave devraient être traitées en premier lorsqu’il n’y a pas assez de lits.

Alors que les contraintes dures sont modélisées comme des égalités ou des inégalités, les contraintes souples sont des expressions à minimiser ou maximiser.

Soit Ω l’ensemble de toutes les solutions qui satisfont aux contraintes dures.“Chaque personne malade doit être placée dans un lit” peut être traduit en “maximiser le nombre de lits occupés”.“Chaque personne doit être prise en charge par l’hôpital le plus proche” peut être traduit en “minimiser la distance entre chaque patient et l’hôpital qui lui est affecté”.“Les personnes malades dans un état grave doivent être traitées en premier lorsqu’il n’y a pas suffisamment de lits” peut être traduit en “maximiser la gravité totale de tous les patients pris en charge”. En désignant sev (k) la gravité du patient k :Nous pouvons réduire toutes ces contraintes en un seul objectif :Il faut alors être prudent: ces contraintes souples n’ont pas toutes le même domaine de définition.

  • La contrainte de maximisation des patients va de 0 à n, avec n le nombre de patients,
  • La contrainte de gravité varie de 0 à 5n,
  • La contrainte de distance va de 0 à la distance euclidienne maximale entre i et k.

Étant donné que toutes ces contraintes partagent la même priorité, nous devons définir des facteurs de pénalité pour équilibrer les différentes contraintes.
Voici le code correspondant:

# Integer distance function
idist = lambda xy1, xy2: int(((xy1[0]-xy2[0])**2 + (xy1[1]-xy2[1])**2)**0.5)
# Gain factors (1/penalty factors)
gain_max_patients = 140
gain_severity = int(140/5)
gain_distance = -1
# Maximization objective
soft_csts = []
for i in range(n_hospitals):
for j in range(n_beds_in_hospitals[i]):
for k in range(n_patients):
factor = \
gain_max_patients \
+ gain_distance * idist(hospitals_loc[i], patients_loc[k]) \
+ gain_severity * patients_severity[k]
soft_csts.append(factor * x[(i,j,k)])
model.Maximize(sum(soft_csts))

Solveur

Nous pouvons maintenant lancer le solveur. Il essaiera de trouver la solution optimale dans un délai spécifié. S’il ne parvient pas à trouver la solution optimale, il renverra la solution sous-optimale la plus proche.

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 60.0
status = solver.Solve(model)

Dans notre cas, le solveur renvoie une solution optimale en 2,5 secondes (2).

 

Fig. 2. Solution retournée par le solveur
 

Conclusion

Cette solution ne demande pas beaucoup de temps afin d’être conçue et implémentée.
Pour une solution équivalente en Deep Learning, le temps de conception est au moins multiplié par 10 avec le tri des données, le choix de l’architecture et l’entraînement du modèle.

De plus, un modèle CP-SAT tel que celui-ci est très robuste s’il est bien modélisé. Voici les résultats avec différents paramètres de simulation (3). Les résultats sont toujours cohérents dans de nombreux cas différents, et en augmentannt les paramètres de simulation (3000 patients, 1000 lits), l’inférence d’une solution a pris un peu moins de 3 minutes.

 

Fig. 3: Différents paramètres de simulation

Bien sûr, les solveurs de contraintes ne s’appliquent guère à des sujets comme la vision par ordinateur et le traîtement du langage, dans lesquels le Deep Learning est souvent la meilleure approche. Cependant, en matière de logistique, d’ordonnancement et de planification, ces solveurs restent dans la plupart des cas la voie à suivre.