Planning de visite d'un musée

Planning de visite d’un musée

Paramètres

  • $nb_{expositions}$ : nombre d’expositions à présenter (4)
  • $nb_{guides}$ : nombre de guides disponibles (6)
  • $nb_{creneaux}$ : nombre de créneaux horaires dans la journée (10)
  • $nb_{guidesDistincts}$ : nombre minimum de guides distincts devant présenter

Variables

  • Guide affecté à l’exposition $e$ au créneau $c$ : $$\forall e \in [0, nb_{expositions}-1], \forall c \in [0, nb_creneaux-1], g_{e,c}$$

Domaines

$$\forall e \in [0, nb_{expositions}-1], \forall c \in [0, nb_creneaux-1], dom(g_{e,c}) = [1, nb_{guides}]$$

Contraintes

  1. Lors de chaque créneau, une collection n’est présentée que par un seul guide - intrinsèque au modèle
  2. Un guide ne peut pas présenter deux expositions en même temps: $$\forall (e_1,e_2) \in [0, nb_{expositions}-1]^2, \forall c \in [0, nb_creneaux-1], g_{e_1,c}\neq g_{e_2,c}$$
  3. pour une journée, chaque exposition doit être présentée par au moins $nb_{guidesDistincts}$ guides différents:
$$\forall e \in [0, nb_{expositions}-1], card(\{g \mid g_{e,c} = g, \forall c \in [0, nb_{creneaux}-1]\}) \geq nb_{guidesDistincts}$$

Code Choco-solver

​
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.variables.IntVar;

// Paramètres
int nbExpositions = 4;
int nbGuides = 6;
int nbCreneaux = 10;
int nbGuidesDistincts = 6;

// Déclaration du modèle
Model model = new Model("Planning musée");
// Déclaration des variables
IntVar[][] g = model.intVarMatrix("g", nbExpositions, nbCreneaux, 1, nbGuides);

// Déclaration des contraintes
// contrainte 2
for (int c = 0; c < nbCreneaux; c++) {
    IntVar[] guidesCreneau = new IntVar[nbExpositions];
    for (int e = 0; e < nbExpositions; e++) {
        guidesCreneau[e] = g[e][c];
    }
    model.allDifferent(guidesCreneau).post();
}
// contrainte 3
for (int e = 0; e < nbExpositions; e++) {
    IntVar nbDistinct = model.intVar(nbGuidesDistincts, nbCreneaux);
    model.nValues(g[e], nbDistinct).post();
} 
Solver solver = model.getSolver();
solver.showStatistics();
if (solver.solve()) {
    for (int e = 0; e < nbExpositions; e++) {
        System.out.print("exp_" + e + " : ");
        for (int c = 0; c < nbCreneaux; c++) {
            System.out.print(g[e][c].getValue() + ", ");
        }
        System.out.println();
    }
} 
from pychoco import *

nb_expositions = 4
nb_guides = 6
nb_creneaux = 10
nb_guides_distincts = 6

# declaration du modèle
m = Model("Planning musée")

# déclaration des variables
g = [m.intvars(nb_creneaux,1,nb_guides) for i in range(nb_expositions)]

# déclaration des contraintes
# contrainte 2
for c in range(nb_creneaux):
  m.all_different([g[e][c] for e in range(nb_expositions) ]).post()

# contrainte 3
for e in range(nb_expositions):
  nb_distint= m.intvar(nb_guides_distincts, nb_creneaux)
  m.n_values(g[e], nb_distint).post()

solver = m.get_solver()
solver.show_statistics()
solution = solver.find_solution()
for e in range(nb_expositions):
  print(f"exp_{e} :", end="")
  for c in range(nb_creneaux):
    print(solution.get_int_val(g[e][c]), end=", ")
  print(end="\n")