Le numéro 203 est en accès libre

Feuilletez gratuitement Stratégies Logistique 203 - octobre/novembre 2023.

En bref

Réindustrialisation : 201 ouvertures nettes de sites industriels en 2023, contre 176 en 2022

Le SITL 2024 a réuni 25 000 participants, une fréquentation en hausse de 16 %

Découvrez l'abonnement numérique

Accueil

Solution du problème 19 : Les tournées vues par Euler

, par La rédaction


Ce problème n’est pas nouveau puisque c’est le mathématicien Euler (1707-1783) qui le premier a trouvé les conditions d’existence d’un circuit passant une fois et une seule par chaque liaison d’un réseau ou par les arêtes d’un graphe si on utilise le langage de la théorie des graphes. L’Histoire dit qu’Euler aimant se promener sur les ponts de la ville de Königsberg (aujourd’hui Kaliningrad) enjambant la Pregel (cf. plan ci-dessous) se demanda s’il pouvait les parcourir tous une fois et une seule avant de rentrer chez lui. C’était la première tentative d’optimisation de tournées (1736).

Plan de la ville de Königsberg

Graphe du réseau associé


Il trouva qu’un circuit peut être effectué que si et seulement si la condition suivante est réalisée : le nombre de liaisons associées à chaque nœud du réseau doit être un nombre pair.
Dans le cas de Königsberg la promenade était donc impossible.

Ce résultat est valable pour n’importe quel réseau et en particulier pour le réseau de rues présenté dans le problème.

livraisons du lundi

livraisons du mardi

Le lundi chaque carrefour est associé à un nombre pair de rues à parcourir le livreur peut donc réaliser son tour en passant une fois et une seule par chaque rue à livrer.
Il y a plusieurs solutions faciles à trouver à condition de ne pas rentrer trop tôt en M.

Par exemple : a, b, l, i, e, d, c, g, m, h, j, k, f. Remarquons que toutes les solutions ont la même longueur puisqu’on emprunte qu’une seule fois toutes les rues, la longueur du tour est la somme des longueurs des rues à livrer.

Le mardi les carrefours « m, h, n, k, f » et « b, c, g, h, l » correspondent chacun avec un nombre impair de rues à parcourir, le tour recherché est donc impossible d’après Euler.
Il est aisé de montrer que la condition énoncée est nécessaire, c’est à dire que sans elle aucun espoir de réussir n’est permis pour le livreur.

En effet s’il existe un tour passant une fois et une seule par chaque rue alors en chaque carrefour traversé le livreur entre et sort par une voie différente, il y a donc un nombre pair de liaisons connectées à chaque nœud du réseau.

La condition suffisante, c’est à dire que si chaque nœud est associé à un nombre pair de liaisons alors il existe un tour réalisable pour le livreur, est plus délicate à établir. En voici le principe :
Tous les nœuds du réseau sont reliés à un nombre de liaisons supérieur ou égal à 2. Ceci implique que l’on peut construire un circuit partiel (ne passant pas nécessairement par tous les nœuds), nous l’appellerons circuit de base. Considérons alors le réseau restant constitué des liaisons non parcourues. Ses nœuds sont encore reliés à un nombre pair de liaisons (non parcourues), il est alors possible de construire un nouveau circuit (circuit secondaire).On continue à construire des circuits secondaires jusqu’à épuisement des liaisons.

Pour reconstruire le circuit cherché, il suffit d’enchaîner le circuit de base avec les différents circuits secondaires en partant d’un nœud du circuit de base et en parcourant les circuits secondaires dans l’ordre où on les rencontre.


Le magazine et les hors-séries

Stratégies Logistique 205 - février / mars 2024

Stratégies Logistique n°205 est paru.

Supplément immobilier / SIMI 2023

Téléchargez ou feuilletez ce hors-série consacré au salon SIMI qui s’est tenu à Paris du 12 au 14 décembre 2023.

Cliquez ici pour télécharger ce hors-série.

Hors-série n° 23 - Eco Class Logistics

Téléchargez ce hors-série consacré à l’événement Eco Class Logistics, qui s’est tenu à Paris le 28 septembre 2023.

Cliquez ici pour télécharger ce hors-série.