🚚 Optimiseur d'Itinéraires de Livraison — Recuit Simulé en Direct

Le recuit simulé est une technique d'optimisation probabiliste inspirée du procédé métallurgique consistant à chauffer un métal puis à le refroidir lentement pour que ses atomes se stabilisent en une structure cristalline de basse énergie. Appliquée au problème du voyageur de commerce / des tournées de véhicules, l'« énergie » est la distance totale de la tournée. À haute température, l'algorithme accepte de nombreux mouvements dégradants, lui permettant d'explorer largement et de s'échapper des mauvais arrangements locaux ; à mesure que la température baisse, il devient de plus en plus gourmand, affinant la tournée jusqu'à converger près d'un itinéraire court. Cette méthode est populaire pour le routage car l'espace de recherche des ordonnancements d'arrêts possibles est de taille factorielle, bien trop grand pour une recherche exhaustive, alors que les voisinages 2-opt combinés au recuit trouvent de façon fiable des tournées à quelques pourcents de l'optimum.

Un mouvement 2-opt retire deux arêtes de la tournée et reconnecte les quatre extrémités de la seule autre façon qui conserve une boucle fermée unique, ce qui équivaut à inverser l'ordre des arrêts entre les deux points de coupe. C'est le mouvement de recherche locale le plus simple capable de décroiser une tournée : chaque fois que deux segments d'itinéraire se croisent sur la carte, exactement un mouvement 2-opt les redresse et raccourcit la distance totale. Comme seules deux arêtes changent, la variation de longueur de la tournée (le delta) peut être calculée en comparant seulement ces deux anciennes et deux nouvelles longueurs d'arêtes, sans resommer l'itinéraire entier.

Une fois le delta de coût d'un mouvement candidat calculé, l'algorithme accepte toujours les mouvements qui raccourcissent la tournée (Δ < 0). Pour les mouvements qui l'allongent, il les accepte avec une probabilité e^(−Δ/T), où T est la température actuelle. Cela signifie qu'un grand mouvement dégradant est rarement accepté, mais que de petits mouvements dégradants restent assez probables tôt dans le processus lorsque T est élevé. À mesure que T décroît vers zéro, e^(−Δ/T) s'effondre vers zéro pour tout Δ positif, si bien que l'algorithme devient effectivement une descente gloutonne pure — l'escalade est interdite et seuls les mouvements améliorants survivent.

Cette simulation utilise un refroidissement géométrique : T est multiplié par un taux de refroidissement α (proche de mais inférieur à 1) après chaque mouvement proposé, si bien que T décroît de façon exponentielle avec le nombre d'itérations. Un taux de refroidissement très proche de 1 (par ex. 0,9995) refroidit lentement, donnant à la recherche de nombreuses itérations à des températures plus élevées pour explorer largement avant de s'engager dans l'affinage d'une solution — cela trouve généralement des tournées plus courtes mais met plus de temps à se stabiliser. Un taux de refroidissement plus bas (par ex. 0,985) refroidit vite et se comporte presque comme une recherche locale 2-opt gloutonne, convergeant rapidement mais plus susceptible de rester bloqué dans un minimum local médiocre.

C'est tout l'intérêt du recuit : à haute température, le critère de Metropolis accepte délibérément certains mouvements qui augmentent la longueur. Une tournée peut sembler localement optimale (aucun mouvement 2-opt unique ne l'améliore) tout en étant encore loin de la plus courte tournée possible — c'est un minimum local. En acceptant occasionnellement un mouvement moins bon, la recherche peut sortir du bassin de ce minimum local et tomber ensuite dans un autre, plus court. En observant le graphique de distance, vous verrez généralement une baisse rapide au début, des pics occasionnels vers le haut tant que T est encore élevé, puis une stabilisation en un déclin monotone et régulier à mesure que T approche de zéro.

Les véritables entreprises de logistique résolvent des problèmes de tournées de véhicules (VRP) avec des centaines ou des milliers d'arrêts, plusieurs véhicules, des fenêtres horaires et des limites de capacité — un problème combinatoire NP-difficile où les solutions exactes sont irréalisables au-delà de quelques dizaines d'arrêts. Les métaheuristiques comme le recuit simulé, ainsi que les algorithmes génétiques, l'optimisation par colonies de fourmis et la recherche tabou, sont des outils standards de l'industrie pour trouver des itinéraires très bons (bien que non prouvés optimaux) en quelques secondes à quelques minutes. Cette simulation modélise le cœur mono-véhicule de ce problème — le problème classique du voyageur de commerce — qui est le même moteur combinatoire au cœur des logiciels de routage en production.