Version classiqueVersion mobile

Méthodes de planification en transport

 | 
Yves Nobert
, 
Roch Ouellet
, 
Régis Parent

10. Le problème du voyageur de commerce

Les formats HTML, PDF et ePub de cet ouvrage sont accessibles aux usagers des bibliothèques et institutions qui l'ont acquis dans le cadre de l'offre OpenEdition Freemium for Books. L’ouvrage pourra également être acheté sur les sites des libraires partenaires, aux formats PDF et ePub, si l’éditeur a fait le choix de cette diffusion commerciale. Si l’édition papier est disponible, des liens vers les librairies sont proposés sur cette page.

Extrait du texte

10.1 Typologie, historique et applications

Définition et exemple euclidien

L’élaboration d’une tournée à coût minimal permettant de visiter exactement une fois chacun des sommets d’un réseau constitue toujours un défi fascinant pour les spécialistes. Ce problème est qualifié dans la littérature scientifique de problème du voyageur de commerce (PVC), car, initialement, les chercheurs imaginaient un voyageur de commerce planifiant la tournée des différentes villes de son territoire. On verra plus loin d’autres applications du PVC. À titre d’exemple, considérons la figure 10.1 : chacun des 11 points représente une ville ; et notre voyageur doit visiter, à partir de la ville numéro 1, les 10 autres villes dans un ordre à déterminer, puis revenir à son point de départ. Poussé par un souci légitime de réduire le plus possible la durée de sa tournée, il s’en tiendra à une seule visite de chacune des villes.

Nous conviendrons, pour l’instant, que le temps pour se rendre d’une ville à l’autre e...

© Presses de l’Université de Montréal, 2014

Conditions d’utilisation : http://www.openedition.org/6540

Acheter

Rechercher dans OpenEdition Search

Vous allez être redirigé vers OpenEdition Search