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

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

• 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))

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