Comment répartir des tournées entre des livreurs ?
Un problème d’affectation consiste à donner à chaque personne exactement une tâche, de façon que le coût total soit le plus petit possible. Une entreprise de livraison le rencontre chaque matin.
Vous saurez le résoudre en essayant toutes les affectations, et vous verrez pourquoi cette méthode ne dure pas.
À la fin de cette leçon
Remarque
Je peux trouver l’affectation la moins chère en essayant toutes les possibilités.
Mots clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Affectation | un choix de une tâche pour chaque personne, sans partage | |
| Matrice de coûts | le tableau du coût de chaque personne sur chaque tâche | |
| Permutation | une façon de ranger des éléments dans un ordre | |
| Factorielle | le produit des nombres de 1 jusqu’à n | 3 ! = 6 |
| Problème de transport | envoyer des marchandises de dépôts vers des magasins au moindre coût |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Trois livreurs, trois tournées, un tableau de minutes
Un atelier de livraison de Lille a trois livreurs et trois tournées. Chacun prend une seule tournée, et chaque tournée est prise par une seule personne.
Le tableau donne la durée en minutes de chaque livreur sur chaque tournée. Il faut choisir pour que le total soit le plus petit.
Exemple travaillé : le tableau des minutes
| Livreur | Tournée 1 | Tournée 2 | Tournée 3 |
|---|---|---|---|
| Livreur 1 | 9 | 2 | 7 |
| Livreur 2 | 6 | 4 | 3 |
| Livreur 3 | 5 | 8 | 1 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
On essaie les six affectations possibles
Avec trois livreurs, il y a 3 × 2 × 1 = 6 façons de distribuer les tournées. Chacune est une permutation des trois tournées.
On calcule le total de chacune et on garde le plus petit. Par exemple, livreur 1 sur la tournée 2, livreur 2 sur la 1 et livreur 3 sur la 3 coûtent 2 + 6 + 1 = 9 minutes.
Essayer toutes les affectations
from itertools import permutations
# Minutes de chaque livreur (ligne) sur chaque tournée (colonne).
couts = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]
meilleur = None
for colonnes in permutations(range(3)):
total = 0
for livreur in range(3):
total = total + couts[livreur][colonnes[livreur]]
print(colonnes, total)
if meilleur is None or total < meilleur:
meilleur = total
print("meilleur total", meilleur)
Trouver la meilleure affectation
docker exec jupyter python3 -c "from itertools import permutations; C = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]; print(min((sum(C[i][c[i]] for i in range(3)), c) for c in permutations(range(3))))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Essayer toutes les affectations ne dure pas
Pour n livreurs, il y a n ! affectations. Cette factorielle grandit très vite : la commande suivante donne celles de 3, 5, 10 et 15.
Avec 15 livreurs, il y en a plus de mille milliards. Pour de grandes tailles, on emploie une méthode plus fine, qui ne les essaie pas toutes.
Voir la croissance de la factorielle
docker exec jupyter python3 -c "from math import factorial; print(factorial(3), factorial(5), factorial(10), factorial(15))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Laisser SciPy résoudre l’affectation
docker exec jupyter python3 -c "import numpy as np; from scipy.optimize import linear_sum_assignment; C = np.array([[9, 2, 7], [6, 4, 3], [5, 8, 1]]); r, c = linear_sum_assignment(C); print(c.tolist(), int(C[r, c].sum()))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
SciPy trouve la même réponse sans tout essayer
La fonction linear_sum_assignment résout le problème d’affectation sans essayer toutes les possibilités. Elle rend les colonnes choisies, puis on calcule le total.
La commande affiche [1, 0, 2] 9 : mêmes colonnes et même total que l’essai complet, ici sur seulement trois livreurs.
Le transport minimise le coût d’envoi
Deux dépôts ont 20 et 30 caisses. Trois magasins en demandent 10, 25 et 15. Envoyer une caisse coûte 4, 6 et 9 euros depuis le premier dépôt, 5, 3 et 7 depuis le second.
C’est un programme linéaire à six variables : le nombre de caisses de chaque dépôt vers chaque magasin. Le total minimal est 240 euros.
Résoudre le transport avec linprog
docker exec jupyter python3 -c "from scipy.optimize import linprog; c = [4, 6, 9, 5, 3, 7]; A = [[1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1], [1, 0, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 0, 1]]; res = linprog(c, A_eq=A, b_eq=[20, 30, 10, 25, 15]); print([round(v, 1) for v in res.x], round(res.fun, 1))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une erreur fréquente
Attention
Beaucoup pensent qu’il suffit de donner à chacun sa tournée la moins chère, l’un après l’autre. Ici le livreur 1 prend la 2 (2 minutes). Le livreur 2 prend la 3 (3), et le livreur 3 reste avec la 1 (5) : 10 minutes. La meilleure affectation fait 9 : un choix local n’est pas un choix global.
Pour aller plus loin
Dans votre carnet, ajoutez un quatrième livreur et une quatrième tournée avec des minutes de votre choix. Cherchez la meilleure affectation avec permutations.
Comptez le nombre d’affectations essayées et comparez-le avec 3 livreurs.