Voyageur de commerce — Optimisation interactive

Le voyageur de commerce

Un voyageur doit visiter toutes les villes puis revenir au départ. Quelle route choisir pour que le trajet soit le plus court possible ? Quelques villes suffisent déjà à créer une énorme quantité d’itinéraires.

Méthode

Réglages

Nombre de villes18

Vitesse d’optimisation12

Affichage

Afficher les numéros des villes Afficher la route initiale Halo lumineux Arrêter quand aucun gain

Actions

Mesures

Distance initiale—

Distance actuelle—

Gain obtenu0 %

Améliorations0

2-opt : on cherche deux arêtes qui se croisent ou qui créent un détour, puis on inverse une portion de la route. Cette méthode ne garantit pas toujours l’optimum absolu, mais elle améliore souvent très fortement le trajet.

Transformer un spaghetti de routes en trajet efficace

Villes 18

Distance —

Gain 0 %

Itinéraire

Route aléatoire

Clique sur une ville pour la mettre en départ • 2-opt élimine souvent les croisements.

Distance au fil des améliorations

Comparaison des méthodes

Complexité : avec n villes, le nombre de circuits possibles explose très vite. Tester toutes les routes devient impossible dès que n grandit.

L’animation montre pourquoi les heuristiques sont utiles : elles trouvent rapidement de très bonnes solutions.