Le problème du voyageur de commerce
ULB · Faculté des Sciences · Sciences informatiques ·
Par Omelyanyuk Oleksandra, Banaityte Rugile, Tsoukalou Maria-Erietta, Blasiak Daniel
Tuteur(s) : Simon RENARD
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.
2026_Sciences_TSPdocument_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