La tournée du voyageur de commerce

Atelier scientifique

Thème(s) disciplinaire(s)

Informatique , Mathématiques

Niveau scolaire

Premières , Terminales

Information(s)

Durée : 1 heure
Langue(s) : Français

Accès :

Cet atelier est accessible aux personnes à mobilité réduite (PMR)

Zone :
Campus principal de Talence

http://www.u-bordeaux.fr/

Adresse :
Institut mathématiques de Bordeaux
351
cours de la libération
33400 Talence

http://www.math.u-bordeaux1.fr/imb/acces-et-localisation

Voir sur Open Street Map

Remarque(s)

Un autre atelier est proposé en parallèle à l'IMB: Comment un ordinateur compresse-t-il des fichiers ? http://circuit-scientifique-bordelais.cnrs.fr/admin/modules/show/190 Il est possible pour un groupe de 24 à 30 élèves de se diviser en deux et de participer aux deux ateliers (1h +1h).

Résumé

Un voyageur de commerce doit visiter ses clients répartis sur toute la France. Connaissant les distances entre chaque paire de villes, il désire trouver la tournée la plus courte passant une et une seule fois par chaque ville.
Dans un premier temps, on essaiera de trouver "à la main" une bonne tournée. On verra ensuite comment formuler le problème en termes mathématiques et comment utiliser l'informatique pour résoudre (exactement ou de manière approchée) ce problème.

Porteur de projet

Institut de Mathématiques de Bordeaux (IMB)

Animateur(s) / Conférencier(s)

François Clautiaux / Boris Detienne / Pierre Pesneau