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

doi:10.4000/books.pum.5066

Informations sur la couverture

Liens vers le livre

Informations sur la couverture

Formats de lecture

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 re

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.

Voir plus de livres

Drogue et criminalité

Une relation complexe

Chantal Plourde, Natacha Brunelle et Serge Brochu

2016

Inégalités : mode d'emploi

L'injustice au travail au Canada

Stéphane Moulin

2016

L'éducation aux médias à l'ère numérique

Entre fondations et renouvellement

Anne-Sophie Letellier et Normand Landry (dir.)

2016

L'intégration des services en santé

Une approche populationnelle

Lucie Bonin, Louise Belzile et Yves Couturier

2016

Les enjeux éthiques de la limite des ressources en santé

Jean-Christophe Bélisle Pipon, Béatrice Godard et Jocelyne Saint-Arnaud (dir.)

2016

Penser la formation en gestion

Repères pour l'enseignement supérieur

Jean-Pierre Béchard

2016

La délinquance sexuelle des mineurs

Théories et recherches

Monique Tardif (dir.)

2015

La détention avant jugement au Canada

Une pratique controversée

Fernanda Prates et Marion Vacheret (dir.)

2015

La politique comparée

Fondements enjeux et approches théoriques

Jane Jenson et Mamoudou Gazibo

2015

Les approches qualitatives en gestion

Paul Prévost et Mario Roy

2015

La Réussite éducative des élèves issus de l'immigration

Dix ans de recherche et d'intervention au Québec

Marie McAndrew (dir.)

2015

Agriculture et paysage

Aménager autrement les territoires ruraux

Gérald Domon et Julie Ruiz (dir.)

2014

Drogue et criminalité

Une relation complexe

Chantal Plourde, Natacha Brunelle et Serge Brochu

2016

Inégalités : mode d'emploi

L'injustice au travail au Canada

Stéphane Moulin

2016

L'éducation aux médias à l'ère numérique

Entre fondations et renouvellement

Anne-Sophie Letellier et Normand Landry (dir.)

2016

L'intégration des services en santé

Une approche populationnelle

Lucie Bonin, Louise Belzile et Yves Couturier

2016

Les enjeux éthiques de la limite des ressources en santé

Jean-Christophe Bélisle Pipon, Béatrice Godard et Jocelyne Saint-Arnaud (dir.)

2016

Penser la formation en gestion

Repères pour l'enseignement supérieur

Jean-Pierre Béchard

2016

La délinquance sexuelle des mineurs

Théories et recherches

Monique Tardif (dir.)

2015

La détention avant jugement au Canada

Une pratique controversée

Fernanda Prates et Marion Vacheret (dir.)

2015

La politique comparée

Fondements enjeux et approches théoriques

Jane Jenson et Mamoudou Gazibo

2015

Les approches qualitatives en gestion

Paul Prévost et Mario Roy

2015

La Réussite éducative des élèves issus de l'immigration

Dix ans de recherche et d'intervention au Québec

Marie McAndrew (dir.)

2015

Agriculture et paysage

Aménager autrement les territoires ruraux

Gérald Domon et Julie Ruiz (dir.)

2014

1 Kwan Mei-Ko, « Graphic Programming Using Odd and Even Points », Chinese Mathematics, vol. 1, 1962, p. 273-277.

2 Voir section 2.1.

3 Lorsque les zigzags sont interdits, pour une raison ou pour une autre, on peut associer au tronçon deux arêtes, chacune représentant le passage sur un côté de la rue.

4 Voir section 2.1.

5 Petit exercice : trouver un cycle eulérien du graphe de la figure 9.3.

6 Les termes multigraphe et multiréseau font allusion au fait que certaines paires de sommets sont reliées par de multiples arêtes.

7 Deux tournées différentes utilisent parfois les mêmes arêtes hors service et admettent alors le même graphe des arêtes ajoutées (voir l’exercice 2).

8 Voir « Traversing Graphs: The Eulerian and Hamiltonian Theme », Herbert Fleischner, dans Arc Routing: Theory, Solutions and Applications, Moshe Dror (dir.), Kluwer Academic Publishers, 2000.

9 Le nombre d’appariements diffère du nombre d’affectations calculé au chapitre 8. En effet, dans un problème d’affectation, les sommets se répartissent naturellement en deux sous-ensembles disjoints. Ici, les sommets impairs à apparier forment un seul ensemble.

10 J. Edmonds, « Paths, trees and flowers », Canadian Journal of Mathematics, vol. 17, 1965, p. 449-467.

11 La partie non couverte peut également se voir comme formée du seul cycle 2 − 5 − 4 − 3 − 5 − 2.

12 Pour une preuve de cette proposition, voir « Traversing Graphs : The Eulerian and Hamiltonian Theme », Herbert Fleischner, dans Arc routing : Theory, Solutions and Applications, Moshe Dror (dir.), Kluwer Academic Publishers, 2000. La décomposition d’un multigraphe en cycles n’est pas unique dans la plupart des cas.

13 Voir, par exemple, Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, Network Flows : Theory, Algorithms and Applications, Prentice-Hall, 1993, section 19.7, p. 742.

14 La longueur de la portion « en service » d’une tournée eulérienne est toujours la somme des durées en service des différentes arêtes du réseau (dans l’exemple du camelot considéré ici, cette portion représente 180 minutes). En effet, dans une tournée eulérienne, chaque arête est empruntée exactement une fois en service, ce qui signifie, par exemple pour l’arête 12, que 8 (x₁₂ + x₂₁) = 8 × 1 = 8. Ainsi, le terme 8 (x₁₂ + x₂₁) est une constante et peut donc être omis de la fonction-objectif. On pourrait également en modifier le coefficient, sans affecter la recherche de solutions optimales. On obtient donc un modèle équivalent en convenant d’écrire la fonction-objectif sous la forme
z’ = 6 (x₁₂ + x₂₁)+ 6 (y₁₂ + y₂₁)+ etc.
ou encore
z’ = 6 (t₁₂ + t₂₁) + etc.
où t ij = x ij + y ij. Cette nouvelle variable t ij dénote le nombre total de parcours de l’arête ij dans le sens de i vers j. Il est possible de réécrire le modèle à l’aide des seules variables de type t ij. On a décrit ci-dessus l’amorce d’une fonction-objectif z’qui s’exprime en fonction de ces seules variables. Les contraintes SOMMET i se réécrivent facilement ; par exemple, SOMMET 2 devient :
SOMMET 2 t₁₂ + t₃₂ + t₅₂ = t₂₁ + t₂₃ + t₂₅.
Les contraintes ARÊTE ij sont alors remplacées par les inéquations suivantes :
t_ij + t_ji ≥ 1.
Dans l’exemple du camelot considéré ici, la valeur optimale de z’est 102, ce qui représente 19 minutes de plus que le total 83 des durées hors service des différentes arêtes. Ce deuxième modèle contient deux fois moins de variables que le premier et est moins lourd dans sa présentation algébrique ; cependant, sa fonction-objectif est moins intuitive et l’interprétation de ses solutions optimales est moins immédiate.

15 Dans un graphe mixte, le degré d’un sommet est le nombre de liens (arcs ou arêtes) incidents à ce sommet.

16 Rappelons que le graphe comporte toujours un nombre pair de sommets impairs. Ainsi, N ne sera jamais un sous-ensemble impair de sommets impairs.

17 Yves Nobert et Jean-Claude Picard, « An Optimal Algorithm for the Mixed Chinese. Postman Problem », Networks, vol. 27, 1996, p. 95-108

18 Voir <www.giro.ca>.

Méthodes de planification en transport

Choisir la taille de l’intégration

Collez le code HTML suivant pour intégrer ce contenu sur votre site.

<iframe src="https://0-books-openedition-org.catalogue.libraries.london.ac.uk/pum/5083?format=embed" style="padding:5px;border:2px solid #ddd;" height="500" width="375"></iframe>

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://0-freemium-openedition-org.catalogue.libraries.london.ac.uk/oebooks

Si vous avez des questions, vous pouvez nous écrire à access[at]openedition.org

Référence numérique du chapitre

Nobert, Y., Ouellet, R., & Parent, R. (2014). 9. Le problème du postier chinois non orienté. In Méthodes de planification en transport (1‑). Presses de l’Université de Montréal. https://0-doi-org.catalogue.libraries.london.ac.uk/10.4000/books.pum.5083

Nobert, Yves, Roch Ouellet, et Régis Parent. « 9. Le problème du postier chinois non orienté ». In Méthodes de planification en transport. Montréal: Presses de l’Université de Montréal, 2014. https://0-doi-org.catalogue.libraries.london.ac.uk/10.4000/books.pum.5083.

Nobert, Yves, et al. « 9. Le problème du postier chinois non orienté ». Méthodes de planification en transport, Presses de l’Université de Montréal, 2014, https://0-doi-org.catalogue.libraries.london.ac.uk/10.4000/books.pum.5083.

Référence numérique du livre

Nobert, Y., Ouellet, R., & Parent, R. (2014). Méthodes de planification en transport (1‑). Presses de l’Université de Montréal. https://0-doi-org.catalogue.libraries.london.ac.uk/10.4000/books.pum.5066

Nobert, Yves, Roch Ouellet, et Régis Parent. Méthodes de planification en transport. Montréal: Presses de l’Université de Montréal, 2014. https://0-doi-org.catalogue.libraries.london.ac.uk/10.4000/books.pum.5066.

Nobert, Yves, et al. Méthodes de planification en transport. Presses de l’Université de Montréal, 2014, https://0-doi-org.catalogue.libraries.london.ac.uk/10.4000/books.pum.5066.

Compatible avec Zotero

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

Extrait

Dans la même collection