Le problème du voyageur de commerce

Un voyageur de commerce doit visiter toutes les villes d’une région en un temps record, sans passer deux fois par la même. Dans quelle ordre doit-il visiter les villes pour ne pas perdre de temps ? Derrière ce problème en l’apparence anodine se cache une vraie difficulté pour les ordinateurs, et des problèmes fondamentaux en informatique théorique.

2026_Sciences_TSPTélécharger ici les autres documents (poster pédagogique)
https://sciences.brussels/printemps/wp-content/uploads/sites/2/2026/01/2026_Sciences_TSP.pdf

Planifier un trajet optimal peut sembler simple, mais le nombre d’itinéraires possibles augmente très rapidement avec le nombre de villes. Tester toutes les solutions devient vite impossible, même pour un ordinateur puissant. Pour résoudre ce problème du voyageur de commerce (TSP), on utilise des algorithmes heuristiques : ce sont des méthodes qui prennent des décisions intelligentes étape par étape pour construire un trajet “probablement bon” rapidement, sans explorer toutes les possibilités.

Notre projet consiste en une application intéractive qui permet aux utilisateurs d’explorer deux heuristiques différentes pour résoudre le problème du voyageur de commerce. Les participants peuvent appliquer ces heuristiques sur trois graphes de difficulté croissante et observer comment le trajet est construit, ainsi que comparer leurs solutions avec celles calculées automatiquement par l’ordinateur. Cette interaction permet de comprendre concrètement le fonctionnement des heuristiques et de visualiser les choix qu’elles effectuent à chaque étape.