L’algorithme génétique (AG) :
est une méthode d’optimisation stochastique inspirée du processus de sélection
naturelle. Il est utilisé pour résoudre des problèmes complexes dans lesquels le
nombre de combinaisons possibles rend difficile l’emploi de méthodes
déterministes classiques. Les AG sont particulièrement utiles pour des situations
où l’on cherche à maximiser ou minimiser une fonction objective dans un espace
de solutions vaste et non linéaire.
Un AG commence par la génération d’une population initiale de solutions
candidates, appelées individus ou chromosomes, généralement créées de
manière aléatoire. Chaque individu représente une solution possible au problème
donné, encodée sous forme de séquence (par exemple, une permutation
d’emplacements dans un entrepôt ou une tournée de ramassage).
Chaque individu est évalué à l’aide d’une fonction de fitness (ou fonction objectif)
qui mesure la qualité de la solution, selon les critères spécifiques du problème
(par exemple : distance parcourue, coût logistique, temps de traitement, etc.).
Le cœur de l’algorithme repose sur un cycle évolutif : à chaque génération, une
sélection est opérée pour retenir les meilleurs individus (c’est-à-dire ceux qui
présentent les meilleurs scores de fitness). Ces individus sont alors utilisés pour
produire une nouvelle génération, par le biais de deux opérations principales : le
croisement (crossover), qui combine deux solutions pour en créer une nouvelle,
et la mutation, qui introduit une modification aléatoire dans un individu afin de
maintenir la diversité génétique et éviter les minima locaux.
Ce processus se répète sur un certain nombre de générations, jusqu’à ce qu’un
critère d’arrêt soit atteint (nombre de générations, stagnation du score, ou seuil
de qualité). L’algorithme retourne alors la meilleure solution rencontrée.
Les algorithmes génétiques sont largement utilisés dans la logistique,
notamment dans les systèmes de gestion d'entrepôt (WMS), pour optimiser le
slotting (répartition optimale des produits dans l’espace de stockage), le
séquençage de tâches, ou encore l’ordonnancement de tournées de préparation
de commandes.
Explication de la recherche manuelle d'une tournée optimale
Dans le cadre de l’optimisation d’une tournée logistique, telle que la préparation
de commandes dans un entrepôt ou le passage par plusieurs points de livraison,
il est important de minimiser la distance totale parcourue. À petite échelle, il est
possible de déterminer manuellement la tournée optimale, en suivant une
méthode rigoureuse.
1. Données du problème
Le problème consiste à partir d’un point de départ (noté Start), visiter un
ensemble de points (dans notre cas, trois emplacements), puis revenir au point
de départ, en cherchant à minimiser la distance totale parcourue.
Les coordonnées des points sont les suivantes :
Poi Coordonnées
nt (X, Y)
Star (0, 0)
t
1 (1, 10)
2 (7, 5)
3 (4, 1)
2. Étape 1 : Calcul des distances
Nous utilisons la formule de la distance euclidienne entre deux points A(x₁, y₁) et
B(x₂, y₂) :
Distance=(x2−x1)2+(y2−y1)2\text{Distance} = \sqrt{(x₂ - x₁)^2 + (y₂ -
y₁)^2}Distance=(x2−x1)2+(y2−y1)2
En appliquant cette formule, nous obtenons les distances entre tous les couples
de points (Start ↔ 1, 1 ↔ 2, etc.).
3. Étape 2 : Énumération des tournées possibles
Puisqu’il y a trois points à visiter, il existe 3! = 6 permutations possibles de
tournée :
1. Start → 1 → 2 → 3 → Start
2. Start → 1 → 3 → 2 → Start
3. Start → 2 → 1 → 3 → Start
4. Start → 2 → 3 → 1 → Start
5. Start → 3 → 1 → 2 → Start
6. Start → 3 → 2 → 1 → Start
4. Étape 3 : Calcul de la distance totale de chaque tournée
Pour chaque tournée, on additionne les distances entre les points successifs. Par
exemple, pour la première tournée :
Start → 1 → 2 → 3 → Start :
Start → 1 ≈ √(1² + 10²) ≈ 10.05
1 → 2 ≈ √(6² + 5²) ≈ 7.81
2 → 3 ≈ √(3² + 4²) = 5.00
3 → Start ≈ √(4² + 1²) ≈ 4.12
Total ≈ 26.98 unités
On répète cette opération pour les 5 autres tournées.
5. Étape 4 : Comparaison et choix de la meilleure solution
Enfin, on compare les distances totales obtenues pour chaque tournée, et on
retient celle ayant la plus faible valeur. C’est la solution optimale au problème.
Conclusion
Ce processus manuel est parfaitement adapté à un petit nombre de points (2 à
5). Cependant, le nombre de combinaisons augmente de manière exponentielle
avec le nombre de points à visiter (n!), ce qui rend la méthode manuelle
rapidement inefficace dans les cas réels de logistique. C’est pourquoi, pour les
problèmes à plus grande échelle, nous utilisons des méthodes heuristiques ou
métaheuristiques, telles que les algorithmes génétiques, capables
d’explorer efficacement l’espace des solutions et d’approcher l’optimum en un
temps raisonnable.
