Précédent Suivant

9. Le problème du postier chinois non orienté

p. 397-441


Extrait

1Dans ce chapitre, nous indiquons comment planifier une tournée optimale qui emprunte au moins une fois chacune des arêtes d’un réseau non orienté connexe avant de revenir à son point de départ. La première mention de ce problème dans la littérature de la recherche opérationnelle remonte à 1962 quand parut un article1 traitant de l’élaboration de tournées pour la distribution du courrier. Son auteur, Kwan Mei-Ko, s’était auparavant frotté de près aux problèmes de distribution du courrier en tant qu’agent des postes chinoises. Le problème du postier chinois non orienté (PCNO) est un problème plus général que celui d’Euler2 où l’on recherche une tournée empruntant exactement une fois chacune des arêtes d’un graphe non orienté.

2Le PCNO est un cas particulier de problèmes d’ordonnancement sur les liens (arcs ou arêtes) d’un réseau. Depuis 1962, de tels problèmes ont fait l’objet de nombreux travaux de chercheurs de divers pays, qui n’ont d’ailleurs pas tardé à généraliser leurs rec

Les formats HTML, PDF et ePub de cet ouvrage sont accessibles aux usagers des bibliothèques 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.

Précédent Suivant

Le texte seul est utilisable sous licence Licence OpenEdition Books. Les autres éléments (illustrations, fichiers annexes importés) sont « Tous droits réservés », sauf mention contraire.