La livraison postale efficace est l'épine dorsale de la communication et du commerce modernes. À mesure que les populations urbaines s'élargissent, le défi de recevoir du courrier et des colis du point A au point B devient de plus en plus complexe. Les gestionnaires de logistique doivent équilibrer les coûts du carburant, les heures de travail, l'usure des véhicules et la fiabilité des services. Un puissant outil mathématique qui s'attaque à ce problème est le problème chinois de la poste (PPC), également connu sous le nom de problème d'inspection de la route.

Quel est le problème du facteur chinois?

Le problème chinois Postman est un problème d'optimisation classique en théorie des graphiques. Il demande : étant donné un graphe connecté (un réseau de nœuds et de bords), quelle est la marche la plus courte fermée qui visite chaque bord au moins une fois ? Le problème tire son nom du scénario réel d'un facteur qui doit livrer des lettres le long de chaque rue dans un quartier et retourner ensuite à la poste. Le facteur veut minimiser la distance totale parcourue ou entraînée, ce qui nécessite inévitablement de marcher certaines rues plus d'une fois si le réseau a des nœuds étranges (intersections avec un nombre impair de rues de connexion). Le CPP vise à minimiser ces traversées supplémentaires. Le problème est étroitement lié aux chemins et circuits eulériens – nommé après le mathématicien du XVIIIe siècle Leonhard Euler, qui a résolu le fameux problème des Sept Ponts de Königsberg. Dans un circuit eulérien, chaque bord est visité exactement une fois, et la marche commence et se termine au même noeud. Un tel circuit n'existe que si chaque noeud du graphique a un degré pair.

Concepts de théorie des graphiques clés

Pour appliquer le problème Postman chinois à l'optimisation de la route, vous avez besoin d'une bonne compréhension de quelques concepts fondamentaux de la théorie des graphiques:

  • Graphique: Une collection de nodes (vertises) reliés par edges (liens).Dans un réseau de rues, les nœuds représentent les intersections et les bords représentent les rues ou les segments de route.
  • Dégression d'un noeud:[ Le nombre d'incidents de bords au noeud. Une intersection où trois rues se rencontrent a degré 3; une intersection de quatre rues a degré 4.
  • Node de degré élevé: Un noeud avec un nombre impair de bords d'incident. Ce sont les points problématiques qui empêchent un circuit eulérien d'exister.
  • Circuit eulérien: Une promenade fermée qui utilise chaque bord exactement une fois.
  • Trajet eulérien (chemin):[ Une promenade ouverte qui utilise chaque bord exactement une fois (départ et se termine à des nœuds impairs).Pour les itinéraires postaux qui n'ont pas besoin de revenir au départ, un sentier eulérien suffit si exactement deux nœuds impairs existent.
  • Graphique pondéré:[ Graphique où les bords ont des coûts connexes (distance, temps ou consommation de carburant). Le RPC sur les graphiques pondérés vise à minimiser le coût total.

Le problème Seven Bridges of Königsberg est le précurseur historique de la théorie du chemin eulérien et le problème chinois Postman. Comprendre ce puzzle original aide à clarifier pourquoi les nœuds étranges de degré comptent.

Formulation mathématique du problème chinois postman

G = (V, E, w) soit un graphique connecté et non dirigé où V est l'ensemble des sommets, E est l'ensemble des bords, et w: E → R+ attribue un poids positif (longueur, temps ou coût) à chaque bord. Le Chinese Postman Problem cherche une marche fermée qui commence et se termine à un vertex désigné (généralement le dépôt) et traverse chaque bord au moins une fois, minimisant la somme totale des poids des bords traversés (compteant les multiples privilèges). Si le graphique a un circuit eulérien, la solution optimale est simplement ce circuit avec un poids total égal à la somme de tous les poids des bords. Sinon, nous devons résoudre une parallèlement minimal sur l'ensemble des sommets de degrés impairs.

  1. Identifiez le jeu de sommets O avec un degré impair. Par le Lemma de façon manuelle, le nombre de sommets impairs est pair.
  2. Computer les chemins les plus courts entre chaque paire de sommets impairs utilisant des algorithmes comme Floyd-Warshall ou Dijkstra.
  3. Solve a minimum-weight perfect appariement[] sur le graphique complet induit par O, où le poids d'un bord entre deux sommets impairs est la longueur du chemin le plus court les reliant en G. Cette étape trouve le jeu de chemins à coût minimal à ajouter (en dupliquer les bords) afin que tous les sommets deviennent de degré pair.
  4. Ajouter les chemins correspondants (en faisant double emploi avec les bords le long de ces chemins) au graphique original, donnant un multigraphe G=" qui est eulérien.
  5. Construire un circuit eulérien en G.] en utilisant un algorithme standard (comme l'algorithme Hierholzer).

Le circuit résultant est la solution optimale au problème Postman chinois. La complexité temporelle de l'algorithme est dominée par l'étape correspondante, qui peut être résolue dans O(n3) en utilisant l'algorithme Blossom (Edmonds 1965) pour les graphiques généraux, où n est le nombre de sommets impairs.

Application du problème chinois Postman à l'optimisation de la route postale

La traduction du modèle mathématique vers un réseau postal réel implique plusieurs étapes pratiques. L'objectif est de générer un itinéraire qu'un transporteur de courrier peut suivre à pied, en vélo ou en véhicule pour servir chaque adresse sur chaque segment de rue tout en minimisant la distance ou le temps. Voici comment le mettre en œuvre:

Étape 1: Carter la zone de livraison comme un graphique

Chaque intersection (y compris les extrémités mortes) devient un nœud. Chaque segment de rue entre deux intersections devient un bord. La direction de rue, les restrictions à sens unique et les restrictions à la rotation doivent être prises en considération – ce qui transforme le problème en Problème du facteur chinois dirigé (pour les rues à sens unique) ou Problème du facteur chinois mixte (pour les rues à sens unique mixtes et à sens unique). Pour simplifier, la plupart des implémentations initiales supposent un graphique non dirigé, mais les itinéraires postaux réels impliquent souvent un mélange de directions.

Étape 2 : Identifier les nœuds de désaccord

Une fois le graphique construit, compter le degré de chaque noeud. Les nœuds avec un degré impair (par exemple, les intersections où 3 ou 5 rues se rencontrent) sont les points de difficulté. Dans une grille urbaine typique, de nombreuses intersections ont degré 4 (même), mais cul-de-sacs et les jonctions T introduisent des nœuds impair-degré. L'ensemble O est la liste de tous les nœuds impair-degré. Leur nombre est toujours égal. Pour un petit quartier, O peut avoir 10 à 20 nœuds; pour un grand quartier, des centaines.

Étape 3: Calculer les chemins les plus courts entre les nœuds odieux

Avec O identifié, calculer le chemin le plus court (poids minimum) entre chaque paire de nœuds impaires. C'est l'étape la plus intensive du calcul si le graphique est grand. Pour un graphique avec des nœuds V et E, en utilisant l'algorithme Dijkstra , de chaque noeud impaire donne la complexité O(==O=* (=E=+=V=Log=V=)). Pour un réseau avec, par exemple, 10 000 nœuds et 50 nœuds impaires, cela est gérable.

Étape 4: Résoudre le couplage parfait minimum-poids

De la distance entre les nœuds impaires, construire un graphique complet avec le vertex set O et les poids de bord égaux aux distances les plus courtes. Ensuite, trouver l'ensemble des bords (paires de nœuds impaires) qui couvrent tous les nœuds impaires exactement une fois et ont le poids total le plus petit. Ceci est le poids minimum parfait correspondant. Pour quelques douzaines de nœuds impaires, l'algorithme Blossom fonctionne bien; pour les ensembles plus grands, algorithmes d'approximation ou heuristique peut être utilisé.

Étape 5: Construire le circuit eulérien

Dupliquer les bords le long des chemins correspondants dans le graphique original (les marquer comme traversé une deuxième fois). Maintenant chaque noeud a même degré. Exécuter l'algorithme Hierholzer , pour trouver un circuit eulérien dans ce multigraphe augmenté. Ce circuit commence et se termine au dépôt et couvre chaque bord original au moins une fois. Les bords dupliqués sont les mouvements supplémentaires que le facteur doit faire. La longueur totale de la route égale la somme de tous les poids de bord d'origine plus la somme des poids des chemins dupliqués.

Étape 6: Après le traitement pour la pratique

Le circuit eulérien pur de l'étape 5 peut ne pas être optimal pour marcher un itinéraire en pratique. Tourner les pénalités, les rues à sens unique, les fenêtres de temps et la distribution du poids du paquet peut nécessiter des ajustements. De plus, si la voie postale est une voie de marche, le transporteur peut ne pas avoir besoin de revenir au départ (p. ex., un camion de courrier les dépose et les reprend plus tard). Dans ce cas, le problème devient le Chemin du postman chinois (marche ouverte), qui est résolu de la même façon, mais permet de commencer et de se terminer à deux nœuds choisis de degrés impairs.

Applications et études de cas dans le monde réel

Le problème chinois des postes n'est pas seulement un exercice théorique, il a été mis en œuvre par les services postaux et les entreprises de logistique dans le monde entier. Voici quelques exemples :

Le courrier royal (Royaume-Uni)

Royal Mail utilise depuis des décennies un logiciel d'optimisation des itinéraires basé sur le RPC. Leur système, connu sous le nom de Planification intégrée du courrier[, modélise les itinéraires de livraison comme des graphiques et résout le problème d'inspection des itinéraires pour minimiser la distance de marche. Des études ont montré que les itinéraires basés sur le RPC réduisent la distance de marche de 10 à 15 % par rapport aux itinéraires prévus manuellement, économisant des millions de livres en coûts de main-d'oeuvre chaque année. L'approche de Royal Mail=» pour l'optimisation des modes de livraison a été documentée dans des documents universitaires.

Service postal des États-Unis (USPS)

Le système de séquence des points de livraison (DPS) trie le courrier dans l'ordre de livraison, et le système de planification des itinéraires utilise des algorithmes graphiques pour concevoir des marches de porte-avions. Dans un programme pilote en Floride, les routes optimisées par le RPC ont réduit la distance de marche du transporteur de 12 % et permis l'ajout de points de livraison sans augmenter les heures de travail.

Services municipaux de moindre importance

Au-delà des postes nationaux, le PPC est utilisé pour le balayage des rues, la collecte des ordures et la labourage des neiges. Par exemple, la ville de Boulder, Colorado, utilise le problème chinois Postman pour planifier les routes de labour des neiges, en veillant à ce que chaque rue soit dégagée avec un minimum de déplacements redondants.

Avantages de l'approche chinoise de la poste pour la livraison postale

La mise en œuvre du problème chinois du facteur dans la planification des routes offre des avantages opérationnels et financiers concrets:

  • Distance de déplacement réduite:[ En minimisant les traversées supplémentaires, la distance totale par route chute de 10% à 30%, selon la topologie du réseau.
  • Frais de carburant et de véhicule moins élevés: Moins de conduite signifie moins de consommation de carburant et moins d'entretien.
  • Délais de livraison améliorés :[ Des itinéraires plus courts permettent une réalisation plus rapide, permettant aux transporteurs de desservir plus d'adresses par quart ou de terminer plus tôt.
  • Mieux répartir les ressources:[ La direction peut réaffecter le temps gagné à des livraisons hautement prioritaires ou réduire la rémunération des heures supplémentaires.
  • Durabilité environnementale : Moins de kilomètres parcourus réduisent les émissions de carbone, soutenant des objectifs logistiques écologiques.
  • Consistance et équité :[ Les routes optimisées sont reproductibles et peuvent être équilibrées entre les transporteurs pour éviter la surcharge.

Défis et limites

Malgré son élégance mathématique, l'application du problème chinois des postes aux itinéraires postaux du monde réel comporte plusieurs défis :

  • Calcul à grande échelle :[ Pour un réseau urbain avec des centaines de milliers de bords et des dizaines de milliers de nœuds impairs, résoudre le poids minimum parfait correspond exactement est calculable prohibitif.
  • Les graphiques directs et mixtes:[ Les rues à sens unique, les restrictions de virage et les règles de la non-tour à gauche exigent la modélisation du graphique comme dirigé ou mixte. Le problème du facteur chinois dirigé est plus difficile à résoudre, et le RPC mixte est difficile en général.
  • Les facteurs dynamiques:[ La congestion de la circulation, les fermetures de routes et les conditions météorologiques modifient dynamiquement les poids des bords. Le RPC fournit une voie statique; une réutilisation en temps réel peut être nécessaire.
  • Dépôts multiples et fenêtres de temps:[ De nombreuses opérations postales ont plusieurs dépôts de livraison et fenêtres de temps (p. ex., les colis doivent être livrés avant midi). Le RPC ne gère pas à lui seul ces contraintes; il doit être intégré dans un cadre plus complexe de problèmes d'acheminement des véhicules (RPV).
  • Qualité des données: Des cartes de rue précises, des restrictions de virage et des mesures de distance sont essentielles.
  • Acceptation humaine: Les transporteurs peuvent résister à des itinéraires mathématiques optimaux mais qui se sentent inhabituels, brisant les habitudes. La gestion du changement est un facteur réel.

Variations avancées et orientations futures

Les recherches en cours continuent de préciser le problème chinois des postes pour la logistique moderne.

Problème de facteur chinois dépendant du temps

Le coût de l'arête change avec le temps (p. ex., les habitudes de circulation). La résolution du RPC dans un graphique dépendant du temps est un domaine de recherche actif.

Problème de poste chinois capacité

Lorsque les véhicules ont des limites de capacité (p. ex., des sacs postaux), les routes peuvent devoir retourner au dépôt pour recharger le milieu de route. Cette variation combine le RPC et le problème d'acheminement du véhicule (CVRP).

Intégration avec les Drones de livraison de dernier cycle

Les services postaux expérimentent les drones pour leur livraison finale. Le problème chinois Postman peut être adapté pour planifier les routes au sol pour les transporteurs qui distribuent des paquets aux drones à des nœuds spécifiques, minimisant ainsi le total des déplacements terrestres et aériens.

Améliorations de l'apprentissage automatique

Les réseaux neuronaux peuvent apprendre les modèles dans les réseaux de rue pour prédire les grappes de nœuds à degrés impairs et suggérer des correspondances efficaces sans calcul de force brute.La recherche récente explore la combinaison du CPP avec un apprentissage profond de renforcement pour s'adapter aux conditions dynamiques.

Outils et ressources de mise en oeuvre

Pour les professionnels de la logistique qui cherchent à appliquer le problème chinois Postman, plusieurs outils et bibliothèques existent :

  • NetworkX (Python): Une puissante bibliothèque de graphiques qui comprend des fonctions pour trouver des circuits eulériens et résoudre le problème chinois Postman sur de petits graphiques (.
  • OR-Tools (Google): Une suite de bibliothèques d'optimisation qui peuvent résoudre les problèmes de routage des véhicules et peuvent être adaptés pour la planification de parcours basée sur le RPC.
  • ArcGIS Network Analyst[: logiciel SIG qui comprend des outils d'optimisation des itinéraires intégrant la théorie des graphiques, adapté aux grands réseaux de rue.
  • OpenRouteService: Un service d'acheminement open-source qui peut fournir des données de chemin plus courtes pour les étapes de correspondance du RPC.
  • LEMON Graph Library[: Une bibliothèque C++ avec des algorithmes efficaces pour un débit minimum de coûts et un appariement, utile pour la mise en œuvre du RPC.

Pour une plongée plus profonde dans la théorie, consultez l'article de Wikipedia sur le problème d'inspection de la route[ ou des textes classiques comme Théorie des graphiques avec applications[ de Bondy et Murty.

Conclusion

En modélisant le réseau de rue comme un graphique, en identifiant les intersections à degrés impairs et en résolvant un ajustement parfait et de poids minimum, les services postaux peuvent dériver des itinéraires qui réduisent les déplacements redondants et maximisent l'efficacité opérationnelle. Alors que les complexités du monde réel telles que le trafic, les rues à sens unique et les fenêtres de temps nécessitent une manipulation soigneuse, la méthodologie de base du RPC demeure une pierre angulaire de l'optimisation des routes.