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)