Une méthode d'optimisation qui améliore une solution pas à pas, mais accepte de temps en temps une solution moins bonne pour ne pas rester coincée dans un optimum local. Au début, elle explore beaucoup ; à mesure que la température baisse, elle devient exigeante. Simple à coder, elle donne de bons résultats sur les tournées, les plannings et les affectations.
Le forgeron chauffe le métal puis le refroidit lentement : les atomes ont le temps de trouver une structure solide. Refroidi trop vite, le métal reste cassant. L'algorithme applique la même idée à une solution.
N'importe quelle tournée fait l'affaire. La température fixe au départ la tolérance aux dégradations.
Par exemple, inverser l'ordre de passage sur un tronçon de la tournée. Si la tournée raccourcit, on garde. Si elle s'allonge, on garde quand même avec une probabilité qui baisse avec l'écart et avec la température.
La température diminue à chaque itération. L'algorithme passe de l'exploration à l'affinage, et l'on retient la meilleure solution rencontrée.
Un dépôt et 29 clients répartis sur une zone de 50 km sur 50 km. Il faut une boucle qui passe une fois chez chacun et revient au dépôt, la plus courte possible. Il existe plus de 10 puissance 30 ordres de passage.
Sur l'exemple simulé en Python, la tournée dans l'ordre des numéros fait 760 km. Une recherche qui refuse toute dégradation s'arrête à 240 km, coincée dans un optimum local. Le recuit simulé descend à 232 km.
On compare la distance totale à la tournée actuelle et à une méthode simple. On relance avec plusieurs graines : si les résultats varient beaucoup, il faut refroidir plus lentement ou itérer plus longtemps.
Noms donnés pour R (optim, méthode SANN). En Python, une boucle NumPy comme ici ; scipy.optimize.dual_annealing couvre le cas des variables continues.
Elle doit être de l'ordre des dégradations typiques. Trop basse, l'algorithme se comporte comme une descente simple ; trop haute, il erre au hasard.
Géométrique (T multipliée par 0,9998 à chaque itération ici) ou logarithmique (optim en R). Plus il est lent, meilleure est la solution, et plus c'est long.
La règle qui transforme une solution en une solution proche. Pour une tournée, l'inversion d'un tronçon (2-opt) est bien plus efficace que l'échange de deux clients au hasard.
Le budget de calcul. Vérifier que la meilleure solution ne bouge plus à la fin ; sinon, augmenter.
# Tournée de livraison : recuit simulé en R
set.seed(42)
points <- matrix(runif(60, 0, 50), ncol = 2) # 30 points sur 50 km x 50 km, point 1 = dépôt
distances <- as.matrix(dist(points))
longueur <- function(t) sum(distances[cbind(t, c(t[-1], t[1]))]) # boucle complète
# Voisin d'une tournée : on inverse un tronçon (mouvement 2-opt), le dépôt reste en tête
voisin <- function(t) {
ij <- sort(sample(2:30, 2))
t[ij[1]:ij[2]] <- rev(t[ij[1]:ij[2]])
t
}
# Recuit simulé : une moins bonne tournée est acceptée avec probabilité exp(-écart / température),
# la température baisse au fil des itérations ; optim renvoie la meilleure tournée rencontrée
res <- optim(par = 1:30, fn = longueur, gr = voisin, method = "SANN",
control = list(maxit = 50000, temp = 10, tmax = 10))
cat("Tournée dans l'ordre des numéros :", round(longueur(1:30), 1), "km\n")
cat("Meilleure tournée trouvée :", round(res$value, 1), "km\n")
cat("Ordre de passage :", res$par, "\n")# Tournée de livraison : recuit simulé en Python
import numpy as np
# 30 points de livraison simulés sur une zone de 50 km x 50 km (dépôt = point 0)
rng = np.random.default_rng(42)
points = rng.uniform(0, 50, (30, 2))
dist = np.linalg.norm(points[:, None] - points[None, :], axis=2)
longueur = lambda t: dist[t, np.roll(t, -1)].sum() # boucle complète, retour au dépôt
def recuit(temperature, n_iter=50000):
tournee = np.arange(30)
actuelle = meilleure = longueur(tournee)
for it in range(n_iter):
i, j = np.sort(rng.choice(np.arange(1, 30), 2, replace=False))
candidate = tournee.copy()
candidate[i:j + 1] = candidate[i:j + 1][::-1] # on inverse un tronçon (mouvement 2-opt)
delta = longueur(candidate) - actuelle
# Meilleure : acceptée. Moins bonne : acceptée avec probabilité exp(-delta / T)
if delta < 0 or rng.uniform() < np.exp(-delta / max(temperature, 1e-12)):
tournee, actuelle = candidate, actuelle + delta
meilleure = min(meilleure, actuelle)
temperature *= 0.9998 # refroidissement progressif
return meilleure
print("Tournée dans l'ordre des numéros :", round(longueur(np.arange(30)), 1), "km")
print("Sans recuit (on refuse toute dégradation) :", round(recuit(0.0), 1), "km")
print("Recuit simulé (température initiale 10) :", round(recuit(10.0), 1), "km")C'est une métaheuristique d'optimisation inspirée du refroidissement des métaux. Elle modifie une solution par petits pas et accepte parfois une solution moins bonne, avec une probabilité qui diminue au fil du temps. Cela lui permet de sortir des optimums locaux où une recherche purement gloutonne resterait bloquée.
Une règle pratique : faire quelques essais de voisins au hasard, mesurer la dégradation moyenne, et choisir une température telle qu'une dégradation typique soit souvent acceptée au départ, par exemple 8 fois sur 10. On vérifie ensuite sur plusieurs lancements que le résultat est stable.
Oui, en planification, en logistique, en conception de circuits électroniques et en placement. Il sert souvent de première approche ou de brique dans un solveur plus large. Pour les tournées de véhicules réelles, les solveurs spécialisés combinent ce type de recherche locale avec d'autres techniques.
Font évoluer des dizaines de solutions en parallèle. Exploration plus large, réglages plus nombreux.
Voir la fiche → pour le continuAdapté aux variables continues : montants, dosages, paramètres de modèles.
Voir la fiche → la descente pureSuit toujours la pente, sans jamais accepter de remonter. Rapide, mais bloquée au premier creux.
Voir la fiche →Dataistudio forme les équipes au machine learning et à l'IA, sur des cas concrets.
Nous utilisons des cookies de mesure d'audience et de suivi publicitaire pour comprendre la fréquentation du site et l'efficacité de nos annonces. Rien n'est déposé sans votre accord. En savoir plus