URL originale : https://books.openedition.org/pum/5083

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.
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.
Méthodes de planification en transport
Ce livre est diffusé en accès limité. L’accès à la lecture en ligne ainsi qu’aux versions PDF et ePub est réservé aux bibliothèques l’ayant acquis. Vous pouvez vous connecter à votre bibliothèque à l’adresse suivante : https://freemium.openedition.org/oebooks
Si vous avez des questions, vous pouvez nous écrire à access[at]openedition.org
Référence numérique du chapitre
Format
Référence numérique du livre
Format
1 / 3